Graphs: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 path 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 directed from υ1 to υk ; in an undirected graph this path is said to be between υ1 and υk.

The number of edges in a path, in this case, k 1, is called the length 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 cycle or circuit is a path in which the first 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 acyclic.

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 induced 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 {e3, e5, e6, e7}.

An undirected graph G is said to be connected if there is at least one path between every pair of vertices υi and υj in G. Graph G is said to be disconnected 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 connected 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 isolated 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 first a few more concepts and definitions.

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 weakly 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 distance 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 undefined 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 difficult 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

A connected, undirected, acyclic (without cycles) graph is called a tree, and a set of trees is called a forest . We have already seen rooted 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.

Incoming search terms:

Related posts:

Leave a comment

Your email address will not be published. Required fields are marked *