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.

Methods#

sage.graphs.traversals.is_valid_lex_M_order(G, alpha, F)#

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')#

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 for the first time)
initial_vertex – (default: None); the first vertex to consider
algorithm – string (default: "fast"); algorithm to use among:
- "slow" – This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. See for instance [CK2008] for more details. The time complexity of this algorithm as described in [CK2008] is in \(O(n + m)\), where \(n\) is the number of vertices and \(m\) is the number of edges, but our implementation is in \(O(n^2)\).
- "fast" – This algorithm uses the notion of slices to refine 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. See [HMPV2000] and next section for more details.

ALGORITHM:

The "fast" algorithm is the \(O(n + m)\) time algorithm proposed in [HMPV2000], where \(n\) is the number of vertices and \(m\) is the number of edges. It uses the notion of slices, i.e., subsets of consecutive vertices in the ordering, and iteratively refines the slices by subdividing them into sub-slices to determine the exact position of the vertices in the ordering.

Consider an ordering \(\sigma\) of the vertices. For a vertex \(v\), we define \(N_i(v) = \{u | u \in N(v) \text{ and } \sigma(u) < i\}\), that is the subset of neighbors of \(v\) appearing before the \(i\)-th vertex in the ordering \(\sigma\). Now, a slice of an ordering \(\sigma\) is a set of consecutive vertices, \(S = \{u | i \leq \sigma(u) \leq j\}\), such that for any \(u \in S\), we have \(N_i(u) = N_i(\sigma^{-1}(i))\) and for any \(v\) such that \(j < \sigma(v)\), \(N_i(v) \neq N_i(\sigma^{-1}(i))\). The head of a slice is the first position of its vertices.

The algorithm starts with a single slice containing all vertices. Then, when the position of the \(i\)-th vertex \(v\) is fixed, it explores the neighbors of \(v\) that have not yet been ordered. Consider a slice \(S\) such that \(N(x)\cap S \neq \emptyset\). The algorithm will rearrange the ordering of the vertices in \(S\) so that the first vertices are the neighbors of \(v\). The sub-slice containing the neighbors of \(v\) is assigned a new slice name, and the head of slice \(S\) is set to the position of the first vertex of \(S \setminus N(v)\) in the ordering \(\sigma\).

Observe that each arc of the graph can induce the subdivision of a slice. Hence, the algorithm can use up to \(m + 1\) different slices.

See also

Wikipedia article Lexicographic_breadth-first_search
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: g = graphs.CompleteGraph(6)
sage: len(g.lex_BFS()) == g.order()
True

Lex BFS ordering of the 3-sun graph:

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]

The method also works for directed graphs:

sage: G = DiGraph([(1, 2), (2, 3), (1, 3)])
sage: G.lex_BFS(initial_vertex=2, algorithm="slow")
[2, 3, 1]
sage: G.lex_BFS(initial_vertex=2, algorithm="fast")
[2, 3, 1]

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

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)]

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

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

Different orderings for different traversals:

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']

sage.graphs.traversals.lex_DFS(G, reverse=False, tree=False, initial_vertex=None)#

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 for the first time)
initial_vertex – (default: None); the first vertex to consider

ALGORITHM:

This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. Lex DFS differs from Lex BFS only in the way codes are updated after each iteration.

Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.

See [CK2008] for more details on the algorithm.

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

EXAMPLES:

A Lex DFS is obviously an ordering of the vertices:

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

Lex DFS ordering of the 3-sun graph:

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]

The method also works for directed graphs:

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

Different orderings for different traversals:

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']

sage.graphs.traversals.lex_DOWN(G, reverse=False, tree=False, initial_vertex=None)#

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 for the first time)
initial_vertex – (default: None); the first vertex to consider

ALGORITHM:

This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. During the \(i\)-th iteration of the algorithm \(n-i\) is prepended to the codes of all neighbors of the selected vertex that are left in the graph.

Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.

See [Mil2017] for more details on the algorithm.

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

EXAMPLES:

A Lex DOWN is obviously an ordering of the vertices:

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

Lex DOWN ordering of the 3-sun graph:

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]

The method also works for directed graphs:

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

Different orderings for different traversals:

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']

sage.graphs.traversals.lex_M(self, triangulation=False, labels=False, initial_vertex=None, algorithm=None)#

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

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

LexM produces a triangulation of given graph:

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

LexM ordering of the 3-sun graph:

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]

sage.graphs.traversals.lex_M_fast(G, triangulation=False, initial_vertex=None)#

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: from sage.graphs.traversals import lex_M_fast
sage: g = graphs.CompleteGraph(6)
sage: len(lex_M_fast(g)) == g.order()
True

LexM ordering of the 3-sun graph:

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]

LexM produces a triangulation of given graph:

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

sage.graphs.traversals.lex_M_slow(G, triangulation=False, labels=False, initial_vertex=None)#

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: from sage.graphs.traversals import lex_M_slow
sage: g = graphs.CompleteGraph(6)
sage: len(lex_M_slow(g)) == g.order()
True

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

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]})

LexM produces a triangulation of given graph:

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

sage.graphs.traversals.lex_UP(G, reverse=False, tree=False, initial_vertex=None)#

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 for the first time)
initial_vertex – (default: None); the first vertex to consider

ALGORITHM:

This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code (according to the lexicographic order) is then removed, and the codes are updated. During the \(i\)-th iteration of the algorithm \(i\) is appended to the codes of all neighbors of the selected vertex that are left in the graph.

Time complexity is \(O(n+m)\) where \(n\) is the number of vertices and \(m\) is the number of edges.

See [Mil2017] for more details on the algorithm.

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

EXAMPLES:

A Lex UP is obviously an ordering of the vertices:

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

Lex UP ordering of the 3-sun graph:

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]

The method also works for directed graphs:

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

Different orderings for different traversals:

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']

sage.graphs.traversals.maximum_cardinality_search(G, reverse=False, tree=False, initial_vertex=None)#

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)\).

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 saw \(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: 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]

Returning the discovery tree:

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)]

sage.graphs.traversals.maximum_cardinality_search_M(G, initial_vertex=None)#

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: G = graphs.RandomChordalGraph(20)
sage: 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: G = graphs.CycleGraph(4)
sage: alpha, F, X = G.maximum_cardinality_search_M(); len(F)
1

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

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

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

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])

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

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: 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()
sage: _, _, X = G.maximum_cardinality_search_M()
sage: len(X) >= len(cc) - 1
True

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

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