离散数学9.5.pptVIP

Planar Graphs and Graph Coloring Consider the problem of joining three houses to each of three separate utilities as shown below. A graph is planar if it has a drawing without crossings. Such a drawing is a planar embedding of G. 平面图的域(面) 内部域、无限域 一个域的边界 Euler’s Formula: If a connected plane graph G has exactly n vertices, e edges, and f faces, then n-e+f=2. 例3 简单平面图G中存在度数小于6的结点。 证明：若每个点的度数不小于6，则所有结点的度数之和≥6n. 由于所有结点的度数之和为边数的2倍，所以 2m≥6n， 故m≥3n。 这与简单平面图满足的性质m≤3n-6相矛盾，故G中必有度数小于6的结点。 Example Determine whether the graph G shown below is planar? Solution The subgraph H of the Petersen graph obtained by deleting b and the three edges that have b as an endpoint, is homeomorphic to K3,3, with vertex sets {f, d, j} and {e, i, h}, since 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. Graph Coloring Coloring- a coloring of a graph G assigns colors to the vertices of G so that adjacent vertices are given different colors. Chromatic Number χ - least number of colors needed to color a graph Chromatic number of a complete graph: χ(Kn) = n The best algorithm known for finding the chromatic number of a graph have exponential worst-case complexity (in the number of vertices of the graph). Even the problem of finding an approximation to the chromatic number of a graph is difficult! Properties of χ(G) χ(G) = 1 if and only if G is totally disconnected χ(G) = 3 if G is an odd cycle χ(G) ≤ Δ(G)+1 (maximum degree) Face Coloring Graph Coloring Dual Map Dual Graph G* of a Plane Graph: A plane graph whose vertices corresponding to the faces of G. The edges of G* corresponds to the edges of G as follows: if e is an edge of G with face X on one side and face Y on the other side, then the endpoints of the dual edge e* in E(G*) are the vertices x and y of G* that represent