Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?

I only
II only
Both I and II
Neither I nor II

LohaHridoy

4 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 3 : Both I and II

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Example:

Graph G(V, E)

[ alt="GATE CS 112 7Q GATE 2019 images raju D 1" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%201.PNG">

G(V, V – 1) → minimum spanning tree

[ alt="GATE CS 112 7Q GATE 2019 images raju D 2" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%202.PNG" style="width: 146px; height: 114px;">

If edge weights are distinct then there exist unique MST.

Hence option 1 is correct

Theorem:

If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree, but converse may not be true.

4 views Answered 2022-09-04 04:29

Related Questions

G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?

1 Answers 9 Views

In the following question below some statements are given followed by some conclusions. Taking the given statements to be true even if they seem to be at variance from commonly known facts, read all the conclusions and then decide which of the given conclusions logically follows the given statements. Statements: Some wall is pillar No pillar is zebra Some zebra is tree Conclusion: I. some wall is not tree II. some tree is not pillar?

1 Answers 4 Views

G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e ?

1 Answers 4 Views

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change?

1 Answers 4 Views

Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements is/are CORRECT I. A connected UDP socket can be used to communicate with multiple peers simultaneously. II. A process can successfully call connect function again for an already connected UDP socket.?

1 Answers 4 Views

In a database system, unique timestamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp. If TS(T2) < TS(T1) then T1 is killed else T2 waits. Assume any transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

1 Answers 4 Views

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: I) Minimum Spanning Tree of G is always unique. II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?

1 Answers 5 Views

Two statements are given followed by two conclusions I and II. You have to consider these statements to be true, even if they seem to be at variance with commonly known facts and choose which f the given conclusions logically follow(s) from the given statements. Statements : All Chairs are expensive All expensive are unique. Conclusion : I. All chairs are unique. II. All unique are expensive.?

1 Answers 4 Views

In the following question below are given three statements followed by three conclusions. Taking the given statements to be true even if they seem to be at variance from commonly known facts, read all the conclusions and then decide which of the given conclusion logically follows the given statements. Statements: I. All tree are green. II. Few green are brown. III. Only a few brown are plant. Conclusions: I. All plant being brown is a possibility. II. Only green being tree is a possibility. III. Some brown being tree is a possibility.?

1 Answers 4 Views

In the question, one statement is given followed by two conclusions I and II. You have to consider the statements to be true even if they seem to be at variance from commonly known facts. You have to decide which of the conclusion, if any, follow from the given statements. Statement: “Flat 15% off on each item on every Wednesday. Offer applicable on Axis bank Debit cards only”. Conclusions: I. Each and every product is available at 15% discount on Wednesday only. II. Customers having credit card of Axis bank can also avail this offer.?

1 Answers 5 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)