Tagged Questions

The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.

learn more… | top users | synonyms

4
votes
1answer
389 views

Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
0
votes
0answers
19 views

check whether given tree is minimum or not

Problem says, suppose you're given a weighted (weights can be negative) graph and a spanning tree of it. Then you've to tell in linear time whether that spanning tree is minimum or not. I was doing ...
3
votes
0answers
45 views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
0
votes
1answer
196 views

Is it possible for a graph to have two different minimum spanning tree

I am suppose to create a minimum spanning tree from this graph below I got this answer However this is my textbook answer Based on what i have learnt , I think my answer and the textbook ...
1
vote
2answers
76 views

Find an MST in a graph with edge weights from {1,2}

I've been asked the following question: Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph. ...
1
vote
1answer
48 views

Choosing spanning trees to maximise node connectivity

Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints. ...
-1
votes
1answer
36 views

Find MST based upon new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
4
votes
1answer
193 views

Why is the k-bounded spanning tree problem NP-complete?

The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$. I ...
2
votes
2answers
450 views

If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
1
vote
0answers
36 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
5
votes
3answers
271 views

Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
1
vote
2answers
113 views

Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
3
votes
0answers
121 views

Prim's Algorithm - Building the Priority Queue

Suppose we were using a priority queue(PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then ...
1
vote
2answers
182 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') ...
-1
votes
2answers
180 views

Proof of Correctness of Prim's algorithm [duplicate]

what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case? Is it because of after any number of steps, $S$ might not be in a sub ...
-1
votes
1answer
188 views

Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
-1
votes
1answer
56 views

Satisfying condition to be in minimum spanning tree of an edge (maximum weight)

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
0
votes
1answer
86 views

Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST: Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$. I want to find another minimum ...
3
votes
2answers
303 views

Minimum spanning tree and its connected subgraph

This problem is from the book Algorithms, Chapter 5: Greedy algorithms. In case of being closed as a duplication to that in Minimum Spanning tree subgraph, I will first make a defense: The accepted ...
2
votes
2answers
2k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
1
vote
2answers
67 views

Showing that graph of spanning trees are connected

Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$. We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in ...
1
vote
1answer
131 views

Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

I'm given this problem: Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen ...
4
votes
1answer
840 views

MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

According to CLRS, the Prim's algorithms is implemented as below -- $\mathtt{\text{MST-PRIM}}(G,w,r)$ for each $u \in V[G]$ do $\mathtt{\text{key}}[u] \leftarrow \infty$ ...
1
vote
1answer
97 views

Upper bound on the number of edges relative to the height of a DFS tree

Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of ...
9
votes
3answers
1k views

Graph Has Two / Three Different Minimal Spanning Trees?

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
4
votes
3answers
1k views

How many minimal spanning trees are there when all edge costs are distinct?

Suppose all costs on edges are distinct. How many minimal spanning trees are possible? I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because ...
2
votes
1answer
120 views

DFS miniumum spanning tree

Just a quick question, If i were to alter the general DFS algorithm to do this: ...
4
votes
2answers
2k views

Minimum spanning tree with two minimum edge weights

Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree? I know the proof for if all edge weights are ...
2
votes
1answer
576 views

Question about Prims algorithm where weights are between 1 and some constant W

I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
1
vote
0answers
161 views

What edges are not in any MST?

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected ...
2
votes
1answer
777 views

Depth First Search to find Minimum spanning tree

A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example ...
11
votes
1answer
298 views

Minimal Spanning Tree With Double Weight Parameters

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
4
votes
1answer
193 views

Why do the swap step in Prim's algorithm for minimum spanning trees?

I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
5
votes
0answers
163 views

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a ...
9
votes
1answer
416 views

Tighter analysis of modified Borůvka's algorithm

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: ...
9
votes
1answer
2k views

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
2
votes
1answer
744 views

NP-completeness of a spanning tree problem

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from NP completeness proof of a spanning tree problem In this problem, I am interested in the original ...
3
votes
2answers
516 views

Does spanning tree make sense for DAG?

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.