Graphs and Matrices Flashcards
What are incident and adjacent nodes?
Adjacent nodes are 2 nodes that have an edge joining them.
Incident nodes and edges relate edges with the nodes that they connect.
What is the handshaking lemma?
The handshaking lemma is the phenomenon that the degree total of a graph is always double the number of edges in the graph.
What is a matrix?
A matrix is a rectangular array of numbers. The dimensions are n x m. n being the number of rows and m being the number of columns.
What is an adjacency matrix?
An adjacency matrix is used to represent a graph. The entries represent the number of edges between 2 nodes.
How can you add 2 matrices?
Matrices must have the same dimensions to be able to add or subtract. Add or subtract the corresponding entries.
Multiply matrices in book.
What do matrices taken to a power represent?
M^n, where n = walk length. Entries in M^n represent the number of walks of length n from node to node.
What is a tree?
A tree is a connected graph with no cycles.
What is a spanning tree?
A spanning tree is a subgraph of G, which contains all the nodes of G and is a tree.
What is a minimum spanning tree?
A minimum spanning tree is a spanning tree where the total length(weight) of the edges is as small as possible.
What is Kruskal’s algorithm? Form a MST using Kruskal’s algorithm.
Kruskal’s algorithm is used to find a minimum spanning tree. It is a greedy algorithm as we make decisions about the nodes with no thoughts about what is to come later.
Method:
-List edges in ascending order of weight.
-Select edge of least weight to start
-Take next edge of least weight, reject if this edge forms a cycle.
-Repeat until all nodes are connected.
What is Prim’s algorithm? Form a MST using Prim’s algorithm.
Prim’s algorithm is also used to find the MST of a graph. Prim’s algorithm works for undirected, weighted graphs. It too is a greedy algorithm.
Method:
Choose any vertex at random from n vertices.
Choose the edge of least weight from that vertex to another vertex.
Next choose an edge of least weight from a vertex in the tree to a vertex not in the tree.
Continue to add the edge of least weight making sure to never create a cycle!
When you have (n – 1) edges, stop. You now have your minimum spanning tree.
Solve a MST on a distance matrix using Prim’s algorithm.
Choose any vertex to start the tree.
Delete the row in the matrix for the chosen vertex.
Number the column in the matrix for the chosen vertex.
Put a ring around the lowest undeleted entry in the numbered column (if equal choice, select at random).
The ringed entry becomes the next edge added to the tree.
Repeat step 2 and 3.
Put a ring around the lowest undeleted entry from the numbered columns, which is not crossed out.
Keep doing this until all the rows are deleted
Compare Kruskal’s and Prim’s algorithm.
Both algorithms achieve the same end. Both are greedy algorithms. The MST branches out using Prim’s, the edges connect at the end in Kruskal’s. Prim’s is better for dense networks as it works on distance matrices.
