1、Outline,9.1 Graph and Graph Models 9.2 Graph Terminology and Special Types of Graphs 9.3 Representing Graphs and Graph Isomorphism 9.4 Connectivity 9.5 Euler and Hamiltonian Paths 9.6 Shortest-Path Problems 9.7 Planar Graphs 9.8 Graph Coloring,Ch9-1,9.1 Graphs and Graph Models,Def 1. A graph G = (V,

2、 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. eg.,Ch9-2,Def Multigraph: simple graph + there may be more than one edge connecting two given

3、nodes(multiedges).,eg.,Def 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.,Ch9-3,Def. Pseudograph:,simple graph + multiedge + loop,(a loop: ),eg.,Ch9-4,Note:,The two edges (u,v),(u,v) are multiedges.,The tw

4、o edges (u,v),(v,u) are not multiedges.,Def 2. Directed graph (digraph): graph with each edge directed,Note: is not allowed in a simple directed graph.,Def. Directed multigraph: digraph+loop+multiedges,Ch9-5,Table 1. Graph Terminology,Exercise : 3, 5, 6, 7, 9,Ch9-6,Example 2. (Acquaintanceship graph

5、s) We can use a simple graph to represent whether two people know each other. Each person is represented by a vertex. An undirected edge is used to connect two people when these people know each other.,Graph Models,eg,Ch9-7,Example 3. (Influence graphs) In studies of group behavior it is observed th

6、at certain people can influence the thinking of others. Simple digraph Each person of the group is represented by a vertex. There is a directed edge from vertex a to vertex b when the person a influences the person b.,eg,Ch9-8,Example 9. (Precedence graphs and concurrent processing) Computer program

7、s can be executed more rapidly by executing certain statements concurrently. It is important not to execute a statement that requires results of statements not yet executed. Simple digraph Each statement is represented by a vertex, and there is an edge from a to b if the statement of b cannot be exe

8、cuted before the statement of a.,eg,S1: a:=0S2: b:=1S3: c:=a+1 S4: d:=b+a S5: e:=d+1S6: e:=c+d,Ch9-9,Ex 13. The intersection graph of a collection of sets A1, A2, , An is the graph that has a vertex for each of these sets and has an edge connecting the vertices representing two sets if these sets ha

9、ve a nonempty intersection. Construct the intersection graph of the following collection of sets.(a) A1 = 0, 2, 4, 6, 8, A2 = 0, 1, 2, 3, 4, A3 = 1, 3, 5, 7, 9, A4 = 5, 6, 7, 8, 9, A5 = 0, 1, 8, 9.,Ch9-10,9.2 Graph Terminology and Special Types of Graphs,Def 1. G: undirected graph u and v are adjace

10、nt (or neighbors) e is incident with u and v u and v are endpoints of e Def 2. The degree of a vertex v, denoted by deg(v), in an undirected graph is the number of edges incident with it.,(Note : A loop adds 2 to the degree.),Ch9-11,Example 1. What are the degrees of the vertices in the graph H ?,De

11、f. A vertex of degree 0 is called isolated.,Sol :,Ch9-12,Thm 1. (The Handshaking Theorem) Let G = (V, E) be an undirected graph with e edges (i.e., |E| = e). Then,Note that this applies even if multiple edges and loops are present,Ch9-13,eg. The graph H has 11 edges, and,Example 3. How many edges ar

12、e there in a graph with 10 vertices each of degree six?,Sol : 10 6 = 2e e=30,Ch9-14,Thm 2. An undirected graph G = (V, E) has an even number of vertices of odd degree.,Pf : Let V1=vV | deg(v) is even, V2=vV | deg(v) is odd.,Def 3. G = (V, E): directed graph, e = (u, v) E : u is adjacent to v v is ad

13、jacent from u u : initial vertex of e v : terminal (end) vertex of e,e,Exercise : 5,Ch9-15,Def 4. G = (V, E) : directed graph, vV deg-(v) : # of edges with v as a terminal. (in-degree) deg+(v) : # of edges with v as a initial vertex (out-degree),Example 4.,deg-(a)=2, deg+(a)=4 deg-(b)=2, deg+(b)=1 d

14、eg-(c)=3, deg+(c)=2 deg-(d)=2, deg+(d)=2 deg-(e)=3, deg+(e)=3 deg-(f )=0, deg+(f )=0,Ch9-16,Thm 3. Let G = (V, E) be a digraph. Then,pf : for each edge deg+(u) gets increased by 1 so does deg-(v),Ch9-17,eg. K4 : is 3-regular.,(ex47) A simple graph G=(V, E) is called regular if every vertex of this g

15、raph has the same degree. A regular graph is called n-regular if deg(v)=n , vV.,Exercise : 7, 49,Ch9-18,Example 5. The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices.,Some Special Simple Graphs,Note. Kn is (n-1)-

16、regular, |V(Kn)|=n,Ch9-19,Example 6. The cycle Cn, n3, consists of n vertices v1, v2, , vn and n edges v1,v2, v2,v3, , vn-1,vn, vn,v1.,Note Cn is 2-regular, |V(Cn)| = n, |E(Cn)| = n,Ch9-20,Example 7. We obtained the wheel Wn when we add an additional vertex to the cycle Cn, for n3, and connect this

17、new vertex to each of the n vertices in Cn, by new edges.,W5,W6,Note. |V(Wn)| = n + 1, |E(Wn)| = 2n, Wn is not a regular graph if n 3.,Ch9-21,Example 8. The n-dimensional hypercube, or n-cube, denoted by Qn, is the graph that has vertices representing the 2n bit strings of length n.Two vertices are

18、adjacent if and only if the bit strings that they represent differ in exactly one bit position.,Q2,Note. Qn is n-regular, |V(Qn)| = 2n, |E(Qn)| = (2nn)/2 =2n-1n,Q1,0,1,10,11,00,01,Ch9-22,Def 5. A simple graph G=(V,E) is called bipartite if V can be partitioned into V1 and V2, V1V2=, such that every

19、edge in the graph connect a vertex in V1 and a vertex in V2.,Some Special Simple Graphs,Ch9-23,Example 11. Is the graph G bipartite?,Yes !,Exercise : 21, 23, 25,Ch9-24,Ch9-25,Thm 4. A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the

20、graph so that no two adjacent vertices are assigned the same color.,Example 12. Use Thm 4 to show that G is bipartite.,1,2,2,2,2,1,1,Example 13. Complete Bipartite graphs (Km,n),K2,3,K3,3,Note. |V(Km,n)| = m+n, |E(Km,n)| = mn, Km,n is regular if and only if m=n.,Ch9-26,Example 14. A subgraph of K5,D

21、ef 6. A subgraph of a graph G=(V, E) is a graph H=(W, F) where W V and F E.,New Graphs from Old,Ch9-27,Def 7. The union of two simple graphs G1=(V1, E1) and G2=(V2, E2) is the simple graph G1G2=(V1V2, E1E2),Ch9-28,Exercise : 51,9.3 Representing Graphs and Graph Isomorphism,Adjacency list Example 1.

22、Use adjacency lists to describe the simple graph given below.,Sol :,Ch9-29,Example 2. (digraph),a,b,e,d,c,Exercise : 3,Ch9-30,Adjacency Matrices Def. G=(V, E) : simple graph, V=v1,v2,vn. A matrix A is called the adjacency matrix of G if A=aijnn , where aij = 1, if vi,vjE, 0, otherwise.,Example 3.,No

23、te: The adjacency matrix of an undirected graph is symmetric.,Ch9-31,Example 5. (Pseudograph),Def. If A=aij is the adjacency matrix for the directed graph, then,Maybe not symmetric.,a,b,c,d,Exercise : 7, 14, 17, 23,Ch9-32,Def 1. The simple graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic if there is

24、an one-to-one and onto function f from V1 to V2 with the property that ab in G1 iff f(a)f(b) in G2, a,bV1 f is called an isomorphism.,Isomorphism of Graphs,u1,G,H,u3,u2,u4,v2,v4,v1,v3,G is isomorphic to H,Ch9-33,Graph Invariants under Isomorphism,Necessary but not sufficient conditions for G1=(V1, E

25、1) to be isomorphic to G2=(V2, E2): |V1|=|V2|, |E1|=|E2|. The number of vertices with degree n is the same in both graphs. For every proper subgraph g of one graph, there is a proper subgraph of the other graph that is isomorphic to g.,Example 8. Show that G and H are isomorphic.,The function f with

26、 f(u1) = v1, f(u2) = v4, f(u3) = v3, and f(u4) = v2 is a one-to-one correspondence between V(G) and V(H).,u1,G,H,u3,u2,u4,v2,v4,v1,v3,Sol.,Ch9-35,Example 9. Show that G and H are not isomorphic.,Sol :,G gets a vertex of degree 1, while H doesnt.,Ch9-36,Example 10. Determine whether G and H are isomo

27、rphic.,H,G,a,Sol1: Are the subgraphs of G and H made up of vertices of degreee 3 and the edges connecting them isomorphic? Sol2: in G, deg(a)=2 a must corresponds to x,y,t,u in H a is not adjacent to a vertex of degree 2 (in G), while all x,y,t,u are adjacent to a vertex of degree 2 (in H). not isom

28、orphic.,Ch9-37,Example 11. Determine whether the graphs G and H are isomorphic.,G,H,u1,u2,u4,u3,u5,u6,v1,v2,v3,v4,v5,v6,Sol: f(u1)=v6, f(u2)=v3, f(u3)=v4, f(u4)=v5, f(u5)=v1, f(u6)=v2 Yes,Exercise : 37, 39, 40,Ch9-38,u6,u5,u8,Ex44. Determine whether the graphs G and H are isomorphic.,G,H,u1,u2,u7,u4

29、,u3,v1,v2,v7,v4,v5,v6,v3,v8,Ch9-39,v1 has 5 neighbors, and the 5 neighbors can form a 5-cycle;,u1 also has 5 neighbors, but the 5 neighbors couldnt form a 5-cycle; Therefore G and H are not isomorphic.,Def. 1,2 : In an undirected graph, a path of length n from u to v is a sequence of n+1 adjacent ve

30、rtices going from vertex u to vertex v. (e.g., P: u=x0, x1, x2, , xn=v.) ( P has n edges.) Def: path: no repetition vertices or edges. trail: path + repetition verticeswalk: path + repetition vertices and edges,Example,9.4: Connectivity,Ch9-40,path: u, v, y trail: u, v, w, y, v, x, y walk: u, v, w,

31、v, x, v, y,Ch9-41,Def: cycle: path with u=vcircuit: trail with u=vclosed walk: walk with u=v,cycle: u, v, y, x, u circuit: u, v, w, y, v, x, u closed walk: u, v, w, v, x, v, y, x, u,Example,Paths in Directed Graphs,The same as in undirected graphs, but the path must go in the direction of the arrows

32、.,Connectedness in Undirected Graphs,Def. 3: An undirected graph is connected if there is a path between every pair of distinct vertices in the graph.,Def: Connected component: maximal connected subgraph.,Ch9-42,Example 6 What are the connected components of the graph H?,a,b,c,d,e,h,g,f,H,Ch9-43,Def

33、:A cut vertex separates one connected component into several components if it is removed.A cut edge separates one connected component into two components if it is removed.,Example 8. Find the cut vertices and cut edges in thegraph G.,cut vertices: b, c, e,cut edges: a, b, c, e,Sol:,Exercise : 29,31,

34、 32,Ch9-44,Def. 4: A directed graph is strongly connected if there is a path from a to b for any two vertices a, b. A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graphs.,Connectedness in Directed Graphs,Example 9 Are the directed grap

35、hs G and H strongly connected or weakly connected?,strongly connected,weakly connected,Ch9-45,Paths and Isomorphism,Example 12. Determine whether the graphs G and H are isomorphic.,Sol: No. G has no simple circuit of length 3, while H does.,Note that connectedness, and the existence of a circuit or

36、simple circuit of length k are graph invariants with respect to isomorphism.,Example 13. Determine whether the graphs G and H are isomorphic.,G,u2,u1,u3,u4,u5,H,v1,v5,v2,v3,v4,Both G and H have 5 vertices, 6 edges, two vertices of deg 3, three vertices of deg 2, a 3-cycle, a 4-cycle, and a 5-cycle.

37、G and H may be isomorphic. The function f with f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2 and f(u5) = v5 is a one-to-one correspondence between V(G) and V(H). G and H are isomorphic.,Sol.,Exercise : 19, 20,Ch9-47,Counting Paths between Vertices,Theorem 2: Let G be a graph with adjacency matrix A

38、 with respect to the ordering v1, v2, , vn. The number of paths (walks) of length r from vi to vj is equal to (Ar)i,j.,Ch9-48,Proof,Exercise : 17,Example 14. How many paths (walks) of length 4 are there from a to d in the graph G?,G,a,b,c,d,Sol. The adjacency matrix of G (ordering as a, b, c, d) is,

39、 8,Ch9-49,Q:,a-b-a-b-d, a-b-a-c-d, a-c-a-b-d, a-c-a-c-d, a-b-d-b-d, a-b-d-c-d, a-c-d-b-d, a-c-d-c-d,The origin of Graph Theory,1736, Euler solved the Knigsberg Bridge Problem,Q: Is there a simple circuit in this multigraph that contains every edge?,9.5: Euler & Hamilton Paths,Ch9-50,Def 1: An Euler

40、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.,Ch9-51,Thm. 1:A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. Thm. 2:A connected multigraph

41、has an Euler path (but not an Euler circuit) if and only if it has exactly 2 vertices of odd degree.,Example 1. Which of the following graphs have an Euler circuit or an Euler path?,Ch9-52,Euler circuit,Euler path,none,Exercise : 3, 5, 21, 26, 28,Procedure Euler(G: connected multigraph with all vert

42、ices of even degree) circuit := a circuit in G beginning at an arbitrary chosen vertex with edges successively added to form a path that returns to this vertex H := G with the edges of this circuit removed while H has edges begin subcircuit := a circuit in H beginning at a vertex in H that also is a

43、n endpoint of an edge of circuit H := H with edges of subcircuit and all isolated vertices removed circuit := circuit with subcircuit inserted at appropriate vertex end circuit is an Euler circuit,Algorithm 1 (Constructing Euler Circuits.),Ch9-53,v1,v2,v3,v5,v4,v6,Step 1: find the 1st circuit,C: v1,

44、 v2, v3, v4, v5, v1,Step 2: H = G - C , find subcircuit,SC: v3, v5, v6, v3,Step 3:,C = C SC, H= G - C =, stop,C: v1, v2, v3, v5, v6, v3, v4, v5, v1,SC embedded,Example,Ch9-54,Exercise : 7,Hamilton Paths and Circuits,Def. 2: A Hamilton path is a path that traverses each vertex in a graph G exactly on

45、ce.A Hamilton circuit is a circuit that traverses each vertex in G exactly once.,Ch9-55,Example 1. Which of the following graphs have a Hamilton circuit or a Hamilton path?,Hamilton circuit: G1,Hamilton path: G1,G2,Exercise : 42, 43,Thm. 3 (Diracs Thm.):If (but not only if) G is a simple graph with

46、n3 vertices such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit.,Ch9-56,each vertex has deg n/2 =3.5 Hamilton circuit exists E.g., a, c, e, g, b, d, f, a,Ch9-57,Thm. 4 (Ores Thm.):If G is a simple graph with n3 vertices such that deg(u)+deg(v) n for every pair of

47、 nonadjacent vertices u and v, then G has a Hamilton circuit.,each nonadjacent vertex pair has deg sum n = 7 Hamilton circuit exists E.g., a, d, f, e, c, b, g, a,9.6: Shortest-Path Problems,Def: 1. Graphs that have a number assigned to each edge are called weighted graphs. 2. The length of a path in

48、 a weighted graph is the sum of the weights of the edges of this path.,Ch9-58,Shortest path Problem: Determining the path of least sum of the weights between two vertices in a weighted graph.,Ch9-59,Example 1. What is the length of a shortest path between a and z in the weighted graph G?,G,Sol.,leng

49、th=6,Procedure Dijkstra(G: weighted connected simple graph, with all weights positive) G has vertices a = v0, v1, , vn = z and weights w(vi, vj) where w(vi, vj) = if vi, vj is not an edge in G for i := 1 to nL(vi) := L(a) := 0 S := while z S begin u := a vertex not in S with L(u) minimal S := S u fo

50、r all vertices v not in S if L(u) + w(u, v) L(v) then L(v) := L(u) + w(u, v) end L(z) = length of a shortest path from a to z,Dijkstras Algorithm,Ch9-60,This algorithm can be extended to construct a shortest path.,(find the length of a shortest path from a to z),Ch9-61,Example 2. Use Dijkstras algor

51、ithm to find the length of a shortest path between a and z in the weighted graph.,Sol.,Ch9-62,Exercise : 3, path: a, c, b, d, e, z length: 13,(last figure from previous page),Procedure Floyd(G: weighted simple graph) G has vertices v1, , vn and weights w(vi, vj) with w(vi, vj) = if vi, vj is not an

52、edge for i := 1 to n for j := 1 to n d(vi, vj) := w(vi, vj) for i := 1 to n for j := 1 to n for k := 1 to n if d(vj, vi) + d(vi, vk) d(vj, vk) then d(vj, vk) := d(vj, vi) + d(vi, vk) d(vi, vj) is the length of a shortest path between vi and vj,Floyds Algorithm (find the distance d(a, b) a, b),Ch9-63

53、,This algorithm cannot be used toconstruct shortest paths.,Exercise : 21,Ch9-64,The Traveling Salesman Problem: A traveling salesman wants to visit each of n cities exactly once and return to his starting point. In which order should he visit these cities to travel the minimum total distance?,Exampl

54、e (starting point D),DTKGS D: 458,DTSGKD: 504,DTSKGD: 540,Equivalently, looking for minimum weight Hamiltonian circuit in a complete weighted graph,9.7: Planar Graphs,Def 1. A graph is called planar if it can be drawn in the plane without any edge crossing. Such a drawing is called a planar represen

55、tation of the graph.,Ch9-65,Example 1: Is K4 planar?,K4 drawn with no crossings, K4 is planar,Ch9-66,Example 3: Show that K3,3 is nonplanar.,Example 2: Is Q3 planar?,Q3,Q3 drawn with no crossings, Q3 is planar,Exercise: 3, 4,Sol.,Aebd is a cycle, it splits the plane into two regions,No matter which

56、region c is in, f cant be drawn without crossing,Ch9-67,Eulers Formula,A planar representation of a graph splits the plane into regions, including an unbounded region.,Example : How many regions are there in the following graph?,Sol. 6,Thm 1 (Eulers Formula)Let G be a connected planar simple graph w

57、ith e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e-v +2.,Ch9-68,Example 4: Suppose that a connected planar graph has 20 vertices, each of degree 3. Into how many regions does a representation of this planar graph split the plane?,Sol. v = 20, 2e =

58、320 = 60, e = 30 r = e-v+2 = 30-20+2 = 12,Corollary 1If G is a connected planar simple graph with e edges and v vertices, where v 3, then e 3v - 6.,Example 5: Show that K5 is nonplanar.,Sol. v= 5, e = 10, but 3v - 6 = 9.,Exercise: 13,Ch9-69,Corollary 2If G is a connected planar simple graph, then G has a vertex of degree 5.,pf:,Let G be a planar graph of v vertices and e edges.,If deg(v) 6 for every vV(G),2e 6v (e 3v - 6),Ch9-70,Corollary 3If a connected planar sim