平面图和五色定理

《平面图和五色定理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.2平面图和五色定理abcdfghxkya1b1c12df31hx31kg22y6.2平面图和五色定理定义6.2.1如果能与这样的一个图同构，其中的顶点在同一个平面上，而的边只能在端点处相交，就称为平面图，而称为的一个平面嵌入，或称为在平面上的实现。如图和就不具有这样的性质。一、平面图的概念及性质定义6.2.2平面图的边把整个平面分割成若干各连通的区域，这些区域的闭包称为平面图的面（包括外部无限区域，称为外部面）。分别用和表示的面的集合和面的个数。定义6.2.3用表示平面图中围成面的周界。用（或）表示围成面的周界的边数，称为的度。推论6.2.2在任何平面图中，度为奇数的面的

2、个数为偶数。定理6.2.1如果G是平面图，则问题：一个平面图的面数是否会随着这个平面图的不同嵌入而改变？定理6.2.3（Euler公式）设是一个有个顶点、条边和个面的连通平面图，则证明：对面数进行归纳证明。由于是连通的平面图，所以当时，是树，因此。故假设对于一切面数少于的所有连通平面图，Euler公式成立。现假设是一个有个顶点、条边和个面的连通图。由于，至少有一个回路，取这回路中的一条边，则仍是连通平面图，有个顶点，条边和个面，根据归纳假设。即证毕。问题：对于非连通的平面图，其相应的点数、边数和面数有什么关系？推论6.2.4若是阶为的平面图，的最短回路的长度为，则证明：现在对

3、的每个面，由于假设，因此由定理6.2.1知不妨设该平面图是连通的平面图，则根据Euler公式，有因此，有推论6.2.4的一般情况：对简单平面图，有由以上结论，容易验证和不是平面图推论6.2.5设是简单平面图，则。证明：反证法。假设是一个平面图，但，则而对于简单平面图，有矛盾。故对每一个简单平面图，有。例：平面上有个点，其中任意两个点之间的距离至少是1。证明在这个点中，距离恰好为1的点对数至多是。二、平面图与正多面体凸多面体在平面上的投影是一个连通的平面图，因此Euler公式也适用于凸多面体。为此我们可以用Euler公式讨论正多面体。正4-面体正6—面体正8-面体—抽象化——抽

4、象化—正12-面体—抽象化—正20-面体定理6.2.6存在且只存在5种正多面体：正四面体、正方体、正八面体、正十二面体和正二十面体。证明：首先一个正多面体在平面上的投影所得平面图是2连通的正则图，而且每个面的度相同，即为。设平面图是正则、每个面的度为，则，，并且即满足上式且至少为3的正整数和只有五对。（见下表）相应的正多面体33464正4-面体348126正6-体35203012正12-面体436128正8-面体53123020正20-面体正4-面体正8-面体正6-面体正12-面体正20-面体平面上看：三、平面图的判别我们可以利用和的非平面性来给出两个有关平面图的判别定理找出

5、一个图是平面图的充分必要条件的研究持续了几十年，直到1930年波兰数学家库拉托夫斯基（Kuratowski）给出了平面图的一个非常简洁的特征。给定图的一个剖分是对图实现有限次过程而得到的另一个图:即删去的一条边后，添一个新的顶点及两条新的边、。也就是说在的边上插入有限个顶点便可得到的一个剖分。定理6.2.7（Kuratowski定理）图是平面图当且仅当它的任何子图都不是或的剖分。定理6.2.8（Wangner定理）一个图为平面图当且仅当它的任何子图都不能收缩为或。可得Petersen图不是平面图。收缩边四、五色定理的证明我们将利用推论6.2.5的结论来证明每一个平面图的点色数

6、不超过5定理6.2.9每一个平面图的色数不超过5。证明：对平面图的顶点数进行归纳。当时，结论显然成立。不妨假设所给的平面图连通。归纳假设对顶点数为的平面图结论成立，下设是顶点数为的简单图。设法证明。反证法：设。首先由推论6.2.5知，设，。作。此时是阶为的平面图，由归纳假设得。如果，只要将五种颜色分配给，即可得，矛盾，故。设已给的顶点染五种颜色，使中相邻顶点染以不同的颜色。如果，可得矛盾。。设的五个邻点依次为。分两种情况：Case1五个点所染颜色有相同的，只要将在没出现的颜色分配给，就有。矛盾。Case2五个点染得颜色各不相同。不妨设分别染。让为的色划分。现考虑的子图。如果在

7、中与不在同一个连通分支中，则可以把中含的连通分支内的与两种颜色互换，而中其余颜色不变，就得到的一个5染色。此时与同染这种颜色，与假设矛盾。所以与在同一连通分支中，于是在中存在一条到的路同样考虑子图，在中存在到的路。由路的构造可知，与不相交（即无公共顶点）。但在中，回路将与分隔在两个不同的区域内，而是平面图，所以路必与相交于某个顶点。由于，因此与相交与某个顶点，矛盾。证毕。一个非平面图G是不能嵌入在一个平面上的，但它可以分解为若干个平面图的并图，即存在若干平面图使，不妨设这些平面图是G的生成子图，我们将这