资源预览内容
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
第9页 / 共18页
第10页 / 共18页
亲,该文档总共18页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
75 平面图,1、平面图,定义:设图G=是一个无向图,如果能够把G的所有结点 和边画在平面上,且使得任何两条边除了端点外没有其 他的交点,就称G是一个平面图。,注意:有些图从表面上看有几条边是相交的,但是改画之后,仍然是平面图。,此图是非平面图,是非平面图,2、面、面的边界,定义:设G是一个连通平面图,由图中的边所包围的区域, 在区域内既不包含图的结点,也不包含图的边,这样 的区域称为G的一个面,包围该面的诸边所构成的回 路称为这个面的边界。面的边界的回路长度称作该面 的次数,记为deg(r)。,deg(r1)= deg(r2)= deg(r3)= deg(r4)= deg(r5)=,无限面,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)提出用四种猜想即可对地图进行着色的猜想,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,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在着色时用了n种颜色,我们称G为n-色的。最小着色数用x(G)表示。 虽然目前还没有一个简单的方法,可以确定任一图G是n-色的。但我们可以用韦尔奇鲍威尔(Welch Powell)对图G着色: a) 将图G中的结点按照度数的递减次序进行排列(这种排列可能并不是唯一的,因为有些点有相同度数); b) 用第一种颜色对第一点着色,并且并且按排列次序,对与前面着色点不邻接的每个点着上同一种颜色; c) 用第二种颜色对尚未着色的点重复b),用第三种颜色继续这种做法,直到所有点全部着上色为止。,定理1 对于n个结点的完全图Kn,有 x(Kn)=n。 证明:因为完全图的每个结点与其它各个结点都邻接,故n个结点的着色数不能少于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的结点称为分支点或 内点。一个无回路的无向图称作森林,它的每个 连通分图是树。,孤立结点可以看成是一个连通分支,但一般情况下 孤立结点不看成是一棵树。除非有特殊说明。,定理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中至少有两个结点度数为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),
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号