Computing matroids from graphs
Posted: 29 Jun 2011, 15:06
There seems to be a bug in matroid::matroid_from_graph: When I generate the complete graph on 5 nodes and its matroid via
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.
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);