Mastering Algorithms With C - Kyle Loudon [113]
Description of Graphs
Graphs are composed of two types of elements: vertices and edges. Vertices represent objects, and edges establish relationships or connections between the objects. In many problems, values, or weights, are associated with a graph's edges; however, such problems will not be considered further until Chapter 16.
Graphs may be either directed or undirected . In a directed graph, edges go from one vertex to another in a specific direction. Pictorially, a directed graph is drawn with circles for its vertices and arrows for its edges (see Figure 11.1a). Sometimes the edges of a directed graph are referred to as arcs . In an undirected graph, edges have no direction; thus, its edges are depicted using lines instead of arrows (see Figure 11.1b).
Figure 11.1. Two graphs: (a) a directed graph and (b) an undirected graph
Formally, a graph is a pair G = (V, E ), where V is a set of vertices and E is a binary relation on V. In a directed graph, if an edge goes from vertex u to vertex v, E contains the ordered pair (u, v). For example, in Figure 11.1a, V = {1, 2, 3, 4} and E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4)}. By convention, parentheses are used instead of braces for sets that represent edges in a graph. In an undirected graph, because an edge (u, v) is the same as (v, u), either edge is listed in E, but not both. Thus, in Figure 11.1b, V = {1, 2, 3, 4} and E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}. Edges may point back to the same vertex in a directed graph, but not in an undirected graph.
Two important relations in graphs are adjacency and incidence . Adjacency is a relation between two vertices. If a graph contains the edge (u, v), vertex v is said to be adjacent to vertex u. In an undirected graph, this implies that vertex u is also adjacent to vertex v. In other words, the adjacency relation is symmetric in an undirected graph. This is not necessarily true in a directed graph. For example, in Figure 11.1a, vertex 2 is adjacent to vertex 1, but vertex 1 is not adjacent to vertex 2. On the other hand, vertices 2 and 3 are adjacent to each other. A graph in which every vertex is adjacent to each other is called complete .
Incidence is a relation between a vertex and an edge. In a directed graph, the edge (u, v) is incident from or leaves vertex u and is incident to or enters vertex v. Thus, in Figure 11.1a, edge (1, 2) is incident from vertex 1 and incident to vertex 2. In a directed graph, the in-degree of a vertex is the number of edges incident to it. Its out-degree is the number of edges incident from it. In an undirected graph, the edge (u, v) is incident on vertices u and v. In an undirected graph, the degree of a vertex is the number of edges incident on it.
Often one talks about paths in a graph. A path is a sequence of vertices traversed by following the edges between them. Formally, a path from one vertex u to another vertex u ′ is a sequence of vertices 〈 v 0, v 1, v 2, . . ., vk 〉 in which u = v 0 and u ′ = vk , and all (vi - 1, vi ) are in E for i = 1, 2, . . ., k. Such a path contains the edges (v 0, v 1), (v 1, v 2), . . ., (vk - 1, vk ) and has a length of k. If a path exists from u to u ′, u ′ is reachable from u. A path is simple if it has no repeated vertices.
A cycle is a path that includes the same vertex two or more times. That is, in a directed graph, a path is a cycle if one of its edges leaves a vertex and another enters it. Thus, Figure 11.2a contains the cycle {1, 2, 4, 1}. Formally, in a directed graph, a path forms a cycle