二：平面图、对偶和作色、树和生成树

《二：平面图、对偶和作色、树和生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7－5平面图1、平面图定义：设图G=是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，就称G是一个平面图。注意：有些图从表面上看有几条边是相交的，但是改画之后，仍然是平面图。BB'K3,3此图是非平面图K5是非平面图2、面、面的边界定义：设G是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为G的一个面，包围该面的诸边所构成的回路称为这个面的边界。面的边界的回路长度称作该面的次数，记为deg(r)。ABCDEFr4r1r2r3r5deg(r1)=deg(r2)=deg(r3)=deg(r4)

2、=deg(r5)=无限面33543定理1一个有限平面图，面的次数之和等于其边数的两倍。ABC图中只有一个面r，由回路ABCBA所围成,deg(r)=4=2×2图中有两个面r1,r2,r1由回路BCDB围成，r2由回路ABCDBA围成，deg(r1)+deg(r2)=3+5=2×4ABCDr1r2定理2(欧拉定理)设有一个连通的平面图G，共有v个结点e条边和r个面，则欧拉公式v－ｅ＋r＝２成立。证明：对ｅ归纳定理3设Ｇ是一个有ｖ个结点ｅ条边的连通简单平面图，若v≥3，则ｅ≤３v－６。用来判断某些图是非平面图K53×5－6＝9＜10设有r个面，则２e≥３r推论：如果图Ｇ＝<Ｖ,Ｅ>是连通的简单

3、平面图，若v≥3，且每个区域至少由四条边围成，则有ｅ≤２v－４。K3,3作业Ｐ317(1)(2)(4)7－6对偶与着色这个问题最早起源于地图着色，一个地图中相邻两个国家以不同的颜色，那么最少需用多少种？一百多年前，英国格色里(Guthrie)提出用四种猜想即可对地图进行着色的猜想，1879年肯普(Kempe)给出该猜想的第一个证明，但到了1890年希伍德(Hewood)发现肯普的证明是错误的，指出肯普的方法，虽不能证明用四种颜色就够了，但可证明用五种就够了，此后四色问题一直成为数学家感兴趣而未解决的难题，到了1976年美国数学家阿佩尔和黑肯宣布：用电子计算机证明了四色猜想是正确的，从此有了

4、“四色理论”。1、对偶定义给定平面图G=，它具有面F1,F2,…,Fn，若有图G*=满足下列条件：(a)对于图的任何一个面Fi，内部有且仅有一个结点vi*∈V*；(b)对于图的面Fi和Fj的公共边界ek，有且仅有一条边e*k∈E*，使得e*k=(v*i,vj*)，且e*k与ek相交；(c)当且仅当ek只是一个面Fi的边界时，v*i存在一个环e*k与ek相交。则称G*是G的对偶图。注意：若G*是G的对偶图，则G也是G*的对偶图。例:P318图7-6.1、图7-6.2定义若图G的对偶图G*同构于G，则称G是自对偶图。从对偶图的概念我们可以看到，对地图的着色问题可以归结为

5、对平面图的结点进行着色的问题，因此四色问题可以归结为证明对于任何一个平面图，一定可以用四种颜色进行着色，使得邻接的结点都有不同的颜色。2、着色图G的正常着色（简称着色）是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图G在着色时用了n种颜色，我们称G为n-色的。最小着色数用x(G)表示。虽然目前还没有一个简单的方法，可以确定任一图G是n-色的。但我们可以用韦尔奇鲍威尔(WelchPowell)对图G着色：a)将图G中的结点按照度数的递减次序进行排列（这种排列可能并不是唯一的，因为有些点有相同度数）；b)用第一种颜色对第一点着色，并且并且按排列次序，对与前面着色点不

6、邻接的每个点着上同一种颜色；c)用第二种颜色对尚未着色的点重复b)，用第三种颜色继续这种做法，直到所有点全部着上色为止。定理1对于n个结点的完全图Kn，有x(Kn)=n。证明：因为完全图的每个结点与其它各个结点都邻接，故n个结点的着色数不能少于n，又n个结点的着色数最多为n，故x(Kn)=n。定理2设G为一个至少具有三个结点的连通平面图，则G中至少有一点u，使得deg(u)≤5。证明：设G=，

7、V

8、=v，

9、E

10、=e，若G中每个结点u，都有deg(u)≥6,但因故2e≥6v，所以e≥3v>3v-6，与ｅ≤3v-6矛盾。定理3任意平面图G最多是5-色的。7-7树与生成树一、树定义：一

11、个连通且无回路的无向图称为树。树中度数为1的结点称为树叶，度数大于1的结点称为分支点或内点。一个无回路的无向图称作森林，它的每个连通分图是树。孤立结点可以看成是一个连通分支，但一般情况下孤立结点不看成是一棵树。除非有特殊说明。定理1以下关于树的定义是等价的。无回路的连通图。无回路且e=v-1，其中e是边数，v是结点数。连通且e=v-1。无回路，但增加一条新边，得到一个且仅有一个回路。连通，但删去任一边后便不连通。每一对结