next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: isConnected(Matroid)

isConnected(Matroid) -- whether a matroid is connected



A matroid M is called connected if for every pair of distinct elements f, g in M, there is a circuit containing both of them. This turns out to be equivalent to saying that there does not exist an element e in M with rank({e}) + rank(M - {e}) = rank(M) (note that <= always holds by submodularity of the rank function).

This method checks connectivity using the first definition above. The second definition generalizes to higher connectivity - cf. is3Connected. In the language of higher connectivity, a matroid is connected (in the sense of the two definitions above) if and only if it is 2-connected, i.e. has no 1-separation.

To obtain the connected components of a matroid, use components.

i1 : M = matroid graph({{0,1},{0,2},{1,2},{3,4},{4,5}})

o1 = a matroid of rank 4 on 5 elements

o1 : Matroid
i2 : isConnected M

o2 = false
i3 : C = components M

o3 = {a matroid of rank 1 on 1 elements, a matroid of rank 1 on 1 elements, a
     matroid of rank 2 on 3 elements}

o3 : List
i4 : all(C, isConnected)

o4 = true

See also