Disconnected and Connected Digraphs
| Definition: A digraph $G = (V(G), E(G))$ is said to be Connected if its underlying graph is also connected. If the underlying graph of $G$ is not connected, then $G$ is said to be a disconnected digraph. |
Let's first look at an example of a disconnected digraph:
This digraph is disconnected because its underlying graph (right) is also disconnected as there exists a vertex with degree $0$.
Now let's look at an example of a connected digraph:
This digraph is connected because its underlying graph (right) is also connected as there exists no vertices with degree $0$.
Strongly Connected Digraphs
| Definition: A digraph $G = (V(G), E(G))$ is said to be Strongly Connected if and only if there exists a path between each pair of vertices (which implies that the underlying graph of $G$ is connected). |
For example, let's look at the following digraph:
This graph is definitely connected as it's underlying graph is connected. But is this graph strongly connected? The answer is yes since we can find a path along the arcs that hits every vertex:
Thus, this graph can be considered strongly connected. Verify for yourself that the connected graph from the earlier example is NOT strongly connected.