离散数学课件图论

《离散数学课件图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十七章平面图本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图SchoolofInformationScienceandEngineering在图中，(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.17.1平面图的基本概念定义:1.G是可平面图或平面图——将G除顶点外无边相交地画在平面上。2.平面嵌入——画出的无边相交的平面图。3.非平面图——无平面嵌入的无向图。(1)(2)(3)(4)SchoolofInformationScienceandEngineering几点说明及一些简单结论一般所谈平面图不一定是指平

2、面嵌入，上图中4个图都是平面图，但讨论某些性质时，一定是指平面嵌入.结论：(1)K5,K3,3都不是平面图（待证）(2)设GG，若G为平面图，则G也是平面图（定理17.1）(3)设GG，若G为非平面图，则G也是非平面图（定理17.2），由此可知，Kn(n6)，K3,n(n4)都是非平面图。(4)平行边与环不影响平面性.v1v5v4v2v3351624afbecdSchoolofInformationScienceandEngineering平面图(平面嵌入)的面与次数定义：1.G的面——G的平面嵌入的边将平面化分成的

3、若干区域2.无限面或外部面——（可用R0表示）——面积无限的面3.有限面或内部面（可用R1,R2,…,Rk等表示）——面积有限的面4.面Ri的边界——包围Ri的回路组5.面Ri的次数——Ri边界的长度，用deg(Ri)表示ADFBCr1r2r3r0r1:边界:ABCDFDAdeg(r1)=6r2:边界:ABCAdeg(r2)=3r3:边界:ACDAdeg(r3)=3r0:边界:ADAdeg(r0)=2SchoolofInformationScienceandEngineering定理17.4平面图各面次数之和等于边数的两倍。几点说

4、明若平面图G有k个面，可笼统地用R1,R2,…,Rk表示，不需要指出外部面.定义中回路组是指：边界可能是初级回路(圈)，可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之并.平面图有4个面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.请写各面的边界。SchoolofInformationScienceandEngineering极大平面图定义：若在简单平面图G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称G为极大平面图.注意：若简单平面图G中已无不相邻顶点，G显然是极大

5、平面图，如K1(平凡图),K2,K3,K4都是极大平面图。极大平面图的主要性质定理17.5极大平面图是连通的。证明思路：否则，加新边不破坏平面性定理17.6n（n3）阶极大平面图中不可能有割点和桥。证明思路：由定理17.5及n3可知，G中若有桥，则一定有割点，因而只需证无割点即可.方法还是反证法。SchoolofInformationScienceandEngineering证明：(1)由于n3,又G必为简单平面图可知，G每个面的次数均3.(2)因为G为平面图，又为极大平面图.可证G不可能存在次数>3的面.就给出的图讨论即可

6、.极大平面图的性质定理17.7设G为n（n3）阶极大平面图，则G的每个面的次数均为3。SchoolofInformationScienceandEngineering定理17.7中的条件也是极大平面图的充分条件。定理17.7设G为n(n3)阶平面图，且每个面的次数均为3，则G为极大平面图.定理的应用上图中，只有(3)为极大平面图(1)(2)(3)SchoolofInformationScienceandEngineering极小非平面图定义：若在非平面图G中任意删除一条边，所得图G为平面图，则称G为极小非平面图.由定义不难看

7、出：(1)K5,K3,3都是极小非平面图(2)极小非平面图必为简单图图中所示各图都是极小非平面图.SchoolofInformationScienceandEngineering定理17.9（欧拉公式的推广）设G是具有k（k2）个连通分支的平面图，则nm+r=k+1证明中对各连通分支用欧拉公式，并注意即可.17.2欧拉公式定理17.8设G为n阶m条边r个面的连通平面图，则nm+r=2（此公式称为欧拉公式）证对边数m做归纳法m=0，G为平凡图，结论为真.设m=k（k1）结论为真，m=k+1时分情况讨论.(1)G中无圈，则G为树

8、，删除一片树叶，用归纳假设.(2)否则，在某一个圈上删除一条边，进行讨论.SchoolofInformationScienceandEngineering解得也可得：定理17.11在具有k（k2）个连通分支的平面图中，与欧拉公式有关