Circuit closures matroids#
Matroids are characterized by a list of all tuples \((C, k)\), where \(C\) is the closure of a circuit, and \(k\) the rank of \(C\). The CircuitClosuresMatroid class implements matroids using this information as data.
Construction#
A CircuitClosuresMatroid
can be created from another matroid or from a
list of circuit-closures. For a full description of allowed inputs, see
below
.
It is recommended to use the
Matroid()
function for a more
flexible construction of a CircuitClosuresMatroid
. For direct access to
the CircuitClosuresMatroid
constructor, run:
sage: from sage.matroids.advanced import *
See also sage.matroids.advanced
.
EXAMPLES:
sage: from sage.matroids.advanced import *
sage: M1 = CircuitClosuresMatroid(groundset='abcdef',
....: circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: M2 = Matroid(circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: M3 = Matroid(circuit_closures=[(2, 'abc'),
....: (3, 'abcdef'), (2, 'ade')])
sage: M1 == M2
True
sage: M1 == M3
True
Note that the class does not implement custom minor and dual operations:
sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(groundset='abcdef',
....: circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: isinstance(M.contract('a'), MinorMatroid)
True
sage: isinstance(M.dual(), DualMatroid)
True
AUTHORS:
Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
Methods#
- class sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid#
Bases:
Matroid
A general matroid \(M\) is characterized by its rank \(r(M)\) and the set of pairs
\((k, \{\) closure \((C) : C ` circuit of ` M, r(C)=k\})\) for \(k=0, .., r(M)-1\)
As each independent set of size \(k\) is in at most one closure(\(C\)) of rank \(k\), and each closure(\(C\)) of rank \(k\) contains at least \(k + 1\) independent sets of size \(k\), there are at most \(\binom{n}{k}/(k + 1)\) such closures-of-circuits of rank \(k\). Each closure(\(C\)) takes \(O(n)\) bits to store, giving an upper bound of \(O(2^n)\) on the space complexity of the entire matroid.
A subset \(X\) of the ground set is independent if and only if
\(| X \cap ` closure `(C) | \leq k\) for all circuits \(C\) of \(M\) with \(r(C)=k\).
So determining whether a set is independent takes time proportional to the space complexity of the matroid.
INPUT:
M
– (default:None
) an arbitrary matroid.groundset
– (default:None
) the groundset of a matroid.circuit_closures
– (default:None
) the collection of circuit closures of a matroid, presented as a dictionary whose keys are ranks, and whose values are sets of circuit closures of the specified rank.
OUTPUT:
If the input is a matroid
M
, return aCircuitClosuresMatroid
instance representingM
.Otherwise, return a
CircuitClosuresMatroid
instance based ongroundset
andcircuit_closures
.
Note
For a more flexible means of input, use the
Matroid()
function.EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = CircuitClosuresMatroid(matroids.named_matroids.Fano()) sage: M Matroid of rank 3 on 7 elements with circuit-closures {2: {{'a', 'b', 'f'}, {'a', 'c', 'e'}, {'a', 'd', 'g'}, {'b', 'c', 'd'}, {'b', 'e', 'g'}, {'c', 'f', 'g'}, {'d', 'e', 'f'}}, 3: {{'a', 'b', 'c', 'd', 'e', 'f', 'g'}}} sage: M = CircuitClosuresMatroid(groundset='abcdefgh', ....: circuit_closures={3: ['edfg', 'acdg', 'bcfg', 'cefh', ....: 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'], ....: 4: ['abcdefgh']}) sage: M.equals(matroids.named_matroids.P8()) True
- circuit_closures()#
Return the list of closures of circuits of the matroid.
A circuit closure is a closed set containing a circuit.
OUTPUT:
A dictionary containing the circuit closures of the matroid, indexed by their ranks.
See also
EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = CircuitClosuresMatroid(matroids.named_matroids.Fano()) sage: CC = M.circuit_closures() sage: len(CC[2]) 7 sage: len(CC[3]) 1 sage: len(CC[1]) Traceback (most recent call last): ... KeyError: 1 sage: [sorted(X) for X in CC[3]] [['a', 'b', 'c', 'd', 'e', 'f', 'g']]
- 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:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.full_rank() 4 sage: M.dual().full_rank() 4
- 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.named_matroids.Pappus() sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']