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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I just need to know if it is possible or not. I have done some digging though. I just want to know if there is any way to generate a spanning tree which is binary as well. $\endgroup$– Aditya.MOct 20, 2014 at 7:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.
In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.