Subdigraphs And Underlying Graphs

Subdigraphs

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:

Screen%20Shot%202014-02-19%20at%205.05.51%20PM.png

One possible subdigraph of the graph above is:

Screen%20Shot%202014-02-19%20at%205.08.10%20PM.png

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

Screen%20Shot%202014-02-19%20at%205.08.19%20PM.png

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:

Screen%20Shot%202014-02-19%20at%205.02.17%20PM.png

The corresponding underlying graph would look like this:

Screen%20Shot%202014-02-19%20at%205.01.36%20PM.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License