《二：平面图、对偶和作色、树和生成树课件》由会员分享，可在线阅读，更多相关《二：平面图、对偶和作色、树和生成树课件（18页珍藏版）》请在金锄头文库上搜索。
1、75 平面图,1、平面图,定义：设图G=是一个无向图，如果能够把G的所有结点 和边画在平面上，且使得任何两条边除了端点外没有其 他的交点，就称G是一个平面图。,注意：有些图从表面上看有几条边是相交的，但是改画之后，仍然是平面图。,此图是非平面图,是非平面图,2、面、面的边界,定义：设G是一个连通平面图，由图中的边所包围的区域， 在区域内既不包含图的结点，也不包含图的边，这样 的区域称为G的一个面，包围该面的诸边所构成的回 路称为这个面的边界。面的边界的回路长度称作该面 的次数，记为deg(r)。,deg(r1)= deg(r2)= deg(r3)= deg(r4)= deg(r5)=,无限面,
2、3 3 5 4 3,定理1 一个有限平面图，面的次数之和等于其边数的两倍。,定理2(欧拉定理) 设有一个连通的平面图G，共有v个结点e条边和r个面， 则欧拉公式vr成立。,证明：对归纳,定理3 设是一个有个结点条边的连通简单平面图， 若v3，则v。,用来判断某些图是非平面图,356910,设有r个面，则er,推论： 如果图是连通的简单平面图，若v 3， 且每个区域至少由四条边围成，则有v。,作业317 (1) (2) (4),76 对偶与着色,这个问题最早起源于地图着色，一个地图中相邻两个国家以不同的颜色，那么最少需用多少种？,一百多年前，英国格色里(Guthrie)提出用四种猜想即可对地图进
3、行着色的猜想，1879年肯普(Kempe)给出该猜想的第一个证明，但到了1890年希伍德(Hewood)发现肯普的证明是错误的，指出肯普的方法，虽不能证明用四种颜色就够了，但可证明用五种就够了，此后四色问题一直成为数学家感兴趣而未解决的难题，到了1976年美国数学家阿佩尔和黑肯宣布：用电子计算机证明了四色猜想是正确的，从此有了“四色理论”。,1、对偶,定义 给定平面图G=，它具有面F1,F2,Fn，若有图 G*=满足下列条件： (a) 对于图的任何一个面Fi ，内部有且仅有一个结点vi* V*； (b) 对于图的面Fi 和Fj的公共边界ek，有且仅有一条边e*k E*，使得e*k =(v*i,
4、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是自对偶图。,从对偶图的概念我们可以看到，对地图的着色问题可以归结为对平面图的结点进行着色的问题，因此四色问题可以归结为证明对于任何一个平面图，一定可以用四种颜色进行着色，使得邻接的结点都有不同的颜色。,2、着色,图G的正常着色（简称着色）是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图G在着
5、色时用了n种颜色，我们称G为n-色的。最小着色数用x(G)表示。 虽然目前还没有一个简单的方法，可以确定任一图G是n-色的。但我们可以用韦尔奇鲍威尔(Welch Powell)对图G着色： a) 将图G中的结点按照度数的递减次序进行排列（这种排列可能并不是唯一的，因为有些点有相同度数）； b) 用第一种颜色对第一点着色，并且并且按排列次序，对与前面着色点不邻接的每个点着上同一种颜色； c) 用第二种颜色对尚未着色的点重复b)，用第三种颜色继续这种做法，直到所有点全部着上色为止。,定理1 对于n个结点的完全图Kn，有 x(Kn)=n。 证明：因为完全图的每个结点与其它各个结点都邻接，故n个结点的
6、着色数不能少于n，又n个结点的着色数最多为n，故 x(Kn)=n。,定理2 设G为一个至少具有三个结点的连通平面图，则G中至少有一点u，使得deg(u) 5。 证明：设G=， |V|=v， |E|=e，若G中每个结点u，都有 deg(u) 6,但因,故2e 6v，所以e 3v3v-6，与3v-6矛盾。,定理3 任意平面图G最多是5-色的。,7-7 树与生成树,一、树,定义： 一个连通且无回路的无向图称为树。树中度数为1 的结点称为树叶，度数大于1的结点称为分支点或 内点。一个无回路的无向图称作森林，它的每个 连通分图是树。,孤立结点可以看成是一个连通分支，但一般情况下 孤立结点不看成是一棵树。
7、除非有特殊说明。,定理1 以下关于树的定义是等价的。 无回路的连通图。 无回路且e=v-1，其中e是边数，v是结点数。 连通且e=v-1。 无回路，但增加一条新边，得到一个且仅有一个回路。 连通，但删去任一边后便不连通。 每一对结点之间有一条且仅有一条路。,定理2 任一棵树中至少有两片树叶。,证明 设树T=，|V|=v，因为T是连通图，对于任意 vi V, 有deg(vi)1且deg(vi)=2(|V|-1) =2v-2。 若T中每个结点度数2，则deg(vi) 2v，得出矛 盾。 若T中只有一个结点度数为1，其他结点度数2 ， 则deg(vi) 2(v-1)+1=2v-1 ，得出矛盾。 故T
8、中至少有两个结点度数为1。,二、生成树,定义： 若图G的生成子图是一棵树，则该树称为G的生成树。,设图G有一棵生成树T，则T中的边称作树枝。图G的不在 生成树中的边称作弦。所有弦的集合称作树T的补。,树枝：e1,e7,e5,e8,e3 T的弦：e2,e4,e6 树T的补：e2,e4,e6,注意：一个连通图可以有许多不同的生成树。,定理3 连通图至少有一颗生成树。,假设G是一个有n个结点,m条边的连通图，则G的生成树 有n-1条边。必须删去G的m-(n-1)条边才能确定G的一棵 生成树。数m-n+1称为连通图G的秩。,定理4 一条回路和任何一棵生成树的补至少有一条公共边。,定理5 一个边割集和任何生成树至少有一条公共边。,定义：在图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。,三、最小生成树,带权树,最小生成树的生成算法： (1)避回路法 (2)破圈法,作业327 (3) (6),
