Dark Mode

1,506 views

1 vote

Consider the graph given below:

Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is

- AD, AE, AG, GC, GB, BF
- GC, GB, BF, GA, AD, AE
- GC, AD, GB, GA, BF, AE
- AD, AG, GC, AE, GB, BF

@abhishekmehta4u If edge weight is not given and it is not in any of the options, we may safely assume that BD is having infinite weight.

0

1 vote

Kruskal's algorithmis an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds asafe edgeto add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

In the given graph edge weight of $\text{BD}$ is not given. But if we see the options, $\text{BD}$ is not in any of them and so we can assume its weight is infinity (or a large value).

The smallest edge weight is $2$ and any of an edge with weight $2$ can be picked by Kruskal’s algorithm which are $\text{AD}$ or $\text{GC}.$ These $2$ edges are not in a cycle and so both must be the first two edges selected by Kruskal’s algorithm. Only option C satisfies.

0 votes

Kruskal's algorithmis an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds asafe edgeto add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

The given graph is

We can see that $DB's$ weight is not given.

We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be $1$(default)

Edge No. | Vertex Pair | Edge Weight |
---|---|---|

E1 | (B,D) | 1 |

E2 | (G,C) | 2 |

E3 | (A,D) | 2 |

E4 | (B,G) | 3 |

E5 | (A,G) | 3 |

E6 | (A,E) | 4 |

E7 | (D,G) | 4 |

E8 | (B,C) | 4 |

E9 | (B,F) | 4 |

E10 | (D,E) | 5 |

E11 | (C,F) | 5 |

E12 | (A,C) | 6 |

Graph

Add edge E1

Add edge E2

Add edge E3

Add edge E4

Edge E5 will not counted, as it'll create cycle.

Add edge E6

Edge E7,E8 will not counted, as it'll create a cycle.

Add edge E9

Edge E10, E11, E12 will not connected, they'll make a cycle.

∴ $\color{green}{\text{Total Cost}}= 1+2+2+3+4+4$

$\qquad\qquad = \color{gold}{16}$

$\color{violet}{\text{The List of the edges of the tree in the order in which they are choosen is}}$ $\color{maroon}{\text{BD, GC, AD, BG, AE, BF}}$