[MathJax on]

4 Operators

4.1 Operators for digraphs

digraph1 = digraph2

returns true if digraph1 and digraph2 have the same vertices, and DigraphEdges(digraph1) = DigraphEdges(digraph2), up to some re-ordering of the edge lists.

Note that this operator does not compare the vertex labels of digraph1 and digraph2.

digraph1 < digraph2

This operator returns true if one of the following holds:

• The number n_1 of vertices in digraph1 is less than the number n_2 of vertices in digraph2;

• n_1 = n_2, and the number m_1 of edges in digraph1 is less than the number m_2 of edges in digraph2;

• n_1 = n_2, m_1 = m_2, and DigraphEdges(digraph1) is less than DigraphEdges(digraph2) after having both of these sets have been sorted with respect to the lexicographical order.

4.1-1 IsSubdigraph

Returns: true or false.

If super and sub are digraphs, then this operation returns true if sub is a subdigraph of super, and false if it is not.

A digraph sub is a subdigraph of a digraph super if sub and super share the same number of vertices, and the collection of edges of super (including repeats) contains the collection of edges of sub (including repeats).

In other words, sub is a subdigraph of super if and only if DigraphNrVertices(sub) = DigraphNrVertices(super), and for each pair of vertices i and j, there are at least as many edges of the form [i, j] in super as there are in sub.

gap> g := Digraph([[2, 3], [1], [2, 3]]);
<immutable digraph with 3 vertices, 5 edges>
gap> h := Digraph([[2, 3], [], [2]]);
<immutable digraph with 3 vertices, 3 edges>
gap> IsSubdigraph(g, h);
true
gap> IsSubdigraph(h, g);
false
gap> IsSubdigraph(CompleteDigraph(4), CycleDigraph(4));
true
gap> IsSubdigraph(CycleDigraph(4), ChainDigraph(4));
true
gap> g := Digraph([[2, 2], [1]]);
<immutable multidigraph with 2 vertices, 3 edges>
gap> h := Digraph([[2], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> IsSubdigraph(g, h);
true
gap> IsSubdigraph(h, g);
false

4.1-2 IsUndirectedSpanningTree

Returns: true or false.

The operation IsUndirectedSpanningTree returns true if the digraph sub is an undirected spanning tree of the digraph super, and the operation IsUndirectedSpanningForest returns true if the digraph sub is an undirected spanning forest of the digraph super.

An undirected spanning tree of a digraph super is a subdigraph of super that is an undirected tree (see IsSubdigraph (4.1-1) and IsUndirectedTree (6.6-9)). Note that a digraph whose MaximalSymmetricSubdigraph (3.3-5) is not connected has no undirected spanning trees (see IsConnectedDigraph (6.6-3)).

An undirected spanning forest of a digraph super is a subdigraph of super that is an undirected forest (see IsSubdigraph (4.1-1) and IsUndirectedForest (6.6-9)), and is not contained in any larger such subdigraph of super. Equivalently, an undirected spanning forest is a subdigraph of super whose connected components coincide with those of the MaximalSymmetricSubdigraph (3.3-5) of super (see DigraphConnectedComponents (5.4-9)).

Note that an undirected spanning tree is an undirected spanning forest that is connected.

gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> tree := Digraph([[3], [4], [1, 4], [2, 3]]);
<immutable digraph with 4 vertices, 6 edges>
gap> IsSubdigraph(D, tree) and IsUndirectedTree(tree);
true
gap> IsUndirectedSpanningTree(D, tree);
true
gap> forest := EmptyDigraph(4);
<immutable empty digraph with 4 vertices>
gap> IsSubdigraph(D, forest) and IsUndirectedForest(forest);
true
gap> IsUndirectedSpanningForest(D, forest);
false
gap> IsSubdigraph(tree, forest);
true
gap> D := DigraphDisjointUnion(CycleDigraph(2), CycleDigraph(2));
<immutable digraph with 4 vertices, 4 edges>
gap> IsUndirectedTree(D);
false
gap> IsUndirectedForest(D) and IsUndirectedSpanningForest(D, D);
true

generated by GAPDoc2HTML