Bài giảng Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh Đức

Đồ thị phẳng Trần Vĩnh Đức HUST Ngày 1 tháng 3 năm 2016 1 / 36 Tài liệu tham khảo I Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) I K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch Tiếng Việt) I Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà Nội, 2004. 2 / 36 Giới thiệu 718 10 / Graphs 27. Find a route with the least total airfare that visits each of the cities in this graph, where the weight on an edge is the least price available for a flight between the two cities. New York Detroit DenverLos Angeles San Francisco $329 $359 $349 $189 $229 $279 $379$209$69 $179 28. Find a route with the least total airfare that visits each of the cities in this graph, where the weight on an edge is the least price available for a flight between the two cities. New York Boston Seattle New OrleansPhoenix $389 $379 $319 $23 9 $429 $309 $409 $109 $229 $119 29. Construct a weighted undirected graph such that the total weight of a circuit that visits every vertex at least once is minimized for a circuit that visits some vertices more than once. [Hint:There are examples with three vertices.] 30. Show that the problem of finding a circuit of minimum total weight that visits every vertex of a weighted graph at least once can be reduced to the problem of finding a circuit of minimum total weight that visits each vertex of a weighted graph exactly once. Do so by constructing a new weighted graph with the same vertices and edges as the original graph but whose weight of the edge con- necting the vertices u and v is equal to the minimum total weight of a path from u to v in the original graph. ∗31. The longest path problem in a weighted directed graph with no simple circuits asks for a path in this graph such that the sum of its edge weights is a maximum. De- vise an algorithm for solving the longest path problem. [Hint: First find a topological ordering of the vertices of the graph.] 10.7 Planar Graphs Introduction Consider the problem of joining three houses to each of three separate utilities, as shown in Figure 1. Is it possible to join these houses and utilities so that none of the connections cross? This problem can be modeled using the complete bipartite graph K3,3. The original question can be rephrased as: Can K3,3 be drawn in the plane so that no two of its edges cross? In this section we will study the question of whether a graph can be drawn in the plane without edges crossing. In particular, we will answer the houses-and-utilities problem. There are always many ways to represent a graph. When is it possible to find at least one way to represent this graph in a plane without any edges crossing? FIGURE 1 Three Houses and Three Utilities. 3 / 36 Định nghĩa Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó trên mặt phẳng mà không có cạnh nào cắt nhau. Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar. 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonpla ar. 4 / 36 Ví dụ 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar. 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 A graph is called planar f it can be drawn in the plane without a y edg s crossing (where a crossing of dges is the intersection of the li es or arcs representing them at a point other than their common endpoint). Such a drawing is called a planar representation of the graph. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a differe t way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar. 5 / 36 Ví dụ Đồ thị K3;3: 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar.không phẳng vì 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as show in Figur 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar. 6 / 36 Euler chứng minh rằng mọi biểu diễn phẳng của một đồ thị đều chia mặt phẳng thành cùng số miền như nhau. 720 10 / Graphs Next, note that there is no way to place the final vertex v6 without forcing a crossing. For if v6 is in R1, then the edge between v6 and v3 cannot be drawn without a crossing. If v6 is in R21, then the edge between v2 and v6 cannot be drawn without a crossing. If v6 is in R22, then the edge between v1 and v6 cannot be drawn without a crossing. A similar argument can be used when v3 is in R1. The completion of this argument is left for the reader (see Exercise 10). It follows that K3,3 is not planar. ! Example 3 solves the utilities-and-houses problem that was described at the beginning of this section. The three houses and three utilities cannot be connected in the plane without a crossing. A similar argument can be used to show that K5 is nonplanar. (See Exercise 11.) APPLICATIONS OF PLANAR GRAPHS Planarity of graphs plays an important role in the design of electronic circuits. We can model a circuit with a graph by representing components of the circuit by vertices and connections between them by edges. We can print a circuit on a single board with no connections crossing if the graph representing the circuit is planar. When this graph is not planar, we must turn to more expensive options. For example, we can partition the vertices in the graph representing the circuit into planar subgraphs. We then construct the circuit using multiple layers. (See the preamble to Exercise 30 to learn about the thickness of a graph.) We can construct the circuit using insulated wires whenever connections cross. In this case, drawing the graph with the fewest possible crossings is important. (See the preamble to Exercise 26 to learn about the crossing number of a graph.) The planarity of graphs is also useful in the design of road networks. Suppose we want to connect a group of cities by roads. We can model a road network connecting these cities using a simple graph with vertices representing the cities and edges representing the highways connecting them.We can built this road network without using underpasses or overpasses if the resulting graph is planar. Euler’s Formula A planar representation of a graph splits the plane into regions, including an unbounded region. For instance, the planar representation of the graph shown in Figure 8 splits the plane into six regions. These are labeled in the figure. Euler showed that all planar representations of a graph split the plane into the same number of regions. He accomplished this by finding a relationship among the number of regions, the number of vertices, and the number of edges of a planar graph. THEOREM 1 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 ofG. Then r = e − v+ 2. Proof: First, we specify a planar representation ofG.We will prove the theorem by constructing a sequence of subgraphsG1,G2, . . . ,Ge = G, successively adding an edge at each stage. This is done using the following inductive definition. Arbitrarily pick one edge of G to obtain G1. Obtai Gn fromGn−1 by arbitrarily adding an edge that is incident with a vertex already inGn−1, R2 R1 R3 R5 R4 R6 FIGURE 8 The Regions of the Planar Representation of a Graph. 7 / 36 Định lý (Công thức Euler) Cho G là một đồ thị phẳng liên thông với e cạnh và v đỉnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó r = e v+ 2: 8 / 36 Ví dụ Xét một đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc 3. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền? I Tổng bậc bằng 3v = 3 20 = 60 I Số cạnh e = 30 I Theo công thức Euler r = e v+ 2 = 30 20 + 2 = 12 9 / 36 Chứng minh công thức Euler I Ta chứng minh bằng quy nạp theo số miền r. I Nếu r = 1 thì đồ thị không có chu trình. Tại sao? I Vậy e = v 1. 3 I Giả sử định lý đúng với r > 1. 10 / 36 Chứng minh công thức Euler I Vì r > 1, nên đồ thị có chu trình. I Giả sử fu; vg là cạnh của một chu trình nào đó. I Vậy fu; vg là biên của hai miền S và T. Tại sao? I Xóa cạnh fu; vg làm nhập hai miền S và T làm một, còn các miền khác giữ nguyên. I Đồ thị mới thu được có e 1 cạnh và r 1 miền. I Theo giả thiết quy nạp: r 1 = e 1 v+ 2 I Ta được r = e v+ 2. 3 11 / 36 Hệ quả Nếu G là một đồ thị phẳng liên thông với e cạnh và v đỉnh thỏa mãn v  3. Vậy thì e  3v 6.722 10 / Graphs c b d e f a g 3R1 R2 R3 6 7 FIGURE 11 The Degrees of Regions. COROLLARY 1 If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v− 6. Before we prove Corollary 1 we will use it to prove the following useful result. COROLLARY 2 If G is a connected planar simple graph, then G has a vertex of degree not exceeding five. Proof: IfGhas one or twovertices, the result is true. IfGhas at least three vertices, byCorollary 1 we know that e ≤ 3v− 6, so 2e ≤ 6v− 12. If the degree of every vertex were at least six, then because 2e =∑v∈V deg(v) (by the handshaking theorem), we would have 2e ≥ 6v. But this contradicts the inequality 2e ≤ 6v− 12. It follows that there must be a vertex with degree no greater than five. The proof of Corollary 1 is based on the concept of the degree of a region, which is defined to be the number of edges on the boundary of this region. When an edge occurs twice on the boundary (so that it is traced out twice when the boundary is traced out), it contributes two to the degree. We denote the degree of a region R by deg(R). The degrees of the regions of the graph shown in Figure 11 are displayed in the figure. The proof of Corollary 1 can now be given. Proof: A connected planar simple graph drawn in the plane divides the plane into regions, say r of them. The degree of each region is at least three. (Because the graphs discussed here are simple graphs, no multiple edges that could produce regions of degree two, or loops that could produce regions of degree one, are permitted.) In particular, note that the degree of the unbounded region is at least three because there are at least three vertices in the graph. Note that the sum of the degrees of the regions is exactly twice the number of edges in the graph, because each edge occurs on the boundary of a region exactly twice (either in two different regions, or twice in the same region). Because each region has degree greater than or equal to three, it follows that 2e = ∑ all regions R deg(R) ≥ 3r. Hence, (2/3)e ≥ r. I Bậc của một miền là số cạnh trên biên của miền đó. I Bậc của mỗi miền ít nhất phải bằng 3. I Tổng bậc các miền bằng bao nhiêu cạnh? 12 / 36 Chứng minh. I Tổng bậc các miền X R deg(R) = 2e  3r Vậy ta có 2e/3  r. I Theo công thức Euler r = e v+ 2  2e/3: I Kết luận e  3v 6. 13 / 36 Bài tập I Dùng hệ quả trước, hãy chỉ ra rằng đồ thị K5 không phẳng. 10.2 Graph Terminology and Special Types of Graphs 663 in exactly one bit. The hypercube network balances the number of direct connections for each processor and the number of intermediate connections required so that processors can com- municate. Many computers have been built using a hypercube network, and many parallel algorithms have been devised that use a hypercube network. The graph Qm, the m-cube, rep- resents the hypercube network with n = 2m processors. Figure 14 displays the hypercube net- work for eight processors. (Figure 14 displays a different way to draw Q3 than was shown in Figure 6.) ! New Graphs from Old Sometimes we need only part of a graph to solve a problem. For instance, we may care only about the part of a large computer network that involves the computer centers in New York, Denver, Detroit, and Atlanta. Then we can ignore the other computer centers and all telephone lines not linking two of these specific four computer centers. In the graph model for the large network, we can remove the vertices corresponding to the computer centers other than the four of interest, and we can remove all edges incident with a vertex that was removed. When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph. DEFINITION 7 A subgraph of a graph G = (V ,E) is a graph H = (W, F ), where W ⊆ V and F ⊆ E. A subgraph H of G is a proper subgraph of G if H "= G. Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices and the edges of the graph that connect them. DEFINITION 8 LetG = (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 inE if and only if both endpoints of this edge are inW . EXAMPLE 18 The graph G shown in Figure 15 is a subgraph of K5. If we add the edge connecting c and e to G, we obtain the subgraph induced byW = {a, b, c, e}. ! REMOVINGORADDING EDGESOF AGRAPH Given a graphG = (V ,E) and an edge e ∈ E, we can produce a subgraph ofG by removing the edge e. The resulting subgraph, denoted by G− e, has the same vertex set V as G. Its edge set is E − e. Hence, G− e = (V ,E − {e}). Similarly, if E′ is a subset of E, we can produce a subgraph of G by removing the edges in E′ from the graph. The resulting subgraph has the same vertex set V as G. Its edge set is E − E′. P0 P7P1 P2 P3 P4 P5 P6 FIGURE 14 A Hypercube Network for Eight Processors. d c a be c a be FIGURE 15 A Subgraph of K5. 14 / 36 Hệ quả Nếu G là một đồ thị phẳng liên thông thì G có một đỉnh bậc không vượt quá 5. Chứng minh. Dùng hệ quả trước & Định lý bắt tay. 15 / 36 Hệ quả Nếu một đồ thị phẳng liên thông có e cạnh, v đỉnh trong đó v  3 và không có chu trình độ dài 3 thì e  2v 4. Chứng minh. I Nếu không có chu trình độ dài 3 thì bậc của mỗi miền  4. I Bài tập: Chứng minh tiếp hệ quả này. 16 / 36 Bài tập I Dùng hệ quả trước, hãy chứng minh rằng đồ thị K3;3 không phẳng? 10.7 Planar Graphs 719 FIGURE 2 The Graph K4. FIGURE 3 K4 Drawn with No Crossings. FIGURE 4 The GraphQ3. FIGURE 5 A Planar Representation ofQ3. DEFINITION 1 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. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. ! EXAMPLE 2 IsQ3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. ! We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar. We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this. EXAMPLE 3 Is K3,3, shown in Figure 6, planar? Solution: Any attempt to draw K3,3 in the plane with no edges crossing is doomed. We now showwhy. In any planar representation ofK3,3, the vertices v1 and v2 must be connected to both v4 and v5. These four edges form a closed curve that splits the plane into two regions, R1 and R2, as shown in Figure 7(a). The vertex v3 is in either R1 or R2. When v3 is in R2, the inside of the closed curve, the edges between v3 and v4 and between v3 and v5 separate R2 into two subregions, R21 and R22, as shown in Figure 7(b). v1 v2 v6 v3 v5v4 FIGURE 6 The Graph K3,3. v1 v4 v5 v2 v1 v4 v5 v2 v3R2 R1 R1 R21 (a) (b) R22 FIGURE 7 Showing that K3,3 Is Nonplanar. 17 / 36 Định nghĩa Độ dài của chu trình ngắn nhất trong đồ thị được gọi là chu vi nhỏ nhất của đồ thị đó. Nếu như đồ thị không tồn tại chu trình, thì chu vi nhỏ nhất của G được định nghĩa bằng 1. 18 / 36 Định lý (Bất đẳng thức cạnh đỉnh) Trong đồ thị phẳng liên thông G = (V;E) bất kỳ với chu vi nhỏ nhất g thỏa mãn 3  g <1 ta luôn có jEj  gg 2(jVj 2): 19 / 36 Bài tập Dùng bất đẳng thức cạnh đỉnh để chứng minh rằng K3;3 và K5 không phải đồ thị phẳng. 20 / 36 Chứng minh bất đẳng thức cạnh đỉnh I Xét G = (V;E) là đồ thị phẳng liên thông với chu vi nhỏ nhất 3  g  1. I Đặt tập cạnh E = fe1; e2; : : : ; etg. I Xét một biểu diễn phẳng bất kỳ của G với ` miền là fR1;R2; : : : ;R`g: I Xây dựng bảng X = (xij) gồm t hàng và ` cột như sau xij = ( 1 nếu ei là một cạnh trên biên của của miền Rj 0 trong trường hợp ngược lại 21 / 36 Ví dụ e2e1 e3 e6 e7 e5 e4 R3 R1 R2 R1 R2 R3 e1 1 0 1 e2 1 0 1 e3 0 1 1 e4 1 1 0 e5 1 0 1 e6 0 1 1 e7 0 1 1 I Mỗi hàng có nhiều nhất 2 số 1. Tại sao? I Mỗi cột có ít nhất g số 1. Tại sao? 22 / 36 Chứng minh (tiếp) I Mỗi cạnh chỉ nằm trên biên của nhiều nhất hai miền, nên mỗi hàng của X có nhiều nhất hai số 1. I Các cạnh trên biên của mỗi miền tạo ra một chu trình trong G, nên mỗi cột có ít nhất g số một. I Đặt s := số lượng số 1 trong X ta được g`  s  2t: với ` là số miền và t là số cạnh. 23 / 36 Chứng minh (tiếp) Kết hợp với công thức Euler ` = t jVj+ 2 ta được g` = g` gjVj+ 2g  2t Vậy thì t(g 2)  g(jVj 2) () jEj  gg 2(jVj 2) Ta hoàn thành chứng minh của bất đẳng thức cạnh đỉnh. 24 / 36 Hai đồ thị đồng phôi Định nghĩa I Phép toán loại bỏ cạnh fu; vg và thêm một đỉnh mới w cùng hai cạnh fu;wg; fw; vg gọi là phép phân chia sơ cấp. I Hai đồ thị gọi là đồng phôi nếu chúng có thể nhận được từ cùng một đồ thị bằng một dãy phép phân chia sơ cấp.10.7 Planar Graphs 723 a dc e b a dc e b a dc e b f g h g i k j G2 G3G1 FIGURE 12 Homeomorphic Graphs. Using r = e − v+ 2 (Euler’s formula), we obtain e − v + 2 ≤ (2/3)e. It follows that e/3 ≤ v− 2. This shows that e ≤ 3v− 6. This corollary can be used to demonstrate that K5 is nonplanar. EXAMPLE 5 Show that K5 is nonplanar using Corollary 1. Solution: The graph K5 has five vertices and 10 edges. However, the inequality e ≤ 3v− 6 is not satisfied for this graph because e = 10 and 3v − 6 = 9. Therefore, K5 is not planar. ! It was previously shown thatK3,3 is not planar.Note, however, that this graph has six vertices and nine edges.Thismeans that the inequality e = 9 ≤ 12 = 3 · 6− 6 is satisfied. Consequently, the fact that the inequality e ≤ 3v− 6 is satisfied does not imply that a graph is planar. However, the following corollary of Theorem 1 can be used to show that K3,3 is nonplanar. COROLLARY 3 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. The proof of Corollary 3 is similar to that of Corollary 1, except that in this case the fact that there are no circuits of length three implies that the degree of a region must be at least four. The details of this proof are left for the reader (see Exercise 15). EXAMPLE 6 Use Corollary 3 to show that K3,3 is nonplanar. Solution: BecauseK3,3 has no circuits of length three (this is easy to see because it is bipartite), Corollary 3 can be used. K3,3 has six vertices and nine edges. Because e = 9 and 2v − 4 = 8, Corollary 3 shows that K3,3 is nonplanar. ! KAZIMIERZ KURATOWSKI (1896–1980) Kazimierz Kuratowski, the son of a famous Warsaw lawyer, attended secondary school inWarsaw. He studied in Glasgow, Scotland, from 1913 to 1914 but could not return there after the outbreak ofWorldWar I. In 1915 he enteredWarsaw University, where he was active in the Polish patriotic studentmovement. He published his first paper in 1919 and received his Ph.D. in 1921. Hewas an active member of the group known as the Warsaw School of Mathematics, working in the areas of the foundations of set theory and topology. He was appointed associate professor at the Lwów Polytechnical University, where he stayed for seven years, collaborating with the important Polish mathematicians Banach and Ulam. In 1930, while at Lwów, Kuratowski completed his work characterizing planar graphs. In 1934 he returned toWarsaw University as a full professor. Until the start of WorldWar II, he was active in research and teaching. During the war, because of the persecution of educated Poles, Kuratowski went into hiding under an assumed name and taught at the clandestine Warsaw University. After the war he helped revive Polish mathematics, serving as director of the Polish National Mathematics Institute. He wrote over 180 papers and three widely used textbooks. 25 / 36 Định lý (Kuratowski) Đồ thị là không phẳng nếu và chỉ nếu nó chứa một đồ thị con đồng phôi với K3;3 hoặc K5. Ví dụ724 10 / Graphs a b g i c a b g i c K5HG d e f a b g i c d e f h j k FIGURE 13 The Undirected Graph G, a Subgraph H Homeomorphic to K5, and K5. Kuratowski’s Theorem We have seen that K3,3 and K5 are not planar. Clearly, a graph is not planar if it contains either of these two graphs as a subgraph. Surprisingly, all nonplanar graphs must contain a subgraph that can be obtained from K3,3 or K5 using certain permitted operations. If a graph is planar, so will be any graph obtained by removing an edge {u, v} and adding a new vertex w together with edges {u,w} and {w, v}. Such an operation is called an elementary subdivision. The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions. EXAMPLE 7 Show that the graphs G1, G2, and G3 displayed in Figure 12 are all homeomorphic. Solution: These three graphs are homeomorphic because all three can be obtained from G1 by elementary subdivisions. G1 can be obtained from itself by an empty sequence of elementary subdivisions. To obtain G2 from G1 we can use this sequence of elementary subdivisions: (i ) remove the edge {a, c}, add the vertex f , and add the edges {a, f } and {f, c}; (ii ) remove the edge {b, c}, add the vertex g, and add the edges {b, g} and {g, c}; and (iii ) remove the edge {b, g}, add the vertex h, and add the edges {g, h} and {b, h}.We leave it to the reader to determine the sequence of elementary subdivisions needed to obtain G3 from G1. ! The Polish mathematician Kazimierz Kuratowski established Theorem 2 in 1930, which characterizes planar graphs using the concept of graph homeomorphism. THEOREM 2 A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5. It is clear that a graph containing a subgraph homeomorphic toK3,3 orK5 is nonplanar. However, the proof of the converse, namely that every nonplanar graph contains a subgraph homeomorphic to K3,3 or K5, is complicated and will not be given here. Examples 8 and 9 illustrate how Kuratowski’s theorem is used. EXAMPLE 8 Determine whether the graph G shown in Figure 13 is planar. Solution: G has a subgraph H homeomorphic to K5. H is obtained by deleting h, j , and k and all edges incident with these vertices. H is homeomorphic to K5 because it can be obtained from K5 (with vertices a, b, c, g, and i) by a sequence of elementary subdivisions, adding the vertices d, e, and f . (The reader should construct such a sequence of elementary subdivisions.) Hence, G is nonplanar. ! 26 / 36 Đồ thị Petersen Ví dụ 10.7 Planar Graphs 725 a b cd e f h gj i f d j hie f d j hi c a g (a) (b) H (c) K3,3 e FIGURE 14 (a) The Petersen Graph, (b) a Subgraph H Homeomorphic to K3,3, and (c) K3,3. EXAMPLE 9 Is the Petersen graph, shown in Figure 14(a), planar? (The Danish mathematician Julius Petersen studied this graph in 1891; it is often used to illustrate various theoretical properties of graphs.) Solution: The subgraph H of the Petersen graph obtained by deleting b and the three edges that have b as an endpoint, shown in Figure 14(b), is homeomorphic to K3,3, with vertex sets {f, d, j} and {e, i, h}, because it can be obtained by a sequence of elementary subdivisions, deleting {d, h} and adding {c, h} and {c, d}, deleting {e, f } and adding {a, e} and {a, f }, and deleting {i, j} and adding {g, i} and {g, j}. Hence, the Petersen graph is not planar. ! Exercises 1. Can five houses be connected to two utilities without con- nections crossing? In Exercises 2–4 draw the given planar graph without any crossings. 2. 3. 4. In Exercises 5–9 determine whether the given graph is planar. If so, draw it so that no edges cross. 5. a e fd b c 6. a b c d e f 7. a b c d f e 8. a b d c e h g f 9. i a c e h g f b d 10. Complete the argument in Example 3. 11. Show that K5 is nonplanar using an argument similar to that given in Example 3. 12. Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph? 13. Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph? 14. Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have? 27 / 36 Dính hai đỉnh kề nhau 28 / 36 Định nghĩa Một minor của đồ thị G là một đồ thị thu được từ G bằng một số hữu hạn lần xóa đỉnh, xóa cạnh, và dính hai đỉnh kề nhau của G. 29 / 36 Ví dụ Chu trình C3 có phải là một minor của đồ thị sau không? 30 / 36 31 / 36 Định lý (Wagner) Đồ thị là không phẳng nếu và chỉ nếu nó chứa một minor là K3;3 hoặc K5. 32 / 36 Bài tập Chứng minh rằng đồ thị Peterson dưới đây không phẳng. 33 / 36 Tô màu bản đồ 10.8 Graph Coloring 727 A B C D E F G A D B C E FIGURE 1 Two Maps. 10.8 Graph Coloring Introduction Problems related to the coloring of maps of regions, such as maps of parts of the world, have generated many results in graph theory. When a map∗ is colored, two regions with a common border are customarily assigned different colors. One way to ensure that two adjacent regions never have the same color is to use a different color for each region. However, this is inefficient, and on maps with many regions it would be hard to distinguish similar colors. Instead, a small number of colors should be used whenever possible. Consider the problem of determining the least number of colors that can be used to color a map so that adjacent regions never have the same color. For instance, for the map shown on the left in Figure 1, four colors suffice, but three colors are not enough. (The reader should check this.) In the map on the right in Figure 1, three colors are sufficient (but two are not). Each map in the plane can be represented by a graph. To set up this correspondence, each region of the map is represented by a vertex. Edges connect two vertices if the regions represented by these vertices have a common border. Two regions that touch at only one point are not considered adjacent. The resulting graph is called the dual graph of the map. By the way in which dual graphs of maps are constructed, it is clear that any map in the plane has a planar dual graph. Figure 2 displays the dual graphs that correspond to the maps shown in Figure 1. The problem of coloring the regions of a map is equivalent to the problem of coloring the vertices of the dual graph so that no two adjacent vertices in this graph have the same color. We now define a graph coloring. DEFINITION 1 A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. A B D C F G E A D B EC FIGURE 2 Dual Graphs of the Maps in Figure 1. ∗Wewill assume that all regions in a map are connected. This eliminates any problems presented by such geographical entities as Michigan. Hình: Hai bản đồ 34 / 36 Tô màu đồ thị 10.8 Graph Coloring 727 A B C D E F G A D B C E FIGURE 1 Two Maps. 10.8 Graph Coloring Introduction Problems related to the coloring of maps of regions, such as maps of parts of the world, have generated many results in graph theory. When a map∗ is colored, two regions with a common border are customarily assigned different colors. One way to ensure that two adjacent regions never have the same color is to use a different color for each region. However, this is inefficient, and on maps with many regions it would be hard to distinguish similar colors. Instead, a small number of colors should be used whenever possible. Consider the problem of determining the least number of colors that can be used to color a map so that adjacent regions never have the same color. For instance, for the map shown on the left in Figure 1, four colors suffice, but three colors are not enough. (The reader should check this.) In the map on the right in Figure 1, three colors are sufficient (but two are not). Each map in the plane can be represented by a graph. To set up this correspondence, each region of the map is represented by a vertex. Edges connect two vertices if the regions represented by these vertices have a common border. Two regions that touch at only one point are not considered adjacent. The resulting graph is called the dual graph of the map. By the way in which dual graphs of maps are constructed, it is clear that any map in the plane has a planar dual graph. Figure 2 displays the dual graphs that correspond to the maps shown in Figure 1. The problem of coloring the regions of a map is equivalent to the problem of coloring the vertices of the dual graph so that no two adjacent vertices in this graph have the same color. We now define a graph coloring. DEFINITION 1 A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. A B D C F G E A D B EC FIGURE 2 Dual Graphs of the Maps in Figure 1. ∗Wewill assume that all regions in a map are connected. This eliminates any problems presented by such geographical entities as Michigan. Hình: Các đồ thị của hai bản đồ trước 35 / 36 Định lý (Bốn màu) Số màu của một đồ thị phẳng không lớn hơn 4. Hình: từ wikipedia 36 / 36