平面图和五色定理.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的正整数 和 只有五对。（见下表）,正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公式得：,但每个面的度数至少为3，故,即,但 为整数，所以。同样，于是,矛盾，因此，7条棱的凸多面体不存在。,现对，以k边形为底的棱锥即为2k条棱的凸多面体。若把底为k-1边形的棱锥中，底角处的一个三面角“锯掉一个尖儿”，得到的是一个2k+1条棱的凸多面体，总之，当 时，才有n条棱的凸多面体。,
