Disconnected Connected And Strongly Connected Digraphs

# 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.