__Connectivity, Distance, and Spanning Trees__

__Connectivity, Distance, and Spanning Trees__

Just as two vertices *x *and *y *in a graph are said to be adjacent if there is an edge joining them, two edges are said to be adjacent if they share (*i.e.*, are incident on) a common vertex. A *simple path*, or *p**a**th *for short, is a sequence of adjacent edges (*υ*1*, υ*2), (*υ*2*, υ*3), *.**. .*, (*υ**k−*2*, υ**k−*1), (*υ**k−*1*, υ**k *), sometimes written (*υ*1*, υ*2*,..**. , υ**k *), in which all the vertices *υ*1*, υ*2*,…**, υ**k *are distinct except possibly *υ*1 = *υ**k *. In a digraph this path is said to be *di**re**c**t**e**d from **υ*1 to *υ**k *; in an undirected graph this path is said to be *b**e**tween **υ*1 and *υ**k*.

The number of edges in a path, in this case, *k **− *1, is called the *le**n**g**t**h *of the path. In Figure 4.3 sequence (*υ*6*, υ*4)*, *(*υ*4*, υ*1)*, *(*υ*1*, υ*2) = (*υ*6*, υ*4*, υ*1*, υ*2) is a path of length 3 between *υ*6 and *υ*2. In the digraph in Figure 4.6 sequence (3*, *1)*, *(1*, *5)*, *(5*, *2)*, *(2*, *4) = (3*, *1*, *5*, *2*, *4) is a directed path of length 4 from vertex 3 to vertex 4. A *cycl**e *or *ci**r**c**u**i**t *is a path in which the ﬁrst and the last vertices are the same. In Figure 4.3 (*υ*3*, υ*6*, υ*4*, υ*1*, υ*3) is a cycle of length 4. In Figure 4.6 (3*, *2*, *1*, *3) is a cycle of length 3. A graph that contains no cycle is called *acycli**c*.

A *subgraph *of a graph *G *= (*V**, E*) is a graph whose vertices and edges are in *G*. A subgraph *g *of *G *is said to be *i**nduced *by a subset of vertices *S **⊆ **V *if *g *results when the vertices in *V **− **S *and all the edges incident on them are removed from *G*. For example, in Figure 4.3, the subgraph induced by *{**υ*1*, υ*3*, υ*4*} *would consists of these three vertices and four edges *{**e*3*, e*5*, e*6*, e*7*}*.

An undirected graph *G *is said to be *c**o**nnected *if there is at least one path between every pair of vertices *υ**i *and *υ**j *in *G*. Graph *G *is said to be *di**sconnected *if it has at least one pair of distinct vertices *u *and *v *such that there is no path between *u *and *v*. Two vertices *x *and *y *in an undirected graph *G *= (*V**, E*) are said to be *c**o**nnected *if there exists a path between *x *and *y*. This relation of being connected is an equivalence relation on the vertex set *V *, and therefore it partitions the vertices of *G *into equivalence classes. Each equivalence class of vertices induces a subgraph of *G*. These subgraphs are called connected components of *G*. In other words, a connected component is a maximal connected subgraph of *G*. A connected graph consists of just one component, whereas a disconnected graph consists of several (connected) components. Each of the graphs in Figures 4.1, 4.3, and 4.4 is connected. But the graph given in Figure 4.7 is disconnected, consisting of four components.

Notice that a component may consist of just one vertex such as *j *in Figure 4.7 with no edges. Such a component (subgraph or graph) is called an *i**solated vertex *. Equivalently, a vertex with zero degree is called an isolated vertex. Likewise, a graph (subgraph or component) may consist of just one edge, such as edge (*i, d*) in Figure 4.7.

One of the simplest and often the most important and useful questions about a given graph *G *is: Is *G *connected? And if *G *is not connected what are its connected components? This question will be taken up in the next section, and an algorithm for determining the connected components will be provided; but ﬁrst a few more concepts and deﬁnitions.

Connectivity in a directed graph *G *is more involved. A digraph is said to be connected if the undirected graph obtained by ignoring the edge directions in *G *is connected. A directed graph is said to be *strongly connected *if for every pair of vertices *υ**i *and *υ**j *there exists at least one directed path from *υ**i *to *υ**j *and at least one from *υ**j *to *υ**i*. A digraph which is connected but not strongly connected is called *w**e**akl**y connected *. A disconnected digraph (like a disconnected undirected graph) consists of connected components; and a weakly-connected digraph consists of strongly-connected components. For example, the connected digraph in Figure 4.5 consists of four strongly-connected components—induced by each of the following subsets of vertices *{*1*, *2*}*,*{*3*}*,*{*4*}*, and *{*5*}*.

Another important question is that of distance from one vertex to another. The *di**stance** *from vertex *a *to *b *is the length of the shortest path (*i.e.**, *a path of the smallest length) from *a *to *b*, if such a path exists. If no path from *a *to *b *exists, the distance is undeﬁned and is often set to *∞*. Thus, the distance from a vertex to itself is 0; and the distance from a vertex to an adjacent vertex is 1. In an undirected graph distance from *a *to *b *equals the distance from *b *to *a*, *i.e.**, *it is symmetric. It is also not diﬃcult to see that the distances in a connected undirected graph (or a strongly connected digraph) satisfy the triangle inequality. In a connected, undirected (unweighted) graph *G*, the maximum distance between any pair of vertices is called the diameter of *G*.

**4****.****3****.****1 Spanning Trees**

**4****.****3****.****1 Spanning Trees**A connected, undirected, acyclic (without cycles) graph is called a *t**r**e**e*, and a set of trees is called a *fo**r**e**st *. We have already seen *r**o**o**ted *trees and forests of rooted trees in the preceding chapter, but the unrooted trees and forests discussed in this chapter are graphs of a very special kind that play an important role in many applications.

In a connected undirected graph *G *there is at least one path between every pair of vertices and the absence of a cycle implies that there is at most one such path between any pair of vertices in *G*. Thus if *G *is a tree, there is exactly one path between every pair of vertices in *G*. The argument is easily reversed, and so an undirected graph *G *is a tree if and only if there is exactly one path between every pair of vertices in *G*. A tree with *n *vertices has exactly (*n **− *1) edges. Since (*n **− *1) edges are the fewest possible to connect *n *points, trees can be thought of as graphs that are *minimally connected *. That is, removing any edge from a tree would disconnect it by destroying the only path between at least one pair of vertices. A *spanning tree *for a connected graph *G *is a subgraph of *G *which is a tree containing every vertex of *G*. If *G *is not connected, a set consisting of one spanning tree for each component is called a *spanning forest *of *G*. To construct a spanning tree (forest) of a given undirected graph *G*, we examine the edges of *G *one at a time and retain only those that do not not form a cycle with the edges already selected. Systematic ways of examining the edges of a graph will be discussed in the next section.