Lecture notes Graph Theory

graph theory and combinatorics lecture notes lecture notes on algebraic graph theory and lecture notes on spectral graph theory advanced graph theory lecture notes
Dr.NaveenBansal Profile Pic
Dr.NaveenBansal,India,Teacher
Published Date:25-10-2017
Your Website URL(Optional)
Comment
CHAPTER 8 Graph Theory 8.1 INTRODUCTION, DATA STRUCTURES Graphs, directed graphs, trees and binary trees appear in many areas of mathematics and computer science. This and the next two chapters will cover these topics. However, in order to understand how these objects may be stored in memory and to understand algorithms on them, we need to know a little about certain data structures. We assume the reader does understand linear and two-dimensional arrays; hence we will only discuss linked lists and pointers, and stacks and queues below. Linked Lists and Pointers Linked lists and pointers will be introduced by means of an example. Suppose a brokerage firm maintains a file in which each record contains a customer’s name and salesman; say the file contains the following data: Customer Adams Brown Clark Drew Evans Farmer Geller Hiller Infeld Salesman Smith Ray Ray Jones Smith Jones Ray Smith Ray There are two basic operations that one would want to perform on the data: Operation A: Given the name of a customer, find his salesman. Operation B: Given the name of a salesman, find the list of his customers. We discuss a number of ways the data may be stored in the computer, and the ease with which one can perform the operations A and B on the data. Clearly, the file could be stored in the computer by an array with two rows (or columns) of nine names. Since the customers are listed alphabetically, one could easily perform operation A. However, in order to perform operation B one must search through the entire array. One can easily store the data in memory using a two-dimensional array where, say, the rows correspond to an alphabetical listing of the customers and the columns correspond to an alphabetical listing of the salesmen, and where there isa1inthe matrix indicating the salesman of a customer and there are 0’s elsewhere. The main drawback of such a representation is that there may be a waste of a lot of memory because many 0’s may be in the matrix. For example, if a firm has 1000 customers and 20 salesmen, one would need 20000 memory locations for the data, but only 1000 of them would be useful. We discuss below a way of storing the data in memory which uses linked lists and pointers. By a linked list, we mean a linear collection of data elements, called nodes, where the linear order is given by means of a field 154 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use. CHAP. 8 GRAPH THEORY 155 of pointers. Figure 8-1 is a schematic diagram of a linked list with six nodes. That is, each node is divided into two parts: the first part contains the information of the element (e.g., NAME, ADDRESS, ...), and the second part, called the link field or nextpointer field, contains the address of the next node in the list. This pointer field is indicated by an arrow drawn from one node to the next node in the list. There is also a variable pointer, called START in Fig. 8-1, which gives the address of the first node in the list. Furthermore, the pointer field of the last node contains an invalid address, called a null pointer, which indicates the end of the list. Fig. 8-1 Linked list with 6 nodes OnemainwayofstoringtheoriginaldatapicturedinFig.8-2,useslinkedlists.Observethatthereareseparate (sorted alphabetically) arrays for the customers and the salesmen. Also, there is a pointer array SLSM parallel to CUSTOMER which gives the location of the salesman of a customer, hence operation A can be performed very easily and quickly. Furthermore, the list of customers of each salesman is a linked list as discussed above. Specifically, there is a pointer array START parallel to SALESMAN which points to the first customer of a salesman, and there is an array NEXT which points to the location of the next customer in the salesman’s list (or containsa0to indicate the end of the list). This process is indicated by the arrows in Fig. 8-2 for the salesman Ray. Fig. 8-2 Operation B can now be performed easily and quickly; that is, one does not need to search through the list of all customers in order to obtain the list of customers of a given salesman. Figure 8-3 gives such an algorithm (which is written in pseudocode). Stacks, Queues, and Priority Queues There are data structures other than arrays and linked lists which will occur in our graph algorithms. These structures, stacks, queues, and priority queues, are briefly described below. (a) Stack:A stack, also called a last-in first-out (LIFO) system, is a linear list in which insertions and deletions can take place only at one end, called the “top” of the list. This structure is similar in its operation to a stack of dishes on a spring system, as pictured in Fig. 8-4(a). Note that new dishes are inserted only at the top of the stack and dishes can be deleted only from the top of the stack.156 GRAPH THEORY CHAP. 8 Fig. 8-3 (b) Queue:Aqueue, also called a first-in first-out (FIFO) system, is a linear list in which deletions can only take place at one end of the list, the “front” of the list, and insertions can only take place at the other end of the list, the “rear” of the list. The structure operates in much the same way as a line of people waiting at a bus stop, as pictured in Fig. 8-4(b). That is, the first person in line is the first person to board the bus, and a new person goes to the end of the line. (c) Priovity queue: Let S be a set of elements where new elements may be periodically inserted, but where the current largest element (element with the “highest priority”) is always deleted. Then S is called a priority queue.The rules “women and children first” and “age before beauty” are examples of priority queues. Stacks and ordinary queues are special kinds of priority queues. Specifically, the element with the highest priority in a stack is the last element inserted, but the element with the highest priority in a queue is the first element inserted. Fig. 8-4 8.2 GRAPHS AND MULTIGRAPHS A graph G consists of two things: (i) A set V = V (G) whose elements are called vertices, points,or nodes of G. (ii) A set E = E(G) of unordered pairs of distinct vertices called edges of G. We denote such a graph by G(V, E) when we want to emphasize the two parts of G.CHAP. 8 GRAPH THEORY 157 Vertices u and v are said to be adjacent or neighbors if there is an edge e=u, v. In such a case, u and v are called the endpoints of e, and e is said to connect u and v.Also, the edge e is said to be incident on each of its endpoints u and v. Graphs are pictured by diagrams in the plane in a natural way. Specifically, each vertex v in V is represented by a dot (or small circle), and each edge e=v ,v is represented by a curve which connects 1 2 its endpoints v and v For example, Fig. 8-5(a) represents the graph G(V, E) where: 1 2 (i) V consists of vertices A, B, C, D. (ii) E consists of edges e =A,B, e =B,C, e =C,D, e =A,C, e =B,D. 1 2 3 4 5 In fact, we will usually denote a graph by drawing its diagram rather than explicitly listing its vertices and edges. Fig. 8-5 Multigraphs Consider the diagram in Fig. 8-5(b). The edges e and e are called multiple edges since they connect the 4 5 same endpoints, and the edge e is called a loop since its endpoints are the same vertex. Such a diagram is called 6 a multigraph; the formal definition of a graph permits neither multiple edges nor loops. Thus a graph may be defined to be a multigraph without multiple edges or loops. Remark: Some texts use the term graph to include multigraphs and use the term simple graph to mean a graph without multiple edges and loops. Degree of a Vertex The degree of a vertex v in a graph G, written deg (v), is equal to the number of edges in G which contain v, that is, which are incident on v. Since each edge is counted twice in counting the degrees of the vertices of G, we have the following simple but important result. Theorem 8.1: The sum of the degrees of the vertices of a graph G is equal to twice the number of edges in G. Consider, for example, the graph in Fig. 8-5(a). We have deg(A)= 2, deg(B)= 3, deg(C)= 3, deg(D)= 2. The sum of the degrees equals 10 which, as expected, is twice the number of edges. A vertex is said to be even or odd according as its degree is an even or an odd number. Thus A and D are even vertices whereas B and C are odd vertices. Theorem 8.1 also holds for multigraphs where a loop is counted twice toward the degree of its endpoint. For example, in Fig. 8-5(b) we have deg(D) = 4 since the edge e is counted twice; hence D is an even vertex. 6 A vertex of degree zero is called an isolated vertex.158 GRAPH THEORY CHAP. 8 Finite Graphs, Trivial Graph Amultigraph is said to be finite if it has a finite number of vertices and a finite number of edges. Observe that a graph with a finite number of vertices must automatically have a finite number of edges and so must be finite. The finite graph with one vertex and no edges, i.e., a single point, is called the trivial graph. Unless otherwise specified, the multigraphs in this book shall be finite. 8.3 SUBGRAPHS, ISOMORPHIC AND HOMEOMORPHIC GRAPHS This section will discuss important relationships between graphs. Subgraphs Consider a graph G= G(V, E).Agraph H = H(V ,E ) is called a subgraph of G if the vertices and edges of H are contained in the vertices and edges of G, that is, if V ⊆ V and E ⊆ E. In particular: (i) A subgraph H(V ,E ) of G(V, E) is called the subgraph induced by its vertices V if its edge set E contains all edges in G whose endpoints belong to vertices in H. (ii) If v is a vertex in G, then G− v is the subgraph of G obtained by deleting v from G and deleting all edges in G which contain v. (iii) If e is an edge in G, then G− e is the subgraph of G obtained by simply deleting the edge e from G. Isomorphic Graphs ∗ ∗ Graphs G(V, E) and G(V ,E ) are said to be isomorphic if there exists a one-to-one correspondence ∗ ∗ f: V → V such thatu, v is an edge of G if and only iff (u), f (v) is an edge of G . Normally, we do not distinguish between isomorphic graphs (even though their diagrams may “look different”). Figure 8-6 gives ten graphs pictured as letters. We note that A and R are isomorphic graphs.Also, F and T are isomorphic graphs, K and X are isomorphic graphs and M, S, V, and Z are isomorphic graphs. Fig. 8-6 Homeomorphic Graphs Given any graph G, we can obtain a new graph by dividing an edge of G with additional vertices.Two graphs ∗ G and G are said to homeomorphic if they can be obtained from the same graph or isomorphic graphs by this method. The graphs (a) and (b) in Fig. 8-7 are not isomorphic, but they are homeomorphic since they can be obtained from the graph (c) by adding appropriate vertices.CHAP. 8 GRAPH THEORY 159 Fig. 8-7 8.4 PATHS, CONNECTIVITY A path in a multigraph G consists of an alternating sequence of vertices and edges of the form v,e,v,e,v , ..., e ,v ,e,v 0 1 1 2 2 n−1 n−1 n n where each edge e contains the vertices v and v (which appear on the sides of e in the sequence). The i i−1 i i number n of edges is called the length of the path. When there is no ambiguity, we denote a path by its sequence of vertices (v ,v ,...,v ). The path is said to be closed if v = v . Otherwise, we say the path is from v ,to v 0 1 n 0 n 0 n or between v and v ,or connects v to v . 0 n 0 n A simple path is a path in which all vertices are distinct. (Apath in which all edges are distinct will be called a trail.) A cycle is a closed path of length 3 or more in which all vertices are distinct except v = v . A cycle of 0 n length k is called a k-cycle. EXAMPLE 8.1 Consider the graph G in Fig. 8-8(a). Consider the following sequences: α = (P ,P ,P ,P ,P ,P ,P ,P ), β = (P ,P ,P ,P ,P ), 4 1 2 5 1 2 3 6 4 1 5 2 6 γ = (P ,P ,P ,P ,P ,P ,P ), δ = (P ,P ,P ,P ,P ). 4 1 5 2 3 5 6 4 1 5 3 6 The sequence α is a path from P to P ; but it is not a trail since the edgeP ,P is used twice. The sequence 4 6 1 2 β is not a path since there is no edge P ,P . The sequence γ is a trail since no edge is used twice; but it is 2 6 not a simple path since the vertex P is used twice. The sequence δ is a simple path from P to P ; but it is 5 4 6 not the shortest path (with respect to length) from P to P . The shortest path from P to P is the simple path 4 6 4 6 (P ,P ,P ) which has length 2. 4 5 6 Fig. 8-8 By eliminating unnecessary edges, it is not difficult to see that any path from a vertex u to a vertex v can be replaced by a simple path from u to v. We state this result formally. Theorem 8.2: There is a path from a vertex u to a vertex v if and only if there exists a simple path from u to v.160 GRAPH THEORY CHAP. 8 Connectivity, Connected Components Agraph Gis connected ifthereisapathbetweenanytwoofitsvertices.ThegraphinFig.8-8(a)isconnected, but the graph in Fig. 8-8(b) is not connected since, for example, there is no path between vertices D and E. Suppose G is a graph. A connected subgraph H of G is called a connected component of G if H is not contained in any larger connected subgraph of G. It is intuitively clear that any graph G can be partitioned into its connected components. For example, the graph G in Fig. 8-8(b) has three connected components, the subgraphs induced by the vertex setsA,C,D,E,F, andB. The vertex B in Fig. 8-8(b) is called an isolated vertex since B does not belong to any edge or, in other words, deg(B) = 0. Therefore, as noted, B itself forms a connected component of the graph. Remark: Formally speaking, assuming any vertex u is connected to itself, the relation “u is connected to v” is an equivalence relation on the vertex set of a graph G and the equivalence classes of the relation form the connected components of G. Distance and Diameter Consider a connected graph G. The distance between vertices u and v in G, written d(u, v), is the length of the shortest path between u and v. The diameter of G, written diam(G), is the maximum distance between any two points in G. For example, in Fig. 8-9(a), d(A,F) = 2 and diam(G) = 3, whereas in Fig. 8-9(b), d(A,F) = 3 and diam(G)= 4. Cutpoints and Bridges Let G be a connected graph.Avertex v in G is called a cutpoint if G− v is disconnected. (Recall that G− v is the graph obtained from G by deleting v and all edges containing v.)An edge e of G is called a bridge if G−e is disconnected. (Recall that G− e is the graph obtained from G by simply deleting the edge e). In Fig. 8-9(a), the vertex D is a cutpoint and there are no bridges. In Fig. 8-9(b), the edge=D,F is a bridge. (Its endpoints D and F are necessarily cutpoints.) Fig. 8-9 8.5 TRAVERSABLE AND EULERIAN GRAPHS, BRIDGES OF KÖNIGSBERG The eighteenth-century East Prussian town of Königsberg included two islands and seven bridges as shown in Fig. 8-10(a). Question: Beginning anywhere and ending anywhere, can a person walk through town crossing all seven bridges but not crossing any bridge twice? The people of Königsberg wrote to the celebrated Swiss mathematician L. Euler about this question. Euler proved in 1736 that such a walk is impossible. He replaced the islands and the two sides of the river by points and the bridges by curves, obtaining Fig. 8-10(b). Observe that Fig. 8-10(b) is a multigraph.Amultigraph is said to be traversable if it “can be drawn without any breaks in the curve and without repeating any edges,” that is, if there is a path which includes all vertices and uses each edge exactly once. Such a path must be a trail (since no edge is used twice) and will be called a traversable trail. Clearly a traversable multigraph must be finite and connected.CHAP. 8 GRAPH THEORY 161 Fig. 8-10 We now show how Euler proved that the multigraph in Fig. 8-10(b) is not traversable and hence that the walk in Königsberg is impossible. Recall first that a vertex is even or odd according as its degree is an even or an odd number. Suppose a multigraph is traversable and that a traversable trail does not begin or end at a vertex P. We claim that P is an even vertex. For whenever the traversable trail enters P by an edge, there must always be an edge not previously used by which the trail can leave P. Thus the edges in the trail incident with P must appear in pairs, and so P is an even vertex. Therefore if a vertex Q is odd, the traversable trail must begin or end at Q. Consequently, a multigraph with more than two odd vertices cannot be traversable. Observe that the multigraph corresponding to the Königsberg bridge problem has four odd vertices.Thus one cannot walk through Königsberg so that each bridge is crossed exactly once. Euler actually proved the converse of the above statement, which is contained in the following theorem and corollary. (The theorem is proved in Problem 8.9.) A graph G is called an Eulerian graph if there exists a closed traversable trail, called an Eulerian trail. Theorem 8.3 (Euler): A finite connected graph is Eulerian if and only if each vertex has even degree. Corollary 8.4: Any finite connected graph with two odd vertices is traversable.Atraversable trail may begin at either odd vertex and will end at the other odd vertex. Hamiltonian Graphs TheabovediscussionofEuleriangraphsemphasizedtravelingedges;hereweconcentrateonvisitingvertices. A Hamiltonian circuit in a graph G, named after the nineteenth-century Irish mathematician William Hamilton (1803–1865), is a closed path that visits every vertex in G exactly once. (Such a closed path must be a cycle.) If G does admit a Hamiltonian circuit, then G is called a Hamiltonian graph. Note that an Eulerian circuit traverses every edge exactly once, but may repeat vertices, while a Hamiltonian circuit visits each vertex exactly once but may repeat edges. Figure 8-11 gives an example of a graph which is Hamiltonian but not Eulerian, and vice versa. Fig. 8-11162 GRAPH THEORY CHAP. 8 Although it is clear that only connected graphs can be Hamiltonian, there is no simple criterion to tell us whetherornotagraphisHamiltonianasthereisforEuleriangraphs.Wedohavethefollowingsufficientcondition which is due to G. A. Dirac. Theorem 8.5: Let G be a connected graph with n vertices. Then G is Hamiltonian if n≥ 3 and n≤ deg(v) for each vertex v in G. 8.6 LABELED AND WEIGHTED GRAPHS A graph G is called a labeled graph if its edges and/or vertices are assigned data of one kind or another. In particular, G is called a weighted graph if each edge e of G is assigned a nonnegative number w(e) called the weight or length of v. Figure 8-12 shows a weighted graph where the weight of each edge is given in the obvious way. The weight (or length) of a path in such a weighted graph G is defined to be the sum of the weights of the edges in the path. One important problem in graph theory is to find a shortest path, that is, a path of minimum weight (length), between any two given vertices. The length of a shortest path between P and Q in Fig. 8-12 is 14; one such path is (P, A ,A ,A ,A ,A ,Q) 1 2 5 3 6 The reader can try to find another shortest path. Fig. 8-12 8.7 COMPLETE, REGULAR, AND BIPARTITE GRAPHS Therearemanydifferenttypesofgraphs.Thissectionconsidersthreeofthem:complete,regular,andbipartite graphs. Complete Graphs Agraph G is said to be complete if every vertex in G is connected to every other vertex in G.Thus a complete graph G must be connected. The complete graph with n vertices is denoted by K . Figure 8-13 shows the graphs n K through K . 1 6 Regular Graphs Agraph G is regular of degree k or k-regular if every vertex has degree k. In other words, a graph is regular if every vertex has the same degree. The connected regular graphs of degrees 0, 1, or 2 are easily described. The connected 0-regular graph is the trivial graph with one vertex and no edges. The connected 1-regular graph is the graph with two vertices and one edge connecting them. The connected 2-regular graph with n vertices is the graph which consists of a single n-cycle. See Fig. 8-14. The 3-regular graphs must have an even number of vertices since the sum of the degrees of the vertices is an even number (Theorem 8.1). Figure 8-15 shows two connected 3-regular graphs with six vertices. In general, regular graphs can be quite complicated. For example, there are nineteen 3-regular graphs with ten vertices. We note that the complete graph with n vertices K is regular of degree n− 1. nCHAP. 8 GRAPH THEORY 163 Fig. 8-13 Fig. 8-14 Fig. 8-15 Bipartite Graphs Agraph G is said to be bipartite if its vertices V can be partitioned into two subsets M and N such that each edge of G connects a vertex of M to a vertex of N. By a complete bipartite graph, we mean that each vertex of M is connected to each vertex of N; this graph is denoted by K where m is the number of vertices in M and m,n n is the number of vertices in N, and, for standardization, we will assume m≤ n. Figure 8-16 shows the graphs K , K , and K , Clearly the graph K has mn edges. 2,3 3,3 2,4 m,n164 GRAPH THEORY CHAP. 8 Fig. 8-16 8.8 TREE GRAPHS A graph T is called a tree if T is connected and T has no cycles. Examples of trees are shown in Fig. 8-17. A forest G is a graph with no cycles; hence the connected components of a forest G are trees. A graph without cycles is said to be cycle-free. The tree consisting of a single vertex with no edges is called the degenerate tree. Consider a tree T . Clearly, there is only one simple path between two vertices of T ; otherwise, the two paths would form a cycle. Also: (a) Suppose there is no edgeu, v in T and we add the edge e=u, v to T . Then the simple path from u to v in T and e will form a cycle; hence T is no longer a tree. (b) On the other hand, suppose there is an edge e=u, v in T , and we delete e from T . Then T is no longer connected (since there cannot be a path from u to v); hence T is no longer a tree. The following theorem (proved in Problem 8.14) applies when our graphs are finite. Theorem 8.6: Let G be a graph withn 1 vertices. Then the following are equivalent: (i) G is a tree. (ii) G is a cycle-free and has n− 1 edges. (iii) G is connected and has n− 1 edges. This theorem also tells us that a finite tree T with n vertices must have n− 1 edges. For example, the tree in Fig. 8-17(a) has 9 vertices and 8 edges, and the tree in Fig. 8-17(b) has 13 vertices and 12 edges. Fig. 8-17 Spanning Trees A subgraph T of a connected graph G is called a spanning tree of G if T is a tree and T includes all the vertices of G. Figure 8-18 shows a connected graph G and spanning trees T , T , and T of G. 1 2 3CHAP. 8 GRAPH THEORY 165 Fig. 8-18 Minimum Spanning Trees Suppose G is a connected weighted graph. That is, each edge of G is assigned a nonnegative number called the weight of the edge. Then any spanning tree T of G is assigned a total weight obtained by adding the weights of the edges in T.A minimal spanning tree of G is a spanning tree whose total weight is as small as possible. Algorithms 8.2 and 8.3, which appear in Fig. 8-19, enable us to find a minimal spanning tree T of a connected weighted graph G where G has n vertices. (In which case T must have n− 1 vertices.) Fig. 8-19 Theweightofaminimalspanningtreeisunique,buttheminimalspanningtreeitselfisnot.Differentminimal spanning trees can occur when two or more edges have the same weight. In such a case, the arrangement of the edges in Step 1 of Algorithms 8.2. or 8.3 is not unique and hence may result in different minimal spanning trees as illustrated in the following example. EXAMPLE 8.2 Find a minimal spanning tree of the weighted graph Q in Fig. 8-20(a). Note that Q has six vertices, so a minimal spanning tree will have five edges. (a) Here we apply Algorithm 8.2. First we order the edges by decreasing weights, and then we successively delete edges without disconnecting Q until five edges remain. This yields the following data: Edges BC AF AC BE CE BF AE DF BD Weight 8 7 7 7 6 5 4 4 3 Delete Yes Yes Yes No No Yes166 GRAPH THEORY CHAP. 8 Thus the minimal spanning tree of Q which is obtained contains the edges BE,CE,AE,DF,BD The spanning tree has weight 24 and it is shown in Fig. 8-20(b). Fig. 8-20 (b) Here we apply Algorithm 8.3. First we order the edges by increasing weights, and then we successively add edges without forming any cycles until five edges are included. This yields the following data: Edges BD AE DF BF CE AC AF BE BC Weight 3 4 4 5 6 7 7 7 8 Add? Yes Yes Yes No Yes No Yes Thus the minimal spanning tree of Q which is obtained contains the edges BD,AE,DF,CE,AF The spanning tree appears in Fig. 8-20(c). Observe that this spanning tree is not the same as the one obtained using Algorithm 8.2 as expected it also has weight 24. Remark: The above algorithms are easily executed when the graph G is relatively small as in Fig. 8-20(a). Suppose G has dozens of vertices and hundreds of edges which, say, are given by a list of pairs of vertices. Then even deciding whether G is connected is not obvious; it may require some type of depth-first search (DFS) or breadth-first search (BFS) graph algorithm. Later sections and the next chapter will discuss ways of representing graphs G in memory and will discuss various graph algorithms. 8.9 PLANAR GRAPHS A graph or multigraph which can be drawn in the plane so that its edges do not cross is said to be planar. Although the complete graph with four vertices K is usually pictured with crossing edges as in Fig. 8-21(a),it 4 can also be drawn with noncrossing edges as in Fig. 8-21(b); hence K is planar. Tree graphs form an important 4 class of planar graphs. This section introduces our reader to these important graphs. Fig. 8-21CHAP. 8 GRAPH THEORY 167 Maps, Regions A particular planar representation of a finite planar multigraph is called a map. We say that the map is connected if the underlying multigraph is connected. A given map divides the plane into various regions. For example, the map in Fig. 8-22 with six vertices and nine edges divides the plane into five regions. Observe that four of the regions are bounded, but the fifth region, outside the diagram, is unbounded. Thus there is no loss in generality in counting the number of regions if we assume that our map is contained in some large rectangle rather than in the entire plane. Observe that the border of each region of a map consists of edges. Sometimes the edges will form a cycle, but sometimes not. For example, in Fig. 8-22 the borders of all the regions are cycles except for r . However, if 3 we do move counterclockwise around r starting, say, at the vertex C, then we obtain the closed path 3 (C,D,E,F,E,C) where the edgeE,F occurs twice. By the degree of a region r, written deg(r), we mean the length of the cycle or closed walk which borders r. We note that each edge either borders two regions or is contained in a region and will occur twice in any walk along the border of the region. Thus we have a theorem for regions which is analogous to Theorem 8.1 for vertices. Fig. 8-22 Theorem 8.7: The sum of the degrees of the regions of a map is equal to twice the number of edges. The degrees of the regions of Fig. 8-22 are: deg(r ) = 3, deg(r ) = 3, deg(r )= 5, deg(r )= 4, deg(r )= 3 1 2 3 4 5 The sum of the degrees is 18, which, as expected, is twice the number of edges. For notational convenience we shall picture the vertices of a map with dots or small circles, or we shall assume that any intersections of lines or curves in the plane are vertices. Euler’s Formula Euler gave a formula which connects the number V of vertices, the number E of edges, and the number R of regions of any connected map. Specifically: Theorem 8.8 (Euler): V − E+ R = 2. (The proof of Theorem 8.8 appears in Problem 8.18.) Observe that, in Fig. 8-22, V = 6, E = 9, and R = 5; and, as expected by Euler’s formula. V − E+ R = 6− 9+ 5 = 2 We emphasize that the underlying graph of a map must be connected in order for Euler’s formula to hold. Let G be a connected planar multigraph with three or more vertices, so G is neither K nor K . Let M be a 1 2 planar representation of G. It is not difficult to see that (1) a region of M can have degree 1 only if its border is a loop, and (2) a region of M can have degree 2 only if its border consists of two multiple edges. Accordingly, if G is a graph, not a multigraph, then every region of M must have degree 3 or more. This comment together with Euler’s formula is used to prove the following result on planar graphs.168 GRAPH THEORY CHAP. 8 Theorem 8.9: Let G be a connected planar graph with p vertices and q edges, where p ≥ 3. Then q ≥ 3p− 6. Note that the theorem is not true for K where p = 1 and q = 0, and is not true for K where p = 2 1 2 and q − 1. Proof: Let r be the number of regions in a planar representation of G. By Euler’s formula, p− q + r = 2. Now the sum of the degrees of the regions equals 2q by Theorem 8.7. But each region has degree 3 or more; hence 2q ≥ 3r. Thus r ≥ 2q/3. Substituting this in Euler’s formula gives 2q q 2 = p− q + r ≤ p− q + or 2≤ p− 3 3 Multiplying the inequality by 3 gives 6 ≤ 3p− q which gives us our result. Nonplanar Graphs, Kuratowski’s Theorem We give two examples of nonplanar graphs. Consider first the utility graph; that is, three houses A , A , A 1 2 3 are to be connected to outlets for water, gas and electricity, B , B , B , as in Fig. 8-23(a). Observe that this is the 1 2 3 graph K and it has p = 6 vertices and q = 9 edges. Suppose the graph is planar. By Euler’s formula a planar 3,3 representation has r = 5 regions. Observe that no three vertices are connected to each other; hence the degree of each region must be 4 or more and so the sum of the degrees of the regions must be 20 or more. By Theorem 8.7 the graph must have 10 or more edges. This contradicts the fact that the graph has q = 9 edges. Thus the utility graph K is nonplanar. 3,3 Consider next the star graph in Fig. 8-23(b).This is the complete graph K on p = 5 vertices and has q = 10 5 edges. If the graph is planar, then by Theorem 8.9. 10 = q ≤ 3p− 6 = 15− 6 = 9 which is impossible. Thus K is nonplanar. 5 For many years mathematicians tried to characterize planar and nonplanar graphs. This problem was finally solved in 1930 by the Polish mathematician K. Kuratowski. The proof of this result, stated below, lies beyond the scope of this text. Fig. 8-23 Theorem 8.10: (Kuratowski)Agraph is nonplanar if and only if it contains a subgraph homeomorphic to K 3,3 or K . 5 8.10 GRAPH COLORINGS Consider a graph G. A vertex coloring, or simply a coloring of G is an assignment of colors to the vertices of G such that adjacent vertices have different colors. We say that G is n-colorable if there exists a coloring of G which uses n colors. (Since the word “color” is used as a noun, we will try to avoid its use as a verb by saying,CHAP. 8 GRAPH THEORY 169 for example, “paint” G rather than “color” G when we are assigning colors to the vertices of G.) The minimum number of colors needed to paint G is called the chromatic number of G and is denoted by χ(G). Fig. 8-24 gives an algorithm by Welch and Powell for a coloring of a graph G. We emphasize that this algorithm does not always yield a minimal coloring of G. Fig. 8-24 EXAMPLE 8.3 (a) ConsiderthegraphGinFig.8-25.WeusetheWelch-PowellAlgorithm8.4toobtainacoloringof G.Ordering the vertices according to decreasing degrees yields the following sequence: A,A,A,A,A,A,A,A 5 3 7 1 2 4 6 8 Fig. 8-25 The first color is assigned to vertices A and A . The second color is assigned to vertices A , A , and A . 5 1 3 4 8 The third color is assigned to vertices A , A , and A . All the vertices have been assigned a color, and so G 7 2 6 is 3-colorable. Observe that G is not 2-colorable since vertices A , A , and A , which are connected to each 1 2 3 other, must be assigned different colors. Accordingly, χ(G) = 3. (b) Consider the complete graph K with n vertices. Since every vertex is adjacent to every other vertex, K n n requires n colors in any coloring. Thus χ(K )= n. n There is no simple way to actually determine whether an arbitrary graph is n-colorable. However, the following theorem (proved in Problem 8.19) gives a simple characterization of 2-colorable graphs.170 GRAPH THEORY CHAP. 8 Theorem 8.11: The following are equivalent for a graph G: (i) G is 2-colorable. (ii) G is bipartite. (iii) Every cycle of G has even length. There is no limit on the number of colors that may be required for a coloring of an arbitrary graph since, for example, the complete graph K requires n colors. However, if we restrict ourselves to planar graphs, regardless n of the number of vertices, five colors suffice. Specifically, in Problem 8.20 we prove: Theorem 8.12: Any planar graph is 5-colorable. Actually, since the 1850s mathematicians have conjectured that planar graphs are 4-colorable since every known planar graph is 4-colorable. KennethAppel and Wolfgang Haken finally proved this conjecture to be true in 1976. That is: Four Color Theorem (Appel and Haken): Any planar graph is 4-colorable. We discuss this theorem in the next subsection. Dual Maps and the Four Color Theorem Consider a map M, say the map M in Fig. 8-26(a). In other words, M is a planar representation of a planar multigraph. Two regions of M are said to be adjacent if they have an edge in common. Thus the regions r and 2 r in Fig. 8-26(a) are adjacent, but the regions r and r are not. By a coloring of M we mean an assignment 5 3 5 of a color to each region of M such that adjacent regions have different colors. A map M is n-colorable if there exists a coloring of M which uses n colors. Thus the map M in Fig. 8-26(a) is 3-colorable since the regions can be assigned the following colors: r red,r white,r red,r white,r red,r blue 1 2 3 4 5 6 Observe the similarity between this discussion on coloring maps and the previous discussion on coloring graphs. In fact, using the concept of the dual map defined below, the coloring of a map can be shown to be equivalent to the vertex coloring of a planar graph. Consider a map M. In each region of M we choose a point, and if two regions have an edge in common then we connect the corresponding points with a curve through the common edge. These curves can be drawn ∗ ∗ so that they are noncrossing. Thus we obtain a new map M , called the dual of M, such that each vertex of M corresponds to exactly one region of M. Figure 8-26(b) shows the dual of the map of Fig. 8-26(a). One can prove ∗ ∗ that each region of M will contain exactly one vertex of M and that each edge of M will intersect exactly one ∗ edge of M and vice versa. Thus M will be the dual of the map M . Fig. 8-26CHAP. 8 GRAPH THEORY 171 Observe that any coloring of the regions of a map M will correspond to a coloring of the vertices of the dual ∗ ∗ map M . Thus M is n-colorable if and only if the planar graph of the dual map M is vertex n-colorable. Thus the above theorem can be restated as follows: Four Color Theorem (Appel and Haken): If the regions of any map M are colored so that adjacent regions have different colors, then no more than four colors are required. Theproofoftheabovetheoremusescomputersinanessentialway.Specifically,AppelandHakenfirstshowed that if the four color theorem was false, then there must be a counterexample among one of approximately 2000 different types of planar graphs. They then showed, using the computer, that none of these types of graphs has such a counterexample. The examination of each different type of graph seems to be beyond the grasp of human beingswithouttheuseofacomputer.Thustheproof,unlikemostproofsinmathematics,istechnologydependent; that is, it depended on the development of high-speed computers. 8.11 REPRESENTING GRAPHS IN COMPUTER MEMORY There are two standard ways of maintaining a graph G in the memory of a computer. One way, called the sequential representation of G, is by means of its adjacency matrix A. The other way, called the linked representation or adjacency structure of G, uses linked lists of neighbors. Matrices are usually used when the graph G is dense, and linked lists are usually used when G is sparse. (A graph G with m vertices and n edges is 2 said to be dense when m = O(n ) and sparse when m= O(n) or even O(nlog n).) Regardless of the way one maintains a graph G in memory, the graph G is normally input into the computer by its formal definition, that is, as a collection of vertices and a collection of pairs of vertices (edges). Adjacency Matrix Suppose G is a graph with m vertices, and suppose the vertices have been ordered, say, v ,v ,...,v . Then 1 2 m the adjacency matrix A=a of the graph G is the m× m matrix defined by ij  1if v is adjacent to v i j a = ij 0 otherwise Figure 8-27(b) contains the adjacency matrix of the graph G in Fig. 8-27(a) where the vertices are ordered A, B, C, D, E. Observe that each edgev ,v of G is represented twice, by a = 1 and a = 1. Thus, in particular, i j ij ji the adjacency matrix is symmetric. The adjacency matrix A of a graph G does depend on the ordering of the vertices of G, that is, a different orderingoftheverticesyieldsadifferentadjacencymatrix.However,anytwosuchadjacencymatricesareclosely related in that one can be obtained from the other by simply interchanging rows and columns. On the other hand, theadjacencymatrixdoesnotdependontheorderinwhichtheedges(pairsofvertics)areinputintothecomputer. There are variations of the above representation. If G is a multigraph, then we usually let a denote the ij number of edgesv ,v . Moreover, if G is a weighted graph, then we may let a denote the weight of the edge i j ij v ,v . i j Fig. 8-27172 GRAPH THEORY CHAP. 8 Linked Representation of a Graph G Let G be a graph with m vertices.The representation of G in memory by its adjacency matrix A has a number of major drawbacks. First of all it may be difficult to insert or delete vertices in G. The reason is that the size of A may need to be changed and the vertices may need to be reordered, so there may be many, many changes in the matrix A. Furthermore, suppose the number of edges is O(m) or even O(mlog m), that is, suppose G is sparse. Then the matrix A will contain many zeros; hence a great deal of memory space will be wasted. Accordingly, when G is sparse, G is usually represented in memory by some type of linked representation, also called an adjacency structure, which is described below by means of an example. Considerthegraph GinFig.8-28(a).Observethat GmaybeequivalentlydefinedbythetableinFig.8-28(b) which shows each vertex in G followed by its adjacency list, i.e., its list of adjacent vertices (neighbors). Here the symbol denotes an empty list. This table may also be presented in the compact form G=A:B,D; B:A,C,D; C:B; D:A,B; E: where a colon “:” separates a vertex from its list of neighbors, and a semicolon “;” separates the different lists. Remark: Observe that each edge of a graph G is represented twice in an adjacency structure; that is, any edge, say A,B, is represented by B in the adjacency list of A, and also by A in the adjacency list of B. The graph G in Fig. 8-28(a) has four edges, and so there must be 8 vertices in the adjacency lists. On the other hand, each vertex in an adjacency list corresponds to a unique edge in the graph G. Fig. 8-28 The linked representation of a graph G, which maintains G in memory by using its adjacency lists, will normally contain two files (or sets of records), one called the Vertex File and the other called the Edge File, as follows. (a) Vertex File: The Vertex File will contain the list of vertices of the graph G usually maintained by an array or by a linked list. Each record of the Vertex File will have the form VERTEX NEXT-V PTR Here VERTEX will be the name of the vertex, NEXT-V points to the next vertex in the list of vertices in the Vertex File when the vertices are maintained by a linked list, and PTR will point to the first element in the adjacency list of the vertex appearing in the Edge File. The shaded area indicates that there may be other information in the record corresponding to the vertex. (b) Edge File: The Edge File contains the edges of the graph G. Specifically, the Edge File will contain all the adjacency lists of G where each list is maintained in memory by a linked list. Each record of the Edge File will correspond to a vertex in an adjacency list and hence, indirectly, to an edge of G. The record will usually have the form EDGE ADJ NEXTCHAP. 8 GRAPH THEORY 173 Here: (1) EDGE will be the name of the edge (if it has one). (2) ADJ points to the location of the vertex in the Vertex File. (3) NEXT points to the location of the next vertex in the adjacency list. We emphasize that each edge is represented twice in the Edge File, but each record of the file corresponds to a unique edge. The shaded area indicates that there may be other information in the record corresponding to the edge. Figure 8-29 shows how the graph G in Fig. 8-28(a) may appear in memory. Here the vertices of G are maintained in memory by a linked list using the variable START to point to the first vertex. (Alternatively, one could use a linear array for the list of vertices, and then NEXT-V would not be required.) Note that the field EDGE is not needed here since the edges have no name. Figure 8-29 also shows, with the arrows, the adjacency listD,C,A of the vertex B. Fig. 8-29 8.12 GRAPH ALGORITHMS This section discusses two important graph algorithms which systematically examine the vertices and edges of a graph G. One is called a depth-first search (DFS) and the other is called a breadth-first search (BFS). Other graph algorithms will be discussed in the next chapter in connection with directed graphs. Any particular graph algorithm may depend on the way G is maintained in memory. Here we assume G is maintained in memory by its adjacency structure. Our test graph G with its adjacency structure appears in Fig. 8-30 where we assume the vertices are ordered alphabetically. Fig. 8-30

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.