Decision Chapter 3: Algorithms on Graphs

10 flashcards · Mathematics · by TheoTyson

1. Number of Arcs in a Spanning Tree

   n vertices means n - 1 edges.

2. Minimum Spanning Tree (Minimum Connector)

   A spanning tree such that the total length of its edges is as small as possible.

3. Kruskal's Algorithm - Function

   To find a minimum spanning tree.

4. Kruskal's Algorithm

   Sort all of the edges into ascending order of weight. Select the edge of least weight to start the tree. Consider the next edge of least weight. If it would form a cycle, reject it. If it does not form a cycle, add it to the tree. Repeat step 3 until all vertices are connected.

5. Prim's Algorithm - Function

   To find a minimum spanning tree.

6. Prim's Algorithm

   Choose any vertex to start the tree. Select the edge of lest weight that joins a vertex in the tree to a vertex not in the tree. Repeat step 2 until all the vertices are connected.

7. Distance Matrix - 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 any of the numbered columns. The ringed entry becomes the next edge to be added to the tree. Repeat steps 2, 3, 4 and 5 until all rows have been deleted.

8. Dijkstra's Algorithm - Function

   Find the shortest path from S to T through a network.

9. Dijkstra's Algorithm

   Label the start vertex (S) and the final label (0). Record a working value at every vertex (Y) that is directly connected to every vertex that has received its final label (X). Working value at (Y) = final label at (X) + weight of (XY). Only replace the working value at Y if it is smaller. Once a vertex has a final label, it is not revisited. Look at the working values at all vertices without final labels. The smallest working value becomes the final label at the vertex. Repeat steps 2 and 3 un…

10. Dijkstra's Algorithm Notation