第11章平面图..ppt

? Peking University 3-2 平面图 基本概念 欧拉公式 平面图的判断 对偶图 着色 点着色 地图着色和平面图的点着色 边着色 在实际应用中,如高速公路设计、印刷电路设计,都要求 线路不交叉,这就是平面图, 一个图能否画在一个平面上, 且任何边都不交叉, 这就是图的平面化问题. 这个问题在 近些年来, 特别是大规模集成电路的发展进一步促进了对 平面图的研究. 设G是无向图, 如果能将G的所有结点和边都画在一个 平面上,且使得任何两条边除了端点外没有其它交点, 则 称G是个平面图。 一个图表面上是个非平面图, 如果通过 改变边的位置就变成平面图, 称此图是可平面化的。 定理11.16 证明:n*=r,m*=m,r*=n-p+1,dG*(vi*)=degG(Ri) 证明：n-m+r = p+1 n*-m*+r*=2 所以 r* = n-p+1 设Ri的边界Ci中有k1条桥,k2条非桥,则 deg(Ri)=k2+2k1 而对应vi*点处有k1个环,k2条非桥对应引出k2条边,则 dG* (vi*)= k2+2k1 所以dG*(vi*)=degG(Ri) # 定理12.5 定理12.5: ?(G) ≤?(G)+1 证: (归纳法)n=1,结论成立. 设n=k结论成立,设G的阶数为k+1, ?v∈V(G),G1=G-v,G1的阶数为k,则 ?(G1) ≤?(G1)+1 ≤?(G)+1,当G1还原成G时,v至多与?(G)个顶点相邻,而G1中, ?(G)个顶点至多用了?(G)种颜色,则?(G)+1种颜色中至少存在一种颜色给v着色,使v与相邻顶点均着不同的颜色. # 例11.6 例11.6: K6的含K3,3的非同构子图有哪些? 解: K6有15条边, K3,3有9条边, 分别给K3,3加0,1,2,3,4,5,6条边: 共10种. # 对偶图(偶图)的定义: 给定平面图G=V,E, 具有平面R1,R2,R3,…,Rn. 如果有 图G*=V*,E*, 满足下面条件: ⑴对于G的任意平面Ri 的内部有且仅有一个结点vi*∈V*. ⑵对于图G的面Ri与Rj的公共边界ek ,有且仅有一条边 ek*∈E* ,使得 ek*=(vi*,vj*), 且ek*与ek相交.(vi*在Ri内, vj*在Rj内) ⑶当且仅当ek只是一个面Ri的边界时, vi*上有一个环ek* 与ek相交. 则称图G*是G的对偶图. ? v4 ? v3 v2 ? ? v1 ?v2* v5 ? v3* ? ?v1* R1 R2 R3 对偶图(dual graph) 对偶图: 平面图G=V,E的对偶图是G*=V*,E*, G和G*的面集合是R和R*,则V*与R, E*与E,都是一一对应的 对偶图的性质 对偶图是连通平面图 环与桥互相对偶 平行边对偶于2个面之间的多条边界 G1?G2,不一定G1*?G2* 着色问题起源于对地图着色, 使得相邻(具有相同边界)国家用不同颜色,需要多少种不同的颜色? 1852年,英国数学家格色里(Guthrie)提出了“四色猜想”. 1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题 1879年肯普(Kempe)给出了这个猜想的第一个证明. 1890年,希伍德(Hewood)发现肯普的证明是错误的, 可是他指出肯普的方法,虽然不能证明地图着色用四种颜色,但可以证明五种颜色就够了. 直到1976年美国伊利诺斯(Illinois)大学的阿佩尔(K.Appel)和哈肯(W.Haken)把四色问题归结为2000个不同的组合结构图形,利用三台高速IBM360计算机对这些图形进行分析用了1200机时,近百亿次逻辑判断, 证明了“四色定理”. 黑 黑 红 蓝 蓝 绿 绿 着色(coloring) 着色: 给图的某类元素(点,边,面)中每个指定1种颜色,使得相邻元素有不同颜色 用颜色集C给X中元素着色: f:X?C, ?x?y( x,y?X?x与y相邻 ? f(x)?f(y) ) 若|C|=k( 如C={1,2,…,k} ), 则称k-着色 (点)着色,边着色,面着色: X=V(无环),E,R 相邻: V,有边相连,(x,y)?E; E,有公共端点, (x,y),(y,z); R,有公共边界 着色(例) k-色图: 可k-着色,但不可(k-1)-着色 色数(chromatic number): 着色所需最少颜色数 点色数?(G), 边色数?’(G), 面色数?*(G) 例: ?(G)=2, ?’(G)=4, ?*(G)=3 点色数性质 ?(G)=1 ? G是零图 ?(Kn)=n ?(G)=2 ? G是非零图二部图 G可2-着色 ? G是