Page 707 - Discrete Mathematics and Its Applications

686 10 / Graphs

DEFINITION 5 A directed graph is weakly connected if there is a path between every two vertices in the
underlying undirected graph.

That is, a directed graph is weakly connected if and only if there is always a path between
two vertices when the directions of the edges are disregarded. Clearly, any strongly connected
directed graph is also weakly connected.

EXAMPLE 10 Are the directed graphs G and H shown in Figure 5 strongly connected? Are they weakly
connected?

Solution: G is strongly connected because there is a path between any two vertices in this
directed graph (the reader should verify this). Hence, G is also weakly connected. The graph
H is not strongly connected. There is no directed path from a to b in this graph. However, H is
weakly connected, because there is a path between any two vertices in the underlying undirected
graph of H (the reader should verify this). ▲

STRONG COMPONENTS OF A DIRECTED GRAPH The subgraphs of a directed graph G
that are strongly connected but not contained in larger strongly connected subgraphs, that is,
the maximal strongly connected subgraphs, are called the strongly connected components or
strong components of G. Note that if a and b are two vertices in a directed graph, their strong
components are either the same or disjoint. (We leave the proof of this last fact as Exercise 17.)

EXAMPLE 11 The graph H in Figure 5 has three strongly connected components, consisting of the vertex a;
the vertex e; and the subgraph consisting of the vertices b, c, and d and edges (b, c), (c, d), and
(d, b). ▲

EXAMPLE 12 The Strongly Connected Components of the Web Graph The Web graph introduced in
Example 5 of Section 10.1 represents Web pages with vertices and links with directed edges. A
snapshot of the Web in 1999 produced a Web graph with over 200 million vertices and over 1.5
billion edges (numbers that have now grown considerably). (See [Br00] for details.)
The underlying undirected graph of this Web graph is not connected, but it has a connected
component that includes approximately 90% of the vertices in the graph. The subgraph of the
In 2010 the Web graph
was estimated to have at original directed graph corresponding to this connected component of the underlying undirected
least 55 billion vertices graph (that is, with the same vertices and all directed edges connecting vertices in this graph)
and one trillion edges. has one very large strongly connected component and many small ones. The former is called
This implies that more the giant strongly connected component (GSCC) of the directed graph. A Web page in this
than 40 TB of computer component can be reached following links starting at any other page in this component. The
memory would have been
needed to represent its GSCC in the Web graph produced by this study was found to have over 53 million vertices.
adjacency matrix. The remaining vertices in the large connected component of the undirected graph represent
three different types of Web pages: pages that can be reached from a page in the GSCC, but
do not link back to these pages following a series of links; pages that link back to pages in the

a b a b

c c

e d e d
G H

FIGURE 5 The Directed Graphs G and H.