平面图和五色定理

1、16.2 平面图和五色定理平面图和五色定理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 33,3K5K6.2 平面图和五色定理平面图和五色定理定义定义 6.2.1 如果如果 能与这样的一个图能与这样的一个图 同构，其中同构，其中 的顶点在同一个平面上，而的顶点在同一个平面上，而 的边只能在端点处相交，就称的边只能在端点处相交，就称 为为平面图平面图，而称，而称 为为 的一个的一个平面嵌入平面嵌入，或称或称 为为 在平面上的实现。在平面上的实现。GGGGGGGGG如图如图 和和 就不具有这样的性质。就不具有这样的性质。

2、5K3,3K一、平面图的概念及性质一、平面图的概念及性质 4定义定义 6.2.2 平面图平面图 的边把整个平面分割成若干各连通的区域，这些区域的的边把整个平面分割成若干各连通的区域，这些区域的闭包称为平面图闭包称为平面图 的的面面（包括外部无限区域，称为外部面）。分别（包括外部无限区域，称为外部面）。分别用用 和和 表示表示 的面的集合和面的个数的面的集合和面的个数。GG( )F G( )GG 定义定义6.2.3 用用 表示平面图表示平面图 中围成面中围成面 的的周界周界。用。用 （或（或 ）表）表示围成面示围成面 的周界的边数，称为的周界的边数，称为 的的度度。 b fGf Gdf dfff

3、5推论推论 6.2.2 在任何平面图中，度为奇数的面的个数为偶数。在任何平面图中，度为奇数的面的个数为偶数。定理定理6.2.1 如果如果G 是平面图，则是平面图，则 2GfF GdFq G6问题问题：一个平面图的面数是否会随着这个平 面图的不同嵌入而改变？7 定理定理6.2.3（Euler公式）公式） 设 是一个有 个顶点、 条边和 个面的连通平面图，则 Gpq2p q 8证明证明：对面数 进行归纳证明。由于 是连通的平面图，所以当 时， 是树，因此 。故 假设对于一切面数少于 的所有连通平面图，Euler公式成立。现假设 是一个有 个顶点、 条边和 个面的连通图。由于 ， 至少有一个回路，取

4、这回路中的一条边 ，则 仍是连通平面图，有 个顶点， 条边和 个面，根据归纳假设。 即 证毕。G1G1 pq2qpe)2(Gpq2eG p1q12) 1() 1(qp2qpG9问题问题：对于非连通的平面图，其相应的点数、 边数和面数有什么关系？10推论推论6.2.4若 是阶为 的平面图， 的最短回路的长度为 ，则GG(3)p p (3)g g 2( )22ggq Gpgg 证明：证明： 现在对 的每个面 ，由于假设 ，因此 由定理6.2.1知 不妨设该平面图是连通的平面图，则根据Euler公式，有 因此，有Gf( )Gdfg()( )( )GfF GdfgG()2 ( )( )GfF Gq G

5、df22( )( )( )( )pq GGpq Gq Gg2( )22ggq Gpgg11推论6.2.4的一般情况：对简单平面图 ，有由以上结论，容易验证 和 不是平面图G6)(3)(GpGq5K3 , 3K12 推论推论6.2.5 设 是简单平面图，则 。G( )5G 证明：证明：反证 法。假设 是一个平面图，但 ，则 而对于简单平面图，有 矛盾。故对每一个简单平面图 ， 有 。G( )6G()2 ( )( )6 ( )Gv V Gq Gdvp G2 ( )6 ( ) 12q Gp G( )5GG13例：平面上有 个点，其中任意两个点之间的距离至少是1。证明在这 个点中，距离恰好为1的点对数

6、至多是 。nn63 n14二、平面图与正多面体二、平面图与正多面体 凸多面体在平面上的投影是一个连通的平面图，因此Euler公式也适用于凸多面体。为此我们可以用Euler公式讨论正多面体。15正正4-面体面体16正正6面体面体17正正8-面体面体抽象化抽象化18抽象化抽象化正正12-面体面体19抽象化抽象化正正20-面体面体20定理定理6.2.6 存在且只存在5种正多面体：正四面体、正方体、正八面体、正十 二面体和正二十面体。21 证明：证明：首先一个正多面体在平面上的投影所得平面图是2连通的正则图，而且每个面的度相同，即为 。 设平面图 是 正则、每个面的度为 ，则 ， ， 并且 即满足上式

7、且至少为3的正整数 和 只有五对。（见下表）*3r 2 ( )/ ( )q GGGr*r3r ( )( )( )2p Gq GG*()2 ( )( )( )GfF Gq GdfrG()2 ( )( )( )Gu V Gq Gdur p G*(2)(2)4rr*rr22rr( )p G( )q G( )G23正正4-面体面体正正8-面体面体正正6-面体面体正正12-面体面体正正20-面体面体平面上看：平面上看：24三、平面图的判别三、平面图的判别 我们可以利用 和 的非平面性来给出两个有关平面图的判别定理5K3 , 3K25 找出一个图是平面图的充分必要条件的研究持续了几十年，直到1930年波兰

8、数学家库拉托夫斯基（Kuratowski）给出了平面图的一个非常简洁的特征。 给定图的一个剖分是对图 实现有限次过程而得到的另一个图 : 即删去 的一条边 后，添一个新的顶点 及两条新的边 、 。也就是说在 的边上插入有限个顶点便可得到 的一个剖分 。GGGuvwwuwvGG3,3K5K26定理定理6.2.7 （ Kuratowski 定理）定理） 图 是平面图当且仅当它的任何子图都不是 或 的剖分。 3,3K5KG定理定理6.2.8（Wangner定理）定理） 一个图为平面图当且仅当它的任何子图都不能收缩 为 或 。5K3,3K1GE可得Petersen图不是平面图。G1e2e3e4e5e收

9、缩边收缩边12345 ,e e e e e27四、五色定理的证明四、五色定理的证明 我们将利用推论6.2.5的结论来证明每一个平面图的点色数不超过528 定理定理6.2.96.2.9 每一个平面图的色数不超过5。 证明：证明： 对平面图的顶点数 进行归纳。 当 时，结论显然成立。不妨假设所给的平面图连通。 归纳假设对顶点数为 的平面图结论成立，下设 是顶点数为 的简单图。设法证明 。 反证法：设 。 首先由推论6.2.5知 ，设 ， 。作 。此时 是阶为 的平面图，由归纳假设得 。如果 ，只要将五种颜色分配给 ，即可得 ，矛盾，故 。设已给 的顶点染五种颜色 ，使 中相邻顶点染以不同的颜色。

10、p5p 1pGp( )5G( )6G( )5G0( )vV G0()( )GdvG0GGvG1p()5G()5G0v( )5G()5GG12345, G29 如果 ，可得矛盾。 。设 的五个邻点依次为 。分两种情况： Case1 五个点所染颜色有相同的，只要将在没出现的颜色分配给 ，就有 。矛盾。 0()5Gdv0()5Gdv0v12345,v vvvv12345,v vvvv0v( )5G Case2 五个点染得颜色各不相同。设 分别染 。让 为 的色划分。 现考虑 的子图 。如果在 中 与 不在 同一个连通分支中，则可以把 中含 的连通分支内的 与两种颜色互换，而 中其余颜色不变，就得到

11、的一个5染色。此时 与 同染 这种颜色，与假设矛盾。所以 与 在同一连通分支中，于是在 中存在一条 到 的路12345,v vvvv12345, 12345,V V V V VGG1,313GG VV1,3G1v3v1,3G1v13GG1v3v31v3v1,3G1,3G1v3v13( ,)P v v30 同样考虑子图 ，在 中存在 到 的路 。 由路的构造可知， 与 不相交（即无公共顶点）。2,424GG VV2,4G2v4v24(,)P v v24(,)P v v13( ,)P v v 但在 中，回路 将 与 分隔在两个不同的区域内，而 是平面图，所以路 必与 相交于某个顶点。由于 ，因此

12、与 相交与某个顶点，矛盾。 证毕。G0 1133 0( ,)Cv v P v v v v2v4vG24(,)P v vC240( (,)()V P v vV Gv13( ,)P v v24(,)P v v31 一个非平面图G是不能嵌入在一个平面上的，但它可以分解为若干个平面图的并图，即存在若干平面图使 ，不妨设这些平面图 是 G 的生成子图，我们将这种平面图分解的最小个数称为 G 的厚度，记为 ，于是 当且仅当 是平面图。kGGG,21kGGGG21iG)(G1)(GG五、非平面图的分解问题五、非平面图的分解问题32定理定理6.2.10 设 是具有围长 的一个非平面图，则 其中 表示不小于 的

13、最小整数 。Gg( )(2)( )( ( )2)q G gGg p G mm(3)g 33证明证明：设非平面图 的厚度为 ，则存在平面图 ，使 kGGG,21kGGGG21这里 是 的生成子图。则每个生成子图 是围长至少为 的平面图，由推论6.2.4，有GiGiGg222)(ggpggGqi故有 )2)()2)()(GpggGqGG)(G34例例1 1 对于那些n，存在n条棱的凸多面体？（1968年波兰数学奥林匹克试题）解：解：以多面体的顶点为图的顶点，以多面体的棱为图的边，组成一个平面图G,则 ，每个面的度至少是3。由Euler公式， ，即没有棱数小于6的凸多面体。( )4, ( )4p GG( )6q G 四面体是棱数为6的凸多面体。 若有7条棱的凸多面体，则存在满足上述条件，的平面图，由Euler公式得：( )7q G ( )( )( )29p GGq G但每个面的度数至少为3，故(