Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Connectedness of a Directed Graph

When dealing with directed graphs, we define two kinds of connectedness, strong and weak. Strong connectedness of a directed graph is defined as follows:

Definition (Strong Connectedness of a Directed Graph)   A directed graph tex2html_wrap_inline69997 is strongly connected   if there is a path in G between every pair of vertices in tex2html_wrap_inline69999.

For example, Figure gif shows the directed graph tex2html_wrap_inline70773 given by

eqnarray50365

Notice that the graph tex2html_wrap_inline70775 is not connected! For example, there is no path from any of the vertices in tex2html_wrap_inline70777 to any of the vertices in tex2html_wrap_inline65998. Nevertheless, the graph ``looks'' connected in the sense that it is not made of up of separate parts in the way that the graph tex2html_wrap_inline70749 in Figure gif is.

This idea of ``looking'' connected is what weak connectedness represents. To define weak connectedness we need to introduce first the notion of the undirected graph that underlies a directed graph: Consider a directed graph tex2html_wrap_inline69997. The underlying undirected graph is the graph tex2html_wrap_inline70785 where tex2html_wrap_inline70787 represents the set of undirected edges that is obtained by removing the arrowheads from the directed edges in G:

displaymath70765

   figure50374
Figure: An weakly connected directed graph and the underlying undirected graph.

Weak connectedness of a directed graph is defined with respect to its underlying, undirected graph:

Definition (Weak Connectedness of a Directed Graph) A directed graph tex2html_wrap_inline69997 is weakly connected   if the underlying undirected graph tex2html_wrap_inline70797 is connected.

For example, since the undirected graph tex2html_wrap_inline70799 in Figure gif is connected, the directed graph tex2html_wrap_inline70775 is weakly connected. Consider what happens when we remove the edge (b,e) from the directed graph tex2html_wrap_inline70775. The underlying undirected graph that we get is tex2html_wrap_inline70749 in Figure gif. Therefore, when we remove edge (b,e) from tex2html_wrap_inline70775, the graph that remains is neither strongly connected nor weakly connected.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.