Page 1 :
UNIT 4 Graphs, Graphs are discrete structures consisting of vertices and edges that connect, these vertices.There are different kinds of graphs, depending on whether edges, have directions, whether multiple edges can connect the same pair of vertices,, and whether loops are allowed., Graphs and Graph Models, We begin with the definition of a graph., DEFINITION 1 A graph G = (V ,E) consists of V , a nonempty set of vertices, (or nodes) and E, a set of edges. Each edge has either one or two vertices, associated with it, called its endpoints. An edge is said to connect its endpoints., Remark: The set of vertices V of a graph G may be infinite. A graph with an, infinite vertex set or an infinite number of edges is called an infinite graph, and, in comparison, a graph with a finite vertex set and a finite edge set is called a, finite graph., Now suppose that a network is made up of data centers and communication, links between computers.We can represent the location of each data center by a, point and each communications link by a line segment, as shown in Figure 1., This computer network can be modeled using a graph in which the vertices of, the graph represent the data centers and the edges represent communication, links. In general, we visualize, , graphs by using points to represent vertices and line segments, possibly curved,, to represent edges, where the endpoints of a line segment representing an edge, are the points representing the endpoints of the edge. When we draw a graph,, we generally try to draw edges so that they do not cross. However, this is not, necessary because any depiction using points to represent vertices and any form, of connection between vertices can be used. Indeed, there are some graphs that
Page 2 :
cannot be drawn in the plane without edges crossing (see Section 10.7). The key, point is that the way we draw a graph is arbitrary, as long as the correct, connections between vertices are depicted., Note that each edge of the graph representing this computer network connects, two different vertices. That is, no edge connects a vertex to itself. Furthermore,, no two different edges connect, the same pair of vertices. A graph in which each edge connects two different, vertices and where no two edges connect the same pair of vertices is called a, simple graph. Note that in a simple graph, each edge is associated to an, unordered pair of vertices, and no other edge is associated, to this same edge. Consequently, when there is an edge of a simple graph, associated to {u, v}, we can also say, without possible confusion, that {u, v} is an, edge of the graph. A computer network may contain multiple links between data, centers, as shown in Figure 2. To model such networks we need graphs that, have more than one edge connecting the same pair of vertices. Graphs that may, have multiple edges connecting the same vertices are called, multigraphs.When there aremdifferent edges associated to the same unordered, pair of vertices {u, v}, we also say that {u, v} is an edge of multiplicity m. That, is, we can think of this set of edges as m different copies of an edge {u, v}., , Sometimes a communications link connects a data center with itself, perhaps a, feedback loop for diagnostic purposes. Such a network is illustrated in Figure 3., To model this network we need to include edges that connect a vertex to itself., Such edges are called loops, and sometimes we may even have more than one, loop at a vertex. Graphs that may include loops, and possibly multiple edges, connecting the same pair of vertices or a vertex to itself, are sometimes called, pseudographs.
Page 3 :
So far the graphs we have introduced are undirected graphs. Their edges are, also said to be undirected. However, to construct a graph model, we may find it, necessary to assign directions to the edges of a graph. For example, in a, computer network, some links may operate in only one direction (such links are, called single duplex lines). This may be the case if there is a large amount of, traffic sent to some data centers, with little or no traffic going in the opposite, direction. Such a network is shown in Figure 4., To model such a computer network we use a directed graph. Each edge of a, directed graph is associated to an ordered pair. The definition of directed graph, we give here is more general than the one we used in Chapter 9, where we used, directed graphs to represent relations., , DEFINITION 2 A directed graph (or digraph) (V ,E) consists of a nonempty, set of vertices V and a set of directed edges (or arcs) E. Each directed edge is, associated with an ordered pair of vertices. The directed edge associated with, the ordered pair (u, v) is said to start at u and end at v., When we depict a directed graph with a line drawing, we use an arrow pointing, from u to v to indicate the direction of an edge that starts at u and ends at v.A, directed graph may contain loops, and it may contain multiple directed edges that start and end at the same, vertices.Adirected graph may also contain directed edges that connect vertices u
Page 4 :
and v in both directions; that is, when a digraph contains an edge from u to v, it, may also contain one or more edges from v to u. Note that, we obtain a directed graph when we assign a direction to each edge in an, undirected graph.When a directed graph has no loops and has no multiple, directed edges, it is called a simple directed graph. Because a simple directed, graph has at most one edge associated to each ordered pair, of vertices (u, v), we call (u, v) an edge if there is an edge associated to it in the, graph.In some computer networks, multiple communication links between two, data centers may be present, as illustrated in Figure 5. Directed graphs that may, have multiple directed edges from a vertex to a second (possibly the same), vertex are used to model such networks.We called, such graphs directed multigraphs. When there are m directed edges, each, associated to an ordered pair of vertices (u, v), we say that (u, v) is an edge of, multiplicity m., , Graph Terminology and Special Types of Graphs, We introduce some of the basic vocabulary of graph theory in this section.We, will use this vocabulary, later in this chapter when we solve many different types of problems. One such, problem
Page 5 :
involves determining whether a graph can be drawn in the plane so that no two, of its edges cross., Another example is deciding whether there is a one-to-one correspondence, between the vertices, of two graphs that produces a one-to-one correspondence between the edges of, the graphs.We, will also introduce several important families of graphs often used as examples, and in models., Several important applications will be described where these special types of, graphs arise., Basic Terminology, First, we give some terminology that describes the vertices and edges of, undirected graphs., DEFINITION 1 Two vertices u and v in an undirected graph G are called, adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an, edge e is called incident with the vertices u and v and e is said to connect u and, v., We will also find useful terminology describing the set of vertices adjacent to a, particular vertex, of a graph., DEFINITION 2 The set of all neighbors of a vertex v of G = (V ,E), denoted by, N(v), is called the neighbourhood of v. If A is a subset of V , we denote by N(A), the set of all vertices in G that are adjacent to at least one vertex in A. So, N(A), = _v∈A N(v)., To keep track of how many edges are incident to a vertex, we make the, following definition., DEFINITION 3 The degree of a vertex in an undirected graph is the number, of edges incident with it, except that a loop at a vertex contributes twice to the, degree of that vertex. The degree of the vertex v is denoted by deg(v)., EXAMPLE 1 What are the degrees and what are the neighborhoods of the, vertices in the graphs G and H, displayed in Figure 1?, Solution: In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) =, 3, and deg(g) = 0. The neighborhoods of these vertices are N(a) = {b, f }, N(b) =
Page 6 :
{a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c}, N(e) = {b, c, f }, N(f ) = {a, b, c, e}, and, N(g) = ∅. In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d ) = 5., The neighborhoods of these vertices are N(a) = {b, d, e}, N(b) = {a, b, c, d, e},, N(c) = {b}, N(d) = {a, b, e}, and N(e) = {a, b, d}., , A vertex of degree zero is called isolated. It follows that an isolated vertex is, not adjacent, to any vertex. Vertex g in graph G in Example 1 is isolated. A vertex is pendant, if and only, if it has degree one. Consequently, a pendant vertex is adjacent to exactly one, other vertex., Vertex d in graph G in Example 1 is pendant., Terminology for graphs with directed edges reflects the fact that edges in, directed graphs, have directions., DEFINITION 4 When (u, v) is an edge of the graph G with directed edges, u is, said to be adjacent to v and v is said to be adjacent from u. The vertex u is, called the initial vertex of (u, v), and v is called, the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a, loop are the, same. Because the edges in graphs with directed edges are ordered pairs, the, definition of the degree, of a vertex can be refined to reflect the number of edges with this vertex as the, initial vertex and, as the terminal vertex., DEFINITION 5 In a graph with directed edges the in-degree of a vertex v,, denoted by deg−
Page 7 :
(v), is the number of edges with v as their terminal vertex. The out-degree of v,, denoted by deg+ (v), is the, number of edges with v as their initial vertex. (Note that a loop at a vertex, contributes 1 to, both the in-degree and the out-degree of this vertex.), EXAMPLE 4 Find the in-degree and out-degree of each vertex in the graph G, with directed edges shown in Figure 2., , Solution: The in-degrees in G are deg− (a) = 2, deg− (b) = 2, deg− (c) = 3, deg, − (d) = 2, deg− (e) = 3, and deg− (f ) = 0. The out-degrees are deg+ (a) = 4,, deg+ (b) = 1, deg+ (c) = 2,, deg+ (d) = 2, deg+ (e) = 3, and deg+ (f ) = 0., , Some Special Simple Graphs, Complete Graphs A complete graph on n vertices, denoted by Kn, is a simple, graph, that contains exactly one edge between each pair of distinct vertices. The graphs, Kn, for, n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is, at least one, pair of distinct vertex not connected by an edge is called noncomplete.
Page 8 :
EXAMPLE 6 Cycles A cycle Cn, n ≥ 3, consists of n vertices v1, v2, . . . , vn, and edges {v1, v2},, {v2, v3}, . . . , {vn−1, vn}, and {vn, v1}. The cycles C3, C4, C5, and C6 are, displayed in, Figure 4., , Representing Graphs, One way to represent a graph without multiple edges is to list all the edges of, this graph. Another, way to represent a graph with no multiple edges is to use adjacency lists, which, specify the, vertices that are adjacent to each vertex of the graph., EXAMPLE 1 Use adjacency lists to describe the simple graph given in Figure, 1., Solution: Table 1 lists those vertices adjacent to each of the vertices of the, graph.
Page 9 :
EXAMPLE 2 Represent the directed graph shown in Figure 2 by listing all the, vertices that are the terminal vertices of edges starting at each vertex of the, graph., Solution: Table 2 represents the directed graph shown in Figure 2., , Adjacency Matrices, Carrying out graph algorithms using the representation of graphs by lists of, edges, or by adjacency, lists, can be cumbersome if there are many edges in the graph. To simplify, computation,, graphs can be represented using matrices. Two types of matrices commonly, used to represent, graphs will be presented here. One is based on the adjacency of vertices, and the, other is based, on incidence of vertices and edges., Suppose that G = (V ,E) is a simple graph where |V| = n. Suppose that the, vertices of, G are listed arbitrarily as v1, v2, . . . , vn. The adjacency matrix A (or AG) of, G, with respect, to this listing of the vertices, is the n x n zero–one matrix with 1 as its (i, j )th, entry when vi, and vj are adjacent, and 0 as its (i, j )th entry when they are not adjacent. In, other words, if its, adjacency matrix is A = [aij ], then, aij = _1 if{vi , vj } is an edge of G,, 0 otherwise., EXAMPLE 3 Use an adjacency matrix to represent the graph shown in Figure, 3.
Page 10 :
Solution:We order the vertices as a, b, c, d. The matrix representing this graph, is
Page 11 :
Isomorphism of Graphs, We often need to know whether it is possible to draw two graphs in the same, way. That is, do, the graphs have the same structure when we ignore the identities of their, vertices? For instance,, in chemistry, graphs are used to model chemical compounds (in a way we will, describe later)., Different compounds can have the same molecular formula but can differ in, structure. Such, compounds can be represented by graphs that cannot be drawn in the same way., The graphs, representing previously known compounds can be used to determine whether a, supposedly new, compound has been studied before., 672 10 / Graphs, There is a useful terminology for graphs with the same structure., DEFINITION 1 The simple graphs G1 = (V1,E1) and G2 = (V2,E2) are, isomorphic if there exists a onetoone and onto function f from V1 to V2 with the property that a and b are, adjacent in G1 if
Page 13 :
Euler and Hamilton Paths, Introduction, Can we travel along the edges of a graph starting at a vertex and returning to it, by traversing each edge of the graph exactly once? Similarly, can we travel, along the edges of a graph starting at a vertex and returning to it while visiting, each vertex of the graph exactly once? Although, these questions seem to be similar, the first question, which asks whether a, graph has an Euler circuit, can be easily answered simply by examining the, degrees of the vertices of the graph, while the second question, which asks, whether a graph has a Hamilton circuit, is quite difficult, to solve for most graphs. In this section we will study these questions and, discuss the difficulty of solving them. Although both questions have many, practical applications in many different, areas, both arose in old puzzles. We will learn about these old puzzles as well as, modern practical applications., Euler Paths and Circuits, The town of Königsberg, Prussia (now called Kaliningrad and part of the, Russian republic), was divided into four sections by the branches of the Pregel, River. These four sections included, the two regions on the banks of the Pregel, Kneiphof Island, and the region, between the two branches of the Pregel. In the eighteenth century seven bridges, connected these regions. Figure 1 depicts these regions and bridges., The townspeople took long walks through town on Sundays. They wondered, whether it was possible to start at some location in the town, travel across all the, bridges once without crossing any bridge twice, and return to the starting point., The Swiss mathematician Leonhard Euler solved this problem. His solution,, published in 1736, may be the first use of graph theory. (For a translation of, Euler’s original paper see, [BiLlWi99].) Euler studied this problem using the multigraph obtained when, the four regions are represented by vertices and the bridges by edges. This, multigraph is shown in Figure 2.
Page 14 :
DEFINITION 1 An Euler circuit in a graph G is a simple circuit containing, every edge of G. An Euler path in G is a simple path containing every edge of, G., Examples 1 and 2 illustrate the concept of Euler circuits and paths., EXAMPLE 1 Which of the undirected graphs in Figure 3 have an Euler, circuit? Of those that do not, which have an Euler path?, Solution: The graph G1 has an Euler circuit, for example, a, e, c, d, e, b, a., Neither of the, graphs G2 or G3 has an Euler circuit (the reader should verify this). However,, G3 has, an Euler path, namely, a, c, d, e, b, d, a, b. G2 does not have an Euler path (as, the readershould verify)., EXAMPLE 2 Which of the directed graphs in Figure 4 have an Euler circuit?, Of those that do not, which have an Euler path?, Solution: The graph H2 has an Euler circuit, for example, a, g, c, b, g, e, d, f, a., Neither H1, nor H3 has an Euler circuit (as the reader should verify). H3 has an Euler path,, namely,, c, a, b, c, d, b, but H1 does not (as the reader should verify)
