平面图和五色定理ppt课件

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

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

3、2.2 在任何平面图中，度为奇数的面的个数为偶数。在任何平面图中，度为奇数的面的个数为偶数。定理定理6.2.1 假设假设G 是平面图，那么是平面图，那么 2GfF GdFq G问题：一个平面图的面数能否会随着这个平问题：一个平面图的面数能否会随着这个平 面图的不同嵌入而改动？面图的不同嵌入而改动？ 定理定理6.2.3Euler公式公式 设设 是一个有是一个有 个顶点、个顶点、 条边和条边和 个面的连通平面图，那么个面的连通平面图，那么 Gpq2p q 证明：对面数证明：对面数 进展归纳证明。由于进展归纳证明。由于 是连通的平面图，是连通的平面图，所以当所以当 时，时， 是树，因此是树，因此 。

4、故。故 假设对于一切面数少于假设对于一切面数少于 的一切连通平面图，的一切连通平面图，Euler公式成立。现假设公式成立。现假设 是一个有是一个有 个顶点、个顶点、 条边条边和和 个面的连通图。由于个面的连通图。由于 ， 至少有一个回路，取至少有一个回路，取这回路中的一条边这回路中的一条边 ，那么，那么 仍是连通平面图，有仍是连通平面图，有 个顶点，个顶点， 条边和条边和 个面，根据归纳假设。个面，根据归纳假设。 即即 证毕。证毕。G1G1 pq2qpe)2(Gpq2eG p1q12) 1() 1(qp2qpG问题：对于非连通的平面图，其相应的点数、问题：对于非连通的平面图，其相应的点数、 边

5、数和面数有什么关系？边数和面数有什么关系？推论推论6.2.4假设假设 是阶为是阶为 的平面图，的平面图， 的最短回路的长度为的最短回路的长度为 ，那么那么GG(3)p p (3)g g 2( )22ggq Gpgg 证明：证明： 如今对如今对 的每个面的每个面 ，由于假设，由于假设 ，因此，因此 由定理由定理6.2.1知知 无妨设该平面图是连通的平面图，那么根据无妨设该平面图是连通的平面图，那么根据Euler公式，有公式，有 因此，有因此，有Gf( )Gdfg()( )( )GfF GdfgG()2 ( )( )GfF Gq Gdf22( )( )( )( )pq GGpq Gq Gg2( )

6、22ggq Gpgg推论6.2.4的普通情况：对简单平面图 ，有由以上结论，容易验证 和 不是平面图G6)(3)(GpGq5K3 , 3K 推论推论6.2.5 设设 是简单平面图，那么是简单平面图，那么 。G( )5G 证明：反证证明：反证 法。假设法。假设 是一个平面图，但是一个平面图，但 ，那么，那么 而对于简单平面图，有而对于简单平面图，有 矛盾。故对每一个简单平面图矛盾。故对每一个简单平面图 ， 有有 。G( )6G()2 ( )( )6 ( )Gv V Gq Gdvp G2 ( )6 ( ) 12q Gp G( )5GG例：平面上有 个点，其中恣意两个点之间的间隔至少是1。证明在这

7、个点中，间隔恰好为1的点对数至多是 。nn63 n二、平面图与正多面体二、平面图与正多面体 凸多面体在平面上的投影是一个连凸多面体在平面上的投影是一个连通的平面图，因此通的平面图，因此Euler公式也适用于公式也适用于凸多面体。为此我们可以用凸多面体。为此我们可以用Euler公式公式讨论正多面体。讨论正多面体。正正4-面体面体正正6面体面体正正8-面体面体笼统化笼统化笼统化笼统化正正12-面体面体笼统化笼统化正正20-面体面体定理定理6.2.6 存在且只存在存在且只存在5种正多面体：正四面体、种正多面体：正四面体、正方体、正八面体、正十正方体、正八面体、正十 二面体和正二十二面体和正二十面体。

8、面体。 证明：首先一个正多面体在平面上的投影所得平面图是证明：首先一个正多面体在平面上的投影所得平面图是2连通的正那么图，连通的正那么图，而且每个面的度一样，即为而且每个面的度一样，即为 。 设平面图设平面图 是是 正那么、每个面的度为正那么、每个面的度为 ，那么，那么 ， ， 并且并且 即即满足上式且至少为满足上式且至少为3的正整数的正整数 和和 只需五对。见下表只需五对。见下表*3r 2 ( )/ ( )q GGGr*r3r ( )( )( )2p Gq GG*()2 ( )( )( )GfF Gq GdfrG()2 ( )( )( )Gu V Gq Gdur p G*(2)(2)4rr*

9、rr相应的正多面体相应的正多面体33464正正4-面体面体348126正正6-体体35203012正正12-面体面体436128正正8-面体面体53123020正正20-面体面体rr( )p G( )q G( )G正正4-面体面体正正8-面体面体正正6-面体面体正正12-面体面体正正20-面体面体平面上看：平面上看：三、平面图的判别三、平面图的判别 我们可以利用我们可以利用 和和 的非平面的非平面性来性来给出两个有关平面图的判别定理给出两个有关平面图的判别定理5K3 , 3K 找出一个图是平面图的充分必要条件的研讨继续了几十年，直到1930年波兰数学家库拉托夫斯基Kuratowski给出了平面

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

11、G1e2e3e4e5e收缩边收缩边12345 ,e e e e e四、五色定理的证明四、五色定理的证明 我们将利用推论我们将利用推论6.2.5的结论来证明的结论来证明每一个平面图的点色数不超越每一个平面图的点色数不超越5 定理定理6.2.9 6.2.9 每一个平面图的色数不超越每一个平面图的色数不超越5 5。 证明：证明： 对平面图的顶点数对平面图的顶点数 进展归纳。进展归纳。 当当 时，结论显然成立。无妨假设所给的平面图连通。时，结论显然成立。无妨假设所给的平面图连通。 归纳假设对顶点数为归纳假设对顶点数为 的平面图结论成立，下设的平面图结论成立，下设 是顶点数为是顶点数为 的简单图。的简单

12、图。设法证明设法证明 。 反证法：设反证法：设 。 首先由推论首先由推论6.2.5知知 ，设，设 ， 。作。作 。此时。此时 是阶为是阶为 的平面图，由归纳假设得的平面图，由归纳假设得 。假设。假设 ，只需将五种颜色分，只需将五种颜色分配给配给 ，即可得，即可得 ，矛盾，故，矛盾，故 。设已给。设已给 的顶点染五种颜的顶点染五种颜色色 ，使，使 中相邻顶点染以不同的颜色。中相邻顶点染以不同的颜色。 p5p 1pGp( )5G( )6G( )5G0( )vV G0()( )GdvG0GGvG1p()5G()5G0v( )5G()5GG12345, G 假设假设 ，可得矛盾。，可得矛盾。 。设。设

13、 的五个邻点依的五个邻点依次为次为 。分两种情况：。分两种情况： Case1 Case1 五个点所染颜色有一样的，只需将在五个点所染颜色有一样的，只需将在没出现的颜色分配给没出现的颜色分配给 ，就有，就有 。矛盾。矛盾。 0()5Gdv0()5Gdv0v12345,v vvvv12345,v vvvv0v( )5G Case2 Case2 五个点染得颜色各不一样。无妨设五个点染得颜色各不一样。无妨设 分分别染别染 。让。让 为为 的色划分。的色划分。 现思索现思索 的子图的子图 。假设在。假设在 中中 与与 不在不在 同一个连通分支中，那么可以把同一个连通分支中，那么可以把 中含中含 的连通分

14、支内的的连通分支内的 与与两种颜色互换，而两种颜色互换，而 中其他颜色不变，就得到中其他颜色不变，就得到 的一个的一个5 5染色。染色。此时此时 与与 同染同染 这种颜色，与假设矛盾。所以这种颜色，与假设矛盾。所以 与与 在在同一连通分支中，于是在同一连通分支中，于是在 中存在一条中存在一条 到到 的路的路12345,v vvvv12345, 12345,V V V V VGG1,313GG VV1,3G1v3v1,3G1v13GG1v3v31v3v1,3G1,3G1v3v13( ,)P v v 同样思索子图同样思索子图 ，在，在 中存在中存在 到到 的的路路 。 由路的构造可知，由路的构造可

15、知， 与与 不相交即无公共顶点。不相交即无公共顶点。2,424GG VV2,4G2v4v24(,)P v v24(,)P v v13( ,)P v v 但在但在 中，回路中，回路 将将 与与 分隔在两个不分隔在两个不同的区域内，而同的区域内，而 是平面图，所以路是平面图，所以路 必与必与 相交于某个顶相交于某个顶点。由于点。由于 ，因此，因此 与与 相交与某相交与某个顶点，矛盾。个顶点，矛盾。 证毕。证毕。G0 1133 0( ,)Cv v P v v v v2v4vG24(,)P v vC240( (,)()V P v vV Gv13( ,)P v v24(,)P v v 一个非平面图G是不

16、能嵌入在一个平面上的，但它可以分解为假设干个平面图的并图，即存在假设干平面图使 ，无妨设这些平面图 是 G 的生成子图，我们将这种平面图分解的最小个数称为 G 的厚度，记为 ，于是 当且仅当 是平面图。kGGG,21kGGGG21iG)(G1)(GG五、非平面图的分解问题五、非平面图的分解问题67)(pKp65)(,pKpp3)(9K3)(10K)10, 9(pp定理定理6.2.10 设设 是具有围长是具有围长 的一个非平面图，那么的一个非平面图，那么 其中其中 表示不小于表示不小于 的最小整数的最小整数 。Gg( )(2)( )( ( )2)q G gGg p G mm(3)g 证明：设非平

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