ExamLookup
Menu mobile
Home
Current Affairs
General Knowledge
Computer
Python
HTML
GATE
: Computer Science and IT
Let Gbe a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ___________. , Let Gbe a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ___________.
Let Gbe a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ___________.
A.
800
800
B.
995
995
C.
1000
1000
D.
456
456
Solution
B. 995
Explanation
Since there are 100 vertices, there must be 99 edges in Minimum Spanning Tree (MST). When weight of every edge is increased by 5, the increment in weight of MST is = 99 * 5 = 495 so new weight of MST is 500 + 495 which is 995. A graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. A graph with just one vertex is connected.
CCC Online Test 2021
CCC Practice Test Hindi
Python Programming Tutorials
Best Computer Training Institute in Prayagraj (Allahabad)
O Level NIELIT Study material and Quiz
Bank SSC Railway TET UPTET Question Bank
career counselling in allahabad
Sarkari Exam Quiz
Website development Company in Allahabad