上海交通大学：《离散数学》课程教学资源（PPT课件）第四章 平面图与图的着色

第四章平面图与图的着色 4.1平面图 。定义4.1.1 若能把图G画在一个平面上，使任何两条边都 不相交，就称G可嵌入平面，或称G是可平面图 可平面图在平面的一个嵌入称为平面图. 。如果G是可平面图，那么它的任何导出子图也是 可平面图

第四章 平面图与图的着色 4.1 平面图 l 定义 4.1.1 若能把图G画在一个平面上，使任何两条边都 不相交,就称G可嵌入平面，或称G是可平面图. 可平面图在平面的一个嵌入称为平面图. l 如果G是可平面图,那么它的任何导出子图也是 可平面图

平面图 定义4.1.2 设G是一个平面图，由它的若干条边所构成的 一 个区域内如果不含任何结点及边，就称该区域 为G的一个面或域.包围这个域的诸边称为该域 的边界. 为了讨论方便，我们把平面图G外边的无限区域 称为无限域，其他的域都叫做内部域.如果两个 域有共同的边界，就说它们是相邻的，否则是 不相邻的.如果e不是割边，它一定是某两个域的 共同边界

平面图 l 定义 4.1.2 设G是一个平面图,由它的若干条边所构成的一 个区域内如果不含任何结点及边，就称该区域 为G的一个面或域.包围这个域的诸边称为该域 的边界. l 为了讨论方便,我们把平面图G外边的无限区域 称为无限域,其他的域都叫做内部域.如果两个 域有共同的边界，就说它们是相邻的,否则是 不相邻的.如果e不是割边,它一定是某两个域的 共同边界

平面图 。定理4.1.1 设G是平面连通图，则G的域的数目是 d=m-n+2. 证明：G是连通图，有支撑树T,它包含n-1条边， 不产生回路，因此对T来说只有一个无限域.由于 G是平面图，每加入一条余树边，它一定不与其 他边相交，也就是说一定是跨在某个域内部，把 该区域分成两部分.这样，加入G的m-n+1条余树 边，就生成了m-n+2个域

平面图 l 定理 4.1.1 设G是平面连通图,则G的域的数目是 d = m – n + 2. 证明:G是连通图,有支撑树T,它包含n-1条边， 不产生回路,因此对T来说只有一个无限域.由于 G是平面图,每加入一条余树边,它一定不与其 他边相交,也就是说一定是跨在某个域内部,把 该区域分成两部分.这样,加入G的m-n+1条余树 边,就生成了m-n+2个域

平面图 。推论4.1.1 若平面图G有k个连通支，则 n-m+d=k-1. 。推论4.1.2 对一般平面图G,恒有 n-m+d>=2

平面图 l 推论 4.1.1 若平面图G有k个连通支,则 n – m + d = k – 1. l 推论 4.1.2 对一般平面图G,恒有 n – m + d >= 2

平面图 。定理4.1.2 设平面连通图G没有割边，且每个域的边界数至 少是t,则 m=m-n+2, 即，m<=t*(n-2)1(t-2)

平面图 l 定理 4.1.2 设平面连通图G没有割边,且每个域的边界数至 少是t,则 m = m - n + 2, 即, m <= t * (n - 2) / (t – 2)

4.3非平面图 如果图G不能嵌入平面，满足任意两边只能在 结点处相交，那么G就称为非平面图 。这样，按平面性质进行划分，图G分为两大类：可 平面图和非平面图

4.3 非平面图 l 如果图G不能嵌入平面,满足任意两边只能在 结点处相交,那么G就称为非平面图 l 这样,按平面性质进行划分,图G分为两大类:可 平面图和非平面图

非平面图 。定理4.3.1 K是非平面图， 证明：在K.中，n=5,m=10.如果它是可平面图，应 该有m<=3n-6.而此时3n-6=9,矛盾. ● 定理4.3.2 K.是非平面图 证明：假定K3是可平面图，由于n=6,m=9.由欧 拉公式，d=5.但G中没有K,子图，因此4d<=2m, 亦即20<=18，矛盾

非平面图 l 定理 4.3.1 是非平面图. 证明:在 中,n=5,m=10.如果它是可平面图,应 该有m<=3n-6.而此时3n-6=9,矛盾. l 定理 4.3.2 是非平面图. 证明:假定 是可平面图,由于n= 6,m=9.由欧 拉公式,d=5.但G中没有 子图,因此4d<=2m, 亦即20<=18,矛盾. K5 K5 K3,3 K3 K3,3

非平面图 。约定K和K3分别记为和2图. 。定义4.3.1 在K四和2图上任意任意增加一些度为2的结点之后 得到的图象为K四型和K2型图，统称为K型图 。定理4.3.3 G是可平面图的充要条件是G不存在K型图

非平面图 l 约定 和 分别记为 和 图. l 定义 4.3.1 在 和 图上任意任意增加一些度为2的结点之后 得到的图象为 型和 型图,统称为K型图. l 定理 4.3.3 G是可平面图的充要条件是G不存在K型图. K5 K3,3 (1) K (2) K (1) K (2) K (1) K (2) K

4.5对偶图 定义4.5.1 满足如下条件的图G*称为G的对偶图. 1.G中每个确定的域内设置一个结点y. 2. 对域f和f的共同边界ek,有一条边e=(%,y)∈E(G), 并与ek相交一次. 3. 若e处于域之内，则侧v有一自环ek与e相交一次

4.5 对偶图 l 定义 4.5.1 满足如下条件的图G*称为G的对偶图. 1. G中每个确定的域 内设置一个结点 . 2. 对域 和 的共同边界 ,有一条边 , 并与 相交一次. 3. 若 处于域 之内,则 有一自环 与 相交一次. i f j f * i v k e ( , ) ( ) * * * ek  vi vj E G * k e i f k e k e i f * i v k e

对偶图 。性质4.5.1 如果G是平面图，G一定有对偶图G*,而且G*是 唯一的.由D过程即可得证 ●性质4.5.2 G*是连通图 在平面G里，每个域都存在相邻的域，而且对G 的任何部分域来说，都存在与它们之中某个域 相邻的域这样由对偶图的定义可知G*连通

对偶图 l 性质 4.5.1 如果G是平面图,G一定有对偶图G* ,而且G*是 唯一的. 由D过程即可得证. l 性质 4.5.2 G*是连通图. 在平面G里,每个域f都存在相邻的域,而且对G 的任何部分域来说，都存在与它们之中某个域 相邻的域.这样由对偶图的定义可知G *连通