离散数学第17章计划.pptVIP

第十七章 平面图;引言;在图中，(2)是(1) 的平面嵌入，(4)是(3)的平面嵌入.;几点说明及一些简单结论;平面图(平面嵌入)的面与次数;定理17.4 平面图各面次数之和等于边数的两倍. ;极大平面图;证明线索： (1) 由于n?3, 又G必为简单 平面图可知，G每个面的 次数均?3. (2) 因为G为平面图，又为极 大平面图. 可证G不可能 存在次数3的面. 就给出的图讨论即可. ;定理17.7中的条件也是极大平面图的充分条件. 定理17.7? 设G为n (n?3) 阶平面图，且每个面的次数均为3，则G为极大平面图.;极小非平面图;定理17.9 （欧拉公式的推广）设G是具有k（k?2）个连通分支的平面图，则n?m+r=k+1 证明中对各连通分支用欧拉公式，并注意 即可. ;解得 ;定理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.3 平面图的判断;2. 收缩边e，见下图所示.;平面图判定定理;17.4 平面图的对偶图;下面两图中，实线边图为平面图，虚线边图为其对偶图. ;G 的对偶图G*有以下性质： (1) G*是平面图，而且是平面嵌入. (2) G*是连通图 (3) 若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环. (4) 在多数情况下，G*为多重图（含平行边的图）. (5) 同构的平面图（平面嵌入）的对偶图不一定是同构的. 如上面的例子. ;平面图与对偶图的阶数、边数与面数之间的关系;平面图与对偶图的阶数、边数与面数之间的关系;自对偶图;第十七章 习题课;练习1;2. 设G是阶数n?11的无向平面图，证明G和 不可能全是平面图. ;3. 证明下图为非平面图;证明;图20