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

1
vote
1answer
63 views

Prize collecting Steiner tree on graph without weights on edges

I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is ...
0
votes
1answer
20 views

Spanning tree with chosen leaves NP-Complete proof

I want to prove that the problem described here Spanning tree with chosen leaves is NP-Complete. Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how ...
4
votes
1answer
42 views

Determining if an undirected connected graph is minimally connected

I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected. ...
0
votes
0answers
23 views

two connected graph - find linear spanning subgrap such that subgraph is still connected

Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths. Graph $G$ is not directed. Our task is to find spanning subgraph $H$ of ...
0
votes
0answers
50 views

Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$

Theorem: Let be $G$ a weighted graph in which every edge has a different weight. Suppose that $G$ has two spanning trees $A$ and $A'$. Let be $i$ the first index such that $e_i\ne e'_i$ ...
0
votes
2answers
18 views

Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

I am studying the algorithm of Sollin and we recently studied a lemma: Let be G a graph which values are diffferent on the edges. We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$ ...
1
vote
0answers
31 views

Local search to find minimum degree spanning tree

Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^*$ be the smallest such quantity over all spanning trees of $G$. We have ...
1
vote
1answer
154 views

Maximum Spanning Tree vs Maximum Product Spanning Tree

So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is ...
2
votes
1answer
29 views

Minimum Spanning Tree over Vertices Proof

This is the problem: $d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices. The goal is an algorithm that finds a ...
0
votes
1answer
68 views

Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph. Karloff [1, p.6] has given a map-reduce algorithm called ...
2
votes
1answer
52 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
1
vote
2answers
85 views

Spanning tree with chosen leaves

I'm working on the following problem: Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the ...
-2
votes
1answer
66 views

Prims Algorithm MST

I have this problem : And here's my attempted solution, could someone inform on whether it's correct thanks Haven't got enough reputation to make them into images so far..
4
votes
1answer
80 views

Borůvka cleanup in linear time?

Given boruvka's algorithm: ...
4
votes
1answer
437 views

Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property: For any cycle C in the graph, if the weight of an edge e of C is larger than the ...
0
votes
1answer
56 views

Unclear about proof for unique MST given graph G with distinct weights

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf I have some trouble understanding the proof above. I understand that we assuming two MSTs, T and T', and an edge e that is the ...
4
votes
0answers
208 views

Necessary and sufficient condition for unique minimum spanning tree

This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13] . Prove that an edge-weighted graph $G$ has a unique minimum ...
1
vote
2answers
463 views

Difference between spanning tree and a tree?

Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem ...
4
votes
2answers
119 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
0
votes
1answer
37 views

simple lower bound for constructing a Spanning tree

i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts ...
2
votes
1answer
234 views

Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

Let G = (V,E) be a unit-capacity graph with n vertices and m edges. Let T denote all the spanning trees in G. If we run Karger's algorithm, we will get a random spanning tree in T formed by the ...
0
votes
2answers
147 views

Show that the tree resulting from BFS is a spanning tree?

Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is ...
8
votes
1answer
655 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?
2
votes
2answers
248 views

minimum spanning tree and minimum heavyweight spanning tree [duplicate]

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree ...
3
votes
0answers
563 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
223 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
449 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
70 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
83 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 ...
5
votes
1answer
2k 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 ...
3
votes
2answers
2k 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 ...
2
votes
1answer
113 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
650 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
208 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
2answers
296 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
239 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
546 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
442 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
72 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
125 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 ...
4
votes
3answers
1k views

Minimum spanning tree and its connected subgraph

This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense: The accepted answer at [2] is still in dispute. The proof given by ...
12
votes
4answers
13k 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
77 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
272 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
2k 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
166 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 ...
10
votes
4answers
4k 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
3k 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
246 views

DFS miniumum spanning tree

Just a quick question, If i were to alter the general DFS algorithm to do this: ...
4
votes
2answers
4k 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 ...