《离散数学：第十七章 平面图》由会员分享，可在线阅读，更多相关《离散数学：第十七章 平面图（27页珍藏版）》请在金锄头文库上搜索。
1、第十七章第十七章 平面图平面图本章的主要内容本章的主要内容l平面图的基本概念平面图的基本概念l欧拉公式欧拉公式l平面图的判断平面图的判断l平面图的对偶图平面图的对偶图1在图中，在图中，(2)是是(1) 的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.17.1 平面图平面图的基本概念的基本概念定义定义17.1 (1) G可嵌入曲面可嵌入曲面S若能将若能将G除顶点外无边相交地画在除顶点外无边相交地画在S上上(2) G是是可平面图可平面图或或平面图平面图G可嵌入平面可嵌入平面 (3) 平面嵌入平面嵌入画出的无边相交的平面图画出的无边相交的平面图(4) 非平面图非平面图无平面嵌入的无向图
2、无平面嵌入的无向图 (1) (2) (3) (4)2几点说明及一些简单结论几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入，上图中一般所谈平面图不一定是指平面嵌入，上图中4个图都是平个图都是平面图，但讨论某些性质时，一定是指平面嵌入面图，但讨论某些性质时，一定是指平面嵌入. 结论：结论： (1) K5, K3,3都不是平面图（待证）都不是平面图（待证）(2) 设设GG，若，若G为平面图，则为平面图，则G 也是平面图（定理也是平面图（定理17.1）(3) 设设GG，若，若G 为非平面图，则为非平面图，则G也是非平面图（定也是非平面图（定理理17.2），由此可知，），由此可知，Kn(n 6)
3、，K3,n(n 4) 都是非平面都是非平面图图. (4) 平行边与环不影响平面性平行边与环不影响平面性. 3平面图平面图(平面嵌入平面嵌入)的面与次数的面与次数定义定义17.2 (1) G的的面面由由G的平面嵌入的边将平面化分成的区域的平面嵌入的边将平面化分成的区域(2) 无限面无限面或或外部面外部面（可用（可用R0表示）表示）面积无限的面面积无限的面(3) 有限面有限面或或内部面内部面（可用（可用R1, R2, , Rk等表示）等表示）面积面积 有限的面有限的面 (4) 面面 Ri 的边界的边界包围包围Ri的回路组的回路组(5) 面面 Ri 的次数的次数Ri边界的长度，用边界的长度，用deg
4、(Ri)表示表示 4定理定理17.4 平面图各面次数之和等于边数的两倍平面图各面次数之和等于边数的两倍. 几点说明几点说明l若平面图若平面图G有有k个面，可笼统地用个面，可笼统地用R1, R2, , Rk表示，不表示，不需要指出外部面需要指出外部面.l定义定义17.2(4) 中回路组是指：边界可能是初级回路中回路组是指：边界可能是初级回路(圈圈)，可，可能是简单回路，也可能是复杂回路能是简单回路，也可能是复杂回路. 特别地，还可能是非特别地，还可能是非连通的回路之并连通的回路之并. 平面图有平面图有4个面，个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=
5、8. 请写各面的边界请写各面的边界. 5极大平面图极大平面图定义定义17.3 若在简单平面图若在简单平面图G中的任意两个不相邻的顶点之间中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称加一条新边所得图为非平面图，则称G为为极大平面图极大平面图.注意：若简单平面图注意：若简单平面图G中已无不相邻顶点，中已无不相邻顶点，G显然是极大平显然是极大平面图，如面图，如K1(平凡图平凡图), K2, K3, K4都是极大平面图都是极大平面图.极大平面图的主要性质极大平面图的主要性质定理定理17.5 极大平面图是连通的极大平面图是连通的. 证明线索：否则，加新边不破坏平面性证明线索：否则，加新边
6、不破坏平面性定理定理17.6 n（n 3）阶极大平面图中不可能有割点和桥）阶极大平面图中不可能有割点和桥. 证明线索：由定理证明线索：由定理17.5及及n 3可知，可知，G中若有桥，则一定有中若有桥，则一定有割点，因而只需证无割点即可割点，因而只需证无割点即可. 方法还是反证法方法还是反证法.6证明线索：证明线索：(1) 由于由于n 3, 又又G必为简单必为简单平面图可知，平面图可知，G每个面的每个面的次数均次数均 3.(2) 因为因为G为平面图，又为极为平面图，又为极大平面图大平面图. 可证可证G不可能不可能存在次数存在次数3的面的面. 就给出的图讨论即可就给出的图讨论即可. 极大平面图的性
7、质极大平面图的性质定理定理17.7 设设G为为n（n 3）阶极大平面图，则）阶极大平面图，则G的每个面的的每个面的次数均为次数均为3. 7定理定理17.7中的条件也是极大平面图的充分条件中的条件也是极大平面图的充分条件. 定理定理17.7 设设G为为n (n 3) 阶平面图，且每个面的次数均为阶平面图，且每个面的次数均为3，则，则G为极大平面图为极大平面图.定理的应用定理的应用上图中，只有上图中，只有(3)为极大平面图为极大平面图 (1) (2) (3) 8极小非平面图极小非平面图定义定义17.4 若在非平面图若在非平面图G中任意删除一条边，所得图中任意删除一条边，所得图G 为平为平面图，则称
8、面图，则称G为为极小非平面图极小非平面图.由定义不难看出：由定义不难看出：(1) K5, K3,3都是极小非平面图都是极小非平面图(2) 极小非平面图必为简单图极小非平面图必为简单图图中所示各图都是极小非平面图图中所示各图都是极小非平面图.9定理定理17.9 （欧拉公式的推广）设（欧拉公式的推广）设G是具有是具有k（k 2）个连通）个连通分支的平面图，则分支的平面图，则n m+r=k+1证明中对各连通分支用欧拉公式，并注意证明中对各连通分支用欧拉公式，并注意即可即可. 17.2 欧拉公式欧拉公式定理定理17.8 设设G为为n阶阶m条边条边r个面的连通平面图，则个面的连通平面图，则n m+r=2
9、（此公式称为（此公式称为欧拉公式欧拉公式）证证 对边数对边数m做归纳法做归纳法m=0，G为平凡图，结论为真为平凡图，结论为真.设设m=k（k 1）结论为真，）结论为真，m=k+1时分情况讨论时分情况讨论.(1) G中无圈，则中无圈，则G为树，删除一片树叶，用归纳假设为树，删除一片树叶，用归纳假设.(2) 否则，在某一个圈上删除一条边，进行讨论否则，在某一个圈上删除一条边，进行讨论.10解得解得 定理定理17.11 在具有在具有k（k 2）个）个连通分支的平面通分支的平面图中，中，与欧拉公式有关的定理与欧拉公式有关的定理定理定理17.10 设设G为连通的平面图，且为连通的平面图，且deg(Ri)
10、 l, l 3，则，则 证证 由定理由定理17.4及及欧拉公式得欧拉公式得推论推论 K5, K3,3不是平面图不是平面图.11定理定理17.12 设G为n（n 3）阶m条条边的的简单平面平面图，则m 3n 6. 证 设G有有k（k 1）个）个连通分支，若通分支，若G为树或森林，当或森林，当n 3时，m 3n 6为真真. 否否则G中含圈，每个面至少由中含圈，每个面至少由l（l 3）条）条边围成，又成，又定理定理17.13 设设G为为n（n 3）阶）阶m条边的极大平面图，则条边的极大平面图，则m=3n 6.证 由定理由定理17.4, 欧拉公式及定理欧拉公式及定理17.7所所证. 定理定理17.14
11、 设G 为简单平面平面图，则 (G) 5. 证 阶数数 n 6，结论为真真. 当当n 7 时，用反，用反证法法. 否否则会推出会推出2m 6n m 3n，这与定理与定理17.12矛盾矛盾. 与欧拉公式有关的定理与欧拉公式有关的定理在在l=3达到最大值，由定理达到最大值，由定理17.11可知可知m 3n 6.1217.3 平面图的判断平面图的判断1. 插入插入2度顶点和消去度顶点和消去2度顶点度顶点定义定义17.5(1) 消去消去2度顶点度顶点v，见下图中，由，见下图中，由(1) 到到(2) (2) 插入插入2度顶点度顶点v，见下图中，从，见下图中，从(2) 到到(1) . (1) (2) 13
12、2. 收缩边收缩边e，见下图所示，见下图所示.3. 图之间的同胚图之间的同胚定义定义17.6 若若G1 G2，或经过反复插入或消去，或经过反复插入或消去2度顶点后所度顶点后所得得G 1 G 2，则称，则称G1与与G2同胚同胚. 图的同胚图的同胚右边两个图同胚右边两个图同胚14平面图判定定理平面图判定定理定理定理17.15 G是平面图是平面图 G中不含与中不含与K5或或K3,3同胚的子图同胚的子图.定理定理17.16 G是平面图是平面图 G中无可收缩为中无可收缩为K5或或K3,3的子图的子图例例1 证明所示图证明所示图(1)与与(2)均为非平面图均为非平面图. (1) (2)右图右图(1),(2
13、)分别为分别为原图原图(1), (2)的子图的子图与与K3,3, K5同胚同胚. 子图子图 (1) (2) 1517.4 平面图的对偶图平面图的对偶图定义定义17.7 设设G是某平面图的某个平面嵌入，构造是某平面图的某个平面嵌入，构造G的对偶图的对偶图G*如下：如下：(1) 在在G的面的面Ri中放置中放置G*的顶点的顶点v*i. (2) 设设e为为G的任意一条边的任意一条边. 若若e在在G的面的面 Ri与与 Rj 的公共边界上，做的公共边界上，做G*的边的边e*与与e相相 交，且交，且e*关联关联G*的位于的位于Ri与与Rj中的顶点中的顶点v*i与与v*j，即，即 e*=(v*i,v*j)，
14、e*不与其它任何边相交不与其它任何边相交. 若若e为为G中的桥且在面中的桥且在面Ri的边界上，则的边界上，则e*是以是以Ri中中G*的顶的顶 点点v*i为端点的环，即为端点的环，即e*=(v*i,v*i). 16下面两图中，实线边图为平面图，虚线边图为其对偶图下面两图中，实线边图为平面图，虚线边图为其对偶图. 实例实例17G 的对偶图的对偶图G*有以下性质：有以下性质：(1) G*是平面图，而且是平面嵌入是平面图，而且是平面嵌入.(2) G*是连通图是连通图(3) 若边若边e为为G中的环，则中的环，则G*与与e对应的边对应的边e*为桥，若为桥，若e为桥，为桥，则则G*中与中与e对应的边对应的边
15、e*为环为环.(4) 在多数情况下，在多数情况下，G*为多重图（含平行边的图）为多重图（含平行边的图）.(5) 同构的平面图（平面嵌入）的对偶图不一定是同构的同构的平面图（平面嵌入）的对偶图不一定是同构的. 如上面的例子如上面的例子. 对偶图的性质对偶图的性质18平面图与对偶图的平面图与对偶图的阶数、边数与面数之间的关系阶数、边数与面数之间的关系定理定理17.17 设设G*是连通平面图是连通平面图G的对偶图，的对偶图，n*, m*, r*和和n, m, r分别为分别为G*和和G的顶点数、边数和面数，则的顶点数、边数和面数，则(1) n*= r(2) m*=m(3) r*=n(4) 设设G*的顶
16、点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(v*i)=deg(Ri)证明线索证明线索(1)、(2)平凡平凡.(3) 应用欧拉公式应用欧拉公式.(4) 的证明中注意，桥只能在某个面的边界中，非桥边在两的证明中注意，桥只能在某个面的边界中，非桥边在两个面的边界上个面的边界上. 19平面图与对偶图的平面图与对偶图的阶数、边数与面数之间的关系阶数、边数与面数之间的关系定理定理17.18 设设G*是具有是具有k（k 2）个连通分支的平面图）个连通分支的平面图G的对的对偶图，则偶图，则(1) n*= r(2) m*=m(3) r*=n k+1(4) 设设G*的顶点的顶点v*i位于位于G的面的面
17、Ri中，则中，则dG*(v*i)=deg(Ri)其中其中n*, m*, r*, n, m, r同定理同定理17.17. 证明证明(3) 时应同时应用欧拉公式及欧拉公式的推广时应同时应用欧拉公式及欧拉公式的推广. 20自对偶图自对偶图定义定义17.8 设设G*是平面图是平面图G的对偶图，若的对偶图，若G* G，则称，则称G为为自自对偶图对偶图. 轮图轮图定义如下：定义如下：在在n 1（n 4）边形）边形Cn 1内放置内放置1个顶点，使这个顶点与个顶点，使这个顶点与Cn 1上的所有的顶点均相邻上的所有的顶点均相邻. 所得所得n 阶简单图称为阶简单图称为n阶轮图阶轮图. n为为奇奇数的轮图称为数的轮
18、图称为奇阶轮图奇阶轮图，n为偶数的轮图称为为偶数的轮图称为偶阶轮图偶阶轮图，常，常将将 n 阶轮图记为阶轮图记为Wn. 轮图都是自对偶图轮图都是自对偶图. 图中给出了图中给出了W6和和W7. 请画出它们的对偶图，请画出它们的对偶图，从而说明它们都是自对偶图从而说明它们都是自对偶图. 21第十七章第十七章 习题课习题课主要内容主要内容l平面图的基本概念平面图的基本概念l欧拉公式欧拉公式l平面图的判断平面图的判断l平面图的对偶图平面图的对偶图基本要求基本要求l深刻理解本部分的基本概念：平面图、平面嵌入、面、次深刻理解本部分的基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图数、
19、极大平面图、极小非平面图、对偶图l牢记极大平面图的主要性质和判别方法牢记极大平面图的主要性质和判别方法l熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题明有关定理与命题l会用库拉图斯基定理证明某些图不是平面图会用库拉图斯基定理证明某些图不是平面图 l记住平面图与它的对偶图阶数、边数、面数之间的关系记住平面图与它的对偶图阶数、边数、面数之间的关系22练习练习1解解 设设G的阶数、边数、面数分别为的阶数、边数、面数分别为n, m, r. (1) 否则，由欧拉公式得否则，由欧拉公式得 2m 5r = 5 (2+m n) 由于由于 (
20、G) 3及握手定理又有及握手定理又有 2m 3n 由由与与得得 m 30 又有又有 r=2+m n 12 由由及及又可得又可得 m30 ,是矛盾的是矛盾的. (2) 正十二面体是一个反例正十二面体是一个反例 1. 设设G是连通的简单的平面图，面数是连通的简单的平面图，面数r12， (G) 3. (1) 证明证明G中存在次数中存在次数 4的面的面(2) 举例说明当举例说明当r=12时，时，(1) 中结论不真中结论不真.232. 设设G是阶数是阶数n 11的无向平面图，证明的无向平面图，证明G和和 不可能全不可能全是平面图是平面图. 证 只需只需证明明G和和 中至少有一个是非平面中至少有一个是非平
21、面图. 采用反采用反证法法. 否否则 与与G 都是平面都是平面图，下面来推出矛盾，下面来推出矛盾.G与与 的的边数数m, m 应满足足 ( Kn的的边数数) 由由鸽巢原理知巢原理知m或或m ，不妨，不妨设m， 又由定理又由定理17.12 知知 m 3n 6 由由与与得得 n2 13n+24 0 由由解得解得 2 n 10 与与n 11矛盾矛盾. 其实，当其实，当n=9,10时，命题结论已真时，命题结论已真. 练习练习2243. 证明下图为非平面图证明下图为非平面图练习练习325证明证明证证 用库拉图斯基定理证明用库拉图斯基定理证明方法一方法一. 下图为原图的子下图为原图的子图，它是图，它是K3
22、,3，由库拉图斯，由库拉图斯基定理得证命题基定理得证命题. 方法二方法二. 下图为原图的子图（删下图为原图的子图（删除边除边(a,f)），收缩本图中的），收缩本图中的(a,e)和和(f,g)所得图为所得图为K5, 由库由库拉图斯基定理得证命题拉图斯基定理得证命题. 26图20 图19 练习练习44. 设设G为为n（n 3）阶极大平面图，证明）阶极大平面图，证明G的对偶图的对偶图G*是是2-边边连通的连通的3-正则图正则图.证证 证明中用上证明中用上n 3的极大平面图的性质，以及平面图与对的极大平面图的性质，以及平面图与对偶图的关系，对偶图的连通性等偶图的关系，对偶图的连通性等.(1) 证证G*是是2-边连通的边连通的. 由由G*的连通性可知，的连通性可知， (G*) 1，又因为，又因为G为极大平面为极大平面 图，故图，故G为简单图，所以为简单图，所以G*中无桥（因为中无桥（因为G中无环），中无环）， 所以，所以， (G*) 2. 故故G*为为2-边连通的边连通的.(2) 证证G*是是3-正则图正则图. 易知易知G*为简单图，且每个顶点的度数均为为简单图，且每个顶点的度数均为3（由定理（由定理 17.7决定），故决定），故G*为为3-正则图正则图.27
