Circuits matroids#
Matroids are characterized by a list of circuits, which are minimal dependent
sets. The CircuitsMatroid
class implements matroids using this information
as data.
A CircuitsMatroid
can be created from another matroid or from a list of
circuits. For a full description of allowed inputs, see
below
. It is
recommended to use the Matroid()
function for a more flexible way of constructing a CircuitsMatroid
and
other classes of matroids. For direct access to the CircuitsMatroid
constructor, run:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid
AUTHORS:
Giorgos Mousa (2023-12-23): initial version
- class sage.matroids.circuits_matroid.CircuitsMatroid#
Bases:
Matroid
A matroid defined by its circuits.
INPUT:
M
– a matroid (default:None
)groundset
– a list (default:None
); the groundset of the matroidcircuits
– a list (default:None
); the collection of circuits of the matroidnsc_defined
– boolean (default:False
); whether the matroid was defined by its nonspanning circuits
Note
For a more flexible means of input, use the
Matroid()
function.- bases()#
Return the bases of the matroid.
OUTPUT: a SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: len(M.bases()) 6
- bases_iterator()#
Return an iterator over the bases of the matroid.
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: it = M.bases_iterator() sage: it.__next__() frozenset({0, 1}) sage: sorted(M.bases_iterator(), key=str) [frozenset({0, 1}), frozenset({0, 2}), frozenset({0, 3}), frozenset({1, 2}), frozenset({1, 3}), frozenset({2, 3})]
- circuits(k=None)#
Return the circuits of the matroid.
INPUT:
k
– an integer (optional); the length of the circuits
OUTPUT: a SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: M.circuits() Iterator over a system of subsets sage: list(M.circuits(0)) [] sage: sorted(M.circuits(3), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
- circuits_iterator(k=None)#
Return an iterator over the circuits of the matroid.
INPUT:
k
– an integer (optional); the length of the circuits
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: sum(1 for C in M.circuits_iterator()) 4 sage: list(M.circuits_iterator(0)) [] sage: sorted(M.circuits_iterator(3), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
- full_rank()#
Return the rank of the matroid.
The rank of the matroid is the size of the largest independent subset of the groundset.
OUTPUT: an integer; the rank of the matroid
EXAMPLES:
sage: M = matroids.Theta(20) sage: M.full_rank() 20
- girth()#
Return the girth of the matroid.
The girth is the size of the smallest circuit. In case the matroid has no circuits the girth is \(\infty\).
EXAMPLES:
sage: matroids.Theta(10).girth() 3
REFERENCES:
[Oxl2011], p. 327.
- groundset()#
Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT: a set
EXAMPLES:
sage: M = matroids.Theta(2) sage: sorted(M.groundset()) ['x0', 'x1', 'y0', 'y1']
- is_paving()#
Return if
self
is paving.A matroid is paving if each of its circuits has size \(r\) or \(r+1\).
OUTPUT: boolean
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.catalog.Vamos()) sage: M.is_paving() True
- is_valid()#
Test if
self
obeys the matroid axioms.For a matroid defined by its circuits, we check the circuit axioms.
OUTPUT: boolean
EXAMPLES:
sage: C = [[1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() True sage: C = [[1,2], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[3,6], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[3,6], [1, 2, 3], [3, 4, 5], [1, 2, 6], [6, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() True sage: C = [[], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[1, 2, 3], [3, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False
- no_broken_circuits_sets(ordering=None)#
Return the no broken circuits (NBC) sets of
self
.An NBC set is a subset \(A\) of the ground set under some total ordering \(<\) such that \(A\) contains no broken circuit.
INPUT:
ordering
– a total ordering of the groundset given as a list
OUTPUT: a list of frozensets
EXAMPLES:
sage: M = Matroid(circuits=[[1,2,3], [3,4,5], [1,2,4,5]]) sage: SimplicialComplex(M.no_broken_circuits_sets()) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)} sage: SimplicialComplex(M.no_broken_circuits_sets([5,4,3,2,1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)}
sage: M = Matroid(circuits=[[1,2,3], [1,4,5], [2,3,4,5]]) sage: SimplicialComplex(M.no_broken_circuits_sets([5,4,3,2,1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (2, 3, 5), (2, 4, 5), (3, 4, 5)}
- nonspanning_circuits()#
Return the nonspanning circuits of the matroid.
OUTPUT: a SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: M.nonspanning_circuits() Iterator over a system of subsets
- nonspanning_circuits_iterator()#
Return an iterator over the nonspanning circuits of the matroid.
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: list(M.nonspanning_circuits_iterator()) []