Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section9.3Connectivity

This section is devoted to a question that, when posed in relation to the graphs that we have examined, seems trivial. That question is: Given two vertices, \(s\) and \(t\), of a graph, is there a path from \(s\) to \(t\)? If \(s = t\), this question is interpreted as asking whether there is a circuit of positive length starting at \(s\). Of course, for the graphs we have seen up to now, this question can be answered after a brief examination.

Subsection9.3.1Preliminaries

There are two situations under which a question of this kind is nontrivial. One is where the graph is very large and an “examination” of the graph could take a considerable amount of time. Anyone who has tried to solve a maze may have run into a similar problem. The second interesting situation is when we want to pose the question to a machine. If only the information on the edges between the vertices is part of the data structure for the graph, how can you put that information together to determine whether two vertices can be connected by a path?

Note9.3.1Connectivity Terminology

Let \(v\) and \(w\) be vertices of a directed graph. Vertex \(v\) is connected to vertex \(w\) if there is a path from \(v\) to \(w\). Two vertices are strongly connected if they are connected in both directions to one another. A graph is connected if, for each pair of distinct vertices, \(v\) and \(w\), \(v\) is connected to \(w\) or \(w\) is connected to \(v\). A graph is strongly connected if every pair of its vertices is strongly connected. For an undirected graph, in which edges can be used in either direction, the notions of strongly connected and connected are the same.

Proof

Subsection9.3.2Adjacency Matrix Method

The main advantage of the adjacency matrix method is that the transitive closure matrix can answer all questions about the existence of paths between any vertices. If \(G^+\) is the matrix of the transitive closure, \(v_i\) is connected to \(v_j\) if and only if \(\left(G^+\right)_{i j }=1\). A directed graph is connected if \(\left(G^+\right)_{i j }=1\) or \(\left(G^+\right)_{j i}=1\) for each \(i\neq j\). A directed graph is strongly connected if its transitive closure matrix has no zeros.

A disadvantage of the adjacency matrix method is that the transitive closure matrix tells us whether a path exists, but not what the path is. The next algorithm solve this problem

Subsection9.3.5Exercises for Section 9.3

1

Apply Algorithm 9.3.8 to find a path from 5 to 1 in Figure . What would be the final value of \(V\)? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order, as we assumed in Example 9.3.10.

Answer
2

Apply Algorithm 9.3.8 to find a path from \(d\) to \(c\) in the road graph in Example 9.1.9 using the edge list in that example. Assume that the elements of the depth sets are put into ascending order.

3

In a simple undirected graph with no self-loops, what is the maximum number of edges you can have, keeping the graph unconnected? What is the minimum number of edges that will assure that the graph is connected?

Answer
4

Use a broadcasting algorithm to determine the shortest path from vertex \(a\) to vertex \(i\) in the graphs shown in the Figure 9.3.11 below. List the depth sets and the stack that is created.

Graphs for exercise 9-3-4
Figure9.3.11Shortest paths from \(a\) to \(i\)?
5

Prove (by induction on \(k\)) that if the relation \(r\) on vertices of a graph is defined by \(v r w\) if there is an edge connecting \(v\) to \(w\), then \(r^k\), \(k \geq 1\), is defined by \(v r^kw\) if there is a path of length \(k\) from \(v\) to \(w\).

Answer