8.4平面图.ppt

1、第8章，8.4平面，平面，让无向图G=，如果G的所有节点和边都可以画在一个平面上，这样除了公共节点外，任何两边都没有其他交点，那么G被称为可嵌入平面，或者称为可平面，平面上可平面的嵌入被称为平面，如果G不可平面，那么G被称为非平面。比如K4，所以K4是有计划的。K5，所以K5不是一个计划。定义：G是一个连通的平面图，由图的边包围的不包含图的节点和边的区域称为g的区域，由包围表面的边形成的环称为表面的边界，表面边界的长度称为表面的度数， 在下图中，有10个点和13条边，将平面分成5个平面，其中只有一个无限平面r0。 在平面图G=，|V|=v，|E|=m中，所有面的度数之和等于边数的两倍，即deg

2、(ri)=2m。最大平面图，简单平面图G，如果通过将任何边(它不是环或其他边的平行边)添加到G而获得的图不是平面图，那么G被称为最大平面图，并且最大平面图的所有接口都是三维表面，并且没有接口的接口也是三维的。也就是说，所有面的边界都是K3。在顶点数为n4的最大平面图中，顶点的最小度不小于3。欧拉公式，定理：连通平面图G=有n个节点，m条边和r个面，那么n-m r=2。这个定理仍然适用于空间多面体。在刚才的例子中，n=10，m=13，r=5满足条件。空间正六面体：n=8，m=12，r=6，空间正八面体：n=6，m=12，r=8，欧拉公式的推广，在任何平面图中，p是g (p1) n-m r=p 1

3、的连通分支数，这证明了图g中有p个连通分支，可以很容易地知道n1 n2 np=n，m1 m2 mp=m，r1 r2 rp-(p-1)=r，ith连通分支满足：ni证明了G在：中有R面。因为G是一个简单的图，每个面至少被3条边包围。Deg(ri)3r和deg(ri)=2m 2m3r，r2m/3，代入欧拉公式2=n-m rn-2m/3=n-m/32n-m/3，m3n-6表明：是简单图为平面的必要条件。例如，K5，例如，在K5，n=5，m=10，3n-6=9，所以m3n-6 K5不能是平面图。例如，已知平面图中的节点数n=10，并且每个平面由四条边包围。找出平面图的边和面的数量，画出平面图。在解：中

4、，因为每个表面的度数是4，2m=4r，m=2r并且n=10，所以替换欧拉公式n-m r=210-2r r=2，解是r=8，然后m=2r=16，插入或删除第二度节点，在图的一侧插入第二度节点，或者与第二度节点相关联。同胚，给出两个图G1和G2，或者它们是同构的，或者它们在重复插入或移除二次节点后是同构的，那么G1和G2在二次节点内是同构的，这也称为同胚。库拉托夫斯基定理，一个图是一个平面图，当且仅当它不包含与K3，3或K5在2度节点上同构的子图。在该图中，首先移除e1的子图，然后移除V2、V4和V6的节点，并且两侧合并成K5，因此该图不是平面图。证明彼得森图不是平面图。按顺序标记彼得森图的顶点，

5、如图(1)所示。在图中，边(a，f)，(b，g)，(c，h)，(d，I)，(e，j)是收缩的，得到的图在图(2)中示出，它是K5。可以知道彼得森图不是平面图。也可以证明彼得森图是由G表示的，所以G=G-(j，G)，(c，d) G如图所示。很容易知道它与K3，3是同胚的，并且可以知道G是一个非平面图。平面图的着色问题，以及问题的提出：这个问题源于地图的着色问题。着色点是给图G的每个节点指定一种颜色，使得相邻节点的颜色不同；给边着色就是给每条边指定一种颜色，这样相邻边的颜色就不同了；给面着色就是给每个面指定一种颜色，这样两个有共同边的面就有不同的颜色。如果你想在给一个图着色时使用至少N种颜色，那么

6、G被称为N色，这个N被称为G的颜色数，它被表示为(G)。边着色和反着色都可以转化为着色节点问题。点着色的鲍威尔法：在第一步：中，每个节点按度的降序排列(具有相同度的节点的顺序可以是任意的)。在第二步骤：中，第一节点用第一颜色着色，并且不与第一节点相邻的节点按顺序用相同的颜色着色，并且不与具有第一颜色的先前节点相邻的节点用第一颜色着色，直到所有节点都被检查。在第三步：中，对于下一个未着色的点，用第二种颜色重复第二步，然后用第三种颜色重复第二步，直到所有的点都被着色。例如，如果一个N阶的完全图Kn有(Kn)=n，并且一个连通平面图G=至少有三个节点，那么一定有一个点uV等于deg(u)5。证明了：

7、集合| V |=M和| E |=N，如果G的每个节点都有6，则有2n=。对偶图，通过在连通平面图G上执行以下步骤获得的图G*被称为G的图的对偶：(1)在G的每个平面ri内形成G*的顶点v，(2)如果G中的ri和ri具有公共边界，则穿过该边界的每个边ek与v的一个边E相关联。E不与G*的其他边相交。(3)当ek是面ri的边界而不是ri和其他面之间的公共边界时，V环与ek相交(并且仅在一个位置相交)。该循环不与G*的边缘相交。例如，G的对偶图G*具有以下性质：从定义中，不难看出G的对偶图G*具有以下性质：G*是平面图并且嵌入在平面中。G*是连通图。如果G*中的边e*是环，则对应于G*的边e*是桥，

8、如果是桥，则对应于G *中的边e *是环。在大多数情况下，G*是一个多重图(一个有平行边的图)。同构平面图(平面嵌入)的成对图不一定是同构的。定理：设G*为连通平面图G的对偶图，n，m，r和n *，m*，r *为G和G的节点数、边数和面数，然后(1) n*r(2) m*m(3) r*n(4)设vi*位于G中。自对偶图：G的对偶图G*有以下关系：GG*，平面图，连通无桥平面图的平面嵌入及其所有面称为平面图或地图，地图的面称为“国家”。如果两个国家的边界至少有一条共同的边界，那么这两个国家就是相邻的。用一种颜色绘制地图G的每个国家，并使相邻国家绘制不同的颜色，这被称为G的表面着色。如果G的表面可以

9、用K色着色，则称G的表面是K色的，或称G是K面可着色的。如果G是k-表面可着色的，但不是(k-1)-表面可着色的，那么G被称为K，其被表示为* (G)=K。映射的着色可以被转换为其对偶图的点着色，当且仅当其对偶图G*是k-可着色的。研究地图的着色相当于研究平面图的点着色。迄今为止，人们已经证明了平面图点着色问题的下列定理。四色定理：任意平面图的色数5。定理被称为五色定理，也称为希伍德定理。根据这个定理，任何平面图都是k(k5)-可着色的，但四色猜想尚未得到证明。四色定理：所谓的四色猜想问题是由英国的格思里于1852年提出来的：它要求在平面或球体上给地图上色，这样邻国就可以被染成不同的颜色，最多可以使用四种颜色。这个问题已经提出了将近150年，但至今还没有完全解决。1879年，肯普给出了一个证明，但在1890年，人们发现有一个错误，但它可以证明五色问题；1976年，两个年轻人，阿佩尔和哈肯，使用高速计算机达1200小时，证明任何计划都是四色计划。但是数学不同意。五色定理证明了任何平面图都是五色的。证据：1)、n5，明显成立；2)当n5时，假设n=k成立，即当n=k时，图g是5-可着色的。根据欧拉公式的推论，G中至少一个节点的度数5被设置为V，度(v)5。在原始图G中，通过假设G-v是5-可着色的，节点v被删除。图中增加了g，2.1，deg(v)