《一些特殊平面图和平面图的对偶图.ppt》由会员分享，可在线阅读，更多相关《一些特殊平面图和平面图的对偶图.ppt（13页珍藏版）》请在三一文库上搜索。
6.2 一些特殊平面图和平面图的对偶图,一些特殊的平面图,极大平面图,极小不可平面图,外可平面图,从概念所想到的。,1) 极大平面图,引理： 设G是极大平面图，则G必连通，若G的点数大于等于3，则G无割边。,定理： 设G是至少有3个顶点的平面图，则G是极大平面图的充要条件为G中各面的次数为3且为简单图。,定理： 设G是至少有3个顶点的极大平面图，则：,定理： 设G是至少有4个顶点的极大平面图，则,2) 极小不可平面图,极小不可平面图一定是简单图,c,a,e,f,d,b,极小不可平面图与极大平面图之间的关系,极小不可平面图任意去掉一边后为极大平面图,极大平面图任意增加一边后为极小不可平面图吗？,3) 外可平面图,K4不是外可平面图,定理： 设G是极大外平面图（n2），所有顶点在外部面上，则G有n2个内部面。,定理： 设G是所有顶点在外部面的平面图(n2)，则G是极大外平面图的充要条件是它的外部面的边界是圈且内部面是三角形。,极大外可平面图,例题1： 画出6个点的极大外平面图。,例题2： 画出7个点的极大外平面图。,至少有7个点的外可平面图的补图不是外可平面图。,对偶图,定理： 平面图的对偶是平面图,定理： 平面图的对偶图是连通图,例题：是否存在平面图G，其有5个面，且任意两面间至少有一公共边。,