The Gateway to Computer Science Excellence
+1 vote
1.4k views

5. 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 choosen is ?


(1) AD, AE, AG, GC, GB, BF

(2) GC, GB, BF, GA, AD, AE

(3) GC, AD, GB, GA, BF, AE

(4) AD, AG, GC, AE, GB, BF

in Graph Theory by (399 points)
retagged by | 1.4k views
0
Where is graph????
0
Incomplete question.

Edge weight of BD is not given.

1 Answer

+1 vote

Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a safe edge to 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}}$

by Boss (15.4k points)
edited by
0
@Sukanya Das
"We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be 1(default)"

I have never heard of such a thing , neither read it in any standard text
could you give some reference please.
0

Sukanya Das Why do we need the value of the value of BD?

0

Rameesh, when i  studied graph theory, i learnt that from my our college professor.

anyway i'll try to give you reference

0

pankaj_vir , to find MST , we need the weight of every edges. 

0

 Sukanya Das, I know that, but nothing is written anywhere that if no weight is given take 1

0
no option matches with this order.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
198,506 comments
105,272 users