Group Abstract Group Abstract

Message Boards Message Boards

Incorrect Spanning trees with FindSpanningTree

GROUPS:

I apologise for my previous post on the subject. Although in the post preview window looked fine, my post did not appear with the graphics I wanted to include. I am having a lot of troubles with the function FindSpanningTree. To better illustrate the issue consider an example provided in the documentation:

g = Graph[{1 <-> 3, 1 <-> 5, 2 <-> 3, 3 <-> 2, 3 <-> 5, 4 <-> 1, 
4 <-> 2, 4 <-> 8, 5 <-> 1, 6 <-> 3, 7 <-> 3, 7 <-> 6, 8 <-> 1},
VertexLabels -> "Name"]

enter image description here

Applying FindSpanningTree does not produce a Tree

HighlightGraph[g, 
FindSpanningTree[g, Method -> "MinimumCostAborescence"]]

enter image description here

Because of the presence uf a cycle, this is not a Tree!! Even in the documentation FindSpanningTree>Options>Method>"MinimumCostAborescence" the given example does not result in a tree.

Hopefully someone from Wolfram could help.

is this a bug?

Best regards

Jesus Rico-Melgoza

Answer
4 months ago

Indeed, FindSpanningTree returns tree:

FindSpanningTree[g, Method -> "MinimumCostAborescence", 
VertexLabels -> "Name"]

enter image description here

The thing is HighlightGraph couldn't distinguish multi edges, i.e., when it come to 2<->3, HighlightGraph will highlight both 2<->3.

POSTED BY: Jaebum Jung
Answer
4 months ago

Jaebum Jung

Thanks!

Jesús

Answer
4 months ago