Graph Theory Basics

Questions and Answers

What characterizes a simple graph?

It contains both directed and undirected edges.

It contains edges that loop back to the same vertex.

It has multiple edges between the same two nodes.

It has at most one edge between any two nodes and no loops. (correct)

How does the Handshaking Lemma relate the sum of vertex degrees to edges in a graph?

The sum of vertex degrees equals twice the total number of edges. (correct)

The sum of vertex degrees equals the total number of edges.

The sum of vertex degrees is less than the number of edges.

The sum of vertex degrees is always zero.

What defines a Minimum Spanning Tree (MST) in graph theory?

It is a subgraph that touches every node and has no edges.

It includes all edges in the graph regardless of weight.

It is a tree-shaped subgraph with the lowest total weight and consists of n - 1 edges for n nodes. (correct)

It is a connected graph that contains cycles.

Which statement about paths and cycles is true?

A cycle is a path that ends at the same node it started from. Signup and view all the answers

What happens when two matrices are multiplied?

The position m,n in the product matrix is the dot product of the mth row in A and the nth column in B. Signup and view all the answers

Consider a graph with nodes A, B, C, D, and E. Edge weights are as follows: AB=2, AC=4, AD=3, AE=5, BC=1, BD=6, BE=7, CD=2, CE=3, DE=4. Using Prim's Algorithm, which edge would be selected after the edge AC?

CD Signup and view all the answers

Suppose we are using Dijkstra's Algorithm to find the shortest path from node A to node E in a graph. We have already determined the shortest distances from A to B and A to C. Which node would we choose to expand from next?

C Signup and view all the answers

Consider a graph with nodes A, B, C, D, and E, and edge weights as follows: AB=2, AC=4, AD=3, AE=5, BC=1, BD=6, BE=7, CD=2, CE=3, DE=4. Which of the following statements about Prim's Algorithm applied to this graph is FALSE?

The final spanning tree produced by Prim's Algorithm might include edges that are not the shortest possible edges between nodes. Signup and view all the answers

In Dijkstra's Algorithm, how do we handle negative edge weights in a graph?

Negative edge weights can cause the algorithm to produce incorrect results, so it is not suitable for graphs with negative edge weights. Signup and view all the answers

Which of the following statements accurately describes the difference between Prim's Algorithm and Dijkstra's Algorithm?

Prim's Algorithm finds a minimum spanning tree, while Dijkstra's Algorithm finds the shortest path between two nodes. Signup and view all the answers

Study Notes

Graphs

A graph is a collection of points (nodes or vertices) connected by lines (edges).
A graph is simple if it has at most one edge between two nodes and no edges that loop back to the same vertex.

Walks and Paths

A walk of length n is a sequence of n connected edges.
A path is a walk that does not visit the same node twice.
A cycle is a path that ends at the same node it started at.
A walk is closed if it ends at the same node it started at, and open otherwise.
Two nodes are adjacent if they are joined by an edge.
A node and edge are incident if they touch.

The Handshaking Lemma

The degree of a vertex is the number of edges that meet at that vertex.
The Handshaking Lemma states that the sum of all vertex degrees in a graph is twice the total number of edges.

Matrices

Graph information can be stored in a grid of numbers called a matrix.
Adjacency matrices store information about graph connections.
Raising an adjacency matrix to a power n gives the number of walks of length n between any two nodes.
Undirected graphs have symmetrical adjacency matrices along their main diagonal.

Distance Matrices

Distance matrices record the weight of each edge between nodes.
Matrix multiplication is used to calculate shortest paths.

Matrix Multiplication

When two matrices A and B multiply, the product matrix position m,n is the dot product of the mth row in A and the nth column in B.
Matrix multiplication is not commutative: AB ≠ BA.

The Minimum Spanning Tree

A tree is a connected graph with no cycles, covering every node once.
The minimum spanning tree (MST) of a graph is the tree-shaped subgraph with the lowest total weight.
The MST for n nodes has n - 1 edges.

Finding the Minimum Spanning Tree

There are two algorithms to find the MST: Kruskal's Algorithm and Prim's Algorithm.

Kruskal's Algorithm

Pick the edge of least weight in the graph.
Select the next edge of least weight that does not create a cycle.
Repeat until all nodes are included.

Prim's Algorithm

For graphs:
- Choose any node.
- Choose the edge of least weight connected to this node.
- Choose the next lowest weight edge connecting the tree to a new node.
- Repeat until all nodes are included.
For matrices:
- Choose a starting node.
- Put a line through the row of the chosen node.
- Highlight the column of the chosen node.
- Circle the edge of least weight in the column.
- Repeat until all rows are deleted.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between any two nodes.
Steps:
- Begin at the starting node.
- Calculate the shortest distance back to the start for all adjacent nodes.
- Choose the node with the shortest distance and repeat the process.
- Repeat until the desired end node has a shortest distance written.