Matching¶

This module implements the functions pertaining to matching of undirected graphs. A matching in a graph is a set of pairwise nonadjacent links (nonloop edges). In other words, a matching in a graph is the edge set of an 1-regular subgraph. A matching is called a perfect matching if it the subgraph generated by a set of matching edges spans the graph, i.e. it’s the edge set of an 1-regular spanning subgraph.

The implemented methods are listed below:

has_perfect_matching()

Return whether the graph has a perfect matching

is_bicritical()

Check if the graph is bicritical

is_factor_critical()

Check whether the graph is factor-critical

is_matching_covered()

Check if the graph is matching covered

matching()

Return a maximum weighted matching of the graph represented by the list of its edges

perfect_matchings()

Return an iterator over all perfect matchings of the graph

M_alternating_even_mark()

Return the vertices reachable from the provided vertex via an even alternating path starting with a non-matching edge

AUTHORS:

Robert L. Miller (2006年10月22日): initial implementations
Janmenjaya Panda (2024年06月17日): added M_alternating_even_mark(), is_bicritical() and is_matching_covered()

Methods¶

sage.graphs.matching.M_alternating_even_mark(G, vertex, matching)[source] ¶

Return the vertices reachable from vertex via an even alternating path starting with a non-matching edge.

This method implements the algorithm proposed in [LR2004]. Note that the complexity of the algorithm is linear in number of edges.

INPUT:

vertex – a vertex of the graph
matching – a matching of the graph; it can be given using any valid input format of Graph

OUTPUT:

even – the set of vertices each of which is reachable from the provided vertex through a path starting with an edge not in the matching and ending with an edge in the matching; note that a note that a ValueError is returned if the graph is not simple

EXAMPLES:

Show the list of required vertices for a graph \(G\) with a matching \(M\) for a vertex \(u\):

Sage

sage: G = graphs.CycleGraph(3)
sage: M = G.matching()
sage: M
[(0, 2, None)]
sage: from sage.graphs.matching import M_alternating_even_mark
sage: S0 = M_alternating_even_mark(G, 0, M)
sage: S0
{0}
sage: S1 = M_alternating_even_mark(G, 1, M)
sage: S1
{0, 1, 2}

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(3))
>>> M = G.matching()
>>> M
[(0, 2, None)]
>>> from sage.graphs.matching import M_alternating_even_mark
>>> S0 = M_alternating_even_mark(G, Integer(0), M)
>>> S0
{0}
>>> S1 = M_alternating_even_mark(G, Integer(1), M)
>>> S1
{0, 1, 2}

The result is equivalent for the underlying simple graph of the provided graph, if the other parameters provided are the same:

Sage

sage: G = graphs.CompleteBipartiteGraph(3, 3)
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 3)
sage: M = G.matching()
sage: u = 0
sage: from sage.graphs.matching import M_alternating_even_mark
sage: S = M_alternating_even_mark(G, u, M)
sage: S
{0, 1, 2}
sage: T = M_alternating_even_mark(G.to_simple(), u, M)
sage: T
{0, 1, 2}

Python

>>> from sage.all import *
>>> G = graphs.CompleteBipartiteGraph(Integer(3), Integer(3))
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(3))
>>> M = G.matching()
>>> u = Integer(0)
>>> from sage.graphs.matching import M_alternating_even_mark
>>> S = M_alternating_even_mark(G, u, M)
>>> S
{0, 1, 2}
>>> T = M_alternating_even_mark(G.to_simple(), u, M)
>>> T
{0, 1, 2}

For a factor critical graph \(G\) (for instance, a wheel graph of an odd order) with a near perfect matching \(M\) and \(u\) being the (unique) \(M\)-exposed vertex, each vertex in \(G\) is reachable from \(u\) through an even length \(M\)-alternating path as described above:

Sage

sage: G = graphs.WheelGraph(11)
sage: M = Graph(G.matching())
sage: G.is_factor_critical(M)
True
sage: for v in G:
....: if v not in M:
....: break
....:
sage: from sage.graphs.matching import M_alternating_even_mark
sage: S = M_alternating_even_mark(G, v, M)
sage: S == set(G)
True

Python

>>> from sage.all import *
>>> G = graphs.WheelGraph(Integer(11))
>>> M = Graph(G.matching())
>>> G.is_factor_critical(M)
True
>>> for v in G:
... if v not in M:
... break
....:
>>> from sage.graphs.matching import M_alternating_even_mark
>>> S = M_alternating_even_mark(G, v, M)
>>> S == set(G)
True

For a matching covered graph \(G\) (for instance, \(K_4 \odot K_{3,3}\)) with a perfect matching \(M\) and for some vertex \(u\) with \(v\) being its \(M\)-matched neighbor, each neighbor of \(v\) is reachable from \(u\) through an even length \(M\)-alternating path as described above:

Sage

sage: G = Graph()
sage: G.add_edges([
....: (0, 2), (0, 3), (0, 4), (1, 2),
....: (1, 3), (1, 4), (2, 5), (3, 6),
....: (4, 7), (5, 6), (5, 7), (6, 7)
....: ])
sage: M = Graph(G.matching())
sage: G.is_matching_covered(M)
True
sage: u = 0
sage: v = next(M.neighbor_iterator(u))
sage: from sage.graphs.matching import M_alternating_even_mark
sage: S = M_alternating_even_mark(G, u, M)
sage: (set(G.neighbor_iterator(v))).issubset(S)
True

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edges([
... (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)),
... (Integer(1), Integer(3)), (Integer(1), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(6)),
... (Integer(4), Integer(7)), (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(6), Integer(7))
... ])
>>> M = Graph(G.matching())
>>> G.is_matching_covered(M)
True
>>> u = Integer(0)
>>> v = next(M.neighbor_iterator(u))
>>> from sage.graphs.matching import M_alternating_even_mark
>>> S = M_alternating_even_mark(G, u, M)
>>> (set(G.neighbor_iterator(v))).issubset(S)
True

For a bicritical graph \(G\) (for instance, the Petersen graph) with a perfect matching \(M\) and for some vertex \(u\) with its \(M\)-matched neighbor being \(v\), each vertex of the graph distinct from \(v\) is reachable from \(u\) through an even length \(M\)-alternating path as described above:

Sage

sage: G = graphs.PetersenGraph()
sage: M = Graph(G.matching())
sage: G.is_bicritical(M)
True
sage: import random
sage: u = random.choice(list(G)) # needs random
sage: v = next(M.neighbor_iterator(u))
sage: from sage.graphs.matching import M_alternating_even_mark
sage: S = M_alternating_even_mark(G, u, M)
sage: S == (set(G) - {v})
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> M = Graph(G.matching())
>>> G.is_bicritical(M)
True
>>> import random
>>> u = random.choice(list(G)) # needs random
>>> v = next(M.neighbor_iterator(u))
>>> from sage.graphs.matching import M_alternating_even_mark
>>> S = M_alternating_even_mark(G, u, M)
>>> S == (set(G) - {v})
True

REFERENCES:

[LR2004]

AUTHORS:

Janmenjaya Panda (2024年06月17日)

sage.graphs.matching.has_perfect_matching(G, algorithm, solver='Edmonds', verbose=None, integrality_tolerance=0)[source] ¶

Return whether the graph has a perfect matching.

INPUT:

algorithm – string (default: 'Edmonds')
- 'Edmonds' uses Edmonds’ algorithm as implemented in NetworkX to find a matching of maximal cardinality, then check whether this cardinality is half the number of vertices of the graph.
- 'LP_matching' uses a Linear Program to find a matching of maximal cardinality, then check whether this cardinality is half the number of vertices of the graph.
- 'LP' uses a Linear Program formulation of the perfect matching problem: put a binary variable b[e] on each edge \(e\), and for each vertex \(v\), require that the sum of the values of the edges incident to \(v\) is 1.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == "LP_matching" or algorithm == "LP")
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT: boolean

EXAMPLES:

Sage

sage: graphs.PetersenGraph().has_perfect_matching() # needs networkx
True
sage: graphs.WheelGraph(6).has_perfect_matching() # needs networkx
True
sage: graphs.WheelGraph(5).has_perfect_matching() # needs networkx
False
sage: graphs.PetersenGraph().has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
sage: graphs.WheelGraph(6).has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
sage: graphs.WheelGraph(5).has_perfect_matching(algorithm='LP_matching')
False
sage: graphs.PetersenGraph().has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
sage: graphs.WheelGraph(6).has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
sage: graphs.WheelGraph(5).has_perfect_matching(algorithm='LP_matching')
False

Python

>>> from sage.all import *
>>> graphs.PetersenGraph().has_perfect_matching() # needs networkx
True
>>> graphs.WheelGraph(Integer(6)).has_perfect_matching() # needs networkx
True
>>> graphs.WheelGraph(Integer(5)).has_perfect_matching() # needs networkx
False
>>> graphs.PetersenGraph().has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
>>> graphs.WheelGraph(Integer(6)).has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
>>> graphs.WheelGraph(Integer(5)).has_perfect_matching(algorithm='LP_matching')
False
>>> graphs.PetersenGraph().has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
>>> graphs.WheelGraph(Integer(6)).has_perfect_matching(algorithm='LP_matching') # needs sage.numerical.mip
True
>>> graphs.WheelGraph(Integer(5)).has_perfect_matching(algorithm='LP_matching')
False

sage.graphs.matching.is_bicritical(G, matching, algorithm=None, coNP_certificate='Edmonds', solver=False, verbose=None, integrality_tolerance=0)[source] ¶

Check if the graph is bicritical.

A nontrivial graph \(G\) is bicritical if \(G - u - v\) has a perfect matching for any two distinct vertices \(u\) and \(v\) of \(G\). Bicritical graphs are special kind of matching covered graphs. Each maximal barrier of a bicritical graph is a singleton. Thus, for a bicritical graph, the canonical partition of the vertex set is the set of sets where each set is an indiviudal vertex. Three-connected bicritical graphs, aka bricks, play an important role in the theory of matching covered graphs.

This method implements the algorithm proposed in [LZ2001] and we assume that a connected graph of order two is bicritical, whereas a disconnected graph of the same order is not. The time complexity of the algorithm is \(\mathcal{O}(|V| \cdot |E|)\), if a perfect matching of the graph is given, where \(|V|\) and \(|E|\) are the order and the size of the graph respectively. Otherwise, time complexity may be dominated by the time needed to compute a maximum matching of the graph.

Note that a ValueError is returned if the graph has loops or if the graph is trivial, i.e., it has at most one vertex.

INPUT:

matching – (default: None); a perfect matching of the graph, that can be given using any valid input format of Graph.

If set to None, a matching is computed using the other parameters.
algorithm – string (default: 'Edmonds'); the algorithm to be used to compute a maximum matching of the graph among
- 'Edmonds' selects Edmonds’ algorithm as implemented in NetworkX,
- 'LP' uses a Linear Program formulation of the matching problem.
coNP_certificate – boolean (default: False); if set to True a set of pair of vertices (say \(u\) and \(v\)) is returned such that \(G - u - v\) does not have a perfect matching if \(G\) is not bicritical or otherwise None is returned.
solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == 'LP').
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A boolean indicating whether the graph is bicritical or not.
If coNP_certificate is set to True, a set of pair of vertices is returned in case the graph is not bicritical otherwise None is returned.

EXAMPLES:

The Petersen graph is bicritical:

Sage

sage: G = graphs.PetersenGraph()
sage: G.is_bicritical()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.is_bicritical()
True

A graph (without a self-loop) is bicritical if and only if the underlying simple graph is bicritical:

Sage

sage: G = graphs.PetersenGraph()
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 5)
sage: G.is_bicritical()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(5))
>>> G.is_bicritical()
True

A nontrivial circular ladder graph whose order is not divisible by 4 is bicritical:

Sage

sage: G = graphs.CircularLadderGraph(5)
sage: G.is_bicritical()
True

Python

>>> from sage.all import *
>>> G = graphs.CircularLadderGraph(Integer(5))
>>> G.is_bicritical()
True

The graph obtained by splicing two bicritical graph is also bicritical. For instance, \(K_4\) with one extra (multiple) edge (say \(G := K_4^+\)) is bicritical. Let \(H := K_4^+ \odot K_4^+\) such that \(H\) is free of multiple edge. The graph \(H\) is also bicritical:

Sage

sage: G = graphs.CompleteGraph(4)
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 1)
sage: G.is_bicritical()
True
sage: H = Graph()
sage: H.add_edges([
....: (0, 1), (0, 2), (0, 3), (0, 4), (1, 2),
....: (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)
....: ])
sage: H.is_bicritical()
True

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(1))
>>> G.is_bicritical()
True
>>> H = Graph()
>>> H.add_edges([
... (Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)),
... (Integer(1), Integer(5)), (Integer(2), Integer(5)), (Integer(3), Integer(4)), (Integer(3), Integer(5)), (Integer(4), Integer(5))
... ])
>>> H.is_bicritical()
True

A graph (of order more than two) with more that one component is not bicritical:

Sage

sage: G = graphs.CycleGraph(4)
sage: G += graphs.CycleGraph(6)
sage: G.connected_components_number()
2
sage: G.is_bicritical()
False

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4))
>>> G += graphs.CycleGraph(Integer(6))
>>> G.connected_components_number()
2
>>> G.is_bicritical()
False

A graph (of order more than two) with a cut-vertex is not bicritical:

Sage

sage: G = graphs.CycleGraph(6)
sage: G.add_edges([(5, 6), (5, 7), (6, 7)])
sage: G.is_cut_vertex(5)
True
sage: G.has_perfect_matching()
True
sage: G.is_bicritical()
False

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(6))
>>> G.add_edges([(Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(6), Integer(7))])
>>> G.is_cut_vertex(Integer(5))
True
>>> G.has_perfect_matching()
True
>>> G.is_bicritical()
False

A connected graph of order two is assumed to be bicritical, whereas the disconnected graph of the same order is not:

Sage

sage: G = graphs.CompleteBipartiteGraph(1, 1)
sage: G.is_bicritical()
True
sage: G = graphs.CompleteBipartiteGraph(2, 0)
sage: G.is_bicritical()
False

Python

>>> from sage.all import *
>>> G = graphs.CompleteBipartiteGraph(Integer(1), Integer(1))
>>> G.is_bicritical()
True
>>> G = graphs.CompleteBipartiteGraph(Integer(2), Integer(0))
>>> G.is_bicritical()
False

A bipartite graph of order three or more is not bicritical:

Sage

sage: G = graphs.CompleteBipartiteGraph(3, 3)
sage: G.has_perfect_matching()
True
sage: G.is_bicritical()
False

Python

>>> from sage.all import *
>>> G = graphs.CompleteBipartiteGraph(Integer(3), Integer(3))
>>> G.has_perfect_matching()
True
>>> G.is_bicritical()
False

One may specify a matching:

Sage

sage: G = graphs.WheelGraph(10)
sage: M = G.matching()
sage: G.is_bicritical(matching=M)
True
sage: H = graphs.HexahedralGraph()
sage: N = H.matching()
sage: H.is_bicritical(matching=N)
False

Python

>>> from sage.all import *
>>> G = graphs.WheelGraph(Integer(10))
>>> M = G.matching()
>>> G.is_bicritical(matching=M)
True
>>> H = graphs.HexahedralGraph()
>>> N = H.matching()
>>> H.is_bicritical(matching=N)
False

One may ask for a co-\(\mathcal{NP}\) certificate:

Sage

sage: G = graphs.CompleteGraph(14)
sage: G.is_bicritical(coNP_certificate=True)
(True, None)
sage: H = graphs.CircularLadderGraph(20)
sage: M = H.matching()
sage: H.is_bicritical(matching=M, coNP_certificate=True)
(False, {0, 2})

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(14))
>>> G.is_bicritical(coNP_certificate=True)
(True, None)
>>> H = graphs.CircularLadderGraph(Integer(20))
>>> M = H.matching()
>>> H.is_bicritical(matching=M, coNP_certificate=True)
(False, {0, 2})

REFERENCES:

AUTHORS:

Janmenjaya Panda (2024年06月17日)

sage.graphs.matching.is_factor_critical(G, matching, algorithm=None, solver='Edmonds', verbose=None, integrality_tolerance=0)[source] ¶

Check whether the graph is factor-critical.

A graph of order \(n\) is factor-critical if every subgraph of \(n-1\) vertices have a perfect matching, hence \(n\) must be odd. See Wikipedia article Factor-critical_graph for more details.

This method implements the algorithm proposed in [LR2004] and we assume that a graph of order one is factor-critical. The time complexity of the algorithm is linear if a near perfect matching is given as input (i.e., a matching such that all vertices but one are incident to an edge of the matching). Otherwise, the time complexity is dominated by the time needed to compute a maximum matching of the graph.

INPUT:

matching – (default: None); a near perfect matching of the graph, that is a matching such that all vertices of the graph but one are incident to an edge of the matching. It can be given using any valid input format of Graph.

If set to None, a matching is computed using the other parameters.
algorithm – string (default: 'Edmonds'); the algorithm to use to compute a maximum matching of the graph among
- 'Edmonds' selects Edmonds’ algorithm as implemented in NetworkX
- 'LP' uses a Linear Program formulation of the matching problem
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == "LP")
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

Odd length cycles and odd cliques of order at least 3 are factor-critical graphs:

Sage

sage: [graphs.CycleGraph(2*i + 1).is_factor_critical() for i in range(5)] # needs networkx
[True, True, True, True, True]
sage: [graphs.CompleteGraph(2*i + 1).is_factor_critical() for i in range(5)] # needs networkx
[True, True, True, True, True]

Python

>>> from sage.all import *
>>> [graphs.CycleGraph(Integer(2)*i + Integer(1)).is_factor_critical() for i in range(Integer(5))] # needs networkx
[True, True, True, True, True]
>>> [graphs.CompleteGraph(Integer(2)*i + Integer(1)).is_factor_critical() for i in range(Integer(5))] # needs networkx
[True, True, True, True, True]

More generally, every Hamiltonian graph with an odd number of vertices is factor-critical:

Sage

sage: G = graphs.RandomGNP(15, .2)
sage: G.add_path([0..14])
sage: G.add_edge(14, 0)
sage: G.is_hamiltonian()
True
sage: G.is_factor_critical() # needs networkx
True

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(15), RealNumber('.2'))
>>> G.add_path((ellipsis_range(Integer(0),Ellipsis,Integer(14))))
>>> G.add_edge(Integer(14), Integer(0))
>>> G.is_hamiltonian()
True
>>> G.is_factor_critical() # needs networkx
True

Friendship graphs are non-Hamiltonian factor-critical graphs:

Sage

sage: [graphs.FriendshipGraph(i).is_factor_critical() for i in range(1, 5)] # needs networkx
[True, True, True, True]

Python

>>> from sage.all import *
>>> [graphs.FriendshipGraph(i).is_factor_critical() for i in range(Integer(1), Integer(5))] # needs networkx
[True, True, True, True]

Bipartite graphs are not factor-critical:

Sage

sage: G = graphs.RandomBipartite(randint(1, 10), randint(1, 10), .5) # needs numpy
sage: G.is_factor_critical() # needs numpy
False

Python

>>> from sage.all import *
>>> G = graphs.RandomBipartite(randint(Integer(1), Integer(10)), randint(Integer(1), Integer(10)), RealNumber('.5')) # needs numpy
>>> G.is_factor_critical() # needs numpy
False

Graphs with even order are not factor critical:

Sage

sage: G = graphs.RandomGNP(10, .5)
sage: G.is_factor_critical()
False

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(10), RealNumber('.5'))
>>> G.is_factor_critical()
False

One can specify a matching:

Sage

sage: F = graphs.FriendshipGraph(4)
sage: M = F.matching() # needs networkx
sage: F.is_factor_critical(matching=M) # needs networkx
True
sage: F.is_factor_critical(matching=Graph(M)) # needs networkx
True

Python

>>> from sage.all import *
>>> F = graphs.FriendshipGraph(Integer(4))
>>> M = F.matching() # needs networkx
>>> F.is_factor_critical(matching=M) # needs networkx
True
>>> F.is_factor_critical(matching=Graph(M)) # needs networkx
True

sage.graphs.matching.is_matching_covered(G, matching, algorithm=None, coNP_certificate='Edmonds', solver=False, verbose=None, integrality_tolerance=0)[source] ¶

Check if the graph is matching covered.

A connected nontrivial graph wherein each edge participates in some perfect matching is called a matching covered graph.

If a perfect matching of the graph is provided, for bipartite graph, this method implements a linear time algorithm as proposed in [LM2024] that is based on the following theorem:

Given a connected bipartite graph \(G[A, B]\) with a perfect matching \(M\). Construct a directed graph \(D\) from \(G\) such that \(V(D) := V(G)\) and for each edge in \(G\) direct the corresponding edge from \(A\) to \(B\) in \(D\), if it is in \(M\) or otherwise direct it from \(B\) to \(A\). The graph \(G\) is matching covered if and only if \(D\) is strongly connected.

For nonbipartite graph, if a perfect matching of the graph is provided, this method implements an \(\mathcal{O}(|V| \cdot |E|)\) algorithm, where \(|V|\) and \(|E|\) are the order and the size of the graph respectively. This implementation is inspired by the \(M\)-\(alternating\) \(tree\) \(search\) method explained in [LZ2001]. For nonbipartite graph, the implementation is based on the following theorem:

Given a nonbipartite graph \(G\) with a perfect matching \(M\). The graph \(G\) is matching covered if and only if for each edge \(uv\) not in \(M\), there exists an \(M\)-\(alternating\) odd length \(uv\)-path starting and ending with edges not in \(M\).

The time complexity may be dominated by the time needed to compute a maximum matching of the graph, in case a perfect matching is not provided. Also, note that for a disconnected or a trivial or a graph with a loop, a ValueError is returned.

INPUT:

matching – (default: None); a perfect matching of the graph, that can be given using any valid input format of Graph.

If set to None, a matching is computed using the other parameters.
algorithm – string (default: 'Edmonds'); the algorithm to be used to compute a maximum matching of the graph among
- 'Edmonds' selects Edmonds’ algorithm as implemented in NetworkX,
- 'LP' uses a Linear Program formulation of the matching problem.
coNP_certificate – boolean (default: False); if set to True an edge of the graph, that does not participate in any perfect matching, is returned if \(G\) is not matching covered or otherwise None is returned.
solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == 'LP').
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A boolean indicating whether the graph is matching covered or not.
If coNP_certificate is set to True, an edge is returned in case the graph is not matching covered otherwise None is returned.

EXAMPLES:

The Petersen graph is matching covered:

Sage

sage: G = graphs.PetersenGraph()
sage: G.is_matching_covered()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.is_matching_covered()
True

A graph (without a self-loop) is matching covered if and only if the underlying simple graph is matching covered:

Sage

sage: G = graphs.PetersenGraph()
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 5)
sage: G.is_matching_covered()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(5))
>>> G.is_matching_covered()
True

A corollary to Tutte’s fundamental result [Tut1947], as a strengthening of Petersen’s Theorem, states that every 2-connected cubic graph is matching covered:

Sage

sage: G = Graph()
sage: G.add_edges([
....: (0, 1), (0, 2), (0, 3),
....: (1, 2), (1, 4), (2, 4),
....: (3, 5), (3, 6), (4, 7),
....: (5, 6), (5, 7), (6, 7)
....: ])
sage: G.vertex_connectivity()
2
sage: degree_sequence = G.degree_sequence()
sage: min(degree_sequence) == max(degree_sequence) == 3
True
sage: G.is_matching_covered()
True

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edges([
... (Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(3)),
... (Integer(1), Integer(2)), (Integer(1), Integer(4)), (Integer(2), Integer(4)),
... (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(7)),
... (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(6), Integer(7))
... ])
>>> G.vertex_connectivity()
2
>>> degree_sequence = G.degree_sequence()
>>> min(degree_sequence) == max(degree_sequence) == Integer(3)
True
>>> G.is_matching_covered()
True

A connected bipartite graph \(G[A, B]\), with \(|A| = |B| \geq 2\), is matching covered if and only if \(|N(X)| \geq |X| + 1\), for all \(X \subset A\) such that \(1 \leq |X| \leq |A| - 1\). For instance, the Hexahedral graph is matching covered, but not the path graphs on even number of vertices, even though they have a perfect matching:

Sage

sage: G = graphs.HexahedralGraph()
sage: G.is_bipartite()
True
sage: G.is_matching_covered()
True
sage: P = graphs.PathGraph(10)
sage: P.is_bipartite()
True
sage: M = Graph(P.matching())
sage: set(P) == set(M)
True
sage: P.is_matching_covered()
False

Python

>>> from sage.all import *
>>> G = graphs.HexahedralGraph()
>>> G.is_bipartite()
True
>>> G.is_matching_covered()
True
>>> P = graphs.PathGraph(Integer(10))
>>> P.is_bipartite()
True
>>> M = Graph(P.matching())
>>> set(P) == set(M)
True
>>> P.is_matching_covered()
False

A connected bipartite graph \(G[A, B]\) of order six or more is matching covered if and only if \(G - a - b\) has a perfect matching for some vertex \(a\) in \(A\) and some vertex \(b\) in \(B\):

Sage

sage: G = graphs.CircularLadderGraph(8)
sage: G.is_bipartite()
True
sage: G.is_matching_covered()
True
sage: A, B = G.bipartite_sets()
sage: # needs random
sage: import random
sage: a = random.choice(list(A))
sage: b = random.choice(list(B))
sage: G.delete_vertices([a, b])
sage: M = Graph(G.matching())
sage: set(M) == set(G)
True
sage: cycle1 = graphs.CycleGraph(4)
sage: cycle2 = graphs.CycleGraph(6)
sage: cycle2.relabel(lambda v: v + 4)
sage: H = Graph()
sage: H.add_edges(cycle1.edges() + cycle2.edges())
sage: H.add_edge(3, 4)
sage: H.is_bipartite()
True
sage: H.is_matching_covered()
False
sage: H.delete_vertices([3, 4])
sage: N = Graph(H.matching())
sage: set(N) == set(H)
False

Python

>>> from sage.all import *
>>> G = graphs.CircularLadderGraph(Integer(8))
>>> G.is_bipartite()
True
>>> G.is_matching_covered()
True
>>> A, B = G.bipartite_sets()
>>> # needs random
>>> import random
>>> a = random.choice(list(A))
>>> b = random.choice(list(B))
>>> G.delete_vertices([a, b])
>>> M = Graph(G.matching())
>>> set(M) == set(G)
True
>>> cycle1 = graphs.CycleGraph(Integer(4))
>>> cycle2 = graphs.CycleGraph(Integer(6))
>>> cycle2.relabel(lambda v: v + Integer(4))
>>> H = Graph()
>>> H.add_edges(cycle1.edges() + cycle2.edges())
>>> H.add_edge(Integer(3), Integer(4))
>>> H.is_bipartite()
True
>>> H.is_matching_covered()
False
>>> H.delete_vertices([Integer(3), Integer(4)])
>>> N = Graph(H.matching())
>>> set(N) == set(H)
False

One may specify a matching:

Sage

sage: G = graphs.WheelGraph(20)
sage: M = Graph(G.matching())
sage: G.is_matching_covered(matching=M)
True
sage: J = graphs.CycleGraph(4)
sage: J.add_edge(0, 2)
sage: N = J.matching()
sage: J.is_matching_covered(matching=N)
False

Python

>>> from sage.all import *
>>> G = graphs.WheelGraph(Integer(20))
>>> M = Graph(G.matching())
>>> G.is_matching_covered(matching=M)
True
>>> J = graphs.CycleGraph(Integer(4))
>>> J.add_edge(Integer(0), Integer(2))
>>> N = J.matching()
>>> J.is_matching_covered(matching=N)
False

One may ask for a co-\(\mathcal{NP}\) certificate:

Sage

sage: G = graphs.CompleteGraph(14)
sage: G.is_matching_covered(coNP_certificate=True)
(True, None)
sage: H = graphs.PathGraph(20)
sage: M = H.matching()
sage: H.is_matching_covered(matching=M, coNP_certificate=True)
(False, (2, 1, None))

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(14))
>>> G.is_matching_covered(coNP_certificate=True)
(True, None)
>>> H = graphs.PathGraph(Integer(20))
>>> M = H.matching()
>>> H.is_matching_covered(matching=M, coNP_certificate=True)
(False, (2, 1, None))

REFERENCES:

AUTHORS:

Janmenjaya Panda (2024年06月23日)

sage.graphs.matching.matching(G, value_only, algorithm=False, use_edge_labels='Edmonds', solver=False, verbose=None, integrality_tolerance=0)[source] ¶

Return a maximum weighted matching of the graph represented by the list of its edges.

For more information, see the Wikipedia article Matching_(graph_theory).

Given a graph \(G\) such that each edge \(e\) has a weight \(w_e\), a maximum matching is a subset \(S\) of the edges of \(G\) of maximum weight such that no two edges of \(S\) are incident with each other.

As an optimization problem, it can be expressed as:

\[\begin{split}\mbox{Maximize : }&\sum_{e\in G.edges()} w_e b_e\\ \mbox{Such that : }&\forall v \in G, \sum_{(u,v)\in G.edges()} b_{(u,v)}\leq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]

INPUT:

value_only – boolean (default: False); when set to True, only the cardinal (or the weight) of the matching is returned
algorithm – string (default: 'Edmonds')
- 'Edmonds' selects Edmonds’ algorithm as implemented in NetworkX
- 'LP' uses a Linear Program formulation of the matching problem
use_edge_labels – boolean (default: False)
- when set to True, computes a weighted matching where each edge is weighted by its label (if an edge has no label, \(1\) is assumed)
- when set to False, each edge has weight \(1\)
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == "LP")
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

When value_only=False (default), this method returns an EdgesView containing the edges of a maximum matching of \(G\).
When value_only=True, this method returns the sum of the weights (default: 1) of the edges of a maximum matching of \(G\). The type of the output may vary according to the type of the edge labels and the algorithm used.

ALGORITHM:

The problem is solved using Edmond’s algorithm implemented in NetworkX, or using Linear Programming depending on the value of algorithm.

EXAMPLES:

Maximum matching in a Pappus Graph:

Sage

sage: g = graphs.PappusGraph()
sage: g.matching(value_only=True) # needs sage.networkx
9

Python

>>> from sage.all import *
>>> g = graphs.PappusGraph()
>>> g.matching(value_only=True) # needs sage.networkx
9

Same test with the Linear Program formulation:

Sage

sage: g = graphs.PappusGraph()
sage: g.matching(algorithm='LP', value_only=True) # needs sage.numerical.mip
9

Python

>>> from sage.all import *
>>> g = graphs.PappusGraph()
>>> g.matching(algorithm='LP', value_only=True) # needs sage.numerical.mip
9

../../_images/matching-1.svg

sage.graphs.matching.perfect_matchings(G, labels=False)[source] ¶

Return an iterator over all perfect matchings of the graph.

ALGORITHM:

Choose a vertex \(v\), then recurse through all edges incident to \(v\), removing one edge at a time whenever an edge is added to a matching.

INPUT:

labels – boolean (default: False); when True, the edges in each perfect matching are triples (containing the label as the third element), otherwise the edges are pairs.

See also

matching()

EXAMPLES:

Sage

sage: G=graphs.GridGraph([2,3])
sage: for m in G.perfect_matchings():
....: print(sorted(m))
[((0, 0), (0, 1)), ((0, 2), (1, 2)), ((1, 0), (1, 1))]
[((0, 0), (1, 0)), ((0, 1), (0, 2)), ((1, 1), (1, 2))]
[((0, 0), (1, 0)), ((0, 1), (1, 1)), ((0, 2), (1, 2))]
sage: G = graphs.CompleteGraph(4)
sage: for m in G.perfect_matchings(labels=True):
....: print(sorted(m))
[(0, 1, None), (2, 3, None)]
[(0, 2, None), (1, 3, None)]
[(0, 3, None), (1, 2, None)]
sage: G = Graph([[1,-1,'a'], [2,-2, 'b'], [1,-2,'x'], [2,-1,'y']])
sage: sorted(sorted(m) for m in G.perfect_matchings(labels=True))
[[(-2, 1, 'x'), (-1, 2, 'y')], [(-2, 2, 'b'), (-1, 1, 'a')]]
sage: G = graphs.CompleteGraph(8)
sage: mpc = G.matching_polynomial().coefficients(sparse=False)[0] # needs sage.libs.flint
sage: len(list(G.perfect_matchings())) == mpc # needs sage.libs.flint
True
sage: G = graphs.PetersenGraph().copy(immutable=True)
sage: [sorted(m) for m in G.perfect_matchings()]
[[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)],
 [(0, 1), (2, 7), (3, 4), (5, 8), (6, 9)],
 [(0, 4), (1, 2), (3, 8), (5, 7), (6, 9)],
 [(0, 4), (1, 6), (2, 3), (5, 8), (7, 9)],
 [(0, 5), (1, 2), (3, 4), (6, 8), (7, 9)],
 [(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]]
sage: list(Graph().perfect_matchings())
[[]]
sage: G = graphs.CompleteGraph(5)
sage: list(G.perfect_matchings())
[]

Python

>>> from sage.all import *
>>> G=graphs.GridGraph([Integer(2),Integer(3)])
>>> for m in G.perfect_matchings():
... print(sorted(m))
[((0, 0), (0, 1)), ((0, 2), (1, 2)), ((1, 0), (1, 1))]
[((0, 0), (1, 0)), ((0, 1), (0, 2)), ((1, 1), (1, 2))]
[((0, 0), (1, 0)), ((0, 1), (1, 1)), ((0, 2), (1, 2))]
>>> G = graphs.CompleteGraph(Integer(4))
>>> for m in G.perfect_matchings(labels=True):
... print(sorted(m))
[(0, 1, None), (2, 3, None)]
[(0, 2, None), (1, 3, None)]
[(0, 3, None), (1, 2, None)]
>>> G = Graph([[Integer(1),-Integer(1),'a'], [Integer(2),-Integer(2), 'b'], [Integer(1),-Integer(2),'x'], [Integer(2),-Integer(1),'y']])
>>> sorted(sorted(m) for m in G.perfect_matchings(labels=True))
[[(-2, 1, 'x'), (-1, 2, 'y')], [(-2, 2, 'b'), (-1, 1, 'a')]]
>>> G = graphs.CompleteGraph(Integer(8))
>>> mpc = G.matching_polynomial().coefficients(sparse=False)[Integer(0)] # needs sage.libs.flint
>>> len(list(G.perfect_matchings())) == mpc # needs sage.libs.flint
True
>>> G = graphs.PetersenGraph().copy(immutable=True)
>>> [sorted(m) for m in G.perfect_matchings()]
[[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)],
 [(0, 1), (2, 7), (3, 4), (5, 8), (6, 9)],
 [(0, 4), (1, 2), (3, 8), (5, 7), (6, 9)],
 [(0, 4), (1, 6), (2, 3), (5, 8), (7, 9)],
 [(0, 5), (1, 2), (3, 4), (6, 8), (7, 9)],
 [(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]]
>>> list(Graph().perfect_matchings())
[[]]
>>> G = graphs.CompleteGraph(Integer(5))
>>> list(G.perfect_matchings())
[]