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*)。第30页，共47页，星期日，2025年，2月5日实线边图为平面图，虚线边图为其对偶图。第31页，共47页，星期日，2025年，2月5日从定义不难看出G的对偶图G*有以下性质：G*是平面图，而且是平面嵌入。G*是连通图。若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环。在多数情况下，G*为多重图（含平行边的图）。同构的平面图（平面嵌入）的对偶图不一定是同构的。第32页，共47页，星期日，2025年，2月5日二、平面图与对偶图的阶数、边数与面数之间的关系。定理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)第33页，共47页，星期日，2025年，2月5日(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)。证明第34页，共47页，星期日，2025年，2月5日定理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)第35页，共47页，星期日，2025年，2月5日三、自对偶图定义17.7设G*是平面图G的对偶图，若G*?G，则称G为自对偶图。第36页，共47页，星期日，2025年，2月5日在n?1(n?4)边形Cn?1内放置1个顶点，使这个顶点与Cn?1上的所有的顶点均相邻，所得n阶简单图称为n阶轮图。记为Wn。n为奇数的轮图称为奇阶轮图。n为偶数的轮图称为偶阶轮图。轮图都是自对偶图。小节结束第37页，共47页，星期日，2025年，2月5日本章主要内容平面图及平面嵌入。?平面图的面与次数。?极大平面图及性质。?极小非平面图。?欧拉公式及其推广。平面图的边数m与顶点数n的关系。简单平面图G中，δ(G)≤5。库拉图斯基的两个定理。平面图的对偶图。第38页，共47页，星期日，2025年，2月5日本章学习要求深刻理解本部分的基本概念：平面图、平面嵌入、平面图的面、次数、极大平面图、极小非平面图、平面图的对偶图、自对偶图等。?熟练掌握极大平面的性质，特别是充分必要条件。?熟练掌握并会应用欧拉公式及其推广形式。?掌握由欧拉公式及其推广形式所证明的平面的性质。?会用库拉图斯基定理证明某些图不是平面图。?掌握平面图与其对偶图某些关系的定理。第39页，共47页，星期日，2025年，2月5日第40页，共47页，星期日，2025年，2月5日解第41页，共47页，星期日，2025年，2月5日第42页，共47页，星期日，2025年，2月5日第1页，共47页，星期日，2025年，2月5日本章说明本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图第2页，共47页，星期日，2025年，2月5日本章所涉及到的图均指无向图。第3页，共47页，星期日，2025年，2月5日17.1平面图的基本概念17.2欧拉公式17.3平面图的判断17.4平面图的对偶图本章小结习题作业第4页，共47页，星期日，2025年，2月5日17.1平面图的基本概念一、关于平面图的一些基本概念