The abstract Matroid class
Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/...) dependence. See the Wikipedia article on matroids for theory and examples. In Sage, various types of matroids are supported: BasisMatroid, CircuitClosuresMatroid, LinearMatroid (and some specialized subclasses), RankMatroid. To construct them, use the function Matroid().
All these classes share a common interface, which includes the following methods (organized by category). Note that most subclasses (notably LinearMatroids) will implement additional functionality (e.g. linear extensions).
In addition to these, all methods provided by SageObject are available, notably save() and rename().
Many methods (such as M.rank()) have a companion method whose name starts with an underscore (such as M._rank()). The method with the underscore does not do any checks on its input. For instance, it may assume of its input that
Using the underscored version could improve the speed of code a little, but will generate more cryptic error messages when presented with wrong input. In some instances, no error might occur and a nonsensical answer returned.
A subclass should always override the underscored method, if available, and as a rule leave the regular method alone.
These underscored methods are not documented in the reference manual. To see them, within Sage you can create a matroid M and type M._<tab>. Then M._rank? followed by <tab> will bring up the documentation string of the _rank() method.
Many mathematical objects give rise to matroids, and not all are available through the provided code. For incidental use, the RankMatroid subclass may suffice. If you regularly use matroids based on a new data type, you can write a subclass of Matroid. You only need to override the __init__, _rank() and groundset() methods to get a fully working class.
EXAMPLE:
In a partition matroid, a subset is independent if it has at most one element from each partition. The following is a very basic implementation, in which the partition is specified as a list of lists:
sage: import sage.matroids.matroid
sage: class PartitionMatroid(sage.matroids.matroid.Matroid):
....: def __init__(self, partition):
....: self.partition = partition
....: E = set()
....: for P in partition:
....: E.update(P)
....: self.E = frozenset(E)
....: def groundset(self):
....: return self.E
....: def _rank(self, X):
....: X2 = set(X)
....: used_indices = set()
....: rk = 0
....: while len(X2) > 0:
....: e = X2.pop()
....: for i in range(len(self.partition)):
....: if e in self.partition[i]:
....: if i not in used_indices:
....: used_indices.add(i)
....: rk = rk + 1
....: break
....: return rk
....:
sage: M = PartitionMatroid([[1, 2], [3, 4, 5], [6, 7]])
sage: M.full_rank()
3
sage: M.tutte_polynomial(var('x'), var('y'))
x^2*y^2 + 2*x*y^3 + y^4 + x^3 + 3*x^2*y + 3*x*y^2 + y^3
Note
The abstract base class has no idea about the data used to represent the matroid. Hence some methods need to be customized to function properly.
Necessary:
Representation:
Comparison:
In Cythonized classes, use __richcmp__() instead of __eq__(), __ne__().
Copying, loading, saving:
See, for instance, rank_matroid or circuit_closures_matroid for sample implementations of these.
Note
The example provided does not check its input at all. You may want to make sure the input data are not corrupt.
EXAMPLES:
Construction:
sage: M = Matroid(Matrix(QQ, [[1, 0, 0, 0, 1, 1, 1],
....: [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 1, 1, 0, 1]]))
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
sage: M.rank([0, 1, 2])
3
sage: M.rank([0, 1, 5])
2
Minors:
sage: M = Matroid(Matrix(QQ, [[1, 0, 0, 0, 1, 1, 1],
....: [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 1, 1, 0, 1]]))
sage: N = M / [2] \ [3, 4]
sage: sorted(N.groundset())
[0, 1, 5, 6]
sage: N.full_rank()
2
Testing. Note that the abstract base class does not support pickling:
sage: M = sage.matroids.matroid.Matroid()
sage: TestSuite(M).run(skip="_test_pickling")
[BC79] |
|
[CMO11] |
|
[CMO12] |
|
[GG12] | Jim Geelen and Bert Gerards, Characterizing graphic matroids by a system of linear equations, submitted, 2012. Preprint: http://www.gerardsbase.nl/papers/geelen_gerards=testing-graphicness%5B2013%5D.pdf |
[GR01] | C.Godsil and G.Royle, Algebraic Graph Theory. Graduate Texts in Mathematics, Springer, 2001. |
[Hlineny] | Petr Hlineny, “Equivalence-free exhaustive generation of matroid representations”, Discrete Applied Mathematics 154 (2006), pp. 1210-1222. |
[Hochstaettler] | Winfried Hochstaettler, “About the Tic-Tac-Toe Matroid”, preprint. |
[Lyons] |
|
[Oxley1] | James Oxley, “Matroid theory”, Oxford University Press, 1992. |
[Oxley] | (1, 2, 3, 4) James Oxley, “Matroid Theory, Second Edition”. Oxford University Press, 2011. |
[Pen12] |
|
AUTHORS:
Bases: sage.structure.sage_object.SageObject
The abstract matroid class, from which all matroids are derived. Do not use this class directly!
To implement a subclass, the least you should do is implement the __init__(), _rank() and groundset() methods. See the source of rank_matroid.py for a bare-bones example of this.
EXAMPLES:
In a partition matroid, a subset is independent if it has at most one element from each partition. The following is a very basic implementation, in which the partition is specified as a list of lists:
sage: class PartitionMatroid(sage.matroids.matroid.Matroid):
....: def __init__(self, partition):
....: self.partition = partition
....: E = set()
....: for P in partition:
....: E.update(P)
....: self.E = frozenset(E)
....: def groundset(self):
....: return self.E
....: def _rank(self, X):
....: X2 = set(X)
....: used_indices = set()
....: rk = 0
....: while len(X2) > 0:
....: e = X2.pop()
....: for i in range(len(self.partition)):
....: if e in self.partition[i]:
....: if i not in used_indices:
....: used_indices.add(i)
....: rk = rk + 1
....: break
....: return rk
....:
sage: M = PartitionMatroid([[1, 2], [3, 4, 5], [6, 7]])
sage: M.full_rank()
3
sage: M.tutte_polynomial(var('x'), var('y'))
x^2*y^2 + 2*x*y^3 + y^4 + x^3 + 3*x^2*y + 3*x*y^2 + y^3
Note
The abstract base class has no idea about the data used to represent the matroid. Hence some methods need to be customized to function properly.
Necessary:
Representation:
Comparison:
In Cythonized classes, use __richcmp__() instead of __eq__(), __ne__().
Copying, loading, saving:
See, for instance, rank_matroid.py or circuit_closures_matroid.pyx for sample implementations of these.
Note
Many methods (such as M.rank()) have a companion method whose name starts with an underscore (such as M._rank()). The method with the underscore does not do any checks on its input. For instance, it may assume of its input that
Using the underscored version could improve the speed of code a little, but will generate more cryptic error messages when presented with wrong input. In some instances, no error might occur and a nonsensical answer returned.
A subclass should always override the underscored method, if available, and as a rule leave the regular method alone.
Return a maximal subset of
such that
.
INPUT:
OUTPUT:
A subset of .
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.augment(['a'], ['e', 'f', 'g', 'h']))
['e', 'g', 'h']
sage: sorted(M.augment(['a']))
['b', 'c', 'e']
sage: sorted(M.augment(['x']))
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
sage: sorted(M.augment(['a'], ['x']))
Traceback (most recent call last):
...
ValueError: input Y is not a subset of the groundset.
Return the list of bases of the matroid.
A basis is a maximal independent set.
OUTPUT:
An iterable containing all bases of the matroid.
EXAMPLES:
sage: M = matroids.Uniform(2, 4)
sage: sorted([sorted(X) for X in M.bases()])
[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
ALGORITHM:
Test all subsets of the groundset of cardinality self.full_rank()
Return an arbitrary basis of the matroid.
A basis is an inclusionwise maximal independent set.
Note
The output of this method can change in between calls.
OUTPUT:
Set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus()
sage: B = M.basis()
sage: M.is_basis(B)
True
sage: len(B)
3
sage: M.rank(B)
3
sage: M.full_rank()
3
Return a circuit.
A circuit of a matroid is an inclusionwise minimal dependent subset.
INPUT:
OUTPUT:
Set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.circuit(['a', 'c', 'd', 'e', 'f']))
['c', 'd', 'e', 'f']
sage: sorted(M.circuit(['a', 'c', 'd']))
Traceback (most recent call last):
...
ValueError: no circuit in independent set.
sage: M.circuit(['x'])
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
sage: sorted(M.circuit())
['a', 'b', 'c', 'd']
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: M = 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']]
Return the list of circuits of the matroid.
OUTPUT:
An iterable containing all circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted([sorted(C) for C in M.circuits()])
[['a', 'b', 'c', 'g'], ['a', 'b', 'd', 'e'], ['a', 'b', 'f'],
['a', 'c', 'd', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'],
['a', 'e', 'f', 'g'], ['b', 'c', 'd'], ['b', 'c', 'e', 'f'],
['b', 'd', 'f', 'g'], ['b', 'e', 'g'], ['c', 'd', 'e', 'g'],
['c', 'f', 'g'], ['d', 'e', 'f']]
Return the closure of a set.
A set is closed if adding any extra element to it will increase the rank of the set. The closure of a set is the smallest closed set containing it.
INPUT:
OUTPUT:
Set of elements containing X.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.closure(set(['a', 'b', 'c'])))
['a', 'b', 'c', 'd']
sage: M.closure(['x'])
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Return an arbitrary cobasis of the matroid.
A cobasis is the complement of a basis. A cobasis is a basis of the dual matroid.
Note
Output can change between calls.
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Pappus()
sage: B = M.cobasis()
sage: M.is_cobasis(B)
True
sage: len(B)
6
sage: M.corank(B)
6
sage: M.full_corank()
6
Return a cocircuit.
A cocircuit is an inclusionwise minimal subset that is dependent in the dual matroid.
INPUT:
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.cocircuit(['a', 'c', 'd', 'e', 'f']))
['c', 'd', 'e', 'f']
sage: sorted(M.cocircuit(['a', 'c', 'd']))
Traceback (most recent call last):
...
ValueError: no cocircuit in coindependent set.
sage: M.cocircuit(['x'])
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
sage: sorted(M.cocircuit())
['e', 'f', 'g', 'h']
Return the list of cocircuits of the matroid.
OUTPUT:
An iterable containing all cocircuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted([sorted(C) for C in M.cocircuits()])
[['a', 'b', 'c', 'g'], ['a', 'b', 'd', 'e'], ['a', 'c', 'd', 'f'],
['a', 'e', 'f', 'g'], ['b', 'c', 'e', 'f'], ['b', 'd', 'f', 'g'],
['c', 'd', 'e', 'g']]
Return the coclosure of a set.
A set is coclosed if it is closed in the dual matroid. The
coclosure of is the smallest coclosed set containing
.
INPUT:
OUTPUT:
A set of elements containing X.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.coclosure(set(['a', 'b', 'c'])))
['a', 'b', 'c', 'd']
sage: M.coclosure(['x'])
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Return a coextension of the matroid.
A coextension of by an element
is a matroid
such that
. The element element is placed such that it
lies in the
coclosure of
each set in subsets, and otherwise as freely as possible.
This is the dual method of M.extension(). See the documentation there for more details.
INPUT:
OUTPUT:
A matroid.
See also
M.dual(), M.coextensions(), M.modular_cut(), M.extension(), M.linear_subclasses(), sage.matroids.extension
EXAMPLES:
Add an element in general position:
sage: M = matroids.Uniform(3, 6)
sage: N = M.coextension(6)
sage: N.is_isomorphic(matroids.Uniform(4, 7))
True
Add one inside the span of a specified hyperplane:
sage: M = matroids.Uniform(3, 6)
sage: H = [frozenset([0, 1])]
sage: N = M.coextension(6, H)
sage: N
Matroid of rank 4 on 7 elements with 34 bases
sage: [sorted(C) for C in N.cocircuits() if len(C) == 3]
[[0, 1, 6]]
Put an element in series with another:
sage: M = matroids.named_matroids.Fano()
sage: N = M.coextension('z', ['c'])
sage: N.corank('cz')
1
Return an iterable set of single-element coextensions of the matroid.
A coextension of a matroid by element
is a matroid
such
that
. By default, this method returns an iterable
containing all coextensions, but it can be restricted in two ways. If
coline_length is specified, the output is restricted to those
matroids not containing a coline minor of length
greater than
coline_length. If subsets is specified, then the output is
restricted to those matroids for which the new element lies in the
coclosure of each
member of subsets.
This method is dual to M.extensions().
INPUT:
OUTPUT:
An iterable containing matroids.
Note
The coextension by a coloop will always occur. The extension by a loop will never occur.
See also
M.coextension(), M.modular_cut(), M.linear_subclasses(), sage.matroids.extension, M.extensions(), M.dual()
EXAMPLES:
sage: M = matroids.named_matroids.P8()
sage: len(list(M.coextensions()))
1705
sage: len(list(M.coextensions(coline_length=4)))
41
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
sage: len(list(M.coextensions(subsets=[{'a', 'b'}], coline_length=4)))
5
Return the collection of coflats of the matroid of specified corank.
A coflat is a coclosed set.
INPUT:
OUTPUT:
An iterable containing all coflats of corank r.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Q6()
sage: sorted([sorted(F) for F in M.coflats(2)])
[['a', 'b'], ['a', 'c'], ['a', 'd', 'f'], ['a', 'e'], ['b', 'c'],
['b', 'd'], ['b', 'e'], ['b', 'f'], ['c', 'd'], ['c', 'e', 'f'],
['d', 'e']]
Return the set of coloops of the matroid.
A coloop is a one-element cocircuit. It is a loop of the dual of the matroid.
OUTPUT:
A set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual()
sage: M.coloops()
frozenset([])
sage: (M \ ['a', 'b']).coloops()
frozenset(['f'])
Return a list of the components of the matroid.
A component is an inclusionwise maximal connected subset of the matroid. A subset is connected if the matroid resulting from deleting the complement of that subset is connected.
OUTPUT:
A list of subsets.
See also
EXAMPLES:
sage: from sage.matroids.advanced import setprint
sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0],
....: [0, 1, 0, 1, 2, 0],
....: [0, 0, 1, 0, 0, 1]])
sage: setprint(M.components())
[{0, 1, 3, 4}, {2, 5}]
Contract elements.
If is a non-loop element, then the matroid
is a matroid
on groundset
. A set
is independent in
if and
only if
is independent in
. If
is a loop then
contracting
is the same as deleting
. We say that
is
the matroid obtained from
by contracting
. Contracting an
element in
is the same as deleting an element in the dual of
.
When contracting a set, the elements of that set are contracted one by one. It can be shown that the resulting matroid does not depend on the order of the contractions.
Sage supports the shortcut notation M / X for M.contract(X).
INPUT:
OUTPUT:
The matroid obtained by contracting the element(s) in X.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: M.contract(['a', 'c'])
Binary matroid of rank 1 on 5 elements, type (1, 0)
sage: M.contract(['a']) == M / ['a']
True
One can use a single element, rather than a set:
sage: M = matroids.CompleteGraphic(4)
sage: M.contract(1) == M.contract([1])
True
sage: M / 1
Regular matroid of rank 2 on 5 elements with 8 bases
Note that one can iterate over strings:
sage: M = matroids.named_matroids.Fano()
sage: M / 'abc'
Binary matroid of rank 0 on 4 elements, type (0, 0)
The following is therefore ambiguous. Sage will contract the single element:
sage: M = Matroid(groundset=['a', 'b', 'c', 'abc'],
....: bases=[['a', 'b', 'c'], ['a', 'b', 'abc']])
sage: sorted((M / 'abc').groundset())
['a', 'b', 'c']
Return the corank of X, or the corank of the groundset if X is None.
The corank of a set is the rank of
in the dual matroid.
If X is None, the corank of the groundset is returned.
INPUT:
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.corank()
4
sage: M.corank('cdeg')
3
sage: M.rank(['a', 'b', 'x'])
Traceback (most recent call last):
...
ValueError: input is not a subset of the groundset.
Return the cosimplification of the matroid.
A matroid is cosimple if it contains no cocircuits of length 1 or 2. The cosimplification of a matroid is obtained by contracting all coloops (cocircuits of length 1) and contracting all but one element from each series class (a coclosed set of rank 1, that is, each pair in it forms a cocircuit of length 2).
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual().delete('a')
sage: M.cosimplify().size()
3
Delete elements.
If is an element, then the matroid
is a matroid
on groundset
. A set
is independent in
if and only if
is independent in
. We say that
is the matroid obtained from
by deleting
.
When deleting a set, the elements of that set are deleted one by one. It can be shown that the resulting matroid does not depend on the order of the deletions.
Sage supports the shortcut notation M \ X for M.delete(X).
INPUT:
OUTPUT:
The matroid obtained by deleting the element(s) in X.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: M.delete(['a', 'c'])
Binary matroid of rank 3 on 5 elements, type (1, 6)
sage: M.delete(['a']) == M \ ['a']
True
One can use a single element, rather than a set:
sage: M = matroids.CompleteGraphic(4)
sage: M.delete(1) == M.delete([1])
True
sage: M \ 1
Regular matroid of rank 3 on 5 elements with 8 bases
Note that one can iterate over strings:
sage: M = matroids.named_matroids.Fano()
sage: M \ 'abc'
Binary matroid of rank 3 on 4 elements, type (0, 5)
The following is therefore ambiguous. Sage will delete the single element:
sage: M = Matroid(groundset=['a', 'b', 'c', 'abc'],
....: bases=[['a', 'b', 'c'], ['a', 'b', 'abc']])
sage: sorted((M \ 'abc').groundset())
['a', 'b', 'c']
Return the list of dependent subsets of fixed size.
INPUT:
OUTPUT:
An iterable containing all dependent subsets of size r.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.dependent_r_sets(3)
[]
sage: sorted([sorted(X) for X in
....: matroids.named_matroids.Vamos().dependent_r_sets(4)])
[['a', 'b', 'c', 'd'], ['a', 'b', 'e', 'f'], ['a', 'b', 'g', 'h'],
['c', 'd', 'e', 'f'], ['e', 'f', 'g', 'h']]
ALGORITHM:
Test all subsets of the groundset of cardinality r
Return the dual of the matroid.
Let be a matroid with ground set
. If
is the set of bases
of
, then the set
is the set of bases of
another matroid, the dual of
.
Note
This function wraps self in a DualMatroid object. For more efficiency, subclasses that can, should override this method.
OUTPUT:
The dual matroid.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus()
sage: N = M.dual()
sage: N.rank()
6
sage: N
Dual of 'Pappus: Matroid of rank 3 on 9 elements with
circuit-closures
{2: {{'a', 'b', 'c'}, {'a', 'f', 'h'}, {'c', 'e', 'g'},
{'b', 'f', 'g'}, {'c', 'd', 'h'}, {'d', 'e', 'f'},
{'a', 'e', 'i'}, {'b', 'd', 'i'}, {'g', 'h', 'i'}},
3: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'}}}'
Test for matroid equality.
Two matroids and
are equal if they have the same groundset
and a subset
is independent in
if and only if it is
independent in
.
INPUT:
OUTPUT:
Boolean.
Note
This method tests abstract matroid equality. The == operator takes a more restricted view: M == N returns True only if
EXAMPLES:
A BinaryMatroid and BasisMatroid use different representations of the matroid internally, so == yields False, even if the matroids are equal:
sage: from sage.matroids.advanced import *
sage: M = matroids.named_matroids.Fano()
sage: M
Fano: Binary matroid of rank 3 on 7 elements, type (3, 0)
sage: M1 = BasisMatroid(M)
sage: M2 = Matroid(groundset='abcdefg', reduced_matrix=[
....: [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1]], field=GF(2))
sage: M.equals(M1)
True
sage: M.equals(M2)
True
sage: M == M1
False
sage: M == M2
True
LinearMatroid instances M and N satisfy M == N if the representations are equivalent up to row operations and column scaling:
sage: M1 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7),
....: [[1, 0, 1, 1], [0, 1, 1, 2]]))
sage: M2 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7),
....: [[1, 0, 1, 1], [0, 1, 1, 3]]))
sage: M3 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7),
....: [[2, 6, 1, 0], [6, 1, 0, 1]]))
sage: M1.equals(M2)
True
sage: M1.equals(M3)
True
sage: M1 == M2
False
sage: M1 == M3
True
Return an extension of the matroid.
An extension of by an element
is a matroid
such that
. The element element is placed such that it
lies in the closure of
each set in subsets, and otherwise as freely as possible. More
precisely, the extension is defined by the
modular cut
generated by the sets in subsets.
INPUT:
OUTPUT:
A matroid.
Note
Internally, sage uses the notion of a linear subclass for matroid extension. If subsets already consists of a linear subclass (i.e. the set of hyperplanes of a modular cut) then the faster method M._extension() can be used.
See also
M.extensions(), M.modular_cut(), M.coextension(), M.linear_subclasses(), sage.matroids.extension
EXAMPLES:
First we add an element in general position:
sage: M = matroids.Uniform(3, 6)
sage: N = M.extension(6)
sage: N.is_isomorphic(matroids.Uniform(3, 7))
True
Next we add one inside the span of a specified hyperplane:
sage: M = matroids.Uniform(3, 6)
sage: H = [frozenset([0, 1])]
sage: N = M.extension(6, H)
sage: N
Matroid of rank 3 on 7 elements with 34 bases
sage: [sorted(C) for C in N.circuits() if len(C) == 3]
[[0, 1, 6]]
Putting an element in parallel with another:
sage: M = matroids.named_matroids.Fano()
sage: N = M.extension('z', ['c'])
sage: N.rank('cz')
1
Return an iterable set of single-element extensions of the matroid.
An extension of a matroid by element
is a matroid
such
that
. By default, this method returns an iterable
containing all extensions, but it can be restricted in two ways. If
line_length is specified, the output is restricted to those
matroids not containing a line minor of length
greater than
line_length. If subsets is specified, then the output is
restricted to those matroids for which the new element lies in the
closure of each
member of subsets.
INPUT:
OUTPUT:
An iterable containing matroids.
Note
The extension by a loop will always occur. The extension by a coloop will never occur.
See also
M.extension(), M.modular_cut(), M.linear_subclasses(), sage.matroids.extension, M.coextensions()
EXAMPLES:
sage: M = matroids.named_matroids.P8()
sage: len(list(M.extensions()))
1705
sage: len(list(M.extensions(line_length=4)))
41
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
sage: len(list(M.extensions(subsets=[{'a', 'b'}], line_length=4)))
5
Return the -vector of the matroid.
The -vector is a vector
, where
is the
number of flats of rank
, and
is the rank of the matroid.
OUTPUT:
List of integers.
EXAMPLES:
sage: M = matroids.named_matroids.BetsyRoss()
sage: M.f_vector()
[1, 11, 20, 1]
Return a minimum-size cover of the nonbases by non-spanning flats.
A nonbasis is a subset that has the size of a basis, yet is dependent. A flat is a closed set.
See also
EXAMPLES:
sage: from sage.matroids.advanced import setprint
sage: M = matroids.named_matroids.Fano()
sage: setprint(M.flat_cover())
[{'a', 'b', 'f'}, {'a', 'c', 'e'}, {'a', 'd', 'g'},
{'b', 'c', 'd'}, {'b', 'e', 'g'}, {'c', 'f', 'g'},
{'d', 'e', 'f'}]
Return the collection of flats of the matroid of specified rank.
A flat is a closed set.
INPUT:
OUTPUT:
An iterable containing all flats of rank r.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted([sorted(F) for F in M.flats(2)])
[['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'],
['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'],
['d', 'e', 'f']]
Return the corank of the matroid.
The corank of the matroid equals the rank of the dual matroid. It is given by M.size() - M.full_rank().
OUTPUT:
Integer.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.full_corank()
4
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
Return the -fundamental circuit using
.
If is a basis, and
an element not in
, then the
-fundamental circuit using
is the unique matroid circuit
contained in
.
INPUT:
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.fundamental_circuit('defg', 'c'))
['c', 'd', 'e', 'f']
Return the -fundamental cocircuit using
.
If is a basis, and
an element of
, then the
-fundamental cocircuit using
is the unique matroid cocircuit
that intersects
only in
.
This is equal to M.dual().fundamental_circuit(M.groundset().difference(B), e).
INPUT:
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.fundamental_cocircuit('abch', 'c'))
['c', 'd', 'e', 'f']
Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
Note
Subclasses should implement this method. The return type should be frozenset or any type with compatible interface.
EXAMPLES:
sage: M = sage.matroids.matroid.Matroid()
sage: M.groundset()
Traceback (most recent call last):
...
NotImplementedError: subclasses need to implement this.
Test if the matroid has a -minor.
The matroid is a matroid on
elements in which every
subset of at most 2 elements is independent, and every subset of more
than two elements is dependent.
The optional argument hyperlines restricts the search space: this
method returns False if is isomorphic to
with
for some
in hyperlines, and True otherwise.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: M.has_line_minor(4)
True
sage: M.has_line_minor(5)
False
sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c']])
False
sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'],
....: ['a', 'b', 'd' ]])
True
Check if self has a minor isomorphic to N.
INPUT:
OUTPUT:
Boolean.
See also
Todo
This important method can (and should) be optimized considerably. See [Hlineny] p.1219 for hints to that end.
EXAMPLES:
sage: M = matroids.Whirl(3)
sage: matroids.named_matroids.Fano().has_minor(M)
False
sage: matroids.named_matroids.NonFano().has_minor(M)
True
Return the set of hyperplanes of the matroid.
A hyperplane is a flat of rank self.full_rank() - 1. A flat is a closed set.
OUTPUT:
An iterable containing all hyperplanes of the matroid.
See also
EXAMPLES:
sage: M = matroids.Uniform(2, 3)
sage: sorted([sorted(F) for F in M.hyperplanes()])
[[0], [1], [2]]
Return the list of size-r independent subsets of the matroid.
INPUT:
OUTPUT:
An iterable containing all independent subsets of the matroid of cardinality r.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus()
sage: M.independent_r_sets(4)
[]
sage: sorted(sorted(M.independent_r_sets(3))[0])
['a', 'c', 'e']
ALGORITHM:
Test all subsets of the groundset of cardinality r
Return a maximum-weight common independent set.
A common independent set of matroids and
with the same
groundset
is a subset of
that is independent both in
and
. The weight of a subset S is sum(weights(e) for e in S).
INPUT:
OUTPUT:
A subset of the groundset.
EXAMPLES:
sage: M = matroids.named_matroids.T12()
sage: N = matroids.named_matroids.ExtendedTernaryGolayCode()
sage: w = {'a':30, 'b':10, 'c':11, 'd':20, 'e':70, 'f':21, 'g':90,
....: 'h':12, 'i':80, 'j':13, 'k':40, 'l':21}
sage: Y = M.intersection(N, w)
sage: sorted(Y)
['a', 'd', 'e', 'g', 'i', 'k']
sage: sum([w[y] for y in Y])
330
sage: M = matroids.named_matroids.Fano()
sage: N = matroids.Uniform(4, 7)
sage: M.intersection(N)
Traceback (most recent call last):
...
ValueError: matroid intersection requires equal groundsets.
Test if the matroid is 3-connected.
A -separation in a matroid is a partition
of the
groundset with
and
.
A matroid is
-connected if it has no
-separations for
.
OUTPUT:
Boolean.
Todo
Implement this using the efficient algorithm from [BC79].
See also
EXAMPLES:
sage: matroids.Uniform(2, 3).is_3connected()
True
sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0],
....: [0, 1, 0, 1, 2, 0],
....: [0, 0, 1, 0, 0, 1]])
sage: M.is_3connected()
False
sage: N = Matroid(circuit_closures={2: ['abc', 'cdef'],
....: 3: ['abcdef']},
....: groundset='abcdef')
sage: N.is_3connected()
False
sage: matroids.named_matroids.BetsyRoss().is_3connected()
True
ALGORITHM:
Test all subsets to see if
does not equal
.
Check if a subset is a basis of the matroid.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_basis('abc')
False
sage: M.is_basis('abce')
True
sage: M.is_basis('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test if a subset is a circuit of the matroid.
A circuit is an inclusionwise minimal dependent subset.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_circuit('abc')
False
sage: M.is_circuit('abcd')
True
sage: M.is_circuit('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test if a subset is a closed set of the matroid.
A set is closed if adding any element to it will increase the rank of the set.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_closed('abc')
False
sage: M.is_closed('abcd')
True
sage: M.is_closed('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Check if a subset is a cobasis of the matroid.
A cobasis is the complement of a basis. It is a basis of the dual matroid.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_cobasis('abc')
False
sage: M.is_cobasis('abce')
True
sage: M.is_cobasis('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test if a subset is a cocircuit of the matroid.
A cocircuit is an inclusionwise minimal subset that is dependent in the dual matroid.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_cocircuit('abc')
False
sage: M.is_cocircuit('abcd')
True
sage: M.is_cocircuit('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test if a subset is a coclosed set of the matroid.
A set is coclosed if it is a closed set of the dual matroid.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_coclosed('abc')
False
sage: M.is_coclosed('abcd')
True
sage: M.is_coclosed('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Check if a subset is codependent in the matroid.
A set is codependent if it is dependent in the dual of the matroid.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_codependent('abc')
False
sage: M.is_codependent('abcd')
True
sage: M.is_codependent('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Check if a subset is coindependent in the matroid.
A set is coindependent if it is independent in the dual matroid.
INPUT:
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_coindependent('abc')
True
sage: M.is_coindependent('abcd')
False
sage: M.is_coindependent('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test if the matroid is connected.
A separation in a matroid is a partition of the
groundset with
nonempty and
.
A matroid is connected if it has no separations.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0],
....: [0, 1, 0, 1, 2, 0],
....: [0, 0, 1, 0, 0, 1]])
sage: M.is_connected()
False
sage: matroids.named_matroids.Pappus().is_connected()
True
Test if the matroid is cosimple.
A matroid is cosimple if it contains no cocircuits of length 1 or 2.
Dual method of M.is_simple().
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual()
sage: M.is_cosimple()
True
sage: N = M \ 'a'
sage: N.is_cosimple()
False
Check if a subset is dependent in the matroid.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_dependent('abc')
False
sage: M.is_dependent('abcd')
True
sage: M.is_dependent('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Check if a subset is independent in the matroid.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_independent('abc')
True
sage: M.is_independent('abcd')
False
sage: M.is_independent('abcx')
Traceback (most recent call last):
...
ValueError: input X is not a subset of the groundset.
Test matroid isomorphism.
Two matroids and
are isomorphic if there is a bijection
from the groundset of
to the groundset of
such that a subset
is independent in
if and only if
is independent in
.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: M1 = matroids.Wheel(3)
sage: M2 = matroids.CompleteGraphic(4)
sage: M1.is_isomorphic(M2)
True
sage: G3 = graphs.CompleteGraph(4)
sage: M1.is_isomorphic(G3)
Traceback (most recent call last):
...
TypeError: can only test for isomorphism between matroids.
sage: M1 = matroids.named_matroids.Fano()
sage: M2 = matroids.named_matroids.NonFano()
sage: M1.is_isomorphic(M2)
False
Test if a provided morphism induces a matroid isomorphism.
A morphism is a map from the groundset of self to the groundset of other.
INPUT:
OUTPUT:
Boolean.
..SEEALSO:
:meth:`M.is_isomorphism() <sage.matroids.matroid.Matroid.is_isomorphism>`
Note
If you know the input is valid, consider using the faster method self._is_isomorphism.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus()
sage: N = matroids.named_matroids.NonPappus()
sage: N.is_isomorphism(M, {e:e for e in M.groundset()})
False
sage: M = matroids.named_matroids.Fano() \ ['g']
sage: N = matroids.Wheel(3)
sage: morphism = {'a':0, 'b':1, 'c': 2, 'd':4, 'e':5, 'f':3}
sage: M.is_isomorphism(N, morphism)
True
A morphism can be specified as a dictionary (above), a permutation, a function, and many other types of maps:
sage: M = matroids.named_matroids.Fano()
sage: P = PermutationGroup([[('a', 'b', 'c'),
....: ('d', 'e', 'f'), ('g')]]).gen()
sage: M.is_isomorphism(M, P)
True
sage: M = matroids.named_matroids.Pappus()
sage: N = matroids.named_matroids.NonPappus()
sage: def f(x):
....: return x
....:
sage: N.is_isomorphism(M, f)
False
sage: N.is_isomorphism(N, f)
True
There is extensive checking for inappropriate input:
sage: M = matroids.CompleteGraphic(4)
sage: M.is_isomorphism(graphs.CompleteGraph(4), lambda x:x)
Traceback (most recent call last):
...
TypeError: can only test for isomorphism between matroids.
sage: M = matroids.CompleteGraphic(4)
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5]
sage: M.is_isomorphism(M, {0: 1, 1: 2, 2: 3})
Traceback (most recent call last):
...
ValueError: domain of morphism does not contain groundset of this
matroid.
sage: M = matroids.CompleteGraphic(4)
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5]
sage: M.is_isomorphism(M, {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
Traceback (most recent call last):
...
ValueError: range of morphism does not contain groundset of other
matroid.
sage: M = matroids.CompleteGraphic(3)
sage: N = Matroid(bases=['ab', 'ac', 'bc'])
sage: f = [0, 1, 2]
sage: g = {'a': 0, 'b': 1, 'c': 2}
sage: N.is_isomorphism(M, f)
Traceback (most recent call last):
...
ValueError: the morphism argument does not seem to be an
isomorphism.
sage: N.is_isomorphism(M, g)
True
Test if the matroid is simple.
A matroid is simple if it contains no circuits of length 1 or 2.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.is_simple()
True
sage: N = M / 'a'
sage: N.is_simple()
False
Test if the data obey the matroid axioms.
The default implementation checks the (disproportionately slow) rank
axioms. If is the rank function of a matroid, we check, for all
pairs
of subsets,
Certain subclasses may check other axioms instead.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.is_valid()
True
The following is the ‘Escher matroid’ by Brylawski and Kelly. See Example 1.5.5 in [Oxley]
sage: M = Matroid(circuit_closures={2: [[1, 2, 3], [1, 4, 5]],
....: 3: [[1, 2, 3, 4, 5], [1, 2, 3, 6, 7], [1, 4, 5, 6, 7]]})
sage: M.is_valid()
False
Return an iterable set of linear subclasses of the matroid.
A linear subclass is a set of hyperplanes (i.e. closed sets of rank
) with the following property:
A linear subclass is the set of hyperplanes of a modular cut and uniquely determines the modular cut. Hence the collection of linear subclasses is in 1-to-1 correspondence with the collection of single-element extensions of a matroid. See [Oxley], section 7.2.
INPUT:
OUTPUT:
An iterable collection of linear subclasses.
Note
The line_length argument only checks for lines using the new element of the corresponding extension. It is still possible that a long line exists by contracting the new element!
See also
M.flats(), M.modular_cut(), M.extension(), sage.matroids.extension
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: len(list(M.linear_subclasses()))
16
sage: len(list(M.linear_subclasses(line_length=3)))
8
sage: len(list(M.linear_subclasses(subsets=[{'a', 'b'}])))
5
The following matroid has an extension by element such that
contracting
creates a 6-point line, but no 6-point line minor uses
. Consequently, this method returns the modular cut, but the
M.extensions()
method doesn’t return the corresponding extension:
sage: M = Matroid(circuit_closures={2: ['abc', 'def'],
....: 3: ['abcdef']})
sage: len(list(M.extensions('g', line_length=5)))
43
sage: len(list(M.linear_subclasses(line_length=5)))
44
Return the set of loops of the matroid.
A loop is a one-element dependent set.
OUTPUT:
A set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.loops()
frozenset([])
sage: (M / ['a', 'b']).loops()
frozenset(['f'])
Compute a maximal coindependent subset.
A set is coindependent if it is independent in the dual matroid. A set is coindependent if and only if the complement is spanning (i.e. contains a basis of the matroid).
INPUT:
OUTPUT:
A subset of X.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.max_coindependent(['a', 'c', 'd', 'e', 'f']))
['a', 'c', 'd', 'e']
sage: M.max_coindependent(['x'])
Traceback (most recent call last):
...
ValueError: input is not a subset of the groundset.
Compute a maximal independent subset of X.
INPUT:
OUTPUT:
Subset of X.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: sorted(M.max_independent(['a', 'c', 'd', 'e', 'f']))
['a', 'd', 'e', 'f']
sage: M.max_independent(['x'])
Traceback (most recent call last):
...
ValueError: input is not a subset of the groundset.
Return a maximum-weight coindependent set contained in X.
The weight of a subset S is sum(weights(e) for e in S).
INPUT:
OUTPUT:
A subset of X.
ALGORITHM:
The greedy algorithm. Sort the elements of X by decreasing weight, then greedily select elements if they are coindependent of all that was selected before.
EXAMPLES:
sage: from sage.matroids.advanced import setprint
sage: M = matroids.named_matroids.Fano()
sage: X = M.max_weight_coindependent()
sage: M.is_cobasis(X)
True
sage: wt = {'a': 1, 'b': 2, 'c': 2, 'd': 1/2, 'e': 1, 'f': 2,
....: 'g': 2}
sage: setprint(M.max_weight_coindependent(weights=wt))
{'b', 'c', 'f', 'g'}
sage: def wt(x):
....: return x
....:
sage: M = matroids.Uniform(2, 8)
sage: setprint(M.max_weight_coindependent(weights=wt))
{2, 3, 4, 5, 6, 7}
sage: setprint(M.max_weight_coindependent())
{0, 1, 2, 3, 4, 5}
sage: M.max_weight_coindependent(X=[], weights={})
frozenset([])
Return a maximum-weight independent set contained in a subset.
The weight of a subset S is sum(weights(e) for e in S).
INPUT:
OUTPUT:
A subset of X.
ALGORITHM:
The greedy algorithm. Sort the elements of X by decreasing weight, then greedily select elements if they are independent of all that was selected before.
EXAMPLES:
sage: from sage.matroids.advanced import setprint
sage: M = matroids.named_matroids.Fano()
sage: X = M.max_weight_independent()
sage: M.is_basis(X)
True
sage: wt = {'a': 1, 'b': 2, 'c': 2, 'd': 1/2, 'e': 1,
....: 'f': 2, 'g': 2}
sage: setprint(M.max_weight_independent(weights=wt))
{'b', 'f', 'g'}
sage: def wt(x):
....: return x
....:
sage: M = matroids.Uniform(2, 8)
sage: setprint(M.max_weight_independent(weights=wt))
{6, 7}
sage: setprint(M.max_weight_independent())
{0, 1}
sage: M.max_weight_coindependent(X=[], weights={})
frozenset([])
Return the minor of self obtained by contracting, respectively deleting, the element(s) of contractions and deletions.
A minor of a matroid is a matroid obtained by repeatedly removing elements in one of two ways: either contract or delete them. It can be shown that the final matroid does not depend on the order in which elements are removed.
INPUT:
OUTPUT:
A matroid.
Note
The output is either of the same type as self, or an instance of MinorMatroid.
See also
EXAMPLES:
sage: M = matroids.Wheel(4)
sage: N = M.minor(contractions=[7], deletions=[0])
sage: N.is_isomorphic(matroids.Wheel(3))
True
The sets of contractions and deletions need not be independent, respectively coindependent:
sage: M = matroids.named_matroids.Fano()
sage: M.rank('abf')
2
sage: M.minor(contractions='abf')
Binary matroid of rank 1 on 4 elements, type (1, 0)
However, they need to be subsets of the groundset, and disjoint:
sage: M = matroids.named_matroids.Vamos()
sage: M.minor('abc', 'defg')
M / {'a', 'b', 'c'} \ {'d', 'e', 'f', 'g'}, where M is Vamos:
Matroid of rank 4 on 8 elements with circuit-closures
{3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'},
{'e', 'f', 'g', 'h'}, {'a', 'b', 'g', 'h'}, {'c', 'd', 'e', 'f'}},
4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}}
sage: M.minor('defgh', 'abc')
M / {'d', 'e', 'f', 'g'} \ {'a', 'b', 'c', 'h'}, where M is Vamos:
Matroid of rank 4 on 8 elements with circuit-closures
{3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'},
{'e', 'f', 'g', 'h'}, {'a', 'b', 'g', 'h'}, {'c', 'd', 'e', 'f'}},
4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}}
sage: M.minor([1, 2, 3], 'efg')
Traceback (most recent call last):
...
ValueError: input contractions is not a subset of the groundset.
sage: M.minor('efg', [1, 2, 3])
Traceback (most recent call last):
...
ValueError: input deletions is not a subset of the groundset.
sage: M.minor('ade', 'efg')
Traceback (most recent call last):
...
ValueError: contraction and deletion sets are not disjoint.
Warning
There can be ambiguity if elements of the groundset are themselves iterable, and their elements are in the groundset. The main example of this is when an element is a string. See the documentation of the methods contract() and delete() for an example of this.
Compute the modular cut generated by subsets.
A modular cut is a collection of flats such that
A flat is a closed set, a modular pair is a pair of
flats with
,
where
is the rank function of the matroid.
The modular cut generated by subsets is the smallest modular cut
for which closure`(S) in C` for all
in subsets.
There is a one-to-one correspondence between the modular cuts of a matroid and the single-element extensions of the matroid. See [Oxley] Section 7.2 for more information.
Note
Sage uses linear subclasses, rather than modular cuts, internally
for matroid extension. A linear subclass is the set of hyperplanes
(flats of rank ) of a modular cut. It determines the
modular cut uniquely (see [Oxley] Section 7.2).
INPUT:
OUTPUT:
A collection of subsets.
See also
EXAMPLES:
Any extension of the Vamos matroid where the new point is placed on
the lines through elements and through
is an
extension by a loop:
sage: M = matroids.named_matroids.Vamos()
sage: frozenset([]) in M.modular_cut(['ab', 'cd'])
True
In any extension of the matroid , a point on the
lines through
and
also is on the line through
:
sage: M = matroids.named_matroids.S8()
sage: N = M \ 'h'
sage: frozenset('bf') in N.modular_cut(['cg', 'ae'])
True
The modular cut of the full groundset is equal to just the groundset:
sage: M = matroids.named_matroids.Fano()
sage: M.modular_cut([M.groundset()]).difference(
....: [frozenset(M.groundset())])
set([])
Return the list of nonbases of the matroid.
A nonbasis is a set with cardinality self.full_rank() that is not a basis.
OUTPUT:
An iterable containing the nonbases of the matroid.
See also
EXAMPLES:
sage: M = matroids.Uniform(2, 4)
sage: list(M.nonbases())
[]
sage: [sorted(X) for X in matroids.named_matroids.P6().nonbases()]
[['a', 'b', 'c']]
ALGORITHM:
Test all subsets of the groundset of cardinality self.full_rank()
Return the list of noncospanning cocircuits of the matroid.
A noncospanning cocircuit is a cocircuit whose corank is strictly smaller than the corank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual()
sage: sorted([sorted(C) for C in M.noncospanning_cocircuits()])
[['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'],
['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'],
['d', 'e', 'f']]
Return the list of closures of nonspanning circuits of the matroid.
A nonspanning circuit closure is a closed set containing a nonspanning circuit.
OUTPUT:
A dictionary containing the nonspanning circuit closures of the matroid, indexed by their ranks.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: CC = M.nonspanning_circuit_closures()
sage: len(CC[2])
7
sage: len(CC[3])
Traceback (most recent call last):
...
KeyError: 3
Return the list of nonspanning circuits of the matroid.
A nonspanning circuit is a circuit whose rank is strictly smaller than the rank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted([sorted(C) for C in M.nonspanning_circuits()])
[['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'],
['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'],
['d', 'e', 'f']]
Return the rank of X.
The rank of a subset is the size of the largest independent set
contained in
.
If X is None, the rank of the groundset is returned.
INPUT:
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.rank()
3
sage: M.rank(['a', 'b', 'f'])
2
sage: M.rank(['a', 'b', 'x'])
Traceback (most recent call last):
...
ValueError: input is not a subset of the groundset.
Return the simplification of the matroid.
A matroid is simple if it contains no circuits of length 1 or 2. The simplification of a matroid is obtained by deleting all loops (circuits of length 1) and deleting all but one element from each parallel class (a closed set of rank 1, that is, each pair in it forms a circuit of length 2).
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().contract('a')
sage: M.size() - M.simplify().size()
3
Return the size of the groundset.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos()
sage: M.size()
8
Return a rank-1 truncation of the matroid.
Let be a matroid of rank
. The truncation of
is the
matroid obtained by declaring all subsets of size
dependent. It
can be obtained by adding an element freely to the span of the matroid
and then contracting that element.
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: N = M.truncation()
sage: N.is_isomorphic(matroids.Uniform(2, 7))
True
Return the Tutte polynomial of the matroid.
The Tutte polynomial of a matroid is the polynomial
where is the groundset of the matroid,
is the rank function,
and
is the corank function. Tutte defined his polynomial
differently:
where the sum ranges over all bases of the matroid, is the
number of internally active elements of
, and
is the number
of externally active elements of
.
INPUT:
OUTPUT:
The Tutte-polynomial , where
and
are substituted with
any values provided as input.
Todo
Make implementation more efficient, e.g. generalizing the approach from trac ticket #1314 from graphs to matroids.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.tutte_polynomial()
y^4 + x^3 + 3*y^3 + 4*x^2 + 7*x*y + 6*y^2 + 3*x + 3*y
sage: M.tutte_polynomial(1, 1) == M.bases_count()
True
ALGORITHM:
Enumerate the bases and compute the internal and external activities
for each .