平面图_工学_高等教育_教育专区。中国地质大学本科生课程 离散数学 第17章 平面图 本章说明 本章所涉及到的图均指无向图。 ?本章的主要内容 –平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图 本章主要内容
中国地质大学本科生课程 离散数学 第17章 平面图 本章说明 本章所涉及到的图均指无向图。 ?本章的主要内容 –平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图 本章主要内容 ? 17.1 平面图的基本概念 ? 17.2 欧拉公式 ? 17.3 平面图的判断 ? 17.4 平面图的对偶图 ? ? ? 本章小结 习 作 题 业 17.1 平面图的基本概念 一、关于平面图的一些基本概念 1、 平面图的定义 定义17.1 ? G可嵌入曲面S——如果图G能以这样的方式画在曲面S上， 即除顶点处外相交。 ? G是可平面图或平面图——若G可嵌入平面。 ? G的平面嵌入——画出的相交的平面图。 ? 非平面图——无平面嵌入的图。 17.1 平面图的基本概念 （2）是（1）的平面嵌入，（4）是（3）的平面嵌入。 17.1 平面图的基本概念 2、 几点说明及一些简单结论 ? 一般所谈平面图不一定是指平面嵌入，但讨论某些性质时， 一定是指平面嵌入。 ? K5和K3,3都不是平面图。 ? 17.1 设G??G，若G为平面图，则G?也是平面图。 ? 设G??G，若G?为非平面图，则G也平面图。 ? 由可知， Kn(n?5)和K3,n(n?3)都平面图。 ? 17.2 若G为平面图，则在G中加平行边或环所得图还是 平面图。 即平行边和环不影响图的平面性。 17.1 平面图的基本概念 二、平面图的面与次数（针对平面图的平面嵌入） 1、 定义 定义17.2 设G是平面图， ? G的面——由G的边将G所在的平面划分成的每一个区域。 ? 无限面（外部面）——面积无限的面，记作R0。 ? 有限面（内部面）——面积有限的面 ，记作R1, R2, …, Rk。 ? 面Ri的边界——包围面Ri的所有边组成的回组。 ? 面Ri的次数——Ri边界的长度，记作deg(Ri)。 17.1 平面图的基本概念 2、几点说明 ? 若平面图G有k个面，可笼统地用R1, R2, …, Rk表示，不需 要指出外部面。 ? 回组是指：边界可能是初级回（圈），可能是简单回 ，也可能是复杂回。特别地，还可能连通的回 之并。 R1 R0 R2 R3 平面图有4个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 17.1 平面图的基本概念 17.3 平面图G中所有面的次数之和等于边数m的两倍，即 ? deg( R ) ? 2m 证 明 i ?1 i r 其中r为G的面数 本中所说平面图是指平面嵌入。 ?e∈E(G)， ?当e为面Ri和Rj(i≠j)的公共边界上的边时，在计算Ri和Rj的次 数时，e各提供1。 ?当e只在某一个面的边界上出现时，则在计算该面的次数时 ，e提供2。 于是每条边在计算总次数时，都提供2，因而deg(Ri)=2m。 17.1 平面图的基本概念 三、极大平面图 1、 定义 定义17.3 若在简单平面图G中的任意两个不相邻的顶点之 间加一条新边所得图为非平面图，则称G为极大平面图。 注意：若简单平面图 G中已无不相邻顶点，G显然是极大平 面图，如K1（平凡图）, K2, K3, K4都是极大平面图。 2、极大平面图的主要性质 17.4 极大平面图是连通的，并且n(n?3)阶极大平面图 中不可能有割点和桥。 17.1 平面图的基本概念 17.5 设G为n(n?3) )阶简单连通的平面图，G为极大平面图 当且仅当G的每个面的次数均为3。 证 明 思 ?本节只证明必要性，即设G为n(n?3) )阶简单连通的平面图，G 为极大平面图，则G的每个面的次数均为3。 ?由于n?3, 又G必为简单平面图，可知，G每个面的次数均?3。 ?因为G为平面图，又为极大平面图。可证G不可能存在次数3 的面。 17.1 平面图的基本概念 假设存在面Ri的次数deg(Ri)=s≥4， 如图所示。 s S-1 在G中，若v1与v3不相邻，在Ri内加边(v1,v3)不平面性，这 与G是极大平面图矛盾，因而v1与v3必相邻，姐妹互换一家亲由于Ri的存在， 边(v1,v3)必在Ri外。 类似地，v2与v4也必相邻，且边(v2,v4)也必在Ri外部，于是必 产生(v1,v3)与(v2,v4)相交于Ri的外部，这又矛盾于G是平面图， 所以必有s＝3，即G中不存在次数大于或等于4的面，所以G的 每个面为3条边所围，也就是各面次数均为3。 17.1 平面图的基本概念 只有右边的图为极大平面图。 因为只有该图每个面的次数都为3。 17.1 平面图的基本概念 四、极小非平面图 定义17.4 若在非平面图G中任意删除一条边，所得图G?为平面 图，则称G为极小非平面图。 由定义不难看出： ? K5, K3,3都是极小非平面图。 ? 极小非平面图必为简单图。 例如：以下各图均为极小非平面图。 小节结束 17.2 欧拉公式 一、欧拉公式相关 1、 欧拉公式 17.6 对于任意的连通的平面图G，有 n-m+r=2 其中，n、m、r分别为G的顶点数、边数和面数。 证明 对边数m作归纳法。 (1) m＝0时，由于G为连通图，所以G只能是由一个孤立顶 点组成的平凡图，即n=1，m=0，r=1，结论显然成立。 (2) m＝1时，由于G为连通图，所以n=2，m=1，r=1，结论 显然成立。 17.7 对于具有k(k≥2)个连通分支的平面图G，有 n-m+r = k+1 其中n，m，r分别为G的顶点数，边数和面数。 证明 设G的连通分支分别为G1、G2、…、Gk，并设Gi的顶点数、 边数、面数分别为ni、mi、ri、i=1，2，…，k。 由欧拉公式可知: ni-mi+ri = 2，i=1，2，…，k 易知， m ? ? mi，n ? ? ni i ?1 i ?1 k k (17.1) 由于每个Gi 有一个外部面，而G只有一个外部面，所以G的面数 k r ? ? ri ? k ? 1 i ?1 于是，对(17.1)的两边同时求和得 2k ? ? (ni ? mi ? ri ) ? ? ni ? ? mi ? ? ri ? n ? m ? r ? k ? 1 i ?1 i ?1 i ?1 i ?1 k k k k 经整理得 n-m+r = k+1。 17.2 欧拉公式 2、 与欧拉公式有关的 17.8 设 G 为连通的平面图，且每个面的次数至少为 l(l ? 3)，则 G的边数与顶点数有如下关系： m? 证明 l ( n ? 2) l?2 由17.3（面的次数之和等于边数的2倍）及欧拉公式得 2m ? ? deg( Ri ) ? l ? r ? l (2 ? m ? n) l ( n ? 2) 解得 m ? l?2 i ?1 r 17.2 欧拉公式 推论 K5, K3,3不是平面图。 证明 ?若K5是平面图，由于K5中无环和平行边，所以每个面的次数 均大于或等于l≥3，由17.8可知边数10应满足 10≤(3/(3-2))(5-2) = 9 这是个矛盾，所以K5不是平面图。 ?若K3,3是平面图，由于K3,3中最短圈的长度为l≥4，于是边数9 应满足 ????9≤ (4/(4-2))(6-2) = 8 这又是矛盾的，所以K3,3也不是平面图。 17.2 欧拉公式 17.9 设G是有k(k≥2)个连通分支的平面图，各面的次数至 少为l(l≥3)，则边数m与顶点数n应有如下关系： m? l (n ? k ? 1) l ?2 17.10 设G为n(n?3)阶m条边的简单平面图，则m?3n?6。 证明 设G有k(k?1)个连通分支， ? 若G为树或森林，当n?3时，m=n-k?3n?6。 ? 若G不是树也不是森林，则G中必含圈，又因为G是简单图 ，所以，每个面至少由l（l?3）条边围成，又在l=3达到最大 值，由17.9可知 m? l 2 (n ? k ? 1) ? (1 ? )(n ? k ? 1) ? 3(n ? 2) ? 3n ? 6 l ?2 l ?2 17.2 欧拉公式 17.11 设G为n(n?3)阶m条边的极大平面图，则m=3n?6。 证明 由于极大平面图是连通图，由欧拉公式得: ????r=2+m-n (17.4) 又因为G是极大平面图，由17.7的必要性可知，G的每个 面的次数均为3，所以： 2m ? ? deg( Ri ) ? 3r i ?1 r (17.5) 将(17.4)代入(17.5)，整理后得 m = 3n-6。 17.2 欧拉公式 二、一个意义重大的 17.12 设G为简单平面图，则G的最小度?(G)?5。 证明 ? 若阶数 n?6，结论显然成立。 ? 若阶数n?7时，用反。 假设?(G) ?6，由握手可知： 2m＝? d (vi ) ? 6n n i ?1 因而m ?3n，这与17.10矛盾。 所以，假设不成立，即G的最小度?(G)?5。 说 明 ?本在图着色理论中占重要地位。 17.3 平面图的判断 一、为判断做准备 1、 插入2度顶点和消去2度顶点 定义17.5 ? 设e=(u,v)为图G的一条边，在G中删除e，增加新的顶点w， 使u、v均与w相邻，称为在G中插入2度顶点w。 ? 设w为G中一个2度顶点，w与u、v相邻，删除w，增加新边 (u,v)，称为在G中消去2度顶点w。 17.3 平面图的判断 2、图之间的同胚 若两个图 G1 与 G2 同构，或通过反复插入或消去 2 度顶点后 是同构的，则称G1与G2是同胚的。 两个图分别与K3,3, K5同胚 。 17.3 平面图的判断 二、两个判断 17.13(库拉图斯基 1) 图G是平面图当且仅当 G中既不 含与K5同胚子图，也不含与K3,3同胚子图。 17.14(库拉图斯基 2) 图G是平面图当且仅当 G中既没 有可以收缩到K5的子图，也没有可以收缩到K3,3的子图。 17.3 平面图的判断 例17.1 证明彼得松图不是平面图。 证 明 将彼得松图顶点标顺序，见图 (1)所示。 在图中将边(a,f), (b,g), (c,h), (d,i), (e,j)收缩， 所得图为图 (2)所示，它是K5， 由17.16可知，彼得松图不是平面图。 还可以这样证明： 用G表示彼得松图，令 G=G-{(j,g),(c,d)} G‘如图 (3)所示，易知它与K3,3同胚， 由17.15可知，G为非平面图。 17.4 平面图的对偶图 一、对偶图的定义 定义17.6 设G是某平面图的某个平面嵌入，构造G的对偶图 G*如下： ? 在G的面Ri中放置G*的顶点vi* 。 ? 设e为G的任意一条边， ? 若 e 在 G 的面 Ri 与 Rj 的公共边界上，做 G* 的边 e* 与 e 相交， 且e*关联G*的位于Ri与Rj中的顶点vi*与vj*，即e*=(vi*,vj*) ，e*不与其它任何边相交。 ?若e为G中的桥且在面Ri的边界上，则e*是以Ri中G*的顶点 vi*为端点的环，即e*=(vi*,vi*)。 17.4 平面图的对偶图 实线 平面图的对偶图 从定义不难看出G的对偶图G*有以下性质： ? G*是平面图，而且是平面嵌入。 ? G*是连通图。 ? 若边 e 为 G中的环，则 G*与 e对应的边 e* 为桥，若 e 为桥， 则G*中与e对应的边e*为环。 ? 在多数情况下，G*为多重图（含平行边的图）。 ? 同构的平面图（平面嵌入）的对偶图不一定是同构的。 17.4 平面图的对偶图 二、平面图与对偶图的阶数、边数与面数之间的关系。 17.15 设G*是连通平面图G的对偶图，n*、m*、r*和n 、 m、r分别为G*和G的顶点数、边数和面数，则 （1）n*= r （2）m*=m （3）r*=n （4）设G*的顶点v*i位于G的面Ri中，则dG*(vi *)=deg(Ri) 证 明 ? (1)、(2)由G*的构造可知是显然的。 ? (3)由于G与G*都连通，因而满足欧拉公式: ???? n-m+r = 2 n*-m*+r* = 2 由(1)、(2))可知， r* = 2+m*-n* = 2+m-r = n ? (4)设G的面Ri的边界为Ci，设Ci中有k1(k1≥0)条桥，k2个非桥边 ，于是 Ci的长度为k2+2k1，即deg(Ri)＝k2+2k1， k1条桥对应vi*处有k1个环，k2条非桥边对应从vi*处引出k2条边， 所以dG*(vi*)＝k2+2k1＝deg(Ri)。 17.4 平面图的对偶图 17.16 设G*是具有k（k?2）个连通分支的平面图G的 对偶图， n*, m*, r*, n, m, r分别为G*和G的顶点数、边数 和面数， （1）n*= r （2）m*=m （3）r*=n?k+1 （4）设G*的顶点v*i位于G的面Ri中，则dG*(v*i)=deg(Ri) 17.4 平面图的对偶图 三、自对偶图 定义17.7 设G*是平面图G的对偶图，若G*?G，则称G为自对偶 图。 17.4 平面图的对偶图 ? 在 n?1(n?4) 边形 Cn?1 内放置 1 个顶点，使这个顶点与 Cn?1 上的 所有的顶点均相邻，所得n阶简单图称为n阶轮图。记为Wn。 ? n为奇数的轮图称为奇阶轮图。 ? n为偶数的轮图称为偶阶轮图。 ? 轮图都是自对偶图。 小节结束 本章主要内容 ? 平面图及平面嵌入。 ? 平面图的面与次数。 ? 极大平面图及性质。 ? 极小非平面图。 ? 欧拉公式及其推广。 ? 平面图的边数m与顶点数n的关系。 ? 简单平面图G中，δ(G)≤5。 ? 库拉图斯基的两个。 ? 平面图的对偶图。 本章学习要求 ? 深刻理解本部分的基本概念：平面图、平面嵌入、平面图的 面、次数、极大平面图、极小非平面图、平面图的对偶图、 自对偶图等。 ? 熟练掌握极大平面的性质，特别是充分必要条件。 ? 熟练掌握并会应用欧拉公式及其推广形式。 ? 掌握由欧拉公式及其推广形式所证明的平面的性质。 ? 会用库拉图斯基证明某些图不是平面图。 ? 掌握平面图与其对偶图某些关系的。 1． 设 G 是连通的简单的平面图，面数 r12，?(G)?3. 证明 G 中存在次数?4 的面 解 解本题可用的有欧拉公式、握手、各面次之和与边数的关 系等. 使用反证明. 设 G 的阶数、边数、面数分别为 n, m, r. 否则，由欧拉公式得 2m 5r = 5 (2+m?n) 由于?(G)?3 及握手又有 2m ? 3n 由①与②得 又有 r=2+m?n 12 由④及②又可得 m30 ③,⑤是矛盾的. ⑤ ④ m?30 ② ③ ① 2. 设 G 是阶数 n?11 的无向平面图，证明 G 和 G 不可能全是平面图. 证 只需证明 G 和 G 中至少有一个平面图. 采用反. 否则 G 与 G 都是平面图，下面来推出矛盾. n( n ? 1) （Kn 的边数） 2 n(n ? 1) m ? 由鸽巢原理知 m 或 m? ，不妨设 m， 4 又由 17.12 知 m ? 3n ? 6 2 由②与③得 n ?13n+24 ? 0 由④解得 2 ? n ?10 ⑤与 n ?11 矛盾. 其实，当 n=9,10 时，命题结论已真. G 与 G 的边数 m, m? 应满足 m ? m ? ① ② ③ ④ ⑤ 3. 证明图 14 所示图为非平面图 图 14 证 用库拉图斯基证明 方法一. 图 15 所示图为图 14 所示图的子图，它是 K3,3（请找 出互补顶点子集） ，由库拉图斯基得证命题. 图 15 证 方法二. 图 16 所示图为图 14 的子图（删除边(a,f)） ，收缩图 16 中的 (a,e) 和 (f,g) 所得图为 K5, 由库拉图斯基得证命题. 图 16 作业 习题十七： 3(b)、 15 结束