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

该【特殊平面图与平面图的对偶 】是由【tieruogong】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【特殊平面图与平面图的对偶 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
Email:
任课教师：杨春
图论及其应用
数学科学学院
本次课主要内容
特殊平面图与平面图的对偶图
一些特殊平面图
平面图的对偶图
极大平面图及其性质
极大外平面图及其性质
2
一些特殊平面图
1、极大平面图及其性质
对于一个简单平面图来说，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图。这样，就启发我们研究平面图的极图问题。
极大可平面图的平面嵌入称为极大平面图。
定义1 设G是简单可平面图，如果G是Ki (1≦i≦4),或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称G是极大可平面图。
3
若不然，G至少两个连通分支。设G1与G2是G的任意两个连通分支。
先证明G连通。
极大平面图
03
引理 设G是极大平面图，则G必然连通；若G的阶数大于等于3，则G无割边。
非极大平面图
02
注：只有在单图前提下才能定义极大平面图。
极大平面图
01
4
把G1画在G2的外部面上，并在G1,*。但这与G是极大平面图相矛盾。
(2) 当G的阶数n≥3时，我们证明G中没有割边。
若不然，设G中有割边e = uv，则G-uv不连通，恰有两个连通分支G1与G2。
u
v
e
G1
G2
G
f
5
设u在G1中，而v在G2中。由于n≥3, 所以，至少有一个分支包含两个以上的顶点。设G2至少含有两个顶点。又设G1中含有点u的面是 f , 将G2画在 f 内。
G2
u
由于G是单图，所以，在G2的外部面上存在不等于点v的点t。现在，在G中连接点u与t得新平面图G*,它比G多一条边。这与G的极大性相矛盾。
e
G
v
G1
6
下面证明极大平面图的一个重要性质。
1
定理1 设G是至少有3个顶点的平面图，则G是极大平面图，当且仅当G的每个面的次数是3且为单图。
2
注：该定理可以简单记为是“极大平面图的三角形特征”，即每个面的边界是三角形。
3
证明：“必要性”
4
由引理知，G是单图、G无割边。于是G的每个面的次数至少是3。
5
假设G中某个面 f 的次数大于等于4。记 f 的边界是v1v2v3v4…vk。如下图所示:
6
7
如果v1与v3不邻接，则连接v1v3，没有破坏G的平面性，这与G是极大平面图矛盾。所以v1v3必须邻接，但必须在 f 外连线；同理v2与v4也必须在 f 外连线。但边v1v3与边v2v4在 f 外交叉，与G是平面图矛盾！
所以，G的每个面次数一定是3.
定理的充分性是显然的。
v1
v2
v3
v4
v5
vk
f
8
所以得：
证明：因为G是极大平面图，所以，：
推论：设G是n个点，m条边和ф个面的极大平面图，且n≥：(1) m=3n-6; (2) ф=2n-4.
由欧拉公式：
9
所以得：
又
所以：
注：顶点数相同的极大平面图并不唯一。例如：
正20面体
非正20面体
10