components(Matroid) -- connected components of matroid

Synopsis

Function: components
Usage:

components M
Inputs:
- M, a matroid,
Outputs:
- a list, the connected components of M

Description

Define an equivalence relation ~ on the ground set of M by e ~ f if e = f or $\{e,f\}$ is contained in a circuit. The equivalence classes under ~ are the connected components of M. A matroid is the direct sum of its connected 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 : C = components M

o2 = {a "matroid" of rank 1 on 1 elements, a "matroid" of rank 1 on 1
     ------------------------------------------------------------------------
     elements, a "matroid" of rank 2 on 3 elements}

o2 : List

i3 : areIsomorphic(M, fold(C, (a, b) -> a ++ b))

o3 = true

i4 : G = graph({{0,1},{0,2},{0,3},{0,4},{1,2},{3,4}})

o4 = Graph{0 => {1, 2, 3, 4}}
           1 => {0, 2}
           2 => {0, 1}
           3 => {0, 4}
           4 => {0, 3}

o4 : Graph

i5 : isConnected G

o5 = true

i6 : components matroid G

o6 = {a "matroid" of rank 2 on 3 elements, a "matroid" of rank 2 on 3
     ------------------------------------------------------------------------
     elements}

o6 : List

Caveat

As the examples above show, the connected components of the graphic matroid M(G) need not be the same as the connected components of the graph G (indeed, for any graph G, there exists a connected graph H with M(G) isomorphic to M(H)).

Ways to use this method: