HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding minimum spanning tree of a special form graph

Submitted by: @import:stackexchange-cs··
0
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,

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)-->vn


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.

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.

Context

StackExchange Computer Science Q#69118, answer score: 3

Revisions (0)

No revisions yet.