Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [minimum-spanning-tree]

Use this tag whenever your question is related to minimum spanning tree (MST). An MST of a connected edge-weighted graph G is a spanning tree whose sum of edge weights is as small as possible. We usually assume $G$ is finite, simple and undirected.

0
votes
1answer
44 views

Proving that a spanning tree of graph is not a minimum

Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$. Now I ...
0
votes
3answers
692 views

Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ? It seems obvious by ...
0
votes
1answer
568 views

Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?

If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph. True/false? and why? Because according to me if there ...
0
votes
1answer
53 views

Distance function such that we visit every “color region” once [closed]

Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ...
0
votes
1answer
38 views

Proving equivalent definitions for MSTs

I am working on the following homework exercise: Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G. I need ...
0
votes
1answer
239 views

Time Complexity of the Kruskal Algorithm after sorting

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
0
votes
1answer
904 views

Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
0
votes
1answer
155 views

Two criteria for an edge to belong to all MSTs

Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1: The edge $e_1$ ...
0
votes
1answer
122 views

What is the maximum possible degrees of a vertex of an MST

What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?
0
votes
1answer
169 views

Turn MST of G to MST of G with one new edge

Given $T$, an MST of $G(V,E)$ connected and undirected. Assume we add an edge $e'$ with weight $w(e')$. Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i ...
0
votes
2answers
395 views

Questions on shortest path and minimum spanning tree

T/F Questions Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False I think this should be True, as Dijkstra's Algorithm ...
0
votes
1answer
301 views

Is this “cycle” condition sufficient for unique minimum spanning tree?

Given a connected, undirected, weighted graph $G$, the condition The maximum-weight edge in any cycle of $G$ is unique. is not necessary for $G$ to have a unique minimum spanning tree (MST). ...
0
votes
1answer
466 views

Proof required for edges in a minimum spanning tree

G=(V,E) is an undirected simple graph in which each edge e 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 ...
0
votes
1answer
3k views

Kruskal's and Prim's algorithm [duplicate]

Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's ...
0
votes
2answers
250 views

Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says: At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ...
0
votes
0answers
26 views

Minimum spanning tree classification problem with adjacent neighbors

I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection. The problem is a minimum cost problem where N ...
0
votes
2answers
51 views

MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ...
0
votes
1answer
57 views

Cost of the MST of the graph [closed]

Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated! Although the picture shows a directed graph, please treat it as ...
0
votes
0answers
53 views

How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
0
votes
1answer
128 views

Boruvka MST algorithm using doubly linked lists

I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following: Develop an implementation of Boruvka's algorithm that uses doubly-linked ...
0
votes
0answers
38 views

N-Guest Table, Graph Problem

The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his ...
0
votes
0answers
100 views

Distributed MST in $O(n \log \log n)$

I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$ I've managed to think of the following, Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
0
votes
0answers
514 views

Using Prim's for finding minimum cost arborescence in a special setting

I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say ...
0
votes
0answers
200 views

find all edges in a weighed tree that are heaviest edges in some cycle

Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$: Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all ...
0
votes
2answers
242 views

Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...
-1
votes
1answer
99 views

Minimum Spanning Tree with Kruskal - bounds on size

I am using Kruskal's algorithm to build minimum-spanning-trees. I would like to know, given that my total set of edges has size N, if there is a bounding number of ...
-1
votes
1answer
148 views

Do we always get the same set of edges after running Kruskal's algorithm on a single graph?

I think it should be false because there may be more than one edge with the same weight.
-1
votes
1answer
3k views

Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....
-2
votes
1answer
131 views

If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer. [closed]

If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer.
-3
votes
2answers
868 views

How can I fix this pseudocode of Kruskal's algorithm? [closed]

So here, I am not sure what the while statement means. In the lecture note there is no definition for T or N or u or v. My guess is T is the minimum spinning tree, but is N the node? Why condition T ...