Subdigraphs And Underlying Graphs


Definition: For a digraph $G = (V(G), E(G))$, a Subdigraph of $G$ is a digraph whose vertices and arcs are also $G$.

For example, let's take a look at the following digraph:


One possible subdigraph of the graph above is:


Notice that this subdigraph contains arcs which are also in the original graph. Direction of the arcs matters though. For example, the following digraph:


Is NOT a subdigraph of the first graph, as the direction of one of the arcs (the blue one) is not the same as the original graph.

Underlying Graphs

Definition: For a digraph $G = (V(G), E(G))$, the Underlying Graph of $G$ is the undirected graph created using all of the vertices in $V(G)$, and replacing all arcs in $E(G)$ with undirected edges.

For example, let's look at the following digraph on $4$ vertices and $5$ arcs:


The corresponding underlying graph would look like this:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License