Graph traversals¶

This module implements the following graph traversals

`lex_BFS()`	Perform a lexicographic breadth first search (LexBFS) on the graph.
`lex_DFS()`	Perform a lexicographic depth first search (LexDFS) on the graph.
`lex_UP()`	Perform a lexicographic UP search (LexUP) on the graph.
`lex_DOWN()`	Perform a lexicographic DOWN search (LexDOWN) on the graph.
`lex_M()`	Return an ordering of the vertices according the LexM graph traversal.
`lex_M_slow()`	Return an ordering of the vertices according the LexM graph traversal.
`lex_M_fast()`	Return an ordering of the vertices according the LexM graph traversal.
`maximum_cardinality_search()`	Return an ordering of the vertices according a maximum cardinality search.
`maximum_cardinality_search_M()`	Return the ordering and the edges of the triangulation produced by MCS-M.

ALGORITHM:

For lex_BFS() with algorithm="slow", lex_DFS(), lex_UP() and lex_DOWN() the same generic implementation is used. It corresponds to an implementation the generic algorithm described in “Algorithm 1” of [Mil2017].

This algorithm maintains for each vertex left in the graph a lexicographic label corresponding to the vertices already removed. The vertex of maximal lexicographic label is then removed, and the lexicographic labels of its neighbors are updated. Depending on how the update is done, it corresponds to LexBFS, LexUP, LexDFS or LexDOWN: during the \(i\)-th iteration of the algorithm \(n-i\) (for LexBFS and LexDOWN) or \(i\) (for LexDFS and LexUP) is appended (for LexBFS and LexUP) or prepended (for LexDFS and LexDOWN) to the lexicographic labels of all neighbors of the selected vertex that are left in the graph.

The time complexity of the algorithm is \(O(mn)\) for SparseGraph and \(O(\max\{mn, n^2\})\) for DenseGraph, where \(n\) is the number of vertices and \(m\) is the number of edges.

See [CK2008] and [Mil2017] for more details on the algorithm and graphs searching.

Methods¶

sage.graphs.traversals.is_valid_lex_M_order(G, alpha, F)[source]¶

Check whether the ordering alpha and the triangulation F are valid for G.

Given the graph \(G = (V, E)\) with vertex set \(V\) and edge set \(E\), and the set \(F\) of edges of a triangulation of \(G\), let \(H = (V, E\cup F)\). By induction one can see that for every \(i \in \{1, ..., n - 1\}\) the neighbors of \(\alpha(i)\) in \(H[\{\alpha(i), ..., \alpha(n)\}]\) induce a clique. The ordering \(\alpha\) is a perfect elimination ordering of \(H\), so \(H\) is chordal. See [RTL76] for more details.

INPUT:

G – a Graph
alpha – list; an ordering of the vertices of \(G\)
F – an iterable of edges given either as (u, v) or (u, v, label), the edges of the triangulation of \(G\)

sage.graphs.traversals.lex_BFS(G, reverse=False, tree=False, initial_vertex=None, algorithm='fast')[source]¶

Perform a lexicographic breadth first search (LexBFS) on the graph.

INPUT:

G – a sage graph
reverse – boolean (default: False); whether to return the vertices in discovery order, or the reverse
tree – boolean (default: False); whether to return the discovery directed tree (each vertex being linked to the one that saw it last)
initial_vertex – (default: None) the first vertex to consider
algorithm – string (default: 'fast'); algorithm to use among:
- 'slow' – it use the generic algorithm for all the lexicographic searchs. See the documentation of the traversals module for more details.
- 'fast' – this algorithm uses the notion of partition refinement to determine the position of the vertices in the ordering. The time complexity of this algorithm is in \(O(n + m)\), and our implementation follows that complexity for SparseGraph. For DenseGraph, the complexity is \(O(n^2)\). See [HMPV2000] and [TCHP2008] for more details. This algorithm is also used to compute slice decompositions of undirected graphs, a more thorough description can be found in the documentation of the slice_decomposition module.

Note

Loops and multiple edges are ignored during the computation of lex_BFS and directed graphs are converted to undirected graphs.

See also

Wikipedia article Lexicographic_breadth-first_search
slice_decomposition module and slice_decomposition() – compute a slice decomposition of the graph using an extended lex BFS algorithm
lex_DFS() – perform a lexicographic depth first search (LexDFS) on the graph
lex_UP() – perform a lexicographic UP search (LexUP) on the graph
lex_DOWN() – perform a lexicographic DOWN search (LexDOWN) on the graph

EXAMPLES:

A Lex BFS is obviously an ordering of the vertices:

Sage

sage: g = graphs.CompleteGraph(6)
sage: set(g.lex_BFS()) == set(g)
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> set(g.lex_BFS()) == set(g)
True

Sage Live

g = graphs.CompleteGraph(6)
set(g.lex_BFS()) == set(g)

Lex BFS ordering of the 3-sun graph:

Sage

sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: g.lex_BFS()
[1, 2, 3, 5, 4, 6]

Python

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> g.lex_BFS()
[1, 2, 3, 5, 4, 6]

Sage Live

g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
g.lex_BFS()

The method also works for directed graphs:

Sage

sage: G = DiGraph([(1, 2), (2, 3), (1, 3)])
sage: correct_anwsers = [[2, 1, 3], [2, 3, 1]]
sage: G.lex_BFS(initial_vertex=2, algorithm='slow') in correct_anwsers
True
sage: G.lex_BFS(initial_vertex=2, algorithm='fast') in correct_anwsers
True

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))])
>>> correct_anwsers = [[Integer(2), Integer(1), Integer(3)], [Integer(2), Integer(3), Integer(1)]]
>>> G.lex_BFS(initial_vertex=Integer(2), algorithm='slow') in correct_anwsers
True
>>> G.lex_BFS(initial_vertex=Integer(2), algorithm='fast') in correct_anwsers
True

Sage Live

G = DiGraph([(1, 2), (2, 3), (1, 3)])
correct_anwsers = [[2, 1, 3], [2, 3, 1]]
G.lex_BFS(initial_vertex=2, algorithm='slow') in correct_anwsers
G.lex_BFS(initial_vertex=2, algorithm='fast') in correct_anwsers

For a Chordal Graph, a reversed Lex BFS is a Perfect Elimination Order:

Sage

sage: g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2))
sage: g.lex_BFS(reverse=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]

Python

>>> from sage.all import *
>>> g = graphs.PathGraph(Integer(3)).lexicographic_product(graphs.CompleteGraph(Integer(2)))
>>> g.lex_BFS(reverse=True)
[(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]

Sage Live

g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2))
g.lex_BFS(reverse=True)

And the vertices at the end of the tree of discovery are, for chordal graphs, simplicial vertices (their neighborhood is a complete graph):

Sage

sage: g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(2))
sage: v = g.lex_BFS()[-1]
sage: peo, tree = g.lex_BFS(initial_vertex = v,  tree=True)
sage: leaves = [v for v in tree if tree.in_degree(v) ==0]
sage: all(g.subgraph(g.neighbors(v)).is_clique() for v in leaves)
True

Python

>>> from sage.all import *
>>> g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(Integer(2)))
>>> v = g.lex_BFS()[-Integer(1)]
>>> peo, tree = g.lex_BFS(initial_vertex = v,  tree=True)
>>> leaves = [v for v in tree if tree.in_degree(v) ==Integer(0)]
>>> all(g.subgraph(g.neighbors(v)).is_clique() for v in leaves)
True

Sage Live

g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(2))
v = g.lex_BFS()[-1]
peo, tree = g.lex_BFS(initial_vertex = v,  tree=True)
leaves = [v for v in tree if tree.in_degree(v) ==0]
all(g.subgraph(g.neighbors(v)).is_clique() for v in leaves)

Different orderings for different traversals:

Sage

sage: # needs sage.combinat
sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000', algorithm='fast')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_BFS(initial_vertex='000', algorithm='slow')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> G = digraphs.DeBruijn(Integer(2),Integer(3))
>>> G.lex_BFS(initial_vertex='000', algorithm='fast')
['000', '001', '100', '010', '011', '110', '101', '111']
>>> G.lex_BFS(initial_vertex='000', algorithm='slow')
['000', '001', '100', '010', '011', '110', '101', '111']
>>> G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
>>> G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
>>> G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Sage Live

# needs sage.combinat
G = digraphs.DeBruijn(2,3)
G.lex_BFS(initial_vertex='000', algorithm='fast')
G.lex_BFS(initial_vertex='000', algorithm='slow')
G.lex_DFS(initial_vertex='000')
G.lex_UP(initial_vertex='000')
G.lex_DOWN(initial_vertex='000')

sage.graphs.traversals.lex_DFS(G, reverse=False, tree=False, initial_vertex=None)[source]¶

Perform a lexicographic depth first search (LexDFS) on the graph.

INPUT:

G – a sage graph
reverse – boolean (default: False); whether to return the vertices in discovery order, or the reverse
tree – boolean (default: False); whether to return the discovery directed tree (each vertex being linked to the one that saw it last)
initial_vertex – (default: None) the first vertex to consider

Note

Loops and multiple edges are ignored during the computation of lex_DFS and directed graphs are converted to undirected graphs.

See also

lex_BFS() – perform a lexicographic breadth first search (LexBFS) on the graph
lex_UP() – perform a lexicographic UP search (LexUP) on the graph
lex_DOWN() – perform a lexicographic DOWN search (LexDOWN) on the graph

ALGORITHM:

See the documentation of the traversals module.

EXAMPLES:

A Lex DFS is obviously an ordering of the vertices:

Sage

sage: g = graphs.CompleteGraph(6)
sage: set(g.lex_DFS()) == set(g)
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> set(g.lex_DFS()) == set(g)
True

Sage Live

g = graphs.CompleteGraph(6)
set(g.lex_DFS()) == set(g)

Lex DFS ordering of the 3-sun graph:

Sage

sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: g.lex_DFS()
[1, 2, 3, 5, 6, 4]

Python

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> g.lex_DFS()
[1, 2, 3, 5, 6, 4]

Sage Live

g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
g.lex_DFS()

The method also works for directed graphs:

Sage

sage: G = DiGraph([(1, 2), (2, 3), (1, 3)])
sage: correct_anwsers = [[2, 1, 3], [2, 3, 1]]
sage: G.lex_DFS(initial_vertex=2) in correct_anwsers
True

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))])
>>> correct_anwsers = [[Integer(2), Integer(1), Integer(3)], [Integer(2), Integer(3), Integer(1)]]
>>> G.lex_DFS(initial_vertex=Integer(2)) in correct_anwsers
True

Sage Live

G = DiGraph([(1, 2), (2, 3), (1, 3)])
correct_anwsers = [[2, 1, 3], [2, 3, 1]]
G.lex_DFS(initial_vertex=2) in correct_anwsers

Different orderings for different traversals:

Sage

sage: # needs sage.combinat
sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> G = digraphs.DeBruijn(Integer(2),Integer(3))
>>> G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
>>> G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
>>> G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
>>> G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Sage Live

# needs sage.combinat
G = digraphs.DeBruijn(2,3)
G.lex_BFS(initial_vertex='000')
G.lex_DFS(initial_vertex='000')
G.lex_UP(initial_vertex='000')
G.lex_DOWN(initial_vertex='000')

sage.graphs.traversals.lex_DOWN(G, reverse=False, tree=False, initial_vertex=None)[source]¶

Perform a lexicographic DOWN search (LexDOWN) on the graph.

INPUT:

G – a sage graph
reverse – boolean (default: False); whether to return the vertices in discovery order, or the reverse
tree – boolean (default: False); whether to return the discovery directed tree (each vertex being linked to the one that saw it)
initial_vertex – (default: None) the first vertex to consider

Note

Loops and multiple edges are ignored during the computation of lex_DOWN and directed graphs are converted to undirected graphs.

See also

lex_BFS() – perform a lexicographic breadth first search (LexBFS) on the graph
lex_DFS() – perform a lexicographic depth first search (LexDFS) on the graph
lex_UP() – perform a lexicographic UP search (LexUP) on the graph

ALGORITHM:

See the documentation of the traversals module.

EXAMPLES:

A Lex DOWN is obviously an ordering of the vertices:

Sage

sage: g = graphs.CompleteGraph(6)
sage: set(g.lex_DOWN()) == set(g)
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> set(g.lex_DOWN()) == set(g)
True

Sage Live

g = graphs.CompleteGraph(6)
set(g.lex_DOWN()) == set(g)

Lex DOWN ordering of the 3-sun graph:

Sage

sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: g.lex_DOWN()
[1, 2, 3, 4, 6, 5]

Python

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> g.lex_DOWN()
[1, 2, 3, 4, 6, 5]

Sage Live

g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
g.lex_DOWN()

The method also works for directed graphs:

Sage

sage: G = DiGraph([(1, 2), (2, 3), (1, 3)])
sage: correct_anwsers = [[2, 1, 3], [2, 3, 1]]
sage: G.lex_DOWN(initial_vertex=2) in correct_anwsers
True

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))])
>>> correct_anwsers = [[Integer(2), Integer(1), Integer(3)], [Integer(2), Integer(3), Integer(1)]]
>>> G.lex_DOWN(initial_vertex=Integer(2)) in correct_anwsers
True

Sage Live

G = DiGraph([(1, 2), (2, 3), (1, 3)])
correct_anwsers = [[2, 1, 3], [2, 3, 1]]
G.lex_DOWN(initial_vertex=2) in correct_anwsers

Different orderings for different traversals:

Sage

sage: # needs sage.combinat
sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> G = digraphs.DeBruijn(Integer(2),Integer(3))
>>> G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
>>> G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
>>> G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
>>> G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Sage Live

# needs sage.combinat
G = digraphs.DeBruijn(2,3)
G.lex_BFS(initial_vertex='000')
G.lex_DFS(initial_vertex='000')
G.lex_UP(initial_vertex='000')
G.lex_DOWN(initial_vertex='000')

sage.graphs.traversals.lex_M(self, triangulation=False, labels=False, initial_vertex=None, algorithm=None)[source]¶

Return an ordering of the vertices according the LexM graph traversal.

LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. LexM can also produce a triangulation of the given graph. This functionality is implemented in this method. For more details on the algorithms used see Sections 4 ('lex_M_slow') and 5.3 ('lex_M_fast') of [RTL76].

Note

This method works only for undirected graphs.

INPUT:

triangulation – boolean (default: False); whether to return a list of edges that need to be added in order to triangulate the graph
labels – boolean (default: False); whether to return the labels assigned to each vertex
initial_vertex – (default: None) the first vertex to consider
algorithm – string (default: None); one of the following algorithms:
- 'lex_M_slow': slower implementation of LexM traversal
- 'lex_M_fast': faster implementation of LexM traversal (works only when labels is set to False)
- None: Sage chooses the best algorithm: 'lex_M_slow' if labels is set to True, 'lex_M_fast' otherwise.

OUTPUT:

Depending on the values of the parameters triangulation and labels the method will return one or more of the following (in that order):

an ordering of vertices of the graph according to LexM ordering scheme
the labels assigned to each vertex
a list of edges that when added to the graph will triangulate it

EXAMPLES:

LexM produces an ordering of the vertices:

Sage

sage: g = graphs.CompleteGraph(6)
sage: ord = g.lex_M(algorithm='lex_M_fast')
sage: len(ord) == g.order()
True
sage: set(ord) == set(g.vertices(sort=False))
True
sage: ord = g.lex_M(algorithm='lex_M_slow')
sage: len(ord) == g.order()
True
sage: set(ord) == set(g.vertices(sort=False))
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> ord = g.lex_M(algorithm='lex_M_fast')
>>> len(ord) == g.order()
True
>>> set(ord) == set(g.vertices(sort=False))
True
>>> ord = g.lex_M(algorithm='lex_M_slow')
>>> len(ord) == g.order()
True
>>> set(ord) == set(g.vertices(sort=False))
True

Sage Live

g = graphs.CompleteGraph(6)
ord = g.lex_M(algorithm='lex_M_fast')
len(ord) == g.order()
set(ord) == set(g.vertices(sort=False))
ord = g.lex_M(algorithm='lex_M_slow')
len(ord) == g.order()
set(ord) == set(g.vertices(sort=False))

Both algorithms produce a valid LexM ordering \(\alpha\) (i.e the neighbors of \(\alpha(i)\) in \(G[\{\alpha(i), ..., \alpha(n)\}]\) induce a clique):

Sage

sage: from sage.graphs.traversals import is_valid_lex_M_order
sage: G = graphs.PetersenGraph()
sage: ord, F = G.lex_M(triangulation=True, algorithm='lex_M_slow')
sage: is_valid_lex_M_order(G, ord, F)
True
sage: ord, F = G.lex_M(triangulation=True, algorithm='lex_M_fast')
sage: is_valid_lex_M_order(G, ord, F)
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import is_valid_lex_M_order
>>> G = graphs.PetersenGraph()
>>> ord, F = G.lex_M(triangulation=True, algorithm='lex_M_slow')
>>> is_valid_lex_M_order(G, ord, F)
True
>>> ord, F = G.lex_M(triangulation=True, algorithm='lex_M_fast')
>>> is_valid_lex_M_order(G, ord, F)
True

Sage Live

from sage.graphs.traversals import is_valid_lex_M_order
G = graphs.PetersenGraph()
ord, F = G.lex_M(triangulation=True, algorithm='lex_M_slow')
is_valid_lex_M_order(G, ord, F)
ord, F = G.lex_M(triangulation=True, algorithm='lex_M_fast')
is_valid_lex_M_order(G, ord, F)

LexM produces a triangulation of given graph:

Sage

sage: G = graphs.PetersenGraph()
sage: _, F = G.lex_M(triangulation=True)
sage: H = Graph(F, format='list_of_edges')
sage: H.is_chordal()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> _, F = G.lex_M(triangulation=True)
>>> H = Graph(F, format='list_of_edges')
>>> H.is_chordal()
True

Sage Live

G = graphs.PetersenGraph()
_, F = G.lex_M(triangulation=True)
H = Graph(F, format='list_of_edges')
H.is_chordal()

LexM ordering of the 3-sun graph:

Sage

sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: g.lex_M()
[6, 4, 5, 3, 2, 1]

Python

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> g.lex_M()
[6, 4, 5, 3, 2, 1]

Sage Live

g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
g.lex_M()

sage.graphs.traversals.lex_M_fast(G, triangulation=False, initial_vertex=None)[source]¶

Return an ordering of the vertices according the LexM graph traversal.

LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. This function implements the algorithm described in Section 5.3 of [RTL76].

Note that instead of using labels \(1, 2, \ldots, k\) and adding \(1/2\), we use labels \(2, 4, \ldots, k\) and add \(1\), thus avoiding to use floats or rationals.

Note

This method works only for undirected graphs.

INPUT:

G – a sage graph
triangulation – boolean (default: False); whether to return the triangulation of given graph produced by the method
initial_vertex – (default: None) the first vertex to consider

OUTPUT:

This method will return an ordering of the vertices of G according to the LexM ordering scheme. Furthermore, if triangulation is set to True the method also returns a list of edges F such that when added to G the resulting graph is a triangulation of G.

EXAMPLES:

A LexM ordering is obviously an ordering of the vertices:

Sage

sage: from sage.graphs.traversals import lex_M_fast
sage: g = graphs.CompleteGraph(6)
sage: len(lex_M_fast(g)) == g.order()
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_fast
>>> g = graphs.CompleteGraph(Integer(6))
>>> len(lex_M_fast(g)) == g.order()
True

Sage Live

from sage.graphs.traversals import lex_M_fast
g = graphs.CompleteGraph(6)
len(lex_M_fast(g)) == g.order()

LexM ordering of the 3-sun graph:

Sage

sage: from sage.graphs.traversals import lex_M_fast
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: lex_M_fast(g)
[6, 4, 5, 3, 2, 1]

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_fast
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> lex_M_fast(g)
[6, 4, 5, 3, 2, 1]

Sage Live

from sage.graphs.traversals import lex_M_fast
g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
lex_M_fast(g)

LexM produces a triangulation of given graph:

Sage

sage: from sage.graphs.traversals import lex_M_fast
sage: G = graphs.PetersenGraph()
sage: _, F = lex_M_fast(G, triangulation=True)
sage: H = G.copy()
sage: H.add_edges(F)
sage: H.is_chordal()
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_fast
>>> G = graphs.PetersenGraph()
>>> _, F = lex_M_fast(G, triangulation=True)
>>> H = G.copy()
>>> H.add_edges(F)
>>> H.is_chordal()
True

Sage Live

from sage.graphs.traversals import lex_M_fast
G = graphs.PetersenGraph()
_, F = lex_M_fast(G, triangulation=True)
H = G.copy()
H.add_edges(F)
H.is_chordal()

sage.graphs.traversals.lex_M_slow(G, triangulation=False, labels=False, initial_vertex=None)[source]¶

Return an ordering of the vertices according the LexM graph traversal.

LexM is a lexicographic ordering scheme that is a special type of breadth-first-search. This function implements the algorithm described in Section 4 of [RTL76].

During the search, the vertices are numbered from \(n\) to \(1\). Let \(\alpha(i)\) denote the vertex numbered \(i\) and let \(\alpha^{-1}(u)\) denote the number assigned to \(u\). Each vertex \(u\) has also a label, denoted by \(label(u)\), consisting of a list of numbers selected from \([1,n]\) and ordered in decreasing order. Given two labels \(L_1=[p_1, p_2,\ldots, p_k]\) and \(L_1=[q_1, q_2,\ldots, q_l]\), we define \(L_1<L_2\) if, for some \(j\), \(p_i==q_i\) for \(i=1,\ldots,j-1\) and \(p_j<q_j\), or if \(p_i==q_i\) for \(i=1,\ldots,k\) and \(k<l\). Observe that this is exactly how Python compares two lists.

Note

This method works only for undirected graphs.

INPUT:

G – a sage graph
triangulation – boolean (default: False); whether to return the triangulation of the graph produced by the method
labels – boolean (default: False); whether to return the labels assigned to each vertex
initial_vertex – (default: None) the first vertex to consider. If not specified, an arbitrary vertex is chosen.

OUTPUT:

Depending on the values of the parameters triangulation and labels the method will return one or more of the following (in that order):

the ordering of vertices of \(G\)
the labels assigned to each vertex
a list of edges that when added to \(G\) will produce a triangulation of \(G\)

EXAMPLES:

A LexM ordering is obviously an ordering of the vertices:

Sage

sage: from sage.graphs.traversals import lex_M_slow
sage: g = graphs.CompleteGraph(6)
sage: len(lex_M_slow(g)) == g.order()
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_slow
>>> g = graphs.CompleteGraph(Integer(6))
>>> len(lex_M_slow(g)) == g.order()
True

Sage Live

from sage.graphs.traversals import lex_M_slow
g = graphs.CompleteGraph(6)
len(lex_M_slow(g)) == g.order()

LexM ordering and label assignments on the vertices of the 3-sun graph:

Sage

sage: from sage.graphs.traversals import lex_M_slow
sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: lex_M_slow(g, labels=True)
([6, 4, 5, 3, 2, 1],
 {1: [], 2: [5], 3: [5, 4], 4: [4, 2], 5: [4, 3], 6: [3, 2]})

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_slow
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> lex_M_slow(g, labels=True)
([6, 4, 5, 3, 2, 1],
 {1: [], 2: [5], 3: [5, 4], 4: [4, 2], 5: [4, 3], 6: [3, 2]})

Sage Live

from sage.graphs.traversals import lex_M_slow
g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
lex_M_slow(g, labels=True)

LexM produces a triangulation of given graph:

Sage

sage: from sage.graphs.traversals import lex_M_slow
sage: G = graphs.PetersenGraph()
sage: _, F = lex_M_slow(G, triangulation=True)
sage: H = G.copy()
sage: H.add_edges(F)
sage: H.is_chordal()
True

Python

>>> from sage.all import *
>>> from sage.graphs.traversals import lex_M_slow
>>> G = graphs.PetersenGraph()
>>> _, F = lex_M_slow(G, triangulation=True)
>>> H = G.copy()
>>> H.add_edges(F)
>>> H.is_chordal()
True

Sage Live

from sage.graphs.traversals import lex_M_slow
G = graphs.PetersenGraph()
_, F = lex_M_slow(G, triangulation=True)
H = G.copy()
H.add_edges(F)
H.is_chordal()

sage.graphs.traversals.lex_UP(G, reverse=False, tree=False, initial_vertex=None)[source]¶

Perform a lexicographic UP search (LexUP) on the graph.

INPUT:

G – a sage graph
reverse – boolean (default: False); whether to return the vertices in discovery order, or the reverse
tree – boolean (default: False); whether to return the discovery directed tree (each vertex being linked to the one that saw it last)
initial_vertex – (default: None) the first vertex to consider

Note

Loops and multiple edges are ignored during the computation of lex_UP and directed graphs are converted to undirected graphs.

See also

lex_BFS() – perform a lexicographic breadth first search (LexBFS) on the graph
lex_DFS() – perform a lexicographic depth first search (LexDFS) on the graph
lex_DOWN() – perform a lexicographic DOWN search (LexDOWN) on the graph

ALGORITHM:

See the documentation of the traversals module.

EXAMPLES:

A Lex UP is obviously an ordering of the vertices:

Sage

sage: g = graphs.CompleteGraph(6)
sage: set(g.lex_UP()) == set(g)
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> set(g.lex_UP()) == set(g)
True

Sage Live

g = graphs.CompleteGraph(6)
set(g.lex_UP()) == set(g)

Lex UP ordering of the 3-sun graph:

Sage

sage: g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
sage: g.lex_UP()
[1, 2, 4, 5, 6, 3]

Python

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3)), (Integer(2), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(5)), (Integer(3), Integer(6)), (Integer(4), Integer(5)), (Integer(5), Integer(6))])
>>> g.lex_UP()
[1, 2, 4, 5, 6, 3]

Sage Live

g = Graph([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 5), (5, 6)])
g.lex_UP()

The method also works for directed graphs:

Sage

sage: G = DiGraph([(1, 2), (2, 3), (1, 3)])
sage: correct_anwsers = [[2, 1, 3], [2, 3, 1]]
sage: G.lex_UP(initial_vertex=2) in correct_anwsers
True

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(1), Integer(3))])
>>> correct_anwsers = [[Integer(2), Integer(1), Integer(3)], [Integer(2), Integer(3), Integer(1)]]
>>> G.lex_UP(initial_vertex=Integer(2)) in correct_anwsers
True

Sage Live

G = DiGraph([(1, 2), (2, 3), (1, 3)])
correct_anwsers = [[2, 1, 3], [2, 3, 1]]
G.lex_UP(initial_vertex=2) in correct_anwsers

Different orderings for different traversals:

Sage

sage: # needs sage.combinat
sage: G = digraphs.DeBruijn(2,3)
sage: G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
sage: G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
sage: G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
sage: G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> G = digraphs.DeBruijn(Integer(2),Integer(3))
>>> G.lex_BFS(initial_vertex='000')
['000', '001', '100', '010', '011', '110', '101', '111']
>>> G.lex_DFS(initial_vertex='000')
['000', '001', '100', '010', '101', '110', '011', '111']
>>> G.lex_UP(initial_vertex='000')
['000', '001', '010', '101', '110', '111', '011', '100']
>>> G.lex_DOWN(initial_vertex='000')
['000', '001', '100', '011', '010', '110', '111', '101']

Sage Live

# needs sage.combinat
G = digraphs.DeBruijn(2,3)
G.lex_BFS(initial_vertex='000')
G.lex_DFS(initial_vertex='000')
G.lex_UP(initial_vertex='000')
G.lex_DOWN(initial_vertex='000')

sage.graphs.traversals.maximum_cardinality_search(G, reverse=False, tree=False, initial_vertex=None)[source]¶

Return an ordering of the vertices according a maximum cardinality search.

Maximum cardinality search (MCS) is a graph traversal introduced in [TY1984]. It starts by assigning an arbitrary vertex (or the specified initial_vertex) of \(G\) the last position in the ordering \(\alpha\). Every vertex keeps a weight equal to the number of its already processed neighbors (i.e., already added to \(\alpha\)), and a vertex of largest such number is chosen at each step \(i\) to be placed in position \(n - i\) in \(\alpha\). This ordering can be computed in time \(O(n + m)\).

Time complexity is \(O(n+m)\) for SparseGraph and \(O(n^2)\) for DenseGraph where \(n\) is the number of vertices and \(m\) is the number of edges.

When the graph is chordal, the ordering returned by MCS is a perfect elimination ordering, like lex_BFS(). So this ordering can be used to recognize chordal graphs. See [He2006] for more details.

Note

The current implementation is for connected graphs only.

INPUT:

G – a Sage graph
reverse – boolean (default: False); whether to return the vertices in discovery order, or the reverse
tree – boolean (default: False); whether to also return the discovery directed tree (each vertex being linked to the one that saw it for the first time)
initial_vertex – (default: None) the first vertex to consider

OUTPUT:

By default, return the ordering \(\alpha\) as a list. When tree is True, the method returns a tuple \((\alpha, T)\), where \(T\) is a directed tree with the same set of vertices as \(G\) and a directed edge from \(u\) to \(v\) if \(u\) was the first vertex to see \(v\).

EXAMPLES:

When specified, the initial_vertex is placed at the end of the ordering, unless parameter reverse is True, in which case it is placed at the beginning:

Sage

sage: G = graphs.PathGraph(4)
sage: G.maximum_cardinality_search(initial_vertex=0)
[3, 2, 1, 0]
sage: G.maximum_cardinality_search(initial_vertex=1)
[0, 3, 2, 1]
sage: G.maximum_cardinality_search(initial_vertex=2)
[0, 1, 3, 2]
sage: G.maximum_cardinality_search(initial_vertex=3)
[0, 1, 2, 3]
sage: G.maximum_cardinality_search(initial_vertex=3, reverse=True)
[3, 2, 1, 0]

Python

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(4))
>>> G.maximum_cardinality_search(initial_vertex=Integer(0))
[3, 2, 1, 0]
>>> G.maximum_cardinality_search(initial_vertex=Integer(1))
[0, 3, 2, 1]
>>> G.maximum_cardinality_search(initial_vertex=Integer(2))
[0, 1, 3, 2]
>>> G.maximum_cardinality_search(initial_vertex=Integer(3))
[0, 1, 2, 3]
>>> G.maximum_cardinality_search(initial_vertex=Integer(3), reverse=True)
[3, 2, 1, 0]

Sage Live

G = graphs.PathGraph(4)
G.maximum_cardinality_search(initial_vertex=0)
G.maximum_cardinality_search(initial_vertex=1)
G.maximum_cardinality_search(initial_vertex=2)
G.maximum_cardinality_search(initial_vertex=3)
G.maximum_cardinality_search(initial_vertex=3, reverse=True)

Returning the discovery tree:

Sage

sage: G = graphs.PathGraph(4)
sage: _, T = G.maximum_cardinality_search(tree=True, initial_vertex=0)
sage: T.order(), T.size()
(4, 3)
sage: T.edges(labels=False, sort=True)
[(1, 0), (2, 1), (3, 2)]
sage: _, T = G.maximum_cardinality_search(tree=True, initial_vertex=3)
sage: T.edges(labels=False, sort=True)
[(0, 1), (1, 2), (2, 3)]

Python

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(4))
>>> _, T = G.maximum_cardinality_search(tree=True, initial_vertex=Integer(0))
>>> T.order(), T.size()
(4, 3)
>>> T.edges(labels=False, sort=True)
[(1, 0), (2, 1), (3, 2)]
>>> _, T = G.maximum_cardinality_search(tree=True, initial_vertex=Integer(3))
>>> T.edges(labels=False, sort=True)
[(0, 1), (1, 2), (2, 3)]

Sage Live

G = graphs.PathGraph(4)
_, T = G.maximum_cardinality_search(tree=True, initial_vertex=0)
T.order(), T.size()
T.edges(labels=False, sort=True)
_, T = G.maximum_cardinality_search(tree=True, initial_vertex=3)
T.edges(labels=False, sort=True)

sage.graphs.traversals.maximum_cardinality_search_M(G, initial_vertex=None)[source]¶

Return the ordering and the edges of the triangulation produced by MCS-M.

Maximum cardinality search M (MCS-M) is an extension of MCS (maximum_cardinality_search()) in the same way that Lex-M (lex_M()) is an extension of Lex-BFS (lex_BFS()). That is, in MCS-M when \(u\) receives number \(i\) at step \(n - i + 1\), it increments the weight of all unnumbered vertices \(v\) for which there exists a path between \(u\) and \(v\) consisting only of unnumbered vertices with weight strictly less than \(w^-(u)\) and \(w^-(v)\), where \(w^-\) is the number of times a vertex has been reached during previous iterations. See [BBHP2004] for the details of this \(O(nm)\) time algorithm.

If \(G\) is not connected, the orderings of each of its connected components are added consecutively. Furthermore, if \(G\) has \(k\) connected components \(C_i\) for \(0 \leq i < k\), \(X\) contains at least one vertex of \(C_i\) for each \(i \geq 1\). Hence, \(|X| \geq k - 1\). In particular, some isolated vertices (i.e., of degree 0) can appear in \(X\) as for such a vertex \(x\), we have that \(G \setminus N(x) = G\) is not connected.

INPUT:

G – a Sage graph
initial_vertex – (default: None) the first vertex to consider

OUTPUT: a tuple \((\alpha, F, X)\), where

\(\alpha\) is the resulting ordering of the vertices. If an initial vertex is specified, it gets the last position in the ordering \(\alpha\).
\(F\) is the list of edges of a minimal triangulation of \(G\) according \(\alpha\)
\(X\) is a list of vertices such that for each \(x \in X\), the neighborhood of \(x\) in \(G\) is a separator (i.e., \(G \setminus N(x)\) is not connected). Note that we may have \(N(x) = \emptyset\) if \(G\) is not connected and \(x\) has degree 0.

EXAMPLES:

Chordal graphs have a perfect elimination ordering, and so the set \(F\) of edges of the triangulation is empty:

Sage

sage: G = graphs.RandomChordalGraph(20)
sage: alpha, F, X = G.maximum_cardinality_search_M(); F
[]

Python

>>> from sage.all import *
>>> G = graphs.RandomChordalGraph(Integer(20))
>>> alpha, F, X = G.maximum_cardinality_search_M(); F
[]

Sage Live

G = graphs.RandomChordalGraph(20)
alpha, F, X = G.maximum_cardinality_search_M(); F

The cycle of order 4 is not chordal and so the triangulation has one edge:

Sage

sage: G = graphs.CycleGraph(4)
sage: alpha, F, X = G.maximum_cardinality_search_M(); len(F)
1

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4))
>>> alpha, F, X = G.maximum_cardinality_search_M(); len(F)
1

Sage Live

G = graphs.CycleGraph(4)
alpha, F, X = G.maximum_cardinality_search_M(); len(F)

The number of edges needed to triangulate of a cycle graph or order \(n\) is \(n - 3\), independently of the initial vertex:

Sage

sage: n = randint(3, 20)
sage: C = graphs.CycleGraph(n)
sage: _, F, X = C.maximum_cardinality_search_M()
sage: len(F) == n - 3
True
sage: _, F, X = C.maximum_cardinality_search_M(initial_vertex=C.random_vertex())
sage: len(F) == n - 3
True

Python

>>> from sage.all import *
>>> n = randint(Integer(3), Integer(20))
>>> C = graphs.CycleGraph(n)
>>> _, F, X = C.maximum_cardinality_search_M()
>>> len(F) == n - Integer(3)
True
>>> _, F, X = C.maximum_cardinality_search_M(initial_vertex=C.random_vertex())
>>> len(F) == n - Integer(3)
True

Sage Live

n = randint(3, 20)
C = graphs.CycleGraph(n)
_, F, X = C.maximum_cardinality_search_M()
len(F) == n - 3
_, F, X = C.maximum_cardinality_search_M(initial_vertex=C.random_vertex())
len(F) == n - 3

When an initial vertex is specified, it gets the last position in the ordering:

Sage

sage: G = graphs.PathGraph(4)
sage: G.maximum_cardinality_search_M(initial_vertex=0)
([3, 2, 1, 0], [], [2, 3])
sage: G.maximum_cardinality_search_M(initial_vertex=1)
([3, 2, 0, 1], [], [2, 3])
sage: G.maximum_cardinality_search_M(initial_vertex=2)
([0, 1, 3, 2], [], [0, 1])
sage: G.maximum_cardinality_search_M(initial_vertex=3)
([0, 1, 2, 3], [], [0, 1])

Python

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(4))
>>> G.maximum_cardinality_search_M(initial_vertex=Integer(0))
([3, 2, 1, 0], [], [2, 3])
>>> G.maximum_cardinality_search_M(initial_vertex=Integer(1))
([3, 2, 0, 1], [], [2, 3])
>>> G.maximum_cardinality_search_M(initial_vertex=Integer(2))
([0, 1, 3, 2], [], [0, 1])
>>> G.maximum_cardinality_search_M(initial_vertex=Integer(3))
([0, 1, 2, 3], [], [0, 1])

Sage Live

G = graphs.PathGraph(4)
G.maximum_cardinality_search_M(initial_vertex=0)
G.maximum_cardinality_search_M(initial_vertex=1)
G.maximum_cardinality_search_M(initial_vertex=2)
G.maximum_cardinality_search_M(initial_vertex=3)

When \(G\) is not connected, the orderings of each of its connected components are added consecutively, the vertices of the component containing the initial vertex occupying the last positions:

Sage

sage: G = graphs.CycleGraph(4) * 2
sage: G.maximum_cardinality_search_M()[0]
[5, 4, 6, 7, 2, 3, 1, 0]
sage: G.maximum_cardinality_search_M(initial_vertex=7)[0]
[2, 1, 3, 0, 5, 6, 4, 7]

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4)) * Integer(2)
>>> G.maximum_cardinality_search_M()[Integer(0)]
[5, 4, 6, 7, 2, 3, 1, 0]
>>> G.maximum_cardinality_search_M(initial_vertex=Integer(7))[Integer(0)]
[2, 1, 3, 0, 5, 6, 4, 7]

Sage Live

G = graphs.CycleGraph(4) * 2
G.maximum_cardinality_search_M()[0]
G.maximum_cardinality_search_M(initial_vertex=7)[0]

Furthermore, if \(G\) has \(k\) connected components, \(X\) contains at least one vertex per connected component, except for the first one, and so at least \(k - 1\) vertices:

Sage

sage: for k in range(1, 5):
....:     _, _, X = Graph(k).maximum_cardinality_search_M()
....:     if len(X) < k - 1:
....:         raise ValueError("something goes wrong")
sage: G = graphs.RandomGNP(10, .2)
sage: cc = G.connected_components(sort=False)
sage: _, _, X = G.maximum_cardinality_search_M()
sage: len(X) >= len(cc) - 1
True

Python

>>> from sage.all import *
>>> for k in range(Integer(1), Integer(5)):
...     _, _, X = Graph(k).maximum_cardinality_search_M()
...     if len(X) < k - Integer(1):
...         raise ValueError("something goes wrong")
>>> G = graphs.RandomGNP(Integer(10), RealNumber('.2'))
>>> cc = G.connected_components(sort=False)
>>> _, _, X = G.maximum_cardinality_search_M()
>>> len(X) >= len(cc) - Integer(1)
True

Sage Live

for k in range(1, 5):
    _, _, X = Graph(k).maximum_cardinality_search_M()
    if len(X) < k - 1:
        raise ValueError("something goes wrong")
G = graphs.RandomGNP(10, .2)
cc = G.connected_components(sort=False)
_, _, X = G.maximum_cardinality_search_M()
len(X) >= len(cc) - 1

In the example of [BPS2010], the triangulation has 3 edges:

Sage

sage: G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
....:            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
....:            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
....:            'i': ['k'], 'j': ['k']})
sage: _, F, _ = G.maximum_cardinality_search_M(initial_vertex='a')
sage: len(F)
3

Python

>>> from sage.all import *
>>> G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
...            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
...            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
...            'i': ['k'], 'j': ['k']})
>>> _, F, _ = G.maximum_cardinality_search_M(initial_vertex='a')
>>> len(F)
3

Sage Live

G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
           'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
           'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
           'i': ['k'], 'j': ['k']})
_, F, _ = G.maximum_cardinality_search_M(initial_vertex='a')
len(F)