Graphic Matroids#

Let \(G = (V,E)\) be a graph and let \(C\) be the collection of the edge sets of cycles in \(G\). The corresponding graphic matroid \(M(G)\) has groundset \(E\) and circuits \(C\).

Construction#

The recommended way to create a graphic matroid is by using the Matroid() function, with a graph \(G\) as input. This function can accept many different kinds of input to get a graphic matroid if the graph keyword is used, similar to the Graph() constructor. However, invoking the class directly is possible too. To get access to it, type:

sage: from sage.matroids.advanced import *

>>> from sage.all import *
>>> from sage.matroids.advanced import *

See also sage.matroids.advanced.

Graphic matroids do not have a representation matrix or any of the functionality of regular matroids. It is possible to get an instance of the RegularMatroid class by using the regular keyword when constructing the matroid. It is also possible to cast a GraphicMatroid as a RegularMatroid with the regular_matroid() method:

sage: M1 = Matroid(graphs.DiamondGraph(), regular=True)
sage: M2 = Matroid(graphs.DiamondGraph())
sage: M3 = M2.regular_matroid()

>>> from sage.all import *
>>> M1 = Matroid(graphs.DiamondGraph(), regular=True)
>>> M2 = Matroid(graphs.DiamondGraph())
>>> M3 = M2.regular_matroid()

Below are some examples of constructing a graphic matroid.

sage: from sage.matroids.advanced import *
sage: edgelist = [(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'c')]
sage: G = Graph(edgelist)
sage: M1 = Matroid(G)
sage: M2 = Matroid(graph=edgelist)
sage: M3 = Matroid(graphs.CycleGraph(3))
sage: M1 == M3
False
sage: M1.is_isomorphic(M3)
True
sage: M1.equals(M2)
True
sage: M1 == M2
True
sage: isinstance(M1, GraphicMatroid)
True
sage: isinstance(M1, RegularMatroid)
False

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> edgelist = [(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(1), Integer(2), 'c')]
>>> G = Graph(edgelist)
>>> M1 = Matroid(G)
>>> M2 = Matroid(graph=edgelist)
>>> M3 = Matroid(graphs.CycleGraph(Integer(3)))
>>> M1 == M3
False
>>> M1.is_isomorphic(M3)
True
>>> M1.equals(M2)
True
>>> M1 == M2
True
>>> isinstance(M1, GraphicMatroid)
True
>>> isinstance(M1, RegularMatroid)
False

Note that if there is not a complete set of unique edge labels, and there are no parallel edges, then vertex tuples will be used for the groundset. The user may wish to override this by specifying the groundset, as the vertex tuples will not be updated if the matroid is modified:

sage: G = graphs.DiamondGraph()
sage: M1 = Matroid(G)
sage: N1 = M1.contract((0,1))
sage: N1.graph().edges_incident(0, sort=True)
[(0, 2, (0, 2)), (0, 2, (1, 2)), (0, 3, (1, 3))]
sage: M2 = Matroid(range(G.num_edges()), G)
sage: N2 = M2.contract(0)
sage: N1.is_isomorphic(N2)
True

>>> from sage.all import *
>>> G = graphs.DiamondGraph()
>>> M1 = Matroid(G)
>>> N1 = M1.contract((Integer(0),Integer(1)))
>>> N1.graph().edges_incident(Integer(0), sort=True)
[(0, 2, (0, 2)), (0, 2, (1, 2)), (0, 3, (1, 3))]
>>> M2 = Matroid(range(G.num_edges()), G)
>>> N2 = M2.contract(Integer(0))
>>> N1.is_isomorphic(N2)
True

AUTHORS:

  • Zachary Gershkoff (2017-07-07): initial version

class sage.matroids.graphic_matroid.GraphicMatroid[source]#

Bases: Matroid

The graphic matroid class.

INPUT:

  • G – Graph

  • groundset – list (optional); in 1-1 correspondence with G.edge_iterator()

OUTPUT: GraphicMatroid where the groundset elements are the edges of \(G\)

Note

If a disconnected graph is given as input, the instance of GraphicMatroid will connect the graph components and store this as its graph.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = GraphicMatroid(graphs.BullGraph()); M
Graphic matroid of rank 4 on 5 elements
sage: N = GraphicMatroid(graphs.CompleteBipartiteGraph(3,3)); N
Graphic matroid of rank 5 on 9 elements

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = GraphicMatroid(graphs.BullGraph()); M
Graphic matroid of rank 4 on 5 elements
>>> N = GraphicMatroid(graphs.CompleteBipartiteGraph(Integer(3),Integer(3))); N
Graphic matroid of rank 5 on 9 elements

A disconnected input will get converted to a connected graph internally:

sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph()
sage: G = G1.disjoint_union(G2)
sage: len(G)
7
sage: G.is_connected()
False
sage: M = GraphicMatroid(G)
sage: M
Graphic matroid of rank 5 on 8 elements
sage: H = M.graph()
sage: H
Looped multi-graph on 6 vertices
sage: H.is_connected()
True
sage: M.is_connected()
False

>>> from sage.all import *
>>> G1 = graphs.CycleGraph(Integer(3)); G2 = graphs.DiamondGraph()
>>> G = G1.disjoint_union(G2)
>>> len(G)
7
>>> G.is_connected()
False
>>> M = GraphicMatroid(G)
>>> M
Graphic matroid of rank 5 on 8 elements
>>> H = M.graph()
>>> H
Looped multi-graph on 6 vertices
>>> H.is_connected()
True
>>> M.is_connected()
False

You can still locate an edge using the vertices of the input graph:

sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph()
sage: G = G1.disjoint_union(G2)
sage: M = Matroid(G)
sage: H = M.graph()
sage: vm = M.vertex_map()
sage: (u, v, l) = G.random_edge()
sage: H.has_edge(vm[u], vm[v])
True

>>> from sage.all import *
>>> G1 = graphs.CycleGraph(Integer(3)); G2 = graphs.DiamondGraph()
>>> G = G1.disjoint_union(G2)
>>> M = Matroid(G)
>>> H = M.graph()
>>> vm = M.vertex_map()
>>> (u, v, l) = G.random_edge()
>>> H.has_edge(vm[u], vm[v])
True
graph()[source]#

Return the graph that represents the matroid.

The graph will always have loops and multiedges enabled.

OUTPUT: graph

EXAMPLES:

sage: M = Matroid(Graph([(0, 1, 'a'), (0, 2, 'b'), (0, 3, 'c')]))
sage: M.graph().edges(sort=True)
[(0, 1, 'a'), (0, 2, 'b'), (0, 3, 'c')]
sage: M = Matroid(graphs.CompleteGraph(5))
sage: M.graph()
Looped multi-graph on 5 vertices

>>> from sage.all import *
>>> M = Matroid(Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(0), Integer(3), 'c')]))
>>> M.graph().edges(sort=True)
[(0, 1, 'a'), (0, 2, 'b'), (0, 3, 'c')]
>>> M = Matroid(graphs.CompleteGraph(Integer(5)))
>>> M.graph()
Looped multi-graph on 5 vertices
graphic_coextension(u, v=None, X=None, element=None)[source]#

Return a matroid coextended by a new element.

A coextension in a graphic matroid is the opposite of contracting an edge; that is, a vertex is split, and a new edge is added between the resulting vertices. This method will create a new vertex \(v\) adjacent to \(u\), and move the edges indicated by \(X\) from \(u\) to \(v\).

INPUT:

  • u – the vertex to be split

  • v – (optional) the name of the new vertex after splitting

  • X – (optional) a list of the matroid elements corresponding to edges incident to u that move to the new vertex after splitting

  • element – (optional) The name of the newly added element

OUTPUT:

An instance of GraphicMatroid coextended by the new element. If X is not specified, the new element will be a coloop.

Note

A loop on u will stay a loop unless it is in X.

EXAMPLES:

sage: G = Graph([(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 4, 3),
....:            (1, 2, 4), (1, 4, 5), (2, 3, 6), (3, 4, 7)])
sage: M = Matroid(G)
sage: M1 = M.graphic_coextension(0, X=[1,2], element='a')
sage: M1.graph().edges(sort=True)
[(0, 1, 0),
 (0, 4, 3),
 (0, 5, 'a'),
 (1, 2, 4),
 (1, 4, 5),
 (2, 3, 6),
 (2, 5, 1),
 (3, 4, 7),
 (3, 5, 2)]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(2), Integer(1)), (Integer(0), Integer(3), Integer(2)), (Integer(0), Integer(4), Integer(3)),
...            (Integer(1), Integer(2), Integer(4)), (Integer(1), Integer(4), Integer(5)), (Integer(2), Integer(3), Integer(6)), (Integer(3), Integer(4), Integer(7))])
>>> M = Matroid(G)
>>> M1 = M.graphic_coextension(Integer(0), X=[Integer(1),Integer(2)], element='a')
>>> M1.graph().edges(sort=True)
[(0, 1, 0),
 (0, 4, 3),
 (0, 5, 'a'),
 (1, 2, 4),
 (1, 4, 5),
 (2, 3, 6),
 (2, 5, 1),
 (3, 4, 7),
 (3, 5, 2)]
graphic_coextensions(vertices=None, v=None, element=None, cosimple=False)[source]#

Return an iterator of graphic coextensions.

This method iterates over the vertices in the input. If cosimple == False, it first coextends by a coloop and series edge for every edge incident with the vertices. For vertices of degree four or higher, it will consider the ways to partition the vertex into two sets of cardinality at least two, and these will be the edges incident with the vertices after splitting.

At most one series coextension will be taken for each series class.

INPUT:

  • vertices – (optional) the vertices to be split

  • v – (optional) the name of the new vertex

  • element – (optional) the name of the new element

  • cosimple – (default: False) if true, coextensions by a coloop or series elements will not be taken

OUTPUT:

An iterable containing instances of GraphicMatroid. If vertices is not specified, the method iterates over all vertices.

EXAMPLES:

sage: G = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 4), (2, 3), (3, 4)])
sage: M = Matroid(range(8), G)
sage: I = M.graphic_coextensions(vertices=[0], element='a')
sage: sorted([N.graph().edges_incident(0, sort=True) for N in I], key=str)
[[(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 5, 'a')],
 [(0, 1, 0), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 3, 2), (0, 5, 'a')],
 [(0, 2, 1), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 2, 1), (0, 3, 2), (0, 5, 'a')]]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)), (Integer(1), Integer(4)), (Integer(2), Integer(3)), (Integer(3), Integer(4))])
>>> M = Matroid(range(Integer(8)), G)
>>> I = M.graphic_coextensions(vertices=[Integer(0)], element='a')
>>> sorted([N.graph().edges_incident(Integer(0), sort=True) for N in I], key=str)
[[(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 3, 2), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 2, 1), (0, 5, 'a')],
 [(0, 1, 0), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 1, 0), (0, 3, 2), (0, 5, 'a')],
 [(0, 2, 1), (0, 3, 2), (0, 4, 3), (0, 5, 'a')],
 [(0, 2, 1), (0, 3, 2), (0, 5, 'a')]]

sage: N = Matroid(range(4), graphs.CycleGraph(4))
sage: I = N.graphic_coextensions(element='a')
sage: for N1 in I:  # random
....:     N1.graph().edges(sort=True)
[(0, 1, 0), (0, 3, 1), (0, 4, 'a'), (1, 2, 2), (2, 3, 3)]
[(0, 1, 0), (0, 3, 1), (1, 4, 2), (2, 3, 3), (2, 4, 'a')]
sage: sum(1 for n in N.graphic_coextensions(cosimple=True))
0

>>> from sage.all import *
>>> N = Matroid(range(Integer(4)), graphs.CycleGraph(Integer(4)))
>>> I = N.graphic_coextensions(element='a')
>>> for N1 in I:  # random
...     N1.graph().edges(sort=True)
[(0, 1, 0), (0, 3, 1), (0, 4, 'a'), (1, 2, 2), (2, 3, 3)]
[(0, 1, 0), (0, 3, 1), (1, 4, 2), (2, 3, 3), (2, 4, 'a')]
>>> sum(Integer(1) for n in N.graphic_coextensions(cosimple=True))
0
graphic_extension(u, v=None, element=None)[source]#

Return a graphic matroid extended by a new element.

A new edge will be added between u and v. If v is not specified, then a loop is added on u.

INPUT:

  • u – vertex in the matroid’s graph

  • v – (optional) another vertex

  • element – (optional) the label of the new element

OUTPUT:

A GraphicMatroid with the specified element added. Note that if v is not specified or if v is u, then the new element will be a loop. If the new element’s label is not specified, it will be generated automatically.

EXAMPLES:

sage: M = matroids.CompleteGraphic(4)
sage: M1 = M.graphic_extension(0,1,'a'); M1
Graphic matroid of rank 3 on 7 elements
sage: list(M1.graph().edge_iterator())
[(0, 1, 'a'), (0, 1, 0), (0, 2, 1), (0, 3, 2), (1, 2, 3), (1, 3, 4), (2, 3, 5)]
sage: M2 = M1.graphic_extension(3); M2
Graphic matroid of rank 3 on 8 elements

>>> from sage.all import *
>>> M = matroids.CompleteGraphic(Integer(4))
>>> M1 = M.graphic_extension(Integer(0),Integer(1),'a'); M1
Graphic matroid of rank 3 on 7 elements
>>> list(M1.graph().edge_iterator())
[(0, 1, 'a'), (0, 1, 0), (0, 2, 1), (0, 3, 2), (1, 2, 3), (1, 3, 4), (2, 3, 5)]
>>> M2 = M1.graphic_extension(Integer(3)); M2
Graphic matroid of rank 3 on 8 elements

sage: M = Matroid(range(10), graphs.PetersenGraph())
sage: sorted(M.graphic_extension(0, 'b', 'c').graph().vertex_iterator(), key=str)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'b']
sage: M.graphic_extension('a', 'b', 'c').graph().vertices(sort=False)
Traceback (most recent call last):
...
ValueError: u must be an existing vertex

>>> from sage.all import *
>>> M = Matroid(range(Integer(10)), graphs.PetersenGraph())
>>> sorted(M.graphic_extension(Integer(0), 'b', 'c').graph().vertex_iterator(), key=str)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'b']
>>> M.graphic_extension('a', 'b', 'c').graph().vertices(sort=False)
Traceback (most recent call last):
...
ValueError: u must be an existing vertex
graphic_extensions(element=None, vertices=None, simple=False)[source]#

Return an iterable containing the graphic extensions.

This method iterates over the vertices in the input. If simple == False, it first extends by a loop. It will then add an edge between every pair of vertices in the input, skipping pairs of vertices with an edge already between them if simple == True.

This method only considers the current graph presentation, and does not take 2-isomorphism into account. Use twist or one_sum if you wish to change the graph presentation.

INPUT:

  • element – (optional) the name of the newly added element in each extension

  • vertices – (optional) a set of vertices over which the extension may be taken

  • simple – (default: False) if true, extensions by loops and parallel elements are not taken

OUTPUT:

An iterable containing instances of GraphicMatroid. If vertices is not specified, every vertex is used.

Note

The extension by a loop will always occur unless simple == True. The extension by a coloop will never occur.

EXAMPLES:

sage: M = Matroid(range(5), graphs.DiamondGraph())
sage: I = M.graphic_extensions('a')
sage: for N in I:
....:     list(N.graph().edge_iterator())
[(0, 0, 'a'), (0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 'a'), (0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 'a'), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (0, 3, 'a'), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 'a'), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 'a'), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 'a'), (2, 3, 4)]

>>> from sage.all import *
>>> M = Matroid(range(Integer(5)), graphs.DiamondGraph())
>>> I = M.graphic_extensions('a')
>>> for N in I:
...     list(N.graph().edge_iterator())
[(0, 0, 'a'), (0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 'a'), (0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 'a'), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (0, 3, 'a'), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 'a'), (1, 2, 2), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 'a'), (1, 3, 3), (2, 3, 4)]
[(0, 1, 0), (0, 2, 1), (1, 2, 2), (1, 3, 3), (2, 3, 'a'), (2, 3, 4)]

sage: M = Matroid(graphs.CompleteBipartiteGraph(3,3))
sage: I = M.graphic_extensions(simple=True)
sage: sum (1 for i in I)
6
sage: I = M.graphic_extensions(vertices=[0,1,2])
sage: sum (1 for i in I)
4

>>> from sage.all import *
>>> M = Matroid(graphs.CompleteBipartiteGraph(Integer(3),Integer(3)))
>>> I = M.graphic_extensions(simple=True)
>>> sum (Integer(1) for i in I)
6
>>> I = M.graphic_extensions(vertices=[Integer(0),Integer(1),Integer(2)])
>>> sum (Integer(1) for i in I)
4
groundset()[source]#

Return the groundset of the matroid as a frozenset.

EXAMPLES:

sage: M = Matroid(graphs.DiamondGraph())
sage: sorted(M.groundset())
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
sage: G = graphs.CompleteGraph(3).disjoint_union(graphs.CompleteGraph(4))
sage: M = Matroid(range(G.num_edges()), G); sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: M = Matroid(Graph([(0, 1, 'a'), (0, 2, 'b'), (0, 3, 'c')]))
sage: sorted(M.groundset())
['a', 'b', 'c']

>>> from sage.all import *
>>> M = Matroid(graphs.DiamondGraph())
>>> sorted(M.groundset())
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
>>> G = graphs.CompleteGraph(Integer(3)).disjoint_union(graphs.CompleteGraph(Integer(4)))
>>> M = Matroid(range(G.num_edges()), G); sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6, 7, 8]
>>> M = Matroid(Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(2), 'b'), (Integer(0), Integer(3), 'c')]))
>>> sorted(M.groundset())
['a', 'b', 'c']
groundset_to_edges(X)[source]#

Return a list of edges corresponding to a set of groundset elements.

INPUT:

  • X – subset of the groundset

OUTPUT: list of graph edges

EXAMPLES:

sage: M = Matroid(range(5), graphs.DiamondGraph())
sage: M.groundset_to_edges([2, 3, 4])
[(1, 2, 2), (1, 3, 3), (2, 3, 4)]
sage: M.groundset_to_edges([2, 3, 4, 5])
Traceback (most recent call last):
...
ValueError: input must be a subset of the groundset

>>> from sage.all import *
>>> M = Matroid(range(Integer(5)), graphs.DiamondGraph())
>>> M.groundset_to_edges([Integer(2), Integer(3), Integer(4)])
[(1, 2, 2), (1, 3, 3), (2, 3, 4)]
>>> M.groundset_to_edges([Integer(2), Integer(3), Integer(4), Integer(5)])
Traceback (most recent call last):
...
ValueError: input must be a subset of the groundset
is_graphic()[source]#

Return if self is graphic.

This is trivially True for a GraphicMatroid.

EXAMPLES:

sage: M = Matroid(graphs.PetersenGraph())
sage: M.is_graphic()
True

>>> from sage.all import *
>>> M = Matroid(graphs.PetersenGraph())
>>> M.is_graphic()
True
is_regular()[source]#

Return if self is regular.

This is always True for a GraphicMatroid.

EXAMPLES:

sage: M = Matroid(graphs.DesarguesGraph())
sage: M.is_regular()
True

>>> from sage.all import *
>>> M = Matroid(graphs.DesarguesGraph())
>>> M.is_regular()
True
is_valid()[source]#

Test if the data obey the matroid axioms.

Since a graph is used for the data, this is always the case.

OUTPUT: True

EXAMPLES:

sage: M = matroids.CompleteGraphic(4); M
M(K4): Graphic matroid of rank 3 on 6 elements
sage: M.is_valid()
True

>>> from sage.all import *
>>> M = matroids.CompleteGraphic(Integer(4)); M
M(K4): Graphic matroid of rank 3 on 6 elements
>>> M.is_valid()
True
one_sum(X, u, v)[source]#

Arrange matroid components in the graph.

The matroid’s graph must be connected even if the matroid is not connected, but if there are multiple matroid components, the user may choose how they are arranged in the graph. This method will take the block of the graph that represents \(X\) and attach it by vertex \(u\) to another vertex \(v\) in the graph.

INPUT:

  • X – subset of the groundset

  • u – vertex spanned by the edges of the elements in X

  • v – vertex spanned by the edges of the elements not in X

OUTPUT: GraphicMatroid isomorphic to this matroid but with a graph that is not necessarily isomorphic

EXAMPLES:

sage: edgedict = {0:[1, 2], 1:[2, 3], 2:[3], 3:[4, 5], 6:[4, 5]}
sage: M = Matroid(range(9), Graph(edgedict))
sage: M.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (2, 3, 4),
 (3, 4, 5),
 (3, 5, 6),
 (4, 6, 7),
 (5, 6, 8)]
sage: M1 = M.one_sum(u=3, v=1, X=[5, 6, 7, 8])
sage: M1.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (1, 4, 5),
 (1, 5, 6),
 (2, 3, 4),
 (4, 6, 7),
 (5, 6, 8)]
sage: M2 = M.one_sum(u=4, v=3, X=[5, 6, 7, 8])
sage: M2.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (2, 3, 4),
 (3, 6, 7),
 (3, 7, 5),
 (5, 6, 8),
 (5, 7, 6)]

>>> from sage.all import *
>>> edgedict = {Integer(0):[Integer(1), Integer(2)], Integer(1):[Integer(2), Integer(3)], Integer(2):[Integer(3)], Integer(3):[Integer(4), Integer(5)], Integer(6):[Integer(4), Integer(5)]}
>>> M = Matroid(range(Integer(9)), Graph(edgedict))
>>> M.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (2, 3, 4),
 (3, 4, 5),
 (3, 5, 6),
 (4, 6, 7),
 (5, 6, 8)]
>>> M1 = M.one_sum(u=Integer(3), v=Integer(1), X=[Integer(5), Integer(6), Integer(7), Integer(8)])
>>> M1.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (1, 4, 5),
 (1, 5, 6),
 (2, 3, 4),
 (4, 6, 7),
 (5, 6, 8)]
>>> M2 = M.one_sum(u=Integer(4), v=Integer(3), X=[Integer(5), Integer(6), Integer(7), Integer(8)])
>>> M2.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 3, 3),
 (2, 3, 4),
 (3, 6, 7),
 (3, 7, 5),
 (5, 6, 8),
 (5, 7, 6)]
regular_matroid()[source]#

Return an instance of RegularMatroid isomorphic to this GraphicMatroid.

EXAMPLES:

sage: M = matroids.CompleteGraphic(5); M
M(K5): Graphic matroid of rank 4 on 10 elements
sage: N = M.regular_matroid(); N
Regular matroid of rank 4 on 10 elements with 125 bases
sage: M.equals(N)
True
sage: M == N
False

>>> from sage.all import *
>>> M = matroids.CompleteGraphic(Integer(5)); M
M(K5): Graphic matroid of rank 4 on 10 elements
>>> N = M.regular_matroid(); N
Regular matroid of rank 4 on 10 elements with 125 bases
>>> M.equals(N)
True
>>> M == N
False
relabel(mapping)[source]#

Return an isomorphic matroid with relabeled groundset.

The output is obtained by relabeling each element \(e\) by mapping[e], where mapping is a given injective map. If mapping[e] is not defined, then the identity map is assumed.

INPUT:

  • mapping – a Python object such that mapping[e] is the new label of \(e\)

OUTPUT: matroid

EXAMPLES:

sage: M = matroids.CompleteGraphic(4)
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5]
sage: N = M.relabel({0: 6, 5: 'e'})
sage: sorted(N.groundset(), key=str)
[1, 2, 3, 4, 6, 'e']
sage: N.is_isomorphic(M)
True

>>> from sage.all import *
>>> M = matroids.CompleteGraphic(Integer(4))
>>> sorted(M.groundset())
[0, 1, 2, 3, 4, 5]
>>> N = M.relabel({Integer(0): Integer(6), Integer(5): 'e'})
>>> sorted(N.groundset(), key=str)
[1, 2, 3, 4, 6, 'e']
>>> N.is_isomorphic(M)
True
subgraph_from_set(X)[source]#

Return the subgraph corresponding to the matroid restricted to \(X\).

INPUT:

  • X – subset of the groundset

OUTPUT: graph

EXAMPLES:

sage: M = Matroid(range(5), graphs.DiamondGraph())
sage: M.subgraph_from_set([0,1,2])
Looped multi-graph on 3 vertices
sage: M.subgraph_from_set([3,4,5])
Traceback (most recent call last):
...
ValueError: input must be a subset of the groundset

>>> from sage.all import *
>>> M = Matroid(range(Integer(5)), graphs.DiamondGraph())
>>> M.subgraph_from_set([Integer(0),Integer(1),Integer(2)])
Looped multi-graph on 3 vertices
>>> M.subgraph_from_set([Integer(3),Integer(4),Integer(5)])
Traceback (most recent call last):
...
ValueError: input must be a subset of the groundset
twist(X)[source]#

Perform a Whitney twist on the graph.

\(X\) must be part of a 2-separation. The connectivity of \(X\) must be 1, and the subgraph induced by \(X\) must intersect the subgraph induced by the rest of the elements on exactly two vertices.

INPUT:

  • X – the set of elements to be twisted with respect to the rest of the matroid

OUTPUT: GraphicMatroid isomorphic to this matroid but with a graph that is not necessarily isomorphic

EXAMPLES:

sage: edgelist = [(0, 1, 0), (1, 2, 1), (1, 2, 2), (2, 3, 3),
....:             (2, 3, 4), (2, 3, 5), (3, 0, 6)]
sage: M = Matroid(Graph(edgelist, multiedges=True))
sage: M1 = M.twist([0, 1, 2]); M1.graph().edges(sort=True)
[(0, 1, 1), (0, 1, 2), (0, 3, 6), (1, 2, 0), (2, 3, 3), (2, 3, 4), (2, 3, 5)]
sage: M2 = M.twist([0, 1, 3])
Traceback (most recent call last):
...
ValueError: the input must display a 2-separation that is not a 1-separation

>>> from sage.all import *
>>> edgelist = [(Integer(0), Integer(1), Integer(0)), (Integer(1), Integer(2), Integer(1)), (Integer(1), Integer(2), Integer(2)), (Integer(2), Integer(3), Integer(3)),
...             (Integer(2), Integer(3), Integer(4)), (Integer(2), Integer(3), Integer(5)), (Integer(3), Integer(0), Integer(6))]
>>> M = Matroid(Graph(edgelist, multiedges=True))
>>> M1 = M.twist([Integer(0), Integer(1), Integer(2)]); M1.graph().edges(sort=True)
[(0, 1, 1), (0, 1, 2), (0, 3, 6), (1, 2, 0), (2, 3, 3), (2, 3, 4), (2, 3, 5)]
>>> M2 = M.twist([Integer(0), Integer(1), Integer(3)])
Traceback (most recent call last):
...
ValueError: the input must display a 2-separation that is not a 1-separation
vertex_map()[source]#

Return a dictionary mapping the input vertices to the current vertices.

The graph for the matroid is always connected. If the constructor is given a graph with multiple components, it will connect them. The Python dictionary given by this method has the vertices from the input graph as keys, and the corresponding vertex label after any merging as values.

OUTPUT: dictionary

EXAMPLES:

sage: G = Graph([(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5),
....: (6, 7), (6, 8), (7, 8), (8, 8), (7, 8)], multiedges=True, loops=True)
sage: M = Matroid(range(G.num_edges()), G)
sage: M.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 4, 3),
 (1, 5, 4),
 (4, 5, 5),
 (4, 7, 6),
 (4, 8, 7),
 (7, 8, 8),
 (7, 8, 9),
 (8, 8, 10)]
sage: M.vertex_map()
{0: 0, 1: 1, 2: 2, 3: 1, 4: 4, 5: 5, 6: 4, 7: 7, 8: 8}

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2)), (Integer(3), Integer(4)), (Integer(3), Integer(5)), (Integer(4), Integer(5)),
... (Integer(6), Integer(7)), (Integer(6), Integer(8)), (Integer(7), Integer(8)), (Integer(8), Integer(8)), (Integer(7), Integer(8))], multiedges=True, loops=True)
>>> M = Matroid(range(G.num_edges()), G)
>>> M.graph().edges(sort=True)
[(0, 1, 0),
 (0, 2, 1),
 (1, 2, 2),
 (1, 4, 3),
 (1, 5, 4),
 (4, 5, 5),
 (4, 7, 6),
 (4, 8, 7),
 (7, 8, 8),
 (7, 8, 9),
 (8, 8, 10)]
>>> M.vertex_map()
{0: 0, 1: 1, 2: 2, 3: 1, 4: 4, 5: 5, 6: 4, 7: 7, 8: 8}