Chapter 04 - Graph theory bài toán graph trong toán rời rạc

bài toán rời rạc- đồ thị

1. Discrete Mathematics Graph Hà Minh Hoàng Faculty of Data Science and Artificial Intelligence College of Technology National Economics University

2. Graphs and Their Classifications Graph Terminologies Graph Representations and Isomorphism Paths and Connectivity Eulerian and Hamiltonian Paths Shortest Path Problem Planar Graphs Graph Coloring Content

3. Graph theory is a well-established field of science with numerous modern applications. Graphs are used to solve problems in various domains such as electrical circuits, chemical compound structures, computer networks, and more. A graph is a discrete structure consisting of vertices and edges connecting those vertices. Graphs are classified based on the properties of the edges connecting pairs of vertices. Graphs and Their Classifications

4. A simple graph 𝐺=(𝑉,𝐸) consists of a non-empty set 𝑉 whose elements are called vertices, and a set 𝐸 whose elements are called edges. Each edge is an unordered pair of distinct vertices. Classification: simple graph

5. A multigraph 𝐺=(𝑉,𝐸), where 𝑉 is the set of vertices and 𝐸 is the set of edges, is an undirected graph that may have multiple edges connecting the same pair of vertices (called parallel edges or multiple edges). A simple graph is a special case of a multigraph. Classification: multigraph

6. Classification: simple graph vs multigraph

7. A pseudograph 𝐺=(𝑉,𝐸), where 𝑉 is the set of vertices and 𝐸 is the set of edges, is a graph that allows edges connecting a vertex to itself (called loops). A pseudograph can have multiple edges and loops. Classification: pseudograph

8. A simple directed graph 𝐺=(𝑉, A ), where 𝑉 is a non-empty set whose elements are called vertices, and A is a set whose elements are called arcs, consists of ordered pairs of distinct vertices. Classification: simple directed graph

9. A directed multigraph 𝐺=(𝑉, A ), where 𝑉 is the set of vertices and A is the set of arcs, is a graph consisting of directed arcs, and multiple directed arcs between the same pair of vertices (called parallel arcs) are allowed. A simple directed graph is a special case of a directed multigraph. Classification: directed multigraph

10. Graph terminology

11. Example 1. Niche overlap graph in ecology . - Graphs are used in many models that consider the interactions between species, e.g., the competition among species in an ecosystem can be modeled using a "niche" graph. - Each species is represented by a vertex. An undirected edge connects two vertices if the corresponding species compete with each other (i.e., they share the same food source). - From this graph, squirrels and raccoons compete with each other, while crows and shrews do not. Examples: Biological networks

12. Example 2. Protein interaction graph . A protein interaction in a living cell occurs when two or more proteins in that cell bind to perform a biological function. Protein interactions are crucial for most biological functions, many scientists work on discovering new proteins and understanding interactions between proteins- Protein interactions within a cell can be modeled using a protein interaction graph (also called a protein–protein interaction network) An undirected graph in which each protein is represented by a vertex, with an edge connecting the vertices representing each pair of proteins that interact. Protein interaction graphs can be used to deduce important biological information, such as by identifying the most important proteins for various functions and the functionality of newly discovered proteins. Examples: Biological networks

13. Example 2. Protein interaction graph . The protein interaction graph of a cell is extremely large and complex. Yeast cells have more than 6,000 proteins, and more than 80,000 interactions Human cells have more than 100,000 proteins, with perhaps 1,000,000 interactions between them. Additional vertices and edges are added to a protein interaction graph when new proteins and interactions between proteins are discovered. The protein interaction graphs are often split into smaller graphs called modules that represent groups of proteins that are involved in a particular function of a cell. Figure illustrates a module of the protein interaction graph, comprising the complex of proteins that degrade RNA in human cells. Examples: Biological networks

14. Example 2. Influence Graph - When studying the personalities of a group of people, it is observed that some individuals may influence the thoughts of others. - A directed graph, known as an influence graph, can be used to model this problem. - Each person in the group is represented by a vertex. - If a person represented by vertex 𝑎 can influence a person represented by vertex 𝑏, then there is a directed arc from vertex 𝑎 to vertex 𝑏. Examples: Social networks

15. Other social networks: - Acquaintanceship and Friendship Graphs. - Collaboration Graphs: Academic collaboration graph, Hollywood graph, in sports. Examples: Social networks

16. Call graphs: Examples: Communication networks

17. Example 3. Citation graph - A citation graph is a directed graph where each node represents a scientific paper, and each directed edge points from one paper to another that it cites. - These graphs form the backbone of scholarly communication and offer powerful insights into the structure and evolution of scientific knowledge. - The Web graph Examples: Information graphs

18. - The Seven Bridges of Königsberg is a famous historical problem in mathematics and is considered the foundation of graph theory. - The city of Königsberg (now Kaliningrad, Russia) was set on both sides of the Pregel River and included two large islands connected to each other and the mainland by seven bridges. - The challenge posed to citizens was:"Is it possible to walk through the city in such a way that each bridge is crossed exactly once?“ - In 1736, Leonhard Euler proved that such a walk was not possible. Examples: Transportation networks

19. Airline routes Road networks Rail networks Shipping networks Examples: Transportation networks

20. Module dependency graphs Precedence graph and concurrent processing Examples: Software design applications

21. Round-robin tournaments Single-elimination tournaments Examples: Tournaments

22. Exercise 1 Exercises

23. Exercise 2 Exercises

24. Exercise 3: Construct an influence graph for the board members of a company if the President can influence the Director of Research and Development, the Director of Marketing, and the Director of Operations; the Director of Research and Development can influence the Director of Operations; the Director of Marketing can influence the Director of Operations; and no one can influence, or be influenced by, the Chief Financial Officer. Exercises

25. Exercise 4: Explain how the two telephone call graphs for calls made during the month of January and calls made during the month of February can be used to determine the new telephone numbers of people who have changed their telephone numbers. Exercises

26. Exercise 5: Exercises

27. 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 . Definition 2: The set of all neighbors of a vertex v of G = ( V , E ), denoted by N ( v ), is called the neighborhood 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. 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 ). Graph Terminologies

28. What are the degrees and what are the neighborhoods of the vertices in the graphs G and H displayed in Figure. Graph Terminologies

29. Theorem 1: Graph Terminologies

30. How many edges are there in a simple graph with 10 vertices, each of degree 5? How many edges are there in a simple graph with 99 vertices, each of degree 5? Graph Terminologies

31. Theorem 2: An undirected graph has an even number of vertices of odd degree. Graph Terminologies

32. 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. Definition 5: In a graph with directed edges the in-degree of a vertex v, denoted by deg−(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.) Graph Terminologies

33. Find the in-degree and out-degree of each vertex in the graph G with directed edges shown in Figure Graph Terminologies

34. Theorem 3: Graph Terminologies

35. Complete Graphs A complete graph on n vertices, denoted by K n , is a simple graph that contains exactly one edge between each pair of distinct vertices. The graphs K n , for n = 1, 2, 3, 4, 5, 6, are displayed in Figure. Graph Terminologies

36. Cycles A cycle C n , n ≥ 3, consists of n vertices v 1 , v 2 , . . . , v n and edges { v 1 , v 2 }, {v 2 , v 3 }, . . . , {v n−1 , v n }, and {v n , v 1 }. The cycles C 3 , C 4 , C 5 , and C 6 are displayed in Figure Graph Terminologies

37. Wheels We obtain a wheel W n when we add an additional vertex to a cycle C n , for n ≥ 3, and connect this new vertex to each of the n vertices in C n , by new edges. The wheels W 3 , W 4 , W 5 , and W 6 are displayed in Figure. Graph Terminologies

38. n-Cubes An n-dimensional hypercube, or n-cube, denoted by Q n , is a graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position. We display Q 1 , Q 2 , and Q 3 in Figure. Graph Terminologies

39. A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V 1 and V 2 such that every edge in the graph connects a vertex in V 1 and a vertex in V 2 (so that no edge in G connects either two vertices in V 1 or two vertices in V 2 ). When this condition holds, we call the pair (V 1 , V 2 ) a bipartition of the vertex set V of G. Example: C 6 is a bipartite graph. Graph Terminologies

40. Example: Is K 3 is a bipartite graph? Graph Terminologies

41. Theorem: A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color. Exercise: Graph Terminologies

42. Complete Bipartite Graphs A complete bipartite graph K m,n is a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. The complete bipartite graphs K 2,3 , K 3,3 , K 3,5 , and K 2,6 are displayed in Figure Graph Terminologies

43. Bipartite graphs and matchings Job assignment Graph Terminologies

44. Bipartite graphs and matchings Marriages on an Island Suppose that there are m men and n women on an island. Each person has a list of members of the opposite gender acceptable as a spouse. Construct a bipartite graph G = (V 1 , V 2 ) where V 1 is the set of men and V 2 is the set of women so that there is an edge between a man and a woman if they find each other acceptable as a spouse. A matching in this graph consists of a set of edges, where each pair of endpoints of an edge is a husband-wife pair. A maximum matching is a largest possible set of married couples, and a complete matching of V 1 is a set of married couples where every man is married, but possibly not all women. Graph Terminologies

45. Local area networks Star topology, ring topology and hybrid topology Some Applications of Special Types of Graphs

46. Definition 7: Graph Terminologies

47. Definition 8: Let G = (V ,E) be a simple graph. The subgraph induced by a subsetW of the vertex set V is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W. - The graph G shown in Figure is a subgraph of K 5 . If we add the edge connecting c and e to G, we obtain the subgraph induced by W = {a, b, c, e}. Graph Terminologies

48. Definition 9: The union of two simple graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) is the simple graph with vertex set V 1 ∪ V 2 and edge set E 1 ∪ E 2 . The union of G 1 and G 2 is denoted by G 1 ∪ G 2 . Graph Terminologies

49. For which values of n are these graphs bipartite? K n C n W n Q n Exercises

50. List all the edges of the graph (without multiple edges) Use adjacency lists which specify the vertices that are adjacent to each vertex of the graph (without multiple edges) Representing Graphs All the edges {a,b} {a,c} {a,e} {c,d} {c,e} {e,d}

51. Adjacency matrices (with or without multiple edges) Representing Graphs

52. Adjacency matrices (with or without multiple edges) Representing Graphs

53. Adjacency matrices (with multiple edges) Representing Graphs

54. Adjacency matrices vs adjacency list Sparse graph: adjacency lists are preferable If each vertex has degree not exceeding c , no more than cn items in adjacency list, where n is the number of vertices in the graph In the adjacency matrices, there are n 2 items Sparse matrices Dense graph: adencecy matrices are preferable Check if there is an edge ( v i , v j ) in the graph Representing Graphs

55. How about representing directed graphs? Representing Graphs

56. Incidence matrices n × m matrix M = [ m ij ] Representing Graphs

57. Incidence matrices Multiple edges and loops? Representing Graphs

58. The simple graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) are isomorphic if there exists a one to-one and onto function f from V 1 to V 2 with the property that a and b are adjacent in G 1 if and only if f (a) and f ( b ) are adjacent in G 2 , for all a and b in V 1 . Such a function f is called an isomorphism. Two simple graphs that are not isomorphic are called nonisomorphic. In other words, when two simple graphs are isomorphic, there is a one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship. Isomorphism of Graphs

59. Show that the graphs G = (V ,E) and H = (W, F) are isomorphic. Isomorphism of Graphs

60. Show that the graphs G = (V ,E) and H = (W, F) are isomorphic. The function f with f(u 1 ) = v 1 , f(u 2 ) = v 4 , f(u 3 ) = v 3 , and f(u 4 ) = v 2 is a one-to-one correspondence between V and W Isomorphism of Graphs

61. Determining whether Two Simple Graphs are Isomorphic. It is often difficult to determine whether two simple graphs are isomorphic. n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices. Sometimes it is not hard to show that two graphs are not isomorphic. We can show that two graphs are not isomorphic if we can find a property only one of the two graphs has, but that is preserved by isomorphism. A property preserved by isomorphism of graphs is called a graph invariant. Isomorphic simple graphs must have the same number of vertices Isomorphic simple graphs also must have the same number of edges, The degrees of the vertices in isomorphic simple graphs must be the same. Isomorphism of Graphs

62. Exercises: Isomorphism of Graphs

63. Exercises: Isomorphism of Graphs

64. Paths (walk) and circuits (closed walk): - Let n be a nonnegative integer and G an undirected graph. A path of length n from u to v in G is a sequence of n edges e 1 , . . . , e n of G for which there exists a sequence x = u, x 1 , . . . , x n−1 , x n = v of vertices such that e i has, for i = 1, . . . , n, the endpoints x i −1 and x i . When the graph is simple, we denote this path by its vertex sequence x , x 1 , . . . , x n (because listing these vertices uniquely determines the path). The path is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length greater than zero. A path or circuit is simple if it does not contain the same edge more than once. Connectivity

65. Paths represent useful information in many graph models Acquaintanceship graphs: Six Degrees of Separation : a famous social theory suggests that any two people in the world can be connected through at most six intermediate relationships. First introduced by Hungarian author Frigyes Karinthy in 1929 in his short story "Chains". Gained popularity through experiments by Stanley Milgram (1960s), who had participants try to send a letter to a target person via acquaintances — the average number of intermediaries was 5–6. The play by John Guare helped bring the idea of “Six Degrees of Separation” into mainstream culture, beyond academic or psychological discussions. Studies on Facebook show that only about 3.5 to 4 intermediaries are needed to connect any two users. Connectivity

66. Paths represent useful information in many graph models: Collaboration graphs – In Academic: Erdos number Càng gần Erdős, bạn càng được coi là gần “trung tâm toán học thế giới” Những người có Erdos number ≤ 4 thường rất được ngưỡng mộ trong cộng đồng nghiên cứu toán . - In Hollywood graph: Bacon number Connectivity

67. - An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. - An undirected graph that is not connected is called disconnected. - We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph. - Any two computers in the network can communicate if and only if the graph of this network is connected. Connectedness in Undirected Graphs

68. - An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. - An undirected graph that is not connected is called disconnected. - We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph. - Any two computers in the network can communicate if and only if the graph of this network is connected. Connectedness in Undirected Graphs

69. Theorem : There is a simple path between every pair of distinct vertices of a connected undirected graph. Proof ??? Connectedness in Undirected Graphs

70. A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G. That is, a connected component of a graph G is a maximal connected subgraph of G. A graph G that is not connected has two or more connected components that are disjoint and have G as their union. Connectedness in Undirected Graphs

71. How connected is a graph? The removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called cut vertices (or articulation points). An edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge. In a graph representing a computer network, a cut vertex and a cut edge represent an essential router and an essential link that cannot fail for all computers to be able to communicate. Connectedness in Undirected Graphs

72. Cut vertex and cut edge Find the cut vertices and cut edges in G 1 and G 2 Connectedness in Undirected Graphs

73. Vertex connectivity Not all graphs have cut vertices. For example, K n , where n ≥ 3 Connected graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex. A measure of graph connectivity based on the minimum number of vertices that can be removed to disconnect a graph. Connectedness in Undirected Graphs

74. Vertex connectivity A subset V’ of the vertex set V of G = (V ,E) is a vertex cut, or separating set, if G − V’ is disconnected. For instance, in the graph in Figure, the set {b, c, e} is a vertex cut with three vertices Every connected graph, except a complete graph, has a vertex cut. The vertex connectivity of a noncomplete graph G, denoted by κ (G), as the minimum number of vertices in a vertex cut. Connectedness in Undirected Graphs

75. Vertex connectivity For every graph G, κ (G) is minimum number of vertices that can be removed from G to either disconnect G or produce a graph with a single vertex Compute κ (K n )? The larger κ (G) is, the more connected we consider G to be. A graph is k -connected (or k -vertex-connected), if κ (G) ≥ k. Find the vertex connectivity for each of the graphs: Connectedness in Undirected Graphs

76. Vertex connectivity Find the vertex connectivity for each of the graphs: κ ( G 1 ) = 1, κ ( G 2 ) = 1 κ ( G 3 ) = 2, κ ( G 4 ) = 2 κ ( G 5 ) = 3 Connectedness in Undirected Graphs

77. Edge connectivity We can also measure the connectivity of a connected graph G = (V ,E) in terms of the minimum number of edges that we can remove to disconnect it. If a graph has a cut edge, we need only remove it to disconnect G. If G does not have a cut edge, we look for the smallest set of edges that can be removed to disconnect it. A set of edges E’ is called an edge cut of G if the subgraph G − E’ is disconnected The edge connectivity of a graph G, denoted by λ (G), is the minimum number of edges in an edge cut of G. λ (G) = n − 1 where G is a graph with n vertices if and only if G = K n λ (G) ≤ n − 2 when G is not a complete graph. Connectedness in Undirected Graphs

78. Edge connectivity Find the edge connectivity for each of the graphs: λ ( G 1 ) = 1, λ ( G 2 ) = 2, λ ( G 3 ) = 2 κ ( G 4 ) = 3, κ ( G 5 ) = 3 Connectedness in Undirected Graphs

79. A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph. Connectedness in Directed Graphs

80. Strong components of a directed graph The subgraphs of a directed graph G that are strongly connected but not contained in larger strongly connected subgraphs, that is, the maximal strongly connected subgraphs, are called the strongly connected components or strong components of G. Connectedness in Directed Graphs

81. Paths and circuits can help determine whether two graphs are isomorphic. The existence of a simple circuit of a particular length is a useful invariant that can be used to show that two graphs are not isomorphic. Paths can be used to construct mappings that may be isomorphisms. Paths and Isomorphism

82. Theorem : Let G be a graph with adjacency matrix A with respect to the ordering v 1 , v 2 , . . . , v n of the vertices of the graph (with directed or undirected edges, with multiple edges and loops allowed). The number of different paths of length r from v i to v j , where r is a positive integer, equals the (i, j )th entry of A r How many paths of length three and four are there from a to d in the simple graph G? Counting Paths Between Vertices

83. How many vertices and how many edges do the following graphs have? a. 𝐾 9 b. 𝐶 15​ c. 𝑊 15 d. 𝐾 3,4 e. 𝑄 7 Exercises

84. Which of the following graphs is a bipartite graph? Exercises

85. Construct and calculate the number of edges of a simple graph with the following vertex degrees: 4, 3, 3, 2, 2 3, 3, 3, 3, 2 1, 2, 3, 4, 5 1, 2, 3, 4, 4 Exercises

86. Let G be a graph with v vertices and e edges. Let M be the maximum degree of the vertices of G, and let m be the minimum degree of the vertices of G. Show that: 2e/v ≥ m. 2e/v ≤ M. Exercises

87. Find the adjacency matrix of 𝐾 2,3 Find the number of paths of length 3 and 4 from a degree-3 vertex to a degree-2 vertex. Exercises

88. 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. Euler and Hamilton Paths

89. Which of the undirected graphs have an Euler circuit? Of those that do not, which have an Euler path? Euler and Hamilton Paths

90. A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. Euler and Hamilton Paths

91. A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree. Necessary and sufficient conditions for Euler paths and circuits in directed graphs are given in Exercises 16 and 17. Euler and Hamilton Paths

92. - A simple path in a graph G that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. The simple path x , x 1 , . . . , x n−1 , x n in the graph G = (V ,E) is a Hamilton path if V = {x , x 1 , . . . , x n−1 , x n } and x i ≠ x j for 0 ≤ i < j ≤ n The simple circuit x , x 1 , . . . , x n−1 , x n , x (with n > 0) is a Hamilton circuit if x , x 1 , . . . , x n−1 , x n is a Hamilton path. Euler and Hamilton Paths

93. - A simple path in a graph G that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. The simple path x , x 1 , . . . , x n−1 , x n in the graph G = (V ,E) is a Hamilton path if V = {x , x 1 , . . . , x n−1 , x n } and x i ≠ x j for 0 ≤ i < j ≤ n The simple circuit x , x 1 , . . . , x n−1 , x n , x (with n > 0) is a Hamilton circuit if x , x 1 , . . . , x n−1 , x n is a Hamilton path. Hamilton’s “A Voyage Round the World” Puzzle. Euler and Hamilton Paths

94. - Which of the simple graphs in Figures have a Hamilton circuit or, if not, a Hamilton path? Euler and Hamilton Paths

95. - Determine whether the picture shown can be drawn with a pencil in a continuous motion without lifting the pencil or retracing part of the picture! Euler and Hamilton Paths

96. - For which values of n do these graphs have an Euler circuit? K n C n W n Q n - For which values of n do the graphs above have an Euler path but no Euler circuit? Euler and Hamilton Paths

97. - For which values of m and n does the complete bipartite graph K m,n have an a) Euler circuit? b) Euler path? Euler and Hamilton Paths

98. Graphs that have a number assigned to each edge are called weighted graphs . Weighted graphs are used to model computer networks. Communications costs (such as the monthly cost of leasing a telephone line), the response times of the computers over these lines, or the distance between computers, can all be studied using weighted graphs. Shortest-Path Problems

99. Graphs that have a number assigned to each edge are called weighted graphs . Weighted graphs are used to model computer networks. Communications costs (such as the monthly cost of leasing a telephone line), the response times of the computers over these lines, or the distance between computers, can all be studied using weighted graphs. A Shortest-Path Algorithm

100. A Shortest-Path Algorithm

101. A Shortest-Path Algorithm

102. A Shortest-Path Algorithm Find the length of a shortest path between these pairs of vertices in the weighted graph in Exercise 3. a) a and d b) a and f c) c and f d) b and z

103. Planar Graphs Can a graph be drawn in the plane without edges crossing? ???

104. Planar Graphs A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint) Such a drawing is called a planar representation of the graph Is K 3,3 planar?

105. Planar Graphs Applications: Design of electronic circuits Road networks

106. Planar Graphs Euler’s formula: Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e − v + 2. Exercise : Suppose that a connected planar simple graph has 20 vertices, each of degree 3. Into how many regions does a representation of this planar graph split the plane?

107. Planar Graphs Prove that: If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v − 6.

108. Planar Graphs Prove that: - If G is a connected planar simple graph, then G has a vertex of degree not exceeding five. - K 5 is nonplanar? - If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of length three, then e ≤ 2v − 4. - K 3 , 3 is nonplanar.

109. Planar Graphs - K 5 , K 3 , 3 are nonplanar. A graph is not planar if it contains either of these two graphs as a subgraph. - A planar graph G and every graph obtained from G by removing an edge (u, v) and adding a vertex w with two edges (u, w) and (w, v) is also planar and is called a homeomorphic graph of G. - A graph is nonplanar if and only if it contains a subgraph homeomorphic to K 3 , 3 or K 5 .

110. Planar Graphs - Is the Petersen graph planar?

111. Planar Graphs - Is the Petersen graph planar?

112. Graph coloring Map Coloring Neighboring regions are colored with different colors. Use the minimum number of colors. Represent the map as a graph

113. Graph coloring - Vietnam map coloring

114. Graph coloring Definition 1. Coloring a simple graph is the assignment of colors to its vertices such that no two adjacent vertices are assigned the same color. Definition 2. The chromatic number of a graph is the minimum number of colors needed to color the graph. Theorem 1. Four Color Theorem . The chromatic number of any planar graph is at most four.

115. Graph coloring Exercise : the number of colors of K n , K m,n , C n ?

116. Graph coloring The graph coloring problem has many applications Application in exam scheduling: Scheduling exams so that no student has to take two exams at the same time. - Courses are represented as vertices of the graph. - Two courses that a student has to take together → an edge. - Exam times are represented by different colors. → Scheduling is equivalent to coloring the graph.