第七章_平面图.ppt

平面图 一个图G如果能以这样的方式画在平面上;除顶点处外没有边交叉出现,则称G为平面图.画出的没有边交叉出现的图称为G的一个平面嵌入或G的一个平图. 平面图中的一些概念 设G是一个连通的平面图(指G的某个平面嵌入),G的边将G所在的平面划分成若干个区域,每个区域称为G的一个面.其中面积无限的区域称为无限面或外部面,常记成R0.包围每个面的所有边所构成的回路称为该面的边界,边界的长度称为该面的次数,R的次数记为deg(R). 图(1)所示为连通的平面图,共有3个面R0,R1,R2.R1的边界为回路v1v3v4v1,deg(R1)=3.R2的边界为回路v1v2v3v1,deg(R2)=3.R0的边界为复杂回路v1v4v5v6v5v4v3v2v1,deg(R0)=8. 例 极大平面图、极小非平面图 设G为一个简单平面图,如果在G中任意不相邻的两个顶点之间再加一条边,所得图为非平面图,则称G为极大平面图. 若在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图. 例 K5, K3,3是极小非平面图， K5任意删除一条边后所得图是极大平面图 性质 极大平面图有以下性质; (1)极大平面图是连通的; (2)任何n(n≥3)阶极大平面图中,每个面的次数均为3. (3)任何n(n≥4)阶极大平面图G中,均有?(G)≥3. 欧拉公式 设G为任意的连通的平面图,则有 n-m+r＝2 成立.其中,n为G中顶点数,m为边数,r为面数. 证明 证明 对边数m作归纳法. (1)m＝0时,G为孤立点,此时n＝1,r＝1,结论自然成立. (2)设m＝k-1(k≥1)时结论成立,要证明m＝k时结论成立. 证明 首先,若G为树,任取一树叶v并删除它,得G＝G-v, G中有n＝n-1个顶点m＝m-1条边,r＝r,由归纳假设有下式成立; n-m+r＝2, 即 (n-1)-(m-1)+r＝2, 整理后得 n-m+r＝2. 证明 其次,G不是树,证明则G中必有初级回路.设C为一初级回路,e在C上.令G＝G-e,由于e在C上,所以,G仍连通,在G中,n＝m,m＝m-1,r＝r-1,利用归纳假设可得 n-m+r＝2. 欧拉公式的推广 对于任意的p(p≥2)个连通分支的平面图G,有 n-m+r＝p+1 成立. 定理 设G是连通的平面图,且每个面的次数至少为l(l≥3),则 证明. 2m≥lr, n-m＋r＝2, ln-lm＋2m≥ ln-lm＋lr＝2l, lm-2m≤ln-2l 推广 设G是p(p≥2)个连通分支的平面图,每个面的次数至少为l(l≥3),则 K5和K3,3 K5和K3,3都不是平面图.若K5是平面图,则每个面的次数至少为3.但是由前面的定理有; 10≤3(5-2)＝9 这是矛盾的,因而K5不是平面图. 类似地,K3,3也不是平面图. 定理6 设G为连通的简单的平面图,则G中至少存在一个顶点v,有d(v)≤5. 证明. 假设任意顶点v,d(v)≥6. 6n≤2m,3r≤2m 3n≤m n-m＋r＝2 6＝3n-3m＋3r≤m-3m＋2m＝0 这不可能. 消去 插入 在图(1)中,从左到右的变换称为消去2度顶点w.图(2)中从左到右的变换称为插入2度顶点w. 同胚 初等收缩 如果两个图G1和G2同构,或经过反复插入或消去2度顶点后同构,则称G1与G2同胚. 图G中相邻顶点u,v之间的初等收缩由下面方法给出;删除边(u,v),用新的顶点w取代u,v,使w关联u,v关联的一切边(除(u,v)外). 库拉图斯基定理 一个图是平面图当且仅当它不含与K5同胚子图,也不含与K3,3同胚子图. 另一种叙述形式; 一个图是平面图当且仅当它没有可以收缩到K5的子图,也没有收缩到K3,3的子图. 例 对偶图 设平面图G＝V,E,G有r个面,n个顶点,m条边.用如下的方法构造G*; (1)在G的面Ri中任取一个顶点vi*作为G*的顶点,G*的顶点集V*＝{v1*,v2*,...,vr*}, 对偶图 (2)若面Ri和Rj的边界中有公共边ek,连接对应顶点vi*和vj*,得G*的边ek*与ek相交.当ek只在G的一个面Rj的边界中出现时,以Ri中的顶点vi*为顶点做环ek*,ek*为G*中一个环.设G*的边集为E*,由于G*的边数与G的边数相同,