ppt平面图的判定与涉及平面性的不变量.pptVIP

* * Email: yc517922@126.com 图论及其应用 任课教师：杨春 数学科学学院 本次课主要内容 (一)、平面图的判定 (二)、涉及平面性的不变量 平面图的判定与涉及平面性的不变量 这次课要解决的问题是：给出判定一个图是否是可平面图的充分必要条件。 (一)、平面图的判定 在本章第一次课中，我们已经明确：对于3阶以上的具有m条边的单图G来说，如果G满足如下条件之一： (1)m3n-6; (2) K5是G的一个子图；(3) K3,3是G的一个子图，那么，G是非可平面图。 但上面的条件仅为G是非可平面图的充分条件。 最早给出图的平面性判定充要条件的是波兰数学家库拉托斯基(30年代给出)。后来，美国数学家惠特尼，加拿大数学家托特，我国数学家吴文俊等都给出了不同的充要条件。 1、相关概念 定义1 在图G的边上插入一个2度顶点，使一条边分成两条边，称将图在2度顶点内扩充；去掉一个图的2度顶点，使关联它们的两条边合并成一条边，称将图G在2度顶点内收缩。 在2度顶点内收缩 在2度顶点内扩充 我们主要介绍波兰数学家库拉托斯基的结果。 定义2 两个图G1与G2说是同胚的，如果 ，或者通过反复在2度顶点内扩充和收缩后能够变成一对同构的图。 G3 G2 G1 上面的G1, G2, G3 是同胚图。 注：显然，图的平面性在同胚意义下不变。 定理1 (库拉托斯基定理) 图G是可平面的，当且仅当它不含K5和K3,3同胚的子图。 例1 求证：下面两图均是非平面图。 图 G1 图 G2 证明：对于G1来说，按G1在2度顶点内收缩后，可得到K5。所以，由库拉托斯基定理知G1是非可平面图。 对于G2来说，先取如下子图 G2的一个子图 对上面子图，按2度顶点收缩得与之同胚子图K3,3: K3,3 所以，G2是非可平面图。 图 G2 例2 确定下图是否是可平面图。 u1 u2 v1 v2 y1 y2 x1 x2 w1 w2 分析：我们根据图的结构形式，怀疑该图是非可平面图。但我们必须找到证据！ 当然我们可能考虑是否m3n-6。遗憾的是该图不满足这个不等式！ u1 u2 v1 v2 y1 y2 x1 x2 w1 w2 所以，我们要在该图中寻找一个与k5或K3,3同胚的子图！ 由于该图的最大度为4的顶点才4个，所以，不存在与K5同胚的子图。因此，只有寻找与K3,3同胚的子图！ 解：取G中红色边的一个导出子图： 也就是得到G的如下形式的一个子图： 上图显然和K3,3同胚。由库拉托斯基定理知，G是非可平面的。 u1 u2 v1 v2 y1 y2 x1 x2 w1 w2 注： (1) 库拉托斯基定理可以等价叙述为： 库拉托斯基定理：图G是非可平面的，当且仅当它含有K5或K3,3同胚的子图。 (2) 库拉托斯基 (1896---1980) 波兰数学家。1913年开始在苏格兰格拉斯哥大学学习工程学，1915年回到波兰发沙大学转学数学，主攻拓扑学。1921年获博士学位。1930年在利沃夫大学作数学教授期间，发现并证明了图论中的库拉托斯基定理。1939年后到发沙大学做数学教授。他的一生主要研究拓扑学与集合论。 定义2 给定图G, 去掉G中的环，用单边代替平行边而得到的图称为G的基础简单图。 库拉托斯基于1954年率波兰数学家代表团对我国进行了学术访问，还送给了华罗庚一些波兰数学家写的数论函数论文。 定理2 (1) 图G是可平面的，当且仅当它的基础简单图是可平面的； (2) 图G是可平面图当且仅当G的每个块是可平面图。 证明： (1) 由平面图的定义，该命题显然成立。 (2) 必要性显然。下面证明充分性。 不失一般性，假设G连通。我们对G的块数n作数学归纳证明。