-----------------------------------

whoareyou

Tue Feb 25, 2014 8:22 pm


Minimum Spanning Tree of a Graph Solutions

-----------------------------------

Hello,

I recently wrote a program that implements a slightly modified version of Prim's Algorithm and it seems to work correctly. However, I am doubtful because my prof claims that this certain tree has only 1 minimal solution but my program gives quite a few different solutions (edit: 2 different solutions). Note that a different solution means that different edges are used to visit every node. Using the same edges in a different order is not a different solution. Can someone please confirm this:

GRAPH:
http://i.imgur.com/d9DKpQx.png

SOLUTIONS:
[code]
A -> B: 2
A -> C: 3
C -> E: 1
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

B -> A: 2
A -> C: 3
C -> E: 1
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

C -> E: 1
C -> A: 3
A -> B: 2
E -> F: 4
F -> G: 2
E -> D: 5

TOTAL DISTANCE: 17

D -> E: 5
E -> C: 1
C -> A: 3
A -> B: 2
E -> F: 4
F -> G: 2

TOTAL DISTANCE: 17

E -> C: 1
C -> A: 3
A -> B: 2
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

F -> G: 2
F -> E: 4
E -> C: 1
C -> A: 3
A -> B: 2
E -> D: 5

TOTAL DISTANCE: 17

G -> F: 2
G -> B: 4
B -> A: 2
A -> C: 3
C -> E: 1
E -> D: 5

TOTAL DISTANCE: 17
[/code]


-----------------------------------

Dreadnought

Tue Feb 25, 2014 9:25 pm


Re: Minimum Spanning Tree of a Graph Solutions

-----------------------------------

I agree, there are two different solutions to this tree.

1)  E(T) = {AB, AC, CE, DE, EF, FG}
2)  E(T) = {AB, AB, BG, CE, DE, FG}


-----------------------------------

whoareyou

Tue Feb 25, 2014 10:11 pm


Re: Minimum Spanning Tree of a Graph Solutions

-----------------------------------


2)  E(T) = {AB, AB, BG, CE, DE, FG}

I think you meant {AB, AC, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well.  :D


-----------------------------------

Dreadnought

Tue Feb 25, 2014 10:44 pm


Re: Minimum Spanning Tree of a Graph Solutions

-----------------------------------

I think you meant {AB, AC, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well.  :D

Ya, that's what I meant, woops!


-----------------------------------

whoareyou

Tue Feb 25, 2014 11:26 pm


RE:Minimum Spanning Tree of a Graph Solutions

-----------------------------------

Could somebody also confirm that there is only one minimal solution to this graph? My prof seems to hint that there may be more than one solution but my program gives the same solution every time (perhaps he got them switched with the one before? or my program is wrong :( ):

GRAPH:
http://i.imgur.com/yah0OL0.png

SOLUTIONS:
[code]A -> B: 3
A -> C: 3
C -> D: 3
B -> H: 6
H -> F: 3
H -> I: 4
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

B -> A: 3
A -> C: 3
C -> D: 3
B -> H: 6
H -> F: 3
H -> I: 4
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

C -> A: 3
C -> D: 3
A -> B: 3
C -> E: 6
E -> G: 4
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

D -> C: 3
C -> A: 3
A -> B: 3
C -> E: 6
E -> G: 4
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

E -> G: 4
E -> C: 6
C -> A: 3
C -> D: 3
A -> B: 3
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

F -> H: 3
H -> I: 4
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

G -> E: 4
E -> C: 6
C -> A: 3
C -> D: 3
A -> B: 3
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

H -> F: 3
H -> I: 4
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

I -> H: 4
H -> F: 3
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32
[/code]


-----------------------------------

Tony

Wed Feb 26, 2014 3:36 am


Re: RE:Minimum Spanning Tree of a Graph Solutions

-----------------------------------

only one minimal solution
...
SOLUTION__S__
Doesn't this answer the question?


-----------------------------------

whoareyou

Wed Feb 26, 2014 8:40 am


Re: RE:Minimum Spanning Tree of a Graph Solutions

-----------------------------------

only one minimal solution
...
SOLUTION__S__
Doesn't this answer the question?

No, the output just shows the path starting from each node but I've analyzed each of the paths and they're all the same so I just want some confirmation that there is only one minimal spanning tree since my prof seems to hint that may be the case. Or my algorithm could be messed up.