Elementary Graph Predicates#

Let \(G\) and \(H\) be two graphs. For clarity, we list here the conditions under which \(G\) is equal to \(H\) and \(H\) is a subgraph of \(G\). The conditions take into account the fact that the graphs may have a support and that their vertex and edges may be decorated.

The graphs \(G\) and \(H\) are equal if and only if:

  • they are of the same type,

  • they are structurally identical,

  • they have the same support,

  • they have identical vertex and edge labels,

  • if applicable, the total capacity from \(u\) to \(v\) in \(G\) is equal to the total capacity from \(u\) to \(v\) in \(H\).

Also, \(H\) is a subgraph of \(G\) if and only if:

  • they are of the same type,

  • \(H\) is a structural subgraph of \(G\),

  • any vertex v in \(H\) has the same support as the vertex VertexSet(G)!v in \(G\),

  • any vertex v in \(H\) has the same label as the vertex VertexSet(G)!v in \(G\),

  • any edge e in \(H\) has the same label as the edge EdgeSet(G)!e in \(G\),

  • if applicable, the total capacity from \(u\) to \(v\) in \(G\) is at least as large as the total capacity from \(u\) to \(v\) in \(H\).

Note that the truth value of the above two tests is not dependent on the weights of the edges of the graphs, should these edges be weighted. One could argue that given this shortcoming, the tests should not be dependent on the capacities of the edges either. We welcome users’ comments on this matter.

u adj v: GrphVert, GrphVert -> BoolElt#

Let \(u\) and \(v\) be two vertices of the same graph \(G\). If \(G\) is undirected, returns true if and only if \(u\) and \(v\) are adjacent. If \(G\) is directed, returns true if and only if there is an edge directed from \(u\) to \(v\).

e adj f: GrphEdge, GrphEdge -> BoolElt#

Let \(e\) and \(f\) be two edges of the same graph \(G\). If \(G\) is undirected, returns true if and only if \(e\) and \(f\) share a common vertex. If \(G\) is directed, returns true if and only if the terminal vertex of \(e\) (\(f\)) is the initial vertex of \(f\) (\(e\)).

u notadj v: GrphVert, GrphVert -> BoolElt#

The negation of the adj predicate applied to vertices.

e notadj f: GrphEdge, GrphEdge -> BoolElt#

The negation of the adj predicate applied to edges.

u in e: GrphVert, GrphEdge -> BoolElt#

Let \(u\) be a vertex and \(e\) an edge of a graph \(G\). Returns true if and only if \(u\) is an end-vertex of \(e\).

u notin e: GrphVert, GrphEdge -> BoolElt#

The negation of the in predicate applied to a vertex with respect to an edge.

G eq H: GrphDir, GrphDir -> BoolElt#
G eq H: GrphUnd, GrphUnd -> BoolElt#

Returns true if the graphs \(G\) and \(H\) are identical, otherwise false. \(G\) and \(H\) are identical if and only if:

  • they are structurally identical,

  • they have the same support,

  • they have identical vertex and edge labels,

  • if applicable, the total capacity from \(u\) to \(v\) in \(G\) is equal to the total capacity from \(u\) to \(v\) in \(H\).

Thus, as an example, if \(G\) and \(H\) are structurally identical graphs, and the vertices of \(G\) are labelled while the vertices of \(H\) are not, then G eq H returns false.

IsSubgraph(G, H): Grph, Grph -> BoolElt#

Returns true if \(H\) is a subgraph of \(G\), otherwise false. \(H\) is a subgraph of \(G\) if and only if:

  • \(H\) can be determined to be a structural subgraph of \(G\),

  • any vertex v in \(H\) has the same support as the vertex VertexSet(G)!v in \(G\),

  • any vertex v in \(H\) has the same label as the vertex VertexSet(G)!v in \(G\),

  • any edge e in \(H\) has the same label as the edge EdgeSet(G)!e in \(G\).

  • if applicable, the total capacity from \(u\) to \(v\) in \(G\) is at least as large as the total capacity from \(u\) to \(v\) in \(H\).

IsBipartite(G): GrphUnd -> BoolElt#

Returns true if the graph \(G\) is a bipartite graph, otherwise false.

IsComplete(G): Grph -> BoolElt#

Returns true if the graph \(G\) on \(n\) vertices is the complete graph on \(n\) vertices, otherwise false.

IsEulerian(G): Grph -> BoolElt#

Returns true if the graph \(G\) is an eulerian graph, otherwise false. A eulerian graph is a graph whose vertices have all even degree. An eulerian digraph is a digraph whose vertices have same in and outdegree. That is, if \(D\) is a digraph, \(D\) is eulerian if and only if OutDegree(v) equals InDegree(v) for all vertices \(v\) of \(D\).

IsForest(G): GrphUnd -> BoolElt#

Returns true if the graph \(G\) is a forest, i.e. does not possess any cycles, otherwise false.

IsEmpty(G): Grph -> BoolElt#

Returns true if the graph \(G\) is an empty graph, otherwise false. A graph is empty if its edge-set \(E\) is empty.

IsNull(G): Grph -> BoolElt#

Returns true if the graph \(G\) is a null graph, otherwise false. A graph is null if its vertex-set \(V\) is empty.

IsPath(G): Grph -> BoolElt#

Returns true if the graph \(G\) is a path graph, otherwise false.

IsPolygon(G): Grph -> BoolElt#

Returns true if the graph \(G\) is a polygon graph, otherwise false.

IsRegular(G): Grph -> BoolElt#

Returns true if the graph \(G\) is a regular graph, otherwise false.

IsTree(G): Grph -> BoolElt#

Returns true if the graph \(G\) is a tree, otherwise false.