离散数学 平面图与着色

离散数学

第12章 平面图与图着色

离散数学

Three kinds of Coloring Problem

1. Vertex

2. Edge

3. Face

http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/

离散数学

Vertex ColoringA simple graph is said to be k colorable if its vertices can be colored using up to k different colors in such a way that each vertex is of a single color and any two adjacent vertices have different colors. (定义12.7) χ(G)=khttp://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/

离散数学

【定理12.7】 χ(G)=1 当且仅当G是零图。 【定理12.8】 χ(Kn)=n 。 【定理12.10】 设G中至少含一条边，则 χ(G)=2 当且仅当G为二部图。

离散数学

Vertex ColoringTheorem If every vertex of G has degree d(v) < k, then G is k-colorable. Proof: Use induction on n (number of vertices). 1.If n = 1 or n = 2, the assertion is easily seen to be true. Suppose n > 2, and assume that the proposition is valid for all graphs with fewer than n vertices. 2.Choose any vertex v of G and delete it and all the edges incident to v. This leaves a subgraph H of G with n - 1 vertices satisfying the given hypothesis (i.e. that every vertex has degree less than k). By the inductive hypothesis, (H) k. Now, consider any particular k-coloring of H. Since d(v) < k, the vertices of H that were adjacent to v in G are colored with at most k 1 different colors. Thus, there’s at least one color left with which we may color v, so that it is of a different color to each of its neighbors. This gives a coloring of G using the same colors as H. Therefore, G is k-colorable.http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/

离散数学

Vertex Coloring

max d v 1 k v V G

http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/

离散数学

12.1平面图的基本概念

离散数学

12.1平面图的基本概念【定义12.1】若能把一个图G的图形画在曲 面S上，使图的边在顶点之外都不相交，则 称图G可嵌入曲面S。可嵌入平面的图称为 可平面图，否则称为不可平面图。已经嵌 入一张平面的图称为平面图。

离散数学

举例【例12.1】 判断下图是否为可平面图

b a

c b a eH

c

eG

d

d

离散数学

【例12.2】 K1(平凡图),K2,K3,K4都 是平面图，其中，K1,K2,K3本身就已经 是平面嵌入，K4的平面嵌入为下图(4)所 示。K5-e (K5删除任意一条边)也是平面 图，它的平面嵌入可表示为下图中(5).完 全二部图K1,n(n≥1), K2,n(n≥2),也都是 平面图，其中标准画法画出的K1,n已经是 平面嵌入，K2,3的平面嵌入可由图12.1.2 中(6)给出。图12.1.2中(1),(2),(3) 分别为K4, Ky-e, K2,3的标准画法。

离散数学

离散数学

【定义12.2】设G是平面图，若G的边围成一个封 闭区域，该区域内的任意两点间都可以作一条曲 线相连接，此曲线不遇到G的任何边和顶点，则 此区域称为G的一个面。界定一个面的所有边称 为该面的边界。边界中的边数称为该面的度，并 规定桥在计算度时算作两条边。对于面f 的边

界 上的一条边e,也称是f 的一条边界。面f 的周线 是由面f 的边界构成且把面f 包含在内的圈。两个 面若有公共边则称它们相邻。一个面与它边界上 的边和点称为相关联。

离散数学

每个平面图恰有一个无界面，称为外部面， 其余的面都是有界面，称为内部面 由定义，外部面没有周线，内部面有一条 周线。

离散数学

【例12.3】 找出下图的面及其度、边界和周线：e1 e3 e2 e5 e4 e6 e8 e7 e9 e10

f1 的边界为e1e3e3e4e5e2,度为6,周线为e1e4e5e2 f2 的边界为e7e8,度为2,周线为e7e8 f3的边界为e10,度为1,周线为e10 f4 的边界为e1e4e6e7e9e10e9e8e6e5e2,度为11,没有 周线 其中f4 是外部面，其他都是内部面。

离散数学

【定理12.1】设G是平面图，则 其中F(G)表示G的所有面的集，d(f)表示f 的度。 【推论12.1】平面图中奇度面数必为偶数。f F ( G )

d ( f ) 2 E(G)

离散数学

12.2=

欧拉公式和极大平面图

【定理12.1】设G是连通平面图，共有n个 顶点，m条边，r个面，则n – m + r =2。 【证】首先构造图G的一系列图子图，G1,G2,…,Gm=G,使得Gk是恰含有k(k=1, 2, …, k)条边的连通图。构造方法如下： (1)任意选择Gk-1中的一条边来获得Gk :任意 的添加一条与Gk-1边中某个顶点相关联的边，若 与这条边关联的另一个顶点不在Gk-1里，则添加 这个顶点。