patternMinor
Finding minimum spanning tree of a special form graph
Viewed 0 times
graphminimumspecialfindingformspanningtree
Problem
I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:
My idea was a recursive solution:
Suppose the algorithm recieve the graph with n as a parameter,
I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.
Any suggestions would be much appreciated.
My idea was a recursive solution:
Suppose the algorithm recieve the graph with n as a parameter,
if n==2 then:
take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
- recursivly call the algorithm for n-1
- take the lower cost edge between v0-->vn and v(n-1)-->vnI'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.
Any suggestions would be much appreciated.
Solution
That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs.
Here is a counterexample with $n=3$.
The graph above was drawn at https://graphonline.ru/en
All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.
By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.
Here is a counterexample with $n=3$.
The graph above was drawn at https://graphonline.ru/en
All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.
By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.
Context
StackExchange Computer Science Q#69118, answer score: 3
Revisions (0)
No revisions yet.