Let G be a connected graph with vertices a, b, c, ...,h, i. Thus | V | = 9. A li

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

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.