第7章-图论(II)讲述.ppt

定理8.4.1 (库拉图斯基定理)一个图G是平面图?G中不含同胚于K3,3或K5的子图。 该定理的证明是看来不算很难但是冗长的，略去了，有兴趣读者可参见图论专著中的证明。 库拉图斯基定理表述还是简明的，例如，图11.4.4(a)所示的图称为彼得森图，它是非平面图。因为当删去边[v6,v8]和[v3,v4]时，它成为含有同胚于K3,3的子图，如图11.4.4(b)或(c)所示。 图 11.4.5 下面介绍平面图中的重要的欧拉公式。 定义8.4.3 设G为一平面图，若由G的一条或多条边所界定的区域内部不含图G的结点和边，这样的区域称为G的一个面，记为f。包围这个区域的各条边所构成的圈，称为该面f的边界，其圈的长度，称为该面f的度，记为d(f)。为强调平面图G中含有面这个元素，今后把平面图表为G=V，E，F，其中F是G中所有面的集合。 为方便有时把平面图G的外部的无限区域当作一个面，称为无限面或外部面，其余的面称为有限面或内部面。 由定义不难证明下面定理： 定理8.4.2 令G=V，E，F是连通平面图，则 。 定理8.4.3 设G=V，E，F是连通平面图，则|V|-|E|+|F|=2。(by induction, 从|F|=1 begin) 这便是著名的欧拉公式。 推论1 给定连通简单平面图G=V，E，F。若|V|≥3，则|E|≤3|V|-6。(补证，除|E|=2外，每个面度至少是3)。 推论2 设G=V，E，F是一个连通简单平面图，若|V|≥3，则存在v∈V，使得d(v)≤5。 推论3 给定连通简单平面图G=V，E，F。若对于每个面f∈F，有d(f)≥4，则 |E|≤2|V|-4 推论4 完全图K5是非平面图。(用推论1) 推论5 完全二部图K3,3是非平面图。(用推论3) 下面讨论平面图的着色问题。 平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1840年，德国数学家麦比乌斯(A.F.Mǒbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题(以下简称四色猜想)。1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了，但却可以证明用五种颜色是够的，即五色定理成立。 在这里，研究的方法并不直接去考察地图着色问题，而是把它转化成平面图。为此，先给出对偶图的概念。 定义8.4.4 给定平面图G=V，E，F，且f1，f2，…，fn∈F。若有图G*=V*，E*满足下列条件： (1) 对于任意fi∈F内部有且仅有一个结点v*i∈V*； (2) 对于G中面fi和面fj的公共边ek有且仅有一条边e*k∈E*，使得ek*= v*i v*j且e*k与ek相交； (3) 当且仅当ek只是一个面fi的边界时，v*i存在一个环ek*且e*k与ek相交，则称图G*是图G的对偶图。 从对偶图的定义可以看出，若G*=V*，E*是平面图G=V，E，F的对偶图，则G也G*的对偶图。一个连通平面图G的对偶图G*，也是平面图，而且有 |E(G*)|=|E(G)| |V(G*)|=|F(G)| dG*(v*)=dG(fi) fi?F，v* ?V * 其中E(G)表示图G的所有边集合，F(G)表示图G的所有面的集合。于是，可得到下面定理： 定理8.4.4 若G=V，E，F是平面图，则 。 定义8.4.5 若图G的对偶图G*同构于G，则称G是自对偶图。 定理8.4.5 若平面图G=V，E是自对偶图，则|E|=2(|V|-1)。 证：因|F|=|V*|=|V|，|V|-|E|+|F|=2，所以|V|-|E|+|V|=2. 从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的结点的着色问题。 因此，四色问题可以归结为要证明：对任意平面图一定可以用四种颜色，对其结点进行着色，使得相邻结点都有不同颜色。 平面图G=V，E的着色α是从结点集V到色集C={c1，c2，…，cn}上一个映射，使对任意边vivj∈E均有α(vi)≠α(vj)，即对G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。 对于平面图G着色时，需要的最少颜色数称为G的着色数，记为χ(G)。 定理8.4.6 (五色定理)对于任何简单平面图G=V，E，均有χ(G)≤5。 Proof . Let G be a plane graph with n≥6 vertices and m edges. We assume inductively that ever