图论课件-平面图的判定与涉及平面性的不变量.ppt

1 图论及其应用 应用数学学院 2 本次课主要内容 一 平面图的判定 二 涉及平面性的不变量 平面图的判定与涉及平面性的不变量 3 这次课要解决的问题是 给出判定一个图是否是可平面图的充分必要条件 一 平面图的判定 在本章第一次课中 我们已经明确 对于3阶以上的具有m条边的图G来说 如果G满足如下条件之一 1 m 3n 6 2 K5是G的一个子图 3 K3 3是G的一个子图 那么 G是非可平面图 但上面的条件仅为G是非可平面图的充分条件 最早给出图的平面性判定充要条件的是波兰数学家库拉托斯基 30年代给出 后来 美国数学家惠特尼 加拿大数学家托特 我国数学家吴文俊等都给出了不同的充要条件 4 所以 我们称K5与K3 3为库拉托斯基图 我们主要介绍波兰数学家库拉托斯基的结果 库拉托斯基定理主要基于K5和K3 3是非可平面图这一事实而提出的平面性判定方法 一个自然的猜测是 G是可平面图的充分必要条件是G不含子图K5和K3 3 上面命题必要性显然成立 但充分性能成立吗 十分遗憾 下面例子给出了回答 NO 下面的图G是一个点数为5 边数为9的极大平面图 考虑F G K3 5 注 F由G的3个拷贝组成 分别是G1 G2 G3 三个拷贝中的边没有画出 图中虚线不是对应的Gi中边 6 可以证明 F中不含K5和K3 3 且F是非可平面图 尽管我们的直觉猜测错了 但库拉托斯基还是基于K5与K3 3得到了图的平面性判据 1 相关概念 定义1在图G的边上插入一个2度顶点 使一条边分成两条边 称将图在2度顶点内扩充 去掉一个图的2度顶点 使关联它们的两条边合并成一条边 称将图G在2度顶点内收缩 7 定义2两个图G1与G2说是同胚的 如果 或者通过反复在2度顶点内扩充和收缩后能够变成一对同构的图 上面的G1 G2 G3是同胚的 注 图的平面性在同胚意义下不变 8 定理1 库拉托斯基定理 图G是可平面的 当且仅当它不含K5或K3 3同胚的子图 例1求证 下面两图均是非平面图 证明 对于G1来说 按G1在2度顶点内收缩后 可得到K5 所以 由库拉托斯基定理知G1是非可平面图 9 对于G2来说 先取如下子图 对上面子图 按2度顶点收缩得与之同胚子图K3 3 所以 G2是非可平面图 10 例2确定下图是否是可平面图 分析 我们根据图的结构形式 怀疑该图是非可平面图 但我们必须找到证据 当然我们可能考虑是否m 3n 6 遗憾的是该图不满足这个不等式 11 所以 我们要在该图中寻找一个与k5或K3 3同胚的子图 由于该图的最大度为4的顶点才4个 所以 不存在与K5同胚的子图 因此 只有寻找与K3 3同胚的子图 解 取G中红色边的一个导出子图 也就是得到G的如下形式的一个子图 12 上图显然和K3 3同胚 由库拉托斯基定理知 G是非可平面的 注 1 库拉托斯基定理可以等价叙述为 库拉托斯基定理 图G是非可平面的 当且仅当它含有K5或K3 3同胚的子图 13 2 库拉托斯基 1896 1980 波兰数学家 1913年开始在苏格兰格拉斯哥大学学习工程学 1915年回到波兰发沙大学转学数学 主攻拓扑学 1921年获博士学位 1930年在利沃夫大学作数学教授期间 发现并证明了图论中的库拉托斯基定理 1939年后到发沙大学做数学教授 他的一生主要研究拓扑学与集合论 库拉托斯基定理 图G是非可平面的 当且仅当它含有K5或K3 3同胚的子图 定义2给定图G 去掉G中的环 用单边代替平行边而得到的图称为G的基础简单图 14 定理2 1 图G是可平面的 当且仅当它的基础简单图是可平面的 2 图G是可平面图当且仅当G的每个块是可平面图 证明 1 由平面图的定义 该命题显然成立 2 必要性显然 下面证明充分性 不失一般性 假设G连通 我们对G的块数n作数学归纳证明 当n 1时 由条件 结论显然成立 设当n k时 若G的每个块是可平面的 有G是可平面的 下面考虑n k时的情形 15 设点v是G的割点 则按照v G可以分成两个边不重子图G1与G2 即G G1 G2 且G1 G2 v 按归纳假设 G1与G2都是可平面图 取G1与G2的平面嵌入满足点v都在外部面边界上 则把它们在点v处对接后 将得到G的平面嵌入 即证G是可平面图 关于图的可平面性刻画 数学家瓦格纳 Wangner 在1937年得到了一个定理 16 定义3设uv是简单图G的一条边 去掉该边 重合其端点 在删去由此产生的环和平行边 这一过程称为图G的初等收缩或图的边收缩运算 称G可收缩到H 是指对G通过一系列边收缩后可得到图H 定理2 瓦格纳定理 简单图G是可平面图当且仅当它不含有可收缩到K5或K3 3的子图 注 这是瓦格纳1937年在科隆大学博士毕业当年提出并证明过的一个定理 17 例3求证彼得森图是非可平面图 证明 很明显 彼得森图通过一些列边收缩运算后得到K5 由瓦格纳定理得证 定理3至少有9个顶点的简单可平面图的补图是不可平面的 而9是这个数目中的最小的一个 18 注 该定理是由数学家巴特尔 哈拉里和科达马首先得到 然后由托特 1963 给出了一个不太笨拙的证明 他采用枚举法进行验证 还不知道有简洁证明 也没有得到推理方法证明 例4找出一个8个顶点的可平面图 使其补图也是可平面的 19 例5设G是一个简单图 若顶点数n 11 则G与G的补图中 至少有一个是不可平面图 要求用推理方法 证明 设G是一个n阶可平面图 则 所以 考虑 20 令 则 所以 当n 6 5时 f n 单调上升 而当n 11时 所以 当n 11时 有 即证明了简单可平面图G的补图是非可平面图 21 例6设Gi是一个有ni个点 mi条边的图 i 1 2 证明 若G1与G2同胚 则 证明 设G1经过p1次2度顶点扩充 p2次2度顶点收缩得到H1 G2经过q1次2度顶点扩充 q2次2度顶点收缩得到H2 使得 又设H1与H2的顶点数分别为n1 和n2 边数分别为m1 与m2 那么 22 所以 而由得 所以 二 涉及平面性的不变量 我们将要讨论的问题是 如何刻画一个非可平面图与平面图之间的差距 只作简单介绍 1 图的亏格 23 环柄 边交叉处建立的 立交桥 通过它 让一条边经过 桥下 而另一条边经过 桥上 从而把两条边在交叉处分开 定义4若通过加上k个环柄可将图G嵌入到球面 则k的最小数目 称为G的亏格 记为 G 24 定理4对于一个亏格为 有n个顶点 m条边和 个面的多面体 有 因多面体对应一个连通图 所以上面恒等式称为一般连通图的欧拉公式 推论 设G是一个有n个点m条边 亏格为 的连通图 则 25 证明 3 因为G的每个面是三角形 所以每条边是两个面的公共边 得 3 2m 于是由定理4得 对于完全图的亏格曾经是一个长期的 有趣的 困难的和成功的努力 1890年希伍德提出如下猜想 26 希伍德由推论 1 证明了 同时希伍德也证明了 K7 1 1891年 赫夫曼对n 8 12进行了证明 1952年 林格尔对n 13进行了证明 记阶数n 12s r 1954年 林格尔对r 5进行了证明 1961 65年 林格尔对r 7 10 3进行了证明 27 1961 65年 杨斯 台里等对r 4 0 1 9 6进行了证明 1967 68年 林格尔 杨斯对r 2 8 11进行了证明 1968年后 法国蒙特派列尔大学文学教授杰恩对n 18 20 23进行了证明 对于完全双图 结果由林格尔独立得到 定理5设m n是正整数 则 28 2 图的厚度 定义5若图G的k个可平面子图的并等于G 则称k的最小值为G的厚度 记为 定理6 1 若 则 2 3 对任意的单图G n m 有 3 图的糙度 29 定义6图G中边不相交的不可平面子图的最多数目称为G的糙度 记为 定理7完全图的糙度由下式给出 3n 1 19并且3n 1 9r 7 其中r为面数 30 定义8将G画在平面上时相交的边对的最少数目称为G的叉数 记为 定理9 31 作业 P143 146习题5 6 7 8 11 12 32 ThankYou