Guichard-Combinatorics-Graph-Theory · Problem 5.6.3
Graph Theory
Mathematics — Probability · optimal-spanning-trees
Problem
In both the Jarn\'{i}k and Kruskal algorithms, it may be that two or more edges can be added at any particular step, and some method is required to choose one over the other. For the graph below, use both algorithms to find a minimum cost spanning tree. Using the labels ei on the graph, at each stage pick the edge ei that the algorithm specifies and that has the lowest possible i among all edges available. For the Jarn\'{i}k algorithm, use the designated v0 as the starting vertex. For each algorithm, list the edges in the order in which they are added. The edge weights e1,e2,…,e10 are 6,7,8,2,3,2,4,6,1,1, shown in red.