Computing matroids from graphs

[hampe]

There seems to be a bug in matroid::matroid_from_graph: When I generate the complete graph on 5 nodes and its matroid via

Code: Select all

@adj=(); for($i = 0; $i < 5; $i++) { @adj = (@adj, sequence(0,5)-$i); } $g = new graph::Graph(N_NODES=>5,ADJACENCY=>\@adj); $m = matroid::matroid_from_graph($g);

I get a matroid with 135 bases. However, Cayleys theorem states that the complete graph on n nodes should have n^(n-2) (in this case: 125) spanning trees. Indeed, $m is not even a matroid: The first two rows of BASES are B1 = {0,1,2,9} and B2 = {0,1,3,6}, which do not fulfill the basis exchange axiom: When removing 9 from B1, adding either 3 or 6 should make {0,1,2} a basis, but neither {0,1,2,6} nor {0,1,2,3} occur in BASES.

[sherrmann]

There is in deed a bug in the matroid_from_graph client. Thanks very much for pointing that out. It will be fixed for the next release at the latest.

[sherrmann]

There is in deed a bug in the matroid_from_graph client. Thanks very much for pointing that out. It will be fixed for the next release at the latest.

Until the next release is available, if you have a source distribution, you can use the attached patch to correct the bug. Please execute

Code: Select all

patch -p2 </path/to/matroid_from_graph.patch make

in your polymake main directory.