ads Connectivity

Section 9.3 Connectivity

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

t ?

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.

🔗

Subsection 9.3.1 Preliminaries

🔗

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?

🔗

Note 9.3.1. Connectivity 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

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

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.

🔗

Theorem 9.3.2. Maximal Path Theorem.

🔗

If a graph has

n

vertices and vertex

u

is connected to vertex

w,

then there exists a path from

u

w

of length no more than

n .

Proof.

(Indirect): Suppose

u

is connected to

w,

but the shortest path from

u

w

has length

m,

where

m > n .

A vertex list for a path of length

m

will have

m + 1

vertices. This path can be represented as

(v_{0}, v_{1}, \dots, v_{m}),

where

v_{0} = u

and

v_{m} = w .

Note that since there are only

n

vertices in the graph and

m

vertices are listed in the path after

v_{0},

we can apply the pigeonhole principle and be assured that there must be some duplication in the last

m

vertices of the vertex list, which represents a circuit in the path. This means that our path of minimum length can be reduced, which is a contradiction.

🔗

Subsection 9.3.2 Adjacency Matrix Method

🔗

Algorithm 9.3.3. Adjacency Matrix Method.

🔗

Suppose that the information about edges in a graph is stored in an adjacency matrix,

G .

The relation,

r,

that

G

defines is

v r w

if there is an edge connecting

v

w .

Recall that the composition of

r

with itself,

r^{2},

is defined by

v r^{2} w

if there exists a vertex

y

such that

v r y

and

y r w;

that is,

v

is connected to

w

by a path of length 2. We could prove by induction that the relation

r^{k},

k \geq 1,

is defined by

v r^{k} w

if and only if there is a path of length

k

from

v

w .

Since the transitive closure,

r^{+},

is the union of

r,

r^{2}

, r^{3}, \dots,

we can answer our connectivity question by determining the transitive closure of

r,

which can be done most easily by keeping our relation in matrix form. Theorem 9.3.2 is significant in our calculations because it tells us that we need only go as far as

G^{n}

to determine the matrix of the transitive closure.

🔗

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

{(G^{+})}_{i j} = 1 .

A directed graph is connected if

{(G^{+})}_{i j} = 1

{(G^{+})}_{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 will solve this problem.

🔗

Subsection 9.3.3 Breadth-First Search

🔗

We will describe the Breadth-First Search Algorithm first with an example.

🔗

The football team at Mediocre State University (MSU) has had a bad year, 2 wins and 9 losses. Thirty days after the end of the football season, the university trustees are meeting to decide whether to rehire the head coach; things look bad for him. However, on the day of the meeting, the coach issues the following press release with results from the past year:

🔗

List 9.3.4. Press Release: MSU completes successful season

🔗

The Mediocre State University football team compared favorably with national champion Enormous State University this season.

Mediocre State defeated Local A and M.
Local A and M defeated City College.
City College defeated Corn State U.
... (25 results later)
Tough Tech defeated Enormous State University (ESU).

🔗

...and ESU went on to win the national championship!

🔗

The trustees were so impressed that they rehired the coach with a raise! How did the coach come up with such a list?

🔗

In reality, such lists exist occasionally and have appeared in newspapers from time to time. Of course they really don’t prove anything since each team that defeated MSU in our example above can produce a similar, shorter chain of results. Since college football records are readily available, the coach could have found this list by trial and error. All that he needed to start with was that his team won at least one game. Since ESU lost one game, there was some hope of producing the chain.

🔗

The problem of finding this list is equivalent to finding a path in the tournament graph for last year’s football season that initiates at MSU and ends at ESU. Such a graph is far from complete and is likely to be represented using edge lists. To make the coach’s problem interesting, let’s imagine that only the winner of any game remembers the result of the game. The coach’s problem has now taken on the flavor of a maze. To reach ESU, he must communicate with the various teams along the path. One way that the coach could have discovered his list in time is by sending the following messages to the coaches of the two teams that MSU defeated during the season:

🔗

Note 9.3.5.

🔗

When this example was first written, we commented that ties should be ignored. Most recent NCAA rules call for a tiebreaker in college football and so ties are no longer an issue. Email was also not common and we described the process in terms of letters, not email messages. Another change is that the coach could also have asked the MSU math department to use Mathematica or Sage to find the path!

🔗

List 9.3.6. The Coach’s Letter

🔗

Dear Football Coach:

🔗

Please follow these directions exactly.

If you are the coach at ESU, contact the coach at MSU now and tell him who sent you this message.
If you are not the coach at ESU and this is the first message of this type that you have received, then:
- Remember from whom you received this message.
- Forward a copy of this message, signed by you, to each of the coaches whose teams you defeated during the past year.
- Ignore this message if you have received one like it already.

🔗

Signed,

🔗

Coach of MSU

🔗

List 9.3.7. Observations

🔗

From the conditions of this message, it should be clear that if everyone cooperates and if coaches participate within a day of receiving the message:

If a path of length $n$ exists from MSU to ESU, then the coach will know about it in $n$ days.
By making a series of phone calls, the coach can construct a path that he wants by first calling the coach who defeated ESU (the person who sent ESU’s coach that message). This coach will know who sent him a letter, and so on. Therefore, the vertex list of the desired path is constructed in reverse order.
If a total of $M$ football games were played, no more than $M$ messages will be sent out.
If a day passes without any message being sent out, no path from MSU to ESU exists.
This method could be extended to construct a list of all teams that a given team can be connected to. Simply imagine a series of letters like the one above sent by each football coach and targeted at every other coach.

🔗

The general problem of finding a path between two vertices in a graph, if one exists, can be solved exactly as we solved the problem above. The following algorithm, commonly called a breadth-first search, uses a stack.

🔗

Algorithm 9.3.8. Breadth-first Search.

🔗

A broadcasting algorithm for finding a path between vertex

i

and vertex

j

of a graph having

n

vertices. Each item

V_{k}

of a list

V = {V_{1}, V_{2}, \dots, V_{n}},

consists of a Boolean field

V_{k} . found

and an integer field

V_{k} . from .

The sets

D_{1},

D_{2}, \dots,

called depth sets, have the property that if

k \in D_{r},

then the shortest path from vertex

i

to vertex

k

is of length

r .

In Step 5, a stack is used to put the vertex list for the path from the vertex

i

to vertex

j

in the proper order. That stack is the output of the algorithm.

🔗

Set the value $V_{k} . found$ equal to False, $k = 1, 2, \dots, n$
$r = 0$
$V_{i} . found = T r u e$
$D_{0} = {i}$
while $(\neg V_{j} . found$ ) and $(D_{r} \neq \emptyset)$
- $D_{r + 1} = \emptyset$
- for each k in $D_{r} :$
  
  for each edge (k,t):
  
  If $V_{t} . found$ == False:
  
  $V_{t} . found = True$
  
  $V_{t} . from = k$
  
  $D_{r + 1} = D_{r + 1} \cup {t}$
- $r = r + 1$
if $V_{j} . found :$
- $S = E m p t y S t a c k$
- $k = j$
- while $V_{k} . from \neq i :$
  
  Push $k$ onto $S$
  
  $k = V_{k} . from$
- Push $k$ onto $S$
- Push $i$ onto $S$

🔗

List 9.3.9. Notes on Breadth-first Search

If $v_{i}$ is the starting vertex and we initialize $v_{i} . f o u n d = F a l s e,$ then the algorithm will find the shortest circuit containing $v_{i} .$ If that is of interest, we would also not initialize the depth of $V_{i}$ to ${i}$
This algorithm will produce one path from vertex $i$ to vertex $j,$ if one exists, and that path will be as short as possible. If more than one path of this length exists, then the one that is produced depends on the order in which the edges are examined and the order in which the elements of $D_{r}$ are examined in Step 4.
The condition $D_{r} \neq \emptyset$ is analogous to the condition that no mail is sent in a given stage of the process, in which case MSU cannot be connected to ESU.
This algorithm can be easily revised to find paths to all vertices that can be reached from vertex $i .$ Step 5 would be put off until a specific path to a vertex is needed since the information in $V$ contains an efficient list of all paths. The algorithm can also be extended further to find paths between any two vertices.

Example 9.3.10. A simple example.

Consider the graph below. The existence of a path from vertex 2 to vertex 3 is not difficult to determine by examination. After a few seconds, you should be able to find two paths of length four. Algorithm 9.3.8 will produce one of them.

described in detail following the image — Figure 9.3.11. A simple example of breadth-first search

Suppose that the edges from each vertex are sorted in ascending order by terminal vertex. For example, the edges from vertex 3 would be in the order

(3, 1), (3, 4), (3, 5) .

In addition, assume that in the body of Step 4 of the algorithm, the elements of

D_{r}

are used in ascending order. Then at the end of Step 4, the value of

V

will be

\begin{array}{cccccccc} k & 1 & 2 & 3 & 4 & 5 & 6 \\ V_{k} . found & T & T & T & T & T & T \\ V_{k} . from & 2 & 4 & 6 & 1 & 1 & 4 \\ Depth set & 1 & 3 & 4 & 2 & 2 & 3 \end{array}

Therefore, the path

(2, 1, 4, 6, 3)

is produced by the algorithm. Note that if we wanted a path from 2 to 5, the information in

V

produces the path (2, 1, 5) since

V_{k} . from = 1

and

V_{1} . from = 2 .

A shortest circuit that initiates at vertex 2 is also available by noting that

V_{2} . from = 4,

V_{4} .from = 1,

and

V_{1} . from = 2;

thus the circuit

(2, 1, 4, 2)

is the output of the algorithm.

🔗

Subsection 9.3.4 Graph Measurements

🔗

If we were to perform a breadth first search from each vertex in a graph, we could proceed to determine several key measurements relating to the general connectivity of that graph. From each vertex

v,

the distance from

v

to any other vertex

w,

d (v, w),

is number of edges in the shortest path from

v

w .

This number is also the index of the depth set to which

w

belongs in a breath-first search starting at

v .

d (v, w) = i ⟺ w \in D_{v} (i)

🔗

where

D_{v}

is the family of depth sets starting at

v .

🔗

If the vector of “from-values” is known from the breath-first search, then the distance can be determined recursively as follows:

d (v, v) = 0

d (v, w) = 1 + d (v, w . f r o m) if w \neq v

Example 9.3.12. Computing Distances.

Consider Figure 9.3.13. If we perform a breadth first search of this graph starting at vertex 2, for example, we get the following “from data” telling us from what vertex each vertex is reached.

\begin{array}{ccccccccccccc} vertex & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ vertex.from & 7 & 2 & 10 & 6 & 9 & 7 & 2 & 4 & 2 & 7 & 9 & 2 \end{array}

For example, 4.from has a value of 6. We can compute

d (2, 4) :

\begin{aligned} d (2, 4) & = 1 + d (2, 4. f r o m) = 1 + d (2, 6) \\ = 2 + d (2, 6. f r o m) = 2 + d (2, 7) \\ = 3 + d (2, 7. f r o m) = 3 + d (2, 2) \\ = 3 \end{aligned}

🔗

Once we know distances between any two vertices, we can determine the eccentricity of each vertex; and the graph’s diameter, radius and center. First, we define these terms precisely.

🔗

Eccentricity of a Vertex: 🔗
The maximum distance from a vertex to all other vertices, $e (v) = max_{w} d (v, w) .$
Diameter of a Graph: 🔗
The maximum eccentricity of vertices in a graph, denoted $d (G) .$
Radius of a Graph: 🔗
The minimum eccentricity of vertices in a graph, denoted $r (G) .$
Center of a Graph: 🔗
The set of vertices with minimal eccentricity, $C (G) = {v \in V ∣ e (v) = r (G)}$

Example 9.3.14. Measurements from distance matrices.

If we compute all distances between vertices, we can summarize the results in a distance matrix, where the entry in row

i,

column

j

is the distance from vertex

i

to vertex

j .

For the graph in Example 9.3.12, that matrix is

(\begin{array}{cccccccccccc} 0 & 2 & 2 & 2 & 3 & 1 & 1 & 3 & 3 & 1 & 2 & 2 \\ 2 & 0 & 3 & 3 & 2 & 2 & 1 & 4 & 1 & 2 & 2 & 1 \\ 2 & 3 & 0 & 2 & 5 & 3 & 2 & 3 & 4 & 1 & 4 & 3 \\ 2 & 3 & 2 & 0 & 3 & 1 & 2 & 1 & 3 & 1 & 2 & 3 \\ 3 & 2 & 5 & 3 & 0 & 2 & 3 & 4 & 1 & 4 & 1 & 3 \\ 1 & 2 & 3 & 1 & 2 & 0 & 1 & 2 & 2 & 2 & 1 & 2 \\ 1 & 1 & 2 & 2 & 3 & 1 & 0 & 3 & 2 & 1 & 2 & 1 \\ 3 & 4 & 3 & 1 & 4 & 2 & 3 & 0 & 4 & 2 & 3 & 4 \\ 3 & 1 & 4 & 3 & 1 & 2 & 2 & 4 & 0 & 3 & 1 & 2 \\ 1 & 2 & 1 & 1 & 4 & 2 & 1 & 2 & 3 & 0 & 3 & 2 \\ 2 & 2 & 4 & 2 & 1 & 1 & 2 & 3 & 1 & 3 & 0 & 3 \\ 2 & 1 & 3 & 3 & 3 & 2 & 1 & 4 & 2 & 2 & 3 & 0 \end{array})

If we scan the matrix, we can see that the maximum distance is the distance between vertices 3 and 5, which is 5 and is the diameter of the graph. If we focus on individual rows and identify the maximum values, which are the eccentricities, their minimum is 3, which the graph’s radius. This eccentricity value is attained by vertices in the set

{1, 4, 6, 7},

which is the center of the graph.

🔗

Subsection 9.3.5 SageMath Note - Graph Searching

🔗

The following sequence of Sage cells illustrates how searching can be done in graphs.

🔗

Generate a random undirected graph with 18 vertices. For each pair of vertices, an edge is included between them with probability 0.2. Since there are

(\binom{18}{2}) = 153

potential edges, we expect that there will be approximately

0.2 \cdot 153 \approx 31

edges. The random number generation is seeded first so that the result will always be the same in spite of the random graph function. Changing or removing that first line will let you experiment with different graphs.

xxxxxxxxxx
 
set_random_seed(2002)
Gr=graphs.RandomGNP(18,0.2)
Gr.show()

🔗

Count the number of edges. In this case the number is a bit less than expected.

xxxxxxxxxx
 
len(Gr.edges(labels=False))

🔗

Find a shortest path from vertex 0 to vertex 8.

xxxxxxxxxx
 
Gr.shortest_path(0, 8)

🔗

Generate a list of vertices that would be reached in a breadth-first search. The expression Gr.breadth_first_search(0) creates an iterator that is convenient for programming. Wrapping list( ) around the expression shows the order in which the vertices are visited with the depth set indicated in the second coordinates.

xxxxxxxxxx
 
list(Gr.breadth_first_search(0,report_distance='True'))

🔗

Exercises 9.3.6 Exercises

🔗

1.

🔗

Apply Algorithm 9.3.8 to find a path from 5 to 1 in Figure 9.3.11. 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.

\begin{array}{ccccccc} k & 1 & 2 & 3 & 4 & 5 & 6 \\ V [k] . found & T & T & T & F & F & T \\ V [k] . from & 2 & 5 & 6 & * & * & 5 \\ Depth Set & 2 & 1 & 2 & * & * & 1 \end{array}

(* = undefined)

🔗

2.

🔗

Apply Algorithm 9.3.8 to find a path from

d

c

in the road graph in Example 9.1.7 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.

If the number of vertices is

n,

there can be

\frac{(n - 1) (n - 2)}{2}

vertices with one vertex not connected to any of the others. One more edge and connectivity is assured.

🔗

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.15 below. List the depth sets and the stack that is created.

🔗

5.

🔗

For each of the following graphs, determine the eccentricities of each vertex, and the diameter, radius, and center of the graph.

An undirected graph with 6 vertices.

Answer.

The eccentricity of each vertex is 2; and the diameter and radius are both 2 as well. All vertices are part of the center.
The corners (1,3,10 and 10) have eccentricities 5. The two central vertices, 5 and 8, which are in the center of the graph have eccentricity 3. All other vertices have eccentricity 4. The diameter is 5. The radius is 3.
Vertices 1, 2 and 5 have eccentricity 2 and make up the center of this graph. Verticies 7 and 8 have eccentricity 4, and all other vertices have eccentricity 3. The diameter is 4. The radius is 2.
The eccentricity of each vertex is 4; and the diameter and radius are both 4 as well. All vertices are part of the center.

🔗

6.

🔗

The terms diameter, radius and center are familiar ones in the context of circles. Compare their usage in circles and graphs. How are they similar and how are they different?
“Eccentricity” might be less familiar. How is is used in geometry, and does it have a compatible use in graph theory?

🔗

7.

🔗

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

w,

then

r^{k},

k \geq 1,

is defined by

v r^{k} w

if there is a path of length

k

from

v

w .

Answer.

Basis:

(k = 1)

Is the relation

r^{1},

defined by

v r^{1} w

if there is a path of length 1 from

v to w ?

Yes, since

v r w

if and only if an edge, which is a path of length

1,

connects

v

w .

Induction: Assume that

v r^{k} w

if and only if there is a path of length

k

from

v

w .

We must show that

v r^{k + 1} w

if and only if there is a path of length

k + 1

from

v

w .

v r^{k + 1} w \Rightarrow v r^{k} y and y r w for some vertex y

By the induction hypothesis, there is a path of length

k

from

v to y .

And by the basis, there is a path of length one from

y

w .

If we combine these two paths, we obtain a path of length

k + 1

from

v

w .

Of course, if we start with a path of length

k + 1

from

v

w,

we have a path of length

k

from

v

to some vertex

y

and a path of length 1 from

y

w .

Therefore,

v r^{k} y and y r w \Rightarrow v r^{k + 1} w .

🔗

8.

🔗

For each of the following distance matrices of graphs, identify the diameter, radius and center. Assume the graphs vertices are the numbers 1 through

n

for an

n \times n

matrix.

$(\begin{array}{cccccccccc} 0 & 2 & 1 & 2 & 2 & 3 & 3 & 2 & 1 & 1 \\ 2 & 0 & 1 & 2 & 3 & 3 & 3 & 2 & 3 & 2 \\ 1 & 1 & 0 & 1 & 2 & 2 & 2 & 1 & 2 & 1 \\ 2 & 2 & 1 & 0 & 3 & 3 & 3 & 2 & 3 & 2 \\ 2 & 3 & 2 & 3 & 0 & 2 & 1 & 1 & 2 & 1 \\ 3 & 3 & 2 & 3 & 2 & 0 & 1 & 1 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 0 & 1 & 3 & 2 \\ 2 & 2 & 1 & 2 & 1 & 1 & 1 & 0 & 2 & 1 \\ 1 & 3 & 2 & 3 & 2 & 3 & 3 & 2 & 0 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 1 & 0 \end{array})$
$(\begin{array}{cccccccccccc} 0 & 2 & 2 & 2 & 3 & 3 & 3 & 1 & 2 & 3 & 1 & 1 \\ 2 & 0 & 2 & 2 & 1 & 1 & 1 & 3 & 2 & 1 & 1 & 3 \\ 2 & 2 & 0 & 1 & 3 & 2 & 1 & 2 & 2 & 3 & 1 & 1 \\ 2 & 2 & 1 & 0 & 3 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ 3 & 1 & 3 & 3 & 0 & 2 & 2 & 4 & 3 & 2 & 2 & 4 \\ 3 & 1 & 2 & 1 & 2 & 0 & 2 & 2 & 3 & 2 & 2 & 2 \\ 3 & 1 & 1 & 2 & 2 & 2 & 0 & 3 & 3 & 2 & 2 & 2 \\ 1 & 3 & 2 & 1 & 4 & 2 & 3 & 0 & 3 & 4 & 2 & 2 \\ 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 0 & 1 & 3 & 1 \\ 3 & 1 & 3 & 3 & 2 & 2 & 2 & 4 & 1 & 0 & 2 & 2 \\ 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 3 & 2 & 0 & 2 \\ 1 & 3 & 1 & 1 & 4 & 2 & 2 & 2 & 1 & 2 & 2 & 0 \end{array})$

You have attempted of activities on this page.

Prev Top Next