next | previous | forward | backward | up | index | toc

# isConnected(Matroid) -- whether a matroid is connected

## Synopsis

• Function: isConnected
• Usage:
isConnected M
• Inputs:
• M, ,
• Outputs:
• , whether M is connected

## Description

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