Matching covered graphs

This module implements functions and operations pertaining to matching covered 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. A connected nontrivial graph is called matching covered if each edge participates in some perfect matching.

Miscellaneous methods

get_matching()

Return an EdgesView of self._matching.

update_matching()

Update the perfect matching captured in self._matching.

Overwritten methods

add_edge()

Add an edge from vertex u to vertex v.

add_edges()

Add edges from an iterable container.

add_vertex()

Add a vertex to the (matching covered) graph.

add_vertices()

Add vertices to the (matching covered) graph from an iterable container of vertices.

allow_loops()

Change whether loops are allowed in (matching covered) graphs.

allows_loops()

Return whether loops are permitted in (matching covered) graphs.

delete_vertex()

Delete a vertex, removing all incident edges.

delete_vertices()

Delete specified vertices form self.

has_perfect_matching()

Check whether the graph has a perfect matching.

REFERENCES:

  • This methods of this module has been adopted and inspired by the book of Lucchesi and Murty — Perfect Matchings: a theory of matching covered graphs [LM2024].

AUTHORS:

  • Janmenjaya Panda (2024-06-14): initial version

Todo

The following methods are to be incorporated in MatchingCoveredGraph:

__hash__()

Compute a hash for self, if self is immutable.

_subgraph_by_deleting()

Return the matching covered subgraph containing the provided vertices and edges.

Overwritten Methods

add_clique()

Add a clique to the graph with the provided vertices.

add_cycle()

Add a cycle to the graph with the provided vertices.

add_path()

Add a path to the graph with the provided vertices.

cartesian_product()

Return the Cartesian product of self and other.

clear()

Empties the graph of vertices and edges and removes name, associated objects, and position information.

complement()

Return the complement of the graph.

contract_edge()

Contract an edge from u to v.

contract_edges()

Contract edges from an iterable container.

degree_constrained_subgraph()

Return a degree-constrained matching covered subgraph.

delete_edge()

Delete the edge from u to v.

delete_edges()

Delete edges from an iterable container.

delete_multiedge()

Delete all edges from u to v.

disjoint_union()

Return the disjoint union of self and other.

disjunctive_product()

Return the disjunctive product of self and other.

has_loops()

Return whether there are loops in the matching covered graph.

is_biconnected()

Check if the matching covered graph is biconnected.

is_block_graph()

Check whether the matching covered graph is a block graph.

is_cograph()

Check whether the matching covered graph is cograph.

is_forest()

Check if the matching covered graph is a forest, i.e. a disjoint union of trees.

is_matching_covered()

Check if the graph is matching covered.

is_path()

Check whether the graph is a path.

is_subgraph()

Check whether the matching covered graph is a subgraph of other.

is_tree()

Check whether the matching covered graph is a tree.

join()

Return the join of self and other.

lexicographic_product()

Return the lexicographic product of self and other.

load_afile()

Load the matching covered graph specified in the given file into the current object.

loop_edges()

Return a list of all loops in the matching covered graph.

loop_vertices()

Return a list of vertices with loops.

merge_vertices()

Merge vertices.

number_of_loops()

Return the number of edges that are loops.

random_subgraph()

Return a random matching covered subgraph containing each vertex with probability p.

remove_loops()

Remove loops on vertices in vertices.

save_afile()

Save the graph to file in alist format.

strong_product()

Return the strong product of self and other.

subdivide_edge()

Subdivide an edge \(k\) times.

subdivide_edges()

Subdivide \(k\) times edges from an iterable container.

subgraph()

Return the matching covered subgraph containing the given vertices and edges.

subgraph_search()

Return a copy of (matching covered) G in self.

subgraph_search_count()

Return the number of labelled occurrences of (matching covered) G in self.

subgraph_search_iterator()

Return an iterator over the labelled copies of (matching covered) G in self.

tensor_product()

Return the tensor product of self and other.

to_undirected()

Return an undirected Graph instance of the matching covered graph.

transitive_closure()

Return the transitive closure of the matching covered graph.

transitive_reduction()

Return a transitive reduction of the matching covered graph.

union()

Return the union of self and other.

Barriers and canonical partition

canonical_partition()

Return the canonical partition of the (matching covered) graph.

maximal_barrier()

Return the (unique) maximal barrier of the (matching covered) graph containing the (provided) vertex.

Bricks, braces and tight cut decomposition

bricks_and_braces()

Return the list of (underlying simple graph of) the bricks and braces of the (matching covered) graph.

is_brace()

Check if the (matching covered) graph is a brace.

is_brick()

Check if the (matching covered) graph is a brick.

number_of_braces()

Return the number of braces.

number_of_bricks()

Return the number of bricks.

number_of_petersen_bricks()

Return the number of Petersen bricks.

tight_cut_decomposition()

Return a tight cut decomposition.

Removability and ear decomposition

add_ear()

Add an ear to the graph with the provided end vertices number of internal vertices.

bisubdivide_edge()

Bisubdivide an edge \(k\) times.

bisubdivide_edges()

Bisubdivide \(k\) times edges from an iterable container.

efficient_ear_decomposition()

Return a matching covered ear decomposition computed at the fastest possible time.

is_removable_double_ear()

Check whether the pair of ears form a removable double ear.

is_removable_doubleton()

Check whether the pair of edges constitute a removable doubleton.

is_removable_ear()

Check whether the ear is removable.

is_removable_edge()

Check whether the edge is removable.

optimal_ear_decomposition()

Return an optimal ear decomposition.

removable_double_ears()

Return a list of removable double ears.

removable_doubletons()

Return a list of removable doubletons.

removable_ears()

Return a list of removable ears.

removable_edges()

Return a EdgesView of removable edges.

retract()

Compute the retract of the (matching covered) graph.

Generating bricks and braces

brace_generation_sequence()

Return a McCuaig brace generation sequence of the (provided) brace.

brick_generation_sequence()

Return a Norine-Thomas brick generation sequence of the (provided) brick.

is_mccuaig_brace()

Check if the brace is a McCuaig brace.

is_norine_thomas_brick()

Check if the brick is a Norine-Thomas brick.

Methods

class sage.graphs.matching_covered_graph.MatchingCoveredGraph(data=None, matching=None, algorithm='Edmonds', solver=None, verbose=0, integrality_tolerance=0.001, *args, **kwds)[source]

Bases: Graph

Matching covered graph

INPUT:

  • data – can be any of the following:

    • Empty or None (throws a ValueError as the graph must be nontrival).

    • An arbitrary graph.

  • 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.

  • 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:

  • An object of the class MatchingCoveredGraph if the input is valid and the graph is matching covered, or otherwise an error is thrown.

Note

All remaining arguments are passed to the Graph constructor

EXAMPLES:

Generating an object of the class MatchingCoveredGraph from the provided instance of Graph without providing any other information:

sage: G = MatchingCoveredGraph(graphs.PetersenGraph())
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: G = graphs.StaircaseGraph(4)
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered staircase graph: graph on 8 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 1, None), (2, 7, None), (3, 6, None), (4, 5, None)]

sage: G = Graph({0: [1, 2, 3, 4], 1: [2, 5],
....:            2: [5], 3: [4, 5], 4: [5]})
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 6 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 4, None), (1, 2, None), (3, 5, None)]

sage: # needs networkx
sage: import networkx
sage: G = Graph(networkx.complete_bipartite_graph(12, 12))
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 24 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 15, None), (1, 14, None), (2, 13, None), (3, 12, None),
 (4, 23, None), (5, 22, None), (6, 21, None), (7, 20, None),
 (8, 19, None), (9, 18, None), (10, 17, None), (11, 16, None)]

sage: G = Graph('E|fG', sparse=True)
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 6 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 2, None), (3, 4, None)]

sage: # needs sage.modules
sage: M = Matrix([(0,1,0,0,1,1,0,0,0,0),
....:             (1,0,1,0,0,0,1,0,0,0),
....:             (0,1,0,1,0,0,0,1,0,0),
....:             (0,0,1,0,1,0,0,0,1,0),
....:             (1,0,0,1,0,0,0,0,0,1),
....:             (1,0,0,0,0,0,0,1,1,0),
....:             (0,1,0,0,0,0,0,0,1,1),
....:             (0,0,1,0,0,1,0,0,0,1),
....:             (0,0,0,1,0,1,1,0,0,0),
....:             (0,0,0,0,1,0,1,1,0,0)])
sage: M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = Graph(M)
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: # needs sage.modules
sage: M = Matrix([(-1, 0, 0, 0, 1, 0, 0, 0, 0, 0,-1, 0, 0, 0, 0),
....:             ( 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 0),
....:             ( 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0),
....:             ( 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0),
....:             ( 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1),
....:             ( 0, 0, 0, 0, 0,-1, 0, 0, 0, 1, 1, 0, 0, 0, 0),
....:             ( 0, 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 1, 0, 0, 0),
....:             ( 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 1, 0, 0),
....:             ( 0, 0, 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 1, 0),
....:             ( 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 1)])
sage: M
[-1  0  0  0  1  0  0  0  0  0 -1  0  0  0  0]
[ 1 -1  0  0  0  0  0  0  0  0  0 -1  0  0  0]
[ 0  1 -1  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  1 -1  0  0  0  0  0  0  0  0  0 -1  0]
[ 0  0  0  1 -1  0  0  0  0  0  0  0  0  0 -1]
[ 0  0  0  0  0 -1  0  0  0  1  1  0  0  0  0]
[ 0  0  0  0  0  0  0  1 -1  0  0  1  0  0  0]
[ 0  0  0  0  0  1 -1  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  1 -1  0  0  0  1  0]
[ 0  0  0  0  0  0  1 -1  0  0  0  0  0  0  1]
sage: G = Graph(M)
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: G = Graph([(0, 1), (0, 3), (0, 4), (1, 2), (1, 5), (2, 3),
....:            (2, 6), (3, 7), (4, 5), (4, 7), (5, 6), (6, 7)])
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 4, None), (1, 5, None), (2, 6, None), (3, 7, None)]

sage: # optional - python_igraph
sage: import igraph
sage: G = Graph(igraph.Graph([(0, 1), (0, 3), (1, 2), (2, 3)]))
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 4 vertices
sage: sorted(H.get_matching())
[(0, 3, {}), (1, 2, {})]

>>> from sage.all import *
>>> G = MatchingCoveredGraph(graphs.PetersenGraph())
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> G = graphs.StaircaseGraph(Integer(4))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered staircase graph: graph on 8 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 1, None), (2, 7, None), (3, 6, None), (4, 5, None)]

>>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3), Integer(4)], Integer(1): [Integer(2), Integer(5)],
...            Integer(2): [Integer(5)], Integer(3): [Integer(4), Integer(5)], Integer(4): [Integer(5)]})
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 6 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 4, None), (1, 2, None), (3, 5, None)]

>>> # needs networkx
>>> import networkx
>>> G = Graph(networkx.complete_bipartite_graph(Integer(12), Integer(12)))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 24 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 15, None), (1, 14, None), (2, 13, None), (3, 12, None),
 (4, 23, None), (5, 22, None), (6, 21, None), (7, 20, None),
 (8, 19, None), (9, 18, None), (10, 17, None), (11, 16, None)]

>>> G = Graph('E|fG', sparse=True)
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 6 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 2, None), (3, 4, None)]

>>> # needs sage.modules
>>> M = Matrix([(Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)),
...             (Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)),
...             (Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0)),
...             (Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0)),
...             (Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)),
...             (Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0)),
...             (Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1)),
...             (Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1)),
...             (Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)),
...             (Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0))])
>>> M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
>>> G = Graph(M)
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> # needs sage.modules
>>> M = Matrix([(-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1))])
>>> M
[-1  0  0  0  1  0  0  0  0  0 -1  0  0  0  0]
[ 1 -1  0  0  0  0  0  0  0  0  0 -1  0  0  0]
[ 0  1 -1  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  1 -1  0  0  0  0  0  0  0  0  0 -1  0]
[ 0  0  0  1 -1  0  0  0  0  0  0  0  0  0 -1]
[ 0  0  0  0  0 -1  0  0  0  1  1  0  0  0  0]
[ 0  0  0  0  0  0  0  1 -1  0  0  1  0  0  0]
[ 0  0  0  0  0  1 -1  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  1 -1  0  0  0  1  0]
[ 0  0  0  0  0  0  1 -1  0  0  0  0  0  0  1]
>>> G = Graph(M)
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)), (Integer(1), Integer(5)), (Integer(2), Integer(3)),
...            (Integer(2), Integer(6)), (Integer(3), Integer(7)), (Integer(4), Integer(5)), (Integer(4), Integer(7)), (Integer(5), Integer(6)), (Integer(6), Integer(7))])
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 4, None), (1, 5, None), (2, 6, None), (3, 7, None)]

>>> # optional - python_igraph
>>> import igraph
>>> G = Graph(igraph.Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(1), Integer(2)), (Integer(2), Integer(3))]))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 4 vertices
>>> sorted(H.get_matching())
[(0, 3, {}), (1, 2, {})]

One may specify a perfect matching:

sage: P = graphs.PetersenGraph()
sage: M = P.matching()
sage: sorted(M)
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: G = MatchingCoveredGraph(P, matching=M)
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: P == G
True
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: sorted(G.get_matching()) == sorted(M)
True

sage: G = graphs.TruncatedBiwheelGraph(14)
sage: M = G.matching()
sage: sorted(M)
[(0, 27, None), (1, 26, None), (2, 3, None), (4, 5, None),
 (6, 7, None), (8, 9, None), (10, 11, None), (12, 13, None),
 (14, 15, None), (16, 17, None), (18, 19, None), (20, 21, None),
 (22, 23, None), (24, 25, None)]
sage: H = MatchingCoveredGraph(G, M)
sage: H
Matching covered truncated biwheel graph: graph on 28 vertices
sage: H == G
True
sage: sorted(H.get_matching()) == sorted(M)
True

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = P.matching()
>>> sorted(M)
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> G = MatchingCoveredGraph(P, matching=M)
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> P == G
True
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> sorted(G.get_matching()) == sorted(M)
True

>>> G = graphs.TruncatedBiwheelGraph(Integer(14))
>>> M = G.matching()
>>> sorted(M)
[(0, 27, None), (1, 26, None), (2, 3, None), (4, 5, None),
 (6, 7, None), (8, 9, None), (10, 11, None), (12, 13, None),
 (14, 15, None), (16, 17, None), (18, 19, None), (20, 21, None),
 (22, 23, None), (24, 25, None)]
>>> H = MatchingCoveredGraph(G, M)
>>> H
Matching covered truncated biwheel graph: graph on 28 vertices
>>> H == G
True
>>> sorted(H.get_matching()) == sorted(M)
True

One may specify some keyword arguments:

sage: G = Graph([(0, 1, 5)], {'weighted': True})
sage: kwds = {
....:   'loops': False,
....:   'multiedges': True,
....:   'pos': {0: (0, 0), 1: (1, 1)}
....: }
sage: H = MatchingCoveredGraph(G, **kwds)
sage: H
Matching covered multi-graph on 2 vertices
sage: H.add_edge(0, 1)
sage: H.edges()
[(0, 1, None), (0, 1, 5)]

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), Integer(5))], {'weighted': True})
>>> kwds = {
...   'loops': False,
...   'multiedges': True,
...   'pos': {Integer(0): (Integer(0), Integer(0)), Integer(1): (Integer(1), Integer(1))}
... }
>>> H = MatchingCoveredGraph(G, **kwds)
>>> H
Matching covered multi-graph on 2 vertices
>>> H.add_edge(Integer(0), Integer(1))
>>> H.edges()
[(0, 1, None), (0, 1, 5)]
add_edge(u, v=None, label=None)[source]

Add an edge from vertex u to vertex v.

Note

This method overwrites the add_edge() method to ensure that resultant graph is also matching covered.

INPUT:

The following forms are all accepted:

  • G.add_edge(1, 2)

  • G.add_edge((1, 2))

  • G.add_edges([(1, 2)])

  • G.add_edge(1, 2, ‘label’)

  • G.add_edge((1, 2, ‘label’))

  • G.add_edges([(1, 2, ‘label’)])

OUTPUT:

  • If an edge is provided with a valid format, but addition of the edge leaves the resulting graph not being matching covered, a ValueError is returned without any alteration to the existing matching covered graph. If the addition of the edge preserves the property of matching covered, then the graph is updated and nothing is returned.

  • If the edge is provided with an invalid format, a ValueError is returned.

WARNING:

The following intuitive input results in nonintuitive output, even though the resulting graph behind the intuition might be matching covered:

sage: P = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge((1, 4), 'label')
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((1, 4), 'label', None)) is not matching covered
sage: G.edges(sort=False)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

>>> from sage.all import *
>>> P = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge((Integer(1), Integer(4)), 'label')
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((1, 4), 'label', None)) is not matching covered
>>> G.edges(sort=False)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

The key word label must be used:

sage: W = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(W)
sage: G.add_edge((1, 4), label='label')
sage: G.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 4, 'label'), (1, 5, None),
 (2, 3, None), (3, 4, None), (4, 5, None)]

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(W)
>>> G.add_edge((Integer(1), Integer(4)), label='label')
>>> G.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 4, 'label'), (1, 5, None),
 (2, 3, None), (3, 4, None), (4, 5, None)]

An expression, analogous to the syntax mentioned above may be used:

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: G.add_edge(0, 5)
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
sage: G.add_edge((2, 3))
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 3, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (5, 7, None), (6, 7, None)]
sage: G.add_edges([(0, 4)])
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]
sage: G.add_edge(2, 4, 'label')
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (5, 7, None), (6, 7, None)]
sage: G.add_edge((4, 6, 'label'))
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (5, 7, None),
 (6, 7, None)]
sage: G.add_edges([(4, 7, 'label')])
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (4, 7, 'label'),
 (5, 7, None), (6, 7, None)]

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> G.add_edge(Integer(0), Integer(5))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
>>> G.add_edge((Integer(2), Integer(3)))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 3, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (5, 7, None), (6, 7, None)]
>>> G.add_edges([(Integer(0), Integer(4))])
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]
>>> G.add_edge(Integer(2), Integer(4), 'label')
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (5, 7, None), (6, 7, None)]
>>> G.add_edge((Integer(4), Integer(6), 'label'))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (5, 7, None),
 (6, 7, None)]
>>> G.add_edges([(Integer(4), Integer(7), 'label')])
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (4, 7, 'label'),
 (5, 7, None), (6, 7, None)]

Note that the weight of the edge shall be input as the label:

sage: G.add_edge((1, 3), label=5)
sage: G.edges()
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 3, 5), (1, 4, None),
 (2, 3, None), (2, 4, 'label'), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 6, 'label'),
 (4, 7, 'label'), (5, 7, None), (6, 7, None)]
sage: G.add_edge((2, 4, 6), label=6)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((2, 4, 6), None, 6)) is not matching covered

>>> from sage.all import *
>>> G.add_edge((Integer(1), Integer(3)), label=Integer(5))
>>> G.edges()
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 3, 5), (1, 4, None),
 (2, 3, None), (2, 4, 'label'), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 6, 'label'),
 (4, 7, 'label'), (5, 7, None), (6, 7, None)]
>>> G.add_edge((Integer(2), Integer(4), Integer(6)), label=Integer(6))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((2, 4, 6), None, 6)) is not matching covered

Vertex name cannot be None, so:

sage: W = graphs.WheelGraph(6)
sage: H = MatchingCoveredGraph(W)
sage: H.add_edge(None, 1)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, 1, None)) is not matching covered
sage: H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]
sage: H.add_edge(None, None)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, None, None)) is not matching covered
sage: H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> H = MatchingCoveredGraph(W)
>>> H.add_edge(None, Integer(1))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, 1, None)) is not matching covered
>>> H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]
>>> H.add_edge(None, None)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, None, None)) is not matching covered
>>> H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

EXAMPLES:

Adding an already existing edge:

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge(next(G.edge_iterator()))
sage: P == G
True
sage: G.size()
15
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 1)
sage: G.size()
16

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge(next(G.edge_iterator()))
>>> P == G
True
>>> G.size()
15
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(1))
>>> G.size()
16

Adding an edge such that the resulting graph is matching covered:

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge(1, 4)
sage: G.edges(sort=False)
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None),
 (1, 4, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None),
 (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge(Integer(1), Integer(4))
>>> G.edges(sort=False)
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None),
 (1, 4, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None),
 (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]

Adding an edge with both the incident vertices being existent such that the resulting graph is not matching covered:

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(0, 2)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 2, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(0), Integer(2))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 2, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding an edge with exactly one incident vertex that is nonexistent throws a ValueError exception, as the resulting graph would have an odd order:

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(0, 4)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 4, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(0), Integer(4))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 4, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding an edge with both the incident vertices that is nonexistent throws a ValueError exception, as the resulting graph would have been disconnected:

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(4, 5)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((4, 5, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(4), Integer(5))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((4, 5, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding a self-loop:

sage: H = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(H)
sage: v = next(G.vertex_iterator())
sage: G.add_edge(v, v)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

>>> from sage.all import *
>>> H = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(H)
>>> v = next(G.vertex_iterator())
>>> G.add_edge(v, v)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
add_edges(edges, loops=False)[source]

Add edges from an iterable container.

Note

This method overwrites the add_edges() method to ensure that resultant graph is also matching covered.

INPUT:

  • edges – an iterable of edges, given either as (u, v) or (u, v, 'label')

  • loops – boolean (default: False); note that this shall always be set to either False or None (since matching covered graphs are free of loops), in which case all the loops (v, v, 'label') are removed from the iterator. If loops is set to True, a ValueError is thrown.

OUTPUT:

  • If loops is set to True, a ValueError is returned.

  • If edges is provided with a valid format, but addition of the edges leave the resulting graph not being matching covered, a ValueError is returned without any alteration to the existing matching covered graph. If the addition of the edges preserves the property of matching covered, then the graph is updated and nothing is returned.

  • If edges is provided with an invalid format, a ValueError is returned.

EXAMPLES:

Providing with an empty list of edges:

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edges([])
sage: G == C
True

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edges([])
>>> G == C
True

Adding some edges, the incident vertices of each of which are existent, such that the resulting graph is matching covered:

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: F = [(0, 4), (2, 4), (4, 6), (4, 7)]
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 4, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (4, 6, None), (4, 7, None), (5, 7, None), (6, 7, None)]

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> F = [(Integer(0), Integer(4)), (Integer(2), Integer(4)), (Integer(4), Integer(6)), (Integer(4), Integer(7))]
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 4, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (4, 6, None), (4, 7, None), (5, 7, None), (6, 7, None)]

Adding some edges, at least one of the incident vertices of some of which are nonexistent such that the resulting graph is matching covered:

sage: C = graphs.CycleGraph(8)
sage: G = MatchingCoveredGraph(C)
sage: F = [(0, 9), (1, 8), (2, 9), (3, 8),
....:      (4, 9), (5, 8), (6, 9), (7, 8)]
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 7, None), (0, 9, None), (1, 2, None),
 (1, 8, None), (2, 3, None), (2, 9, None), (3, 4, None),
 (3, 8, None), (4, 5, None), (4, 9, None), (5, 6, None),
 (5, 8, None), (6, 7, None), (6, 9, None), (7, 8, None)]
sage: G.is_isomorphic(graphs.BiwheelGraph(5))
True

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(8))
>>> G = MatchingCoveredGraph(C)
>>> F = [(Integer(0), Integer(9)), (Integer(1), Integer(8)), (Integer(2), Integer(9)), (Integer(3), Integer(8)),
...      (Integer(4), Integer(9)), (Integer(5), Integer(8)), (Integer(6), Integer(9)), (Integer(7), Integer(8))]
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 7, None), (0, 9, None), (1, 2, None),
 (1, 8, None), (2, 3, None), (2, 9, None), (3, 4, None),
 (3, 8, None), (4, 5, None), (4, 9, None), (5, 6, None),
 (5, 8, None), (6, 7, None), (6, 9, None), (7, 8, None)]
>>> G.is_isomorphic(graphs.BiwheelGraph(Integer(5)))
True

Adding a removable double ear to a matching covered graph:

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: F = {(0, 8, None), (1, 10), (4, 11, 'label'),
....:      (5, 9), (8, 9), (10, 11)}
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 8, None),
 (1, 2, None), (1, 5, None), (1, 10, None), (2, 3, None),
 (2, 6, None), (3, 7, None), (4, 5, None), (4, 7, None),
 (4, 11, 'label'), (5, 6, None), (5, 9, None), (6, 7, None),
 (8, 9, None), (10, 11, None)]

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> F = {(Integer(0), Integer(8), None), (Integer(1), Integer(10)), (Integer(4), Integer(11), 'label'),
...      (Integer(5), Integer(9)), (Integer(8), Integer(9)), (Integer(10), Integer(11))}
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 8, None),
 (1, 2, None), (1, 5, None), (1, 10, None), (2, 3, None),
 (2, 6, None), (3, 7, None), (4, 5, None), (4, 7, None),
 (4, 11, 'label'), (5, 6, None), (5, 9, None), (6, 7, None),
 (8, 9, None), (10, 11, None)]

Adding some edges, the incident vertices of each of which are existent, such that the resulting graph is NOT matching covered:

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: F = [(0, 2), (3, 5)]
sage: G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> F = [(Integer(0), Integer(2)), (Integer(3), Integer(5))]
>>> G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered

Adding some edges, at least one of the incident vertices of some of which are nonexistent such that the resulting graph is NOT matching covered:

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: F = [(3, 8), (6, 9), (8, 9)]
sage: G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
sage: I = [(0, 8), (1, 9)]
sage: G.add_edges(I)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
sage: J = [(u, 8) for u in range(8)]
sage: G.add_edges(J)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> F = [(Integer(3), Integer(8)), (Integer(6), Integer(9)), (Integer(8), Integer(9))]
>>> G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
>>> I = [(Integer(0), Integer(8)), (Integer(1), Integer(9))]
>>> G.add_edges(I)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
>>> J = [(u, Integer(8)) for u in range(Integer(8))]
>>> G.add_edges(J)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

Setting the parameter loops to either False or None:

sage: W = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(W)
sage: F = [(0, 0), (1, 3), (2, 4)]
sage: G.add_edges(edges=F, loops=False)
sage: G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]
sage: J = [(1, 1), (3, 5)]
sage: G.add_edges(edges=J, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(W)
>>> F = [(Integer(0), Integer(0)), (Integer(1), Integer(3)), (Integer(2), Integer(4))]
>>> G.add_edges(edges=F, loops=False)
>>> G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]
>>> J = [(Integer(1), Integer(1)), (Integer(3), Integer(5))]
>>> G.add_edges(edges=J, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]

Setting the parameter loops to True:

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: F = [(0, 0), (0, 2), (0, 3)]
sage: G.add_edges(edges=F, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> F = [(Integer(0), Integer(0)), (Integer(0), Integer(2)), (Integer(0), Integer(3))]
>>> G.add_edges(edges=F, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Adding a multiple edge:

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: G.allow_multiple_edges(True)
sage: F = [(0, 1, 'label'), (0, 4), (1, 2)]
sage: G.add_edges(F)
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 4, None),
 (0, 6, None), (1, 2, None), (1, 2, None), (1, 4, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> G.allow_multiple_edges(True)
>>> F = [(Integer(0), Integer(1), 'label'), (Integer(0), Integer(4)), (Integer(1), Integer(2))]
>>> G.add_edges(F)
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 4, None),
 (0, 6, None), (1, 2, None), (1, 2, None), (1, 4, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]
add_vertex(name=None)[source]

Add a vertex to the (matching covered) graph.

Note

This method overwrites the add_vertex() method to ensure that isolated vertices are forbidden in MatchingCoveredGraph.

INPUT:

  • name – an immutable object (default: None); when no name is specified (default), then the new vertex will be represented by the least integer not already representing a vertex. name must be an immutable object (e.g., an integer, a tuple, etc.).

OUTPUT:

  • If name specifies an existing vertex, then nothing is done. Otherwise a ValueError is returned with no change to the existing (matching covered) graph is returned since matching covered graphs are free of isolated vertices.

EXAMPLES:

Adding an existing vertex:

sage: P = graphs.PetersenGraph()
sage: P
Petersen graph: Graph on 10 vertices
sage: G = MatchingCoveredGraph(P)
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: u = next(G.vertex_iterator())
sage: G.add_vertex(u)
sage: G
Matching covered petersen graph: graph on 10 vertices

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P
Petersen graph: Graph on 10 vertices
>>> G = MatchingCoveredGraph(P)
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> u = next(G.vertex_iterator())
>>> G.add_vertex(u)
>>> G
Matching covered petersen graph: graph on 10 vertices

Adding a new/ non-existing vertex:

sage: G.add_vertex()
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: u = 100
sage: G.add_vertex(u)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

>>> from sage.all import *
>>> G.add_vertex()
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> u = Integer(100)
>>> G.add_vertex(u)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
add_vertices(vertices)[source]

Add vertices to the (matching covered) graph from an iterable container of vertices.

Note

This method overwrites the add_vertices() method to ensure that isolated vertices are forbidden in MatchingCoveredGraph.

INPUT:

  • vertices – iterator container of vertex labels. A new label is created, used and returned in the output list for all None values in vertices.

OUTPUT:

  • If all of the vertices are existing vertices of the (matching covered) graph, then nothing is done; otherwise a ValueError is returned with no change to the existing (matching covered) graph since matching covered graphs are free of isolated vertices.

EXAMPLES:

Adding a list of already existing vertices:

sage: T = graphs.TruncatedBiwheelGraph(15)
sage: T
Truncated biwheel graph: Graph on 30 vertices
sage: G = MatchingCoveredGraph(T)
sage: G
Matching covered truncated biwheel graph: graph on 30 vertices
sage: S = [0, 1, 2, 3]  # We choose 4 existing vertices
sage: G.add_vertices(S)
sage: G
Matching covered truncated biwheel graph: graph on 30 vertices

>>> from sage.all import *
>>> T = graphs.TruncatedBiwheelGraph(Integer(15))
>>> T
Truncated biwheel graph: Graph on 30 vertices
>>> G = MatchingCoveredGraph(T)
>>> G
Matching covered truncated biwheel graph: graph on 30 vertices
>>> S = [Integer(0), Integer(1), Integer(2), Integer(3)]  # We choose 4 existing vertices
>>> G.add_vertices(S)
>>> G
Matching covered truncated biwheel graph: graph on 30 vertices

Adding a list of vertices in which at least one is non-existent or None or possibly both:

sage: T = graphs.CompleteGraph(2)
sage: T
Complete graph: Graph on 2 vertices
sage: G = MatchingCoveredGraph(T)
sage: G
Matching covered complete graph: graph on 2 vertices
sage: S1 = [2, 3, 4]
sage: G.add_vertices(S1)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: S2 = [None, None]
sage: G.add_vertices(S2)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: S3 = [2, None, None, 5]
sage: G.add_vertices(S3)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

>>> from sage.all import *
>>> T = graphs.CompleteGraph(Integer(2))
>>> T
Complete graph: Graph on 2 vertices
>>> G = MatchingCoveredGraph(T)
>>> G
Matching covered complete graph: graph on 2 vertices
>>> S1 = [Integer(2), Integer(3), Integer(4)]
>>> G.add_vertices(S1)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> S2 = [None, None]
>>> G.add_vertices(S2)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> S3 = [Integer(2), None, None, Integer(5)]
>>> G.add_vertices(S3)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
allow_loops(new, check=True)[source]

Change whether loops are allowed in (matching covered) graphs.

Note

This method overwrites the allow_loops() method to ensure that loops are forbidden in MatchingCoveredGraph.

INPUT:

  • new – boolean

  • check – boolean (default: True); whether to remove existing loops from the graph when the new status is False. It is an argument in allow_loops() method and is not used in this overwritten one.

OUTPUT:

  • A ValueError is returned with no change to the existing (matching covered) graph if new is True since a matching covered graph, by definition, is free of self-loops. If new is set to False, there is no output.

EXAMPLES:

Petersen graph is matching covered:

sage: P = graphs.PetersenGraph()
sage: P.is_matching_covered()
True
sage: G = MatchingCoveredGraph(P)
sage: G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.is_matching_covered()
True
>>> G = MatchingCoveredGraph(P)
>>> G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
allows_loops()[source]

Return whether loops are permitted in (matching covered) graphs.

Note

This method overwrites the allows_loops() method to show that loops are forbidden in MatchingCoveredGraph.

OUTPUT:

  • A boolean value False is returned, since matching covered graphs, by definition, are free of loops.

EXAMPLES:

Petersen graph is matching covered:

sage: P = graphs.PetersenGraph()
sage: P.is_matching_covered()
True
sage: G = MatchingCoveredGraph(P)
sage: G.allows_loops()
False

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.is_matching_covered()
True
>>> G = MatchingCoveredGraph(P)
>>> G.allows_loops()
False
delete_vertex(vertex, in_order=False)[source]

Delete a vertex, removing all incident edges.

Note

This method overwrites the delete_vertex() method to ensure that an odd order is forbidden in MatchingCoveredGraph.

INPUT:

  • vertex – a vertex that is to be deleted.

  • in_order – boolean (default: False); if True, this deletes the \(i\)-th vertex in the sorted list of vertices, i.e. G.vertices(sort=True)[i]

OUTPUT:

  • Deleting a non-existent vertex raises a ValueError exception; also a (different) ValueError is returned on deleting an existing vertex since matching covered graphs are of even order. In both cases no modifications are made to the existing (matching covered) graph.

EXAMPLES:

Deleting a non-existent vertex:

sage: W = graphs.WheelGraph(12)
sage: G = MatchingCoveredGraph(W)
sage: u = 100
sage: G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph
sage: G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(12))
>>> G = MatchingCoveredGraph(W)
>>> u = Integer(100)
>>> G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph
>>> G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph

Deleting an existing vertex:

sage: W = graphs.WheelGraph(12)
sage: G = MatchingCoveredGraph(W)
sage: u = next(G.vertex_iterator())
sage: G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs
sage: G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(12))
>>> G = MatchingCoveredGraph(W)
>>> u = next(G.vertex_iterator())
>>> G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs
>>> G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs
delete_vertices(vertices)[source]

Delete specified vertices form self.

This method deletes the vertices from the iterable container vertices from self along with incident edges. An error is raised if the resulting graph is not matching covered.

Note

This method overwrites the delete_vertices() method to ensure that an odd order is forbidden in MatchingCoveredGraph.

INPUT:

  • vertices – a list/ set of vertices that are to be deleted.

OUTPUT:

  • Deleting a non-existent vertex will raise a ValueError exception, in which case none of the vertices in vertices is deleted.

  • If all of the vertices in the list/ set provided exist in the graph, but the resulting graph after deletion of all of those is not matching covered, then a ValueError exception is raised without any alterations to the existing (matching covered) graph, otherwise the vertices are deleted and nothing is returned.

EXAMPLES:

Providing with an empty list of vertices:

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: G.delete_vertices([])
sage: G == C
True

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> G.delete_vertices([])
>>> G == C
True

Removing all the existent vertices:

sage: M = graphs.MoebiusLadderGraph(10)
sage: G = MatchingCoveredGraph(M)
sage: S = list(G.vertices())
sage: G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of the vertices
is trivial, therefore is not matching covered

>>> from sage.all import *
>>> M = graphs.MoebiusLadderGraph(Integer(10))
>>> G = MatchingCoveredGraph(M)
>>> S = list(G.vertices())
>>> G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of the vertices
is trivial, therefore is not matching covered

Providing with a list of vertices with at least one non-existent vertex:

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = list(range(5, 20, 2))
sage: G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: vertex (9) not in the graph

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = list(range(Integer(5), Integer(20), Integer(2)))
>>> G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: vertex (9) not in the graph

Removing an odd no. of distinct vertices from a matching covered graph:

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: S = [0, 1, 2, 10, 10, 100]
sage: G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: an odd no. of distinct vertices can not be
removed from a matching covered graph

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> S = [Integer(0), Integer(1), Integer(2), Integer(10), Integer(10), Integer(100)]
>>> G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: an odd no. of distinct vertices can not be
removed from a matching covered graph

Providing with a list of existent vertices whose deletion results in a graph which is not matching covered:

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = [1, 4]
sage: G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of
the vertices is not matching covered

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = [Integer(1), Integer(4)]
>>> G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of
the vertices is not matching covered

Providing with a list of existent vertices after the deletion of which the resulting graph is still matching covered; note that in the following example, after the deletion of two vertices from a staircase graph, the resulting graph is NOT a staircase graph (see Issue #38768):

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = [6, 7]
sage: G.delete_vertices(T)
sage: G  # Matching covered graph on 6 vertices
Matching covered staircase graph: graph on 6 vertices

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = [Integer(6), Integer(7)]
>>> G.delete_vertices(T)
>>> G  # Matching covered graph on 6 vertices
Matching covered staircase graph: graph on 6 vertices
get_matching()[source]

Return an EdgesView of self._matching.

OUTPUT:

  • This method returns EdgesView of the edges of a perfect matching of the (matching covered) graph.

EXAMPLES:

If one specifies a perfect matching while initializing the object, the value of self._matching is captures the same matching:

sage: P = graphs.PetersenGraph()
sage: M = [(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: G = MatchingCoveredGraph(P, M)
sage: sorted(G.get_matching())
[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: M == sorted(G.get_matching())
True

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = [(Integer(0), Integer(1)), (Integer(2), Integer(3)), (Integer(4), Integer(9)), (Integer(5), Integer(7)), (Integer(6), Integer(8))]
>>> G = MatchingCoveredGraph(P, M)
>>> sorted(G.get_matching())
[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
>>> M == sorted(G.get_matching())
True

If no matching is specified while initilizing a matching covered graph, a perfect is computed matching() and that is captured as self._matching:

sage: P = graphs.PetersenGraph()
sage: M = P.matching()
sage: G = MatchingCoveredGraph(P)
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: sorted(M) == sorted(G.get_matching())
True

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = P.matching()
>>> G = MatchingCoveredGraph(P)
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> sorted(M) == sorted(G.get_matching())
True
has_perfect_matching(G, algorithm, solver='Edmonds', verbose=None, integrality_tolerance=0)[source]

Check whether the graph has a perfect matching.

Note

This method overwrites the has_perfect_matching() method in order to return True (provided the input arguments are valid) as matching covered graphs always admit 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:

  • If the input arguments are valid, a boolean (True) is returned as a maximum matching of a matching covered graph is always a perfect matching, otherwise a ValueError is raised.

EXAMPLES:

Note that regardless of the algorithm (as long as the input arguments are in valid format), the method always returns the boolean True:

sage: P = graphs.PetersenGraph()
sage: P.has_perfect_matching()  # Calls Graph.has_perfect_matching()
True
sage: G = MatchingCoveredGraph(P)
sage: G.has_perfect_matching()  # Calls MatchingCoveredGraph.has_perfect_matching()
True
sage: W = graphs.WheelGraph(6)
sage: H = MatchingCoveredGraph(W)
sage: H.has_perfect_matching(algorithm='LP_matching')
True

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.has_perfect_matching()  # Calls Graph.has_perfect_matching()
True
>>> G = MatchingCoveredGraph(P)
>>> G.has_perfect_matching()  # Calls MatchingCoveredGraph.has_perfect_matching()
True
>>> W = graphs.WheelGraph(Integer(6))
>>> H = MatchingCoveredGraph(W)
>>> H.has_perfect_matching(algorithm='LP_matching')
True

Providing with an algorithm, that is not one of 'Edmonds', 'LP_matching' or 'LP':

sage: S = graphs.StaircaseGraph(4)
sage: J = MatchingCoveredGraph(S)
sage: J.has_perfect_matching(algorithm='algorithm')
Traceback (most recent call last):
...
ValueError: algorithm must be set to 'Edmonds',
'LP_matching' or 'LP'

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> J = MatchingCoveredGraph(S)
>>> J.has_perfect_matching(algorithm='algorithm')
Traceback (most recent call last):
...
ValueError: algorithm must be set to 'Edmonds',
'LP_matching' or 'LP'
update_matching(matching)[source]

Update the perfect matching captured in self._matching.

INPUT:

  • matching – a perfect matching of the graph, that can be given using any valid input format of Graph.

OUTPUT:

  • If matching is a valid perfect matching of the graph, then self._matching gets updated to this provided matching, or otherwise an exception is returned without any alterations to self._matching.

EXAMPLES:

Providing with a valid perfect matching of the graph:

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: M = [(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: G.update_matching(M)
sage: sorted(G.get_matching())
[(0, 1, None), (2, 3, None), (4, 9, None), (5, 7, None), (6, 8, None)]

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> M = [(Integer(0), Integer(1)), (Integer(2), Integer(3)), (Integer(4), Integer(9)), (Integer(5), Integer(7)), (Integer(6), Integer(8))]
>>> G.update_matching(M)
>>> sorted(G.get_matching())
[(0, 1, None), (2, 3, None), (4, 9, None), (5, 7, None), (6, 8, None)]