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