Let G be a connected graph with vertices a, b, c, ...,h, i. Thus | V | = 9. A li
ID: 3714777 • Letter: L
Question
Let G be a connected graph with vertices a, b, c, ...,h, i. Thus |V| = 9. A list of edges, sorted by weight, is shown below. Execute both Kruskal's and Prims algorithms without drawing any part of G, as shown in class. Indicate the order edges are added to "T." Initialize Prim's with vertex a . For Kruskal's algorithm, show the connected components, as illustrated in class.
Kruskal
T = V, add cheapest (globally) edge keeping circuit-free until |E| = n-1
w(e) edge
1 cf 1 hi 2 eh 2 fi 3 bd 3 gh 4 bc 4 dg 4 fh 5 ef 6 ab 6 be 7 ad 8 de
Prim
T = {a}, add edges and vertices by adding cheapest (locally) edge connecting T to V-T until |E| = n-1
w(e) edge
1 cf 1 hi 2 eh 2 fi 3 bd 3 gh 4 bc 4 dg 4 fh 5 ef 6 ab 6 be 7 ad 8 de
Explanation / Answer
Solution:
The graph is given as
1 cf 1 hi 2 eh 2 fi 3 bd 3 gh 4 bc 4 dg 4 fh 5 ef 6 ab 6 be 7 ad 8 de
Kruskal's:
Initially,
the components are
a b c d e f g h i
first cf will be added
components
{c, f}, a b d e g h i
now 1 hi will be selected
components
{c, f}, a b d e g {h i}
now 2 eh will be selected
components
{c, f}, a b d g {e h i}
2 fi will be connected
components
a b d g {c f e h i}
3 bd will be connected
components
a {b d} g {c f e h i}
3 gh will be connected
components
a {b d} {c f e h g i}
now 4 bc will be connected
components
a {b d c f e h g i}
now 6 ab will be connected
components
{a b d c f e h g i}
b)
Here the order in which the vertices are connected is
a-b-d-c-f-i-e-g- h
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.