Register

GO Classes DPP | GATE CS, DA | Algorithms | MST

90 views
1 1 vote

Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.

We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e)$ is as small as possible.

Is the optimal solution $E'$ guaranteed to form a tree?

  1. Yes
     
  2. No

1 Answer

0 0 votes

With ordinary MST reasoning, cycles are unnecessary because removing an appropriate cycle edge does not hurt connectivity and can reduce or preserve total cost.

But this changes when edges can have negative weights.

Consider a triangle:

$A-B$

$B-C$

$C-A$

where every edge has weight $-1$

Any spanning tree contains two edges, so its total weight is $-2$

But choosing all three edges gives $-3$

The resulting graph is connected and has lower total weight.

However, it contains a cycle.

Therefore the optimal connected edge subset need not be a tree.

In fact, negative edges can be beneficial even when they create cycles, because adding them decreases the objective value.


Answer : B

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

0 0 votes
1 1 answer
91
91 views
GO Classes asked Aug 26
91 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Let $G=(V,E)$ be a directed graph with positive edge weights.Given vertices $s,w,t$ we want the length of the shortest path from $s$ to $t$ that must pass through $w$.Con...
2 2 votes
1 1 answer
77
77 views
GO Classes asked Aug 26
77 views
GO Classes DPP | GATE CS, DA | Algorithms | Floyd-Warshall
What is the primary reason to use Floyd's algorithm for the all-pairs shortest-path problem instead of Dijkstra's algorithm?Faster for dense graphs. Faster for sparse gra...
0 0 votes
1 1 answer
122
122 views
GO Classes asked Aug 26
122 views
GO Classes DPP | GATE CS, DA | Algorithms | Binary Search
Which of the following cannot be a sequence of keys compared during a binary search for some target key?$500,200,450,180$ $500,450,200,180$ $180,500,200,450$ $180,200,500...
0 0 votes
1 1 answer
65
65 views
GO Classes asked Aug 26
65 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...