《图论及其应用》课程教学课件（PPT讲稿）第六章 平面图 6-3 平面图的判定

本次课主要内容 平面图的判定与涉及平面性的不变量 (一)、平面图的判定 (二)、涉及平面性的不变量

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 本次课主要内容 (一)、平面图的判定 (二)、涉及平面性的不变量 平面图的判定与涉及平面性的不变量

(一)、平面图的判定 在本章第一次课中，我们已经明确：对于3阶以上的 具有m条边的单图G来说，如果G满足如下条件之一： (1)m>3n-6;(2)K是G的一个子图；(3)K33是G的一个 子图，那么，G是非可平面图。 但上面的条件仅为G是非可平面图的充分条件。 这次课要解决的问题是：给出判定一个图是否是可 平面图的充分必要条件。 最早给出图的平面性判定充要条件的是波兰数学家 库拉托斯基30年代给出)。后来，美国数学家惠特尼， 加拿大数学家托特，我国数学家吴文俊等都给出了不同 的充要条件

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 这次课要解决的问题是：给出判定一个图是否是可 平面图的充分必要条件。 (一)、平面图的判定 在本章第一次课中，我们已经明确：对于3阶以上的 具有m条边的单图G来说，如果G满足如下条件之一： (1)m>3n-6; (2) K5是G的一个子图；(3) K3,3是G的一个 子图，那么，G是非可平面图。 但上面的条件仅为G是非可平面图的充分条件。 最早给出图的平面性判定充要条件的是波兰数学家 库拉托斯基(30年代给出)。后来，美国数学家惠特尼， 加拿大数学家托特，我国数学家吴文俊等都给出了不同 的充要条件

我们主要介绍波兰数学家库拉托斯基的结果。 库拉托斯基定理主要基于K和K33是非可平面图这一 事实而提出的平面性判定方法。 所以，我们称K与K33为库拉托斯基图。 一个自然的猜测是：G是可平面图的充分必要条件是 G不含子图K和K33 上面命题必要性显然成立！但充分性能成立吗？ 十分遗憾！下面例子给出了回答：NO! 下面的图G是一个点数为5，边数为9的极大平面图。 考虑F=GXK3

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 所以，我们称K5与K3,3为库拉托斯基图。 我们主要介绍波兰数学家库拉托斯基的结果。 库拉托斯基定理主要基于K5和K3,3是非可平面图这一 事实而提出的平面性判定方法。 一个自然的猜测是：G是可平面图的充分必要条件是 G不含子图K5和K3,3。 上面命题必要性显然成立！但充分性能成立吗？ 十分遗憾！下面例子给出了回答：NO! 下面的图G是一个点数为5，边数为9的极大平面图。 考虑 F=G×K3

Ws 7=G×K3 注：F由G的3个拷贝组成，分别是G,G2,G3。三个拷 贝中的边没有画出。图中虚线不是对应的G中边

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 注：F由G的3个拷贝组成，分别是G1 ,G2 ,G3。三个拷 贝中的边没有画出。图中虚线不是对应的Gi中边。 G u5 u4 u3 u2 u1 v5 v4 v3 v2 v1 w5 w4 w3 w2 w1 F G K =  3 G3 G1 G2

可以证明：F中不含K和K33, 且F是非可平面图。 尽管我们的直觉猜测错了，但库拉托斯基还是基于 K,与K33得到了图的平面性判据。 1、相关概念 定义1在图G的边上插入一个2度顶点，使一条边分 成两条边，称将图在2度顶点内扩充；去掉一个图的2度 顶点，使关联它们的两条边合并成一条边，称将图G在 2度顶点内收缩。 在2度顶点内收缩 在2度顶点内扩充

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 可以证明：F中不含K5和K3,3，且F是非可平面图。 尽管我们的直觉猜测错了，但库拉托斯基还是基于 K5与K3,3得到了图的平面性判据。 1、相关概念 定义1 在图G的边上插入一个2度顶点，使一条边分 成两条边，称将图在2度顶点内扩充；去掉一个图的2度 顶点，使关联它们的两条边合并成一条边，称将图G在 2度顶点内收缩。 在2度顶点内收缩 在2度顶点内扩充

定义2两个图G,与G2说是同胚的，如果GG，或 者通过反复在2度顶点内扩充和收缩后能够变成一对同 构的图。 上面的G,G2,G3是同胚图。 注：显然，图的平面性在同胚意义下不变

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 定义2 两个图G1与G2说是同胚的，如果 ，或 者通过反复在2度顶点内扩充和收缩后能够变成一对同 构的图。 G G 1 2  G1 G2 G3 上面的G1 , G2 , G3 是同胚图。 注：显然，图的平面性在同胚意义下不变

定理1（库拉托斯基定理）图G是可平面的，当且仅当 它不含K或K33同胚的子图。 例1求证：下面两图均是非平面图。 图G1 图G2 证明：对于G来说，按G在2度顶点内收缩后，可得 到K。所以，由库拉托斯基定理知G,是非可平面图

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 定理1 (库拉托斯基定理) 图G是可平面的，当且仅当 它不含K5或K3,3同胚的子图。 例1 求证：下面两图均是非平面图。 图 G1 图 G2 证明：对于G1来说，按G1在2度顶点内收缩后，可得 到K5。所以，由库拉托斯基定理知G1是非可平面图

对于G,来说，先取如下子图 图G2 G2的一个子图 对上面子图，按2度顶点收缩得与之同胚子图K,3: K33 所以，G2是非可平面图

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 对于G2来说，先取如下子图 G2的一个子图 对上面子图，按2度顶点收缩得与之同胚子图K3,3: K3,3 所以，G2是非可平面图。 图 G2

例2确定下图是否是可平面图。 W2 分析：我们根据图的结构形式，怀疑该图是非可平 面图。但我们必须找到证据！ 当然我们可能考虑是否m>3n-6。遗憾的是该图不满 足这个不等式！

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 例2 确定下图是否是可平面图。 u1 u2 v1 v2 y1 y2 x1 x2 w1 w2 分析：我们根据图的结构形式，怀疑该图是非可平 面图。但我们必须找到证据！ 当然我们可能考虑是否m>3n-6。遗憾的是该图不满 足这个不等式！

所以，我们要在该图中寻找一个与k或K33同胚的子 图！ 由于该图的最大度为4的顶点才4个，所以，不存在与 K同胚的子图。因此，只有寻找与K33同胚的子图！ 解：取G中红色边的一个导出子图： W2 也就是得到G的如下形式的一个子图： 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 u1 u2 v1 v2 y1 y2 x1 x2 w1 w2 所以，我们要在该图中寻找一个与k5或K3,3同胚的子 图！ 由于该图的最大度为4的顶点才4个，所以，不存在与 K5同胚的子图。因此，只有寻找与K3,3同胚的子图！ 解：取G中红色边的一个导出子图： 也就是得到G的如下形式的一个子图：