特殊平面图与平面图的对偶

《特殊平面图与平面图的对偶》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Email:yc517922@126.com图论及其应用任课教师：杨春数学科学学院1本次课主要内容(一)、一些特殊平面图(二)、平面图的对偶图特殊平面图与平面图的对偶图1、极大平面图及其性质2、极大外平面图及其性质21、极大平面图及其性质(一)、一些特殊平面图对于一个简单平面图来说，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图。这样，就启发我们研究平面图的极图问题。定义1设G是简单可平面图，如果G是Ki(1≦i≦4),或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图

2、，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图。3注：只有在单图前提下才能定义极大平面图。引理设G是极大平面图，则G必然连通；若G的阶数大于等于3，则G无割边。极大平面图非极大平面图极大平面图(1)先证明G连通。若不然，G至少两个连通分支。设G1与G2是G的任意两个连通分支。4把G1画在G2的外部面上，并在G1,G2上分别取一点u与v.连接u与v得到一个新平面图G*。但这与G是极大平面图相矛盾。(2)当G的阶数n≥3时，我们证明G中没有割边。若不然，设G中有割边e=uv，则G-uv不

3、连通，恰有两个连通分支G1与G2。uveG1G2Gf5设u在G1中，而v在G2中。由于n≥3,所以，至少有一个分支包含两个以上的顶点。设G2至少含有两个顶点。又设G1中含有点u的面是f,将G2画在f内。由于G是单图，所以，在G2的外部面上存在不等于点v的点t。现在，在G中连接点u与t得新平面图G*,它比G多一条边。这与G的极大性相矛盾。vueG1G2G6下面证明极大平面图的一个重要性质。定理1设G是至少有3个顶点的平面图，则G是极大平面图，当且仅当G的每个面的次数是3且为单图。注：该定理可以简单记

4、为是“极大平面图的三角形特征”，即每个面的边界是三角形。证明：“必要性”由引理知，G是单图、G无割边。于是G的每个面的次数至少是3。假设G中某个面f的次数大于等于4。记f的边界是v1v2v3v4…vk。如下图所示:7如果v1与v3不邻接，则连接v1v3，没有破坏G的平面性，这与G是极大平面图矛盾。所以v1v3必须邻接，但必须在f外连线；同理v2与v4也必须在f外连线。但边v1v3与边v2v4在f外交叉，与G是平面图矛盾！所以，G的每个面次数一定是3.定理的充分性是显然的。v1v2v3v4v5vkf

5、8推论：设G是n个点，m条边和ф个面的极大平面图，且n≥3.则：(1)m=3n-6;(2)ф=2n-4.证明：因为G是极大平面图，所以，每个面的次数为3.由次数公式：由欧拉公式：所以得：9所以得：又所以：注：顶点数相同的极大平面图并不唯一。例如：正20面体非正20面体10还在研究中的问题是：顶点数相同的极大平面图的个数和结构问题。2、极大外平面图及其性质定义2若一个可平面图G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图。外可平面图

6、外平面图1f外平面图2f11注：对外可平面图G来说，一定存在一种外平面嵌入，使得G的顶点均在外部面的边界上。这由球极投影法可以说明。下面研究极大外平面图的性质。定义3设G是一个简单外可平面图，若在G中任意不邻接顶点间添上一条边后，G成为非外可平面图，则称G是极大外可平面图。极大外可平面图的外平面嵌入，称为极大外平面图。极大外平面图12定理2设G是一个有n(n≥3)个点，且所有点均在外部面上的极大外平面图，则G有n-2个内部面。证明：对G的阶数作数学归纳。当n=3时，G是三角形，显然只有一个内部面；

7、设当n=k时，结论成立。当n=k+1时，首先，注意到G必有一个2度顶点u在G的外部面上。(这可以由上面引理得到)考虑G1=G-v。由归纳假设，G1有k-2个内部面。这样G有k-1个内部面。于是定理2得证。引理设G是一个连通简单外可平面图，则在G中有一个度数至多是2的顶点。13定理3设G是一个有n(n≥3)个点，且所有点均在外部面上的外平面图，则G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形。注：这是极大外平面图的典型特征。证明：先证明必要性。(1)证明G的边界是圈。容易知道：G的外部

8、面边界一定为闭迹，否则，G不能为极大外平面图。设W=v1v2…vnv1是G的外部面边界。若W不是圈，则存在i与j,使vi=vj=v.此时，G可以示意如下：Wvi-1v1vnv2vi+1vj-1vj+1v14vi-1与vi+1不能邻接。否则W不能构成G的外部面边界。这样，我们连接vi-1与vi+1：vi-1v1vnv2vi+1vj-1vj+1v得到一个新外平面图。这与G的极大性矛盾。(2)证明G的内部面是三角形。首先，注意到，G的内部面必须是圈。因为，G的外部面的边界是生成圈，所以G