平面图和五色定理.ppt

6.2 平面图和五色定理 a b c d f g h x k y a 1 b 1 c 1 2 d f 3 1 h x 3 1 k g 2 2 y 6.2 平面图和五色定理 定义 6.2.1 如果 能与这样的一个图 同构，其中 的顶点在同一个平面上，而 的边只能在端点处相交，就称 为平面图，而称 为 的一个平面嵌入， 或称 为 在平面上的实现。 如图 和 就不具有这样的性质。 一、平面图的概念及性质 定义 6.2.2 平面图 的边把整个平面分割成若干各连通的区域，这些区域的 闭包称为平面图 的面（包括外部无限区域，称为外部面）。分别用 和 表示 的面的集合和面的个数。 定义6.2.3 用 表示平面图 中围成面 的周界。用 （或 ）表 示围成面 的周界的边数，称为 的度。 推论 6.2.2 在任何平面图中，度为奇数的面的个数为偶数。 定理6.2.1 如果G 是平面图，则 问题：一个平面图的面数是否会随着这个平 面图的不同嵌入而改变？ 定理6.2.3（Euler公式） 设 是一个有 个顶点、 条边和 个面的连通平面图，则 证明：对面数 进行归纳证明。由于 是连通的平面图， 所以当 时， 是树，因此 。故 假设对于一切面数少于 的所有连通平面图， Euler公式成立。现假设 是一个有 个顶点、 条边 和 个面的连通图。由于 ， 至少有一个回路，取 这回路中的一条边 ，则 仍是连通平面图，有 个顶点， 条边和 个面，根据归纳假设。 即 证毕。 问题：对于非连通的平面图，其相应的点数 、 边数和面数有什么关系？ 推论6.2.4 若 是阶为 的平面图， 的最短回路的长度为 ，则 证明： 现在对 的每个面 ，由于假设 ，因此 由定理6.2.1知 不妨设该平面图是连通的平面图，则根据Euler公式，有 因此，有 推论6.2.4的一般情况： 对简单平面图 ，有 由以上结论，容易验证 和 不是平面图 推论6.2.5 设 是简单平面图，则 。 证明：反证 法。假设 是一个平面图，但 ，则 而对于简单平面图，有 矛盾。故对每一个简单平面图 ， 有 。 例：平面上有 个点，其中任意两个点之间 的距离至少是1。证明在这 个点中，距离 恰好为1的点对数至多是 。 二、平面图与正多面体 凸多面体在平面上的投影是一个连通的平面 图，因此Euler公式也适用于凸多面体。为此我们 可以用Euler公式讨论正多面体。 正4-面体 正6面体 正8-面体 抽象化 抽象化 正12-面体 抽象化 正20-面体 定理6.2.6 存在且只存在5种正多面体：正四面体、 正方体、正八面体、正十 二面体和正二十 面体。 证明：首先一个正多面体在平面上的投影所得平面图是2连通的正则图，而 且每个面的度相同，即为 。 设平面图 是 正则、每个面的度为 ，则 ， ， 并且 即 满足上式且至少为3的正整数 和 只有五对。（见下表） 相应的正多面体 33464 正4-面体 348126 正6-体 35203012 正12-面体 436128 正8-面体 53123020 正20-面体 正4-面体 正8-面体 正6-面体 正12-面体 正20-面体 平面上看： 三、平面图的判别 我们可以利用 和 的非平面性来 给出两个有关平面图的判别定理 找出一个图是平面图的充分必要条件的研究持续了几十年，直到1930年 波兰数学家库拉托夫斯基（Kuratowski）给出了平面图的一个非常简洁的 特征。 给定图的一个剖分是对图 实现有限次过程而得到的另一个图 : 即 删去 的一条边 后，添一个新的顶点 及两条新的边 、 。也 就是说在 的边上插入有限个顶点便可得到 的一个剖分 。 定理6.2.7 （ Kuratowski 定理） 图 是平面图当且仅当它的任何子图都不是 或 的剖分 。 定理6.2.8（Wangner定理） 一个图为平面图当且仅当它的任何子图都不能收缩 为 或 。 可得Petersen图不是平面图。 收缩边 四、五色定理的证明 我们将利用推论6.2.5的结论来证明每一 个平面图的点色数不超过5 定理6.2.9 每一个平面图的色数不超过5。 证明： 对平面图的顶点数 进行归纳。 当 时，结论显然成立。不妨假设所给的平面图连通。 归纳假设对顶点数为 的平面图结论成立，下设 是 顶点数为 的简单图。设法证明 。 反证法：设 。 首先由推论6.2.5知 ，设 ， 。 作 。此时 是阶为 的平面图，由归纳假设得 。如果 ，只要将五种颜色分配给 ，即可得 ，矛盾，故 。设已给 的顶点染五种颜色 ，使 中相邻顶点染以不同的颜色。 如果 ，可得矛盾。 。设 的五个邻点依 次为 。分两种情况： Case1 五个点所染颜色有相同的，只要将在 没出现的颜色分配给 ，就有 。矛盾。 Case2 五个点染得颜色各不相同。不妨不妨设 分 别染 。让 为 的色划分。 现考虑 的子图 。如果在 中 与 不在 同一个连通分支中，则可以把 中含 的连通分支内的 与 两种颜色互换，而 中其余颜色不变，就得到 的一个5染色。 此时 与 同染 这种颜色，与假设矛盾。所以 与 在 同一连通分支中，于是在 中存在一条 到 的路 同样考虑子图 ，在 中存在 到 的路 。 由路的构造可知， 与 不相交（即无公共顶点） 。 但在 中，回路 将 与 分隔在两个不 同的区域内，而 是平面图，所以路 必与 相交于某个顶 点。由于 ，因此 与 相交与某 个顶点，矛盾。 证毕。 一个非平面图G是不能嵌入在一个平面上的，但它 可以分解为若干个平面图的并图，即存在若干平面图 使 ，不妨设这些平面图 是 G 的 生成子图，我们将这种平面图分解的最小个数称为 G 的 厚度，记为 ，于是 当且仅当 是平面图。 五、非平面图的分解问题 定理6.2.10 设 是具有围长 的一个非平面图，则 其中 表示不小于 的最小整数 。 证明：设非平面图 的厚度为 ，则存在平 面图 ，使 这里 是 的生成子图。则每个生成子图 是围长至少为 的平面图，由推论6.2.4， 有 故有 例1 对于那些n，存在n条棱的凸多面体？（1968年波兰数学 奥林匹克试题） 解：以多面体的顶点为图的顶点，以多面体的棱为图的边 ，组成一个平面图G,则 ，每个面的度至 少是3。由Euler公式， ，即没有棱数小于6的凸多 面体。 四面体是棱数为6的凸多面体。 若有7条棱的凸多面体，则存在满足上述条件， 的平面图，由Euler公式得： 但每个面的度数至