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.

-

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.

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.