16树17平面图及图着色

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,16.,树,16.1,无向树及其性质,定义,16.1,:,连通且无回路的无向图称为无向树。用,T,表示,T,中次数为,1,的点称为树叶,次数大于,1,的结点称为分支点或内部结点。非连通图的每个连通分支是树的无向图称为森林。,1,16.,树,16.1,无向树及其性质,图中,v,1,到,v,6,都是树叶,其他结点是内部结点,v,1,v,4,v,3,v,6,v,5,v,2,2,16.,树,16.1,无向树及其性质,定理,16. 1,:,无向图,T,是树,当且仅当,以下命题之一成立。,T,是连通且无回路,T,无回路且,m=n-1,其中,|V|=n,|E|=m,T,连通且,m=n-1,T,无回路,但增加一边后得到且仅得一个圈,T,连通,但删去任一边后就不连通,每一对结点间有且仅有一条路径。,3,16.,树,16.1,无向树及其性质,证明,:,(1) T,是连通且无回路,（,2,）,T,无回路且,m=n-1,当,n=2,时,连通无回路则,m=1,满足,m=n-1,设,n=k,时结论成立。,当,n=k+1,时,因,T,连通无回路,所以至少有一点的度数为,1,在,T,中删去该点及相关联的边得到,k,个结点的连通且无回路的图,由归纳假设知它有,k-1,条边,故,n=k+1,时,有,k,条边,故结论在,n=k+1,时成立。,4,16.,树,16.1,无向树及其性质,(2),T,无回路且,m=n-1,(,3),T,连通且,m=n-1,只要证明连通即可,反证如,T,不连通,设,T,的连通分支数为,k,k1,每个连通分支是树,点数为,n,1,n,2,n,k,边数则由（,2,）知为,n,1,-1,n,2,-1,n,k,-1,m=n,1,+n,2,+,+,n,k,-k,=n-kn-1,矛盾,故,T,是连通的。,(3),(,4),T,无回路,但增加一边后得到且仅得一个圈,由归纳法可以证明,T,是无回路的（略）,任取两点,u,v,V,因,T,连通故,uv,间有一条路,P,。将,uv,两点间加一条边则必构成回路,如,uv,u,v,P,v,1,v,2,v,u,5,16.,树,16.1,无向树及其性质,若两点间一条边构成两个回路,uv,1,v,和,uv,2,v,则原来的图就有回路,uv,1,vv,2,u,。,(4),T,无回路,但增加一边后得到且仅得一个圈,(,5),T,连通,但删去任一边后就不连通,任取两结点,u,vV,加上边,(u,v),就构成回路,uv,v,1,u,则原来,u,到,v,之间就有一条通路,uv,1,v,T,中任取一条边,eE,e=(u,v),如果删,掉,e,仍连通,u,到,v,另有,一条路,则原来就有回路。,v,1,v,u,6,16.,树,16.1,无向树及其性质,(5),(,6),反证如果两结点间有两条通路,则该图必有回路则删去回路上的一边,T,仍是连通的与,(5),矛盾。,(6),(,1),任两点间均有路,则,T,是连通的,反证如,T,是有回路的,则必存在两点,使该两点间有两条路,与（,6,）矛盾。,7,16.,树,16.1,无向树及其性质,定理,16.2,:,设,T,是,n,阶非平凡的无向树,则,T,至少存在两个叶,(n2,时,),。,证明,：,因,T,连通则,v,T,，,deg(v),1,设,T,有,k,个一度点,其它点度数均大于等于,2,，则,2m=,deg(v,i,),k+2(n-k)=2n-k,因,m=n-1,2,（,n-1,）,2n-k,则,k,2,。,8,16.,树,16.1,无向树及其性质,例,：,设,T=,是树,如,|V|=20,树叶共有,8,个,其它点的度数均,3,问：,2,度点和,3,度点各有多少？,解,:,设,2,度点为,x,个,则,3,度点为,20-8-X,。,因,2m=,deg(v,i,),而,m=n-1,2,(20-1)=1,8+2x+3(20-8-x),解为,x=6,则,3,度点共有,20-8-6=6,。,9,16.,树,16.2,生成树,定义,16. 3,:,设,T,是无向图,G,的子图并且为树，则称,T,为,G,的树。若无向,图,G,的,生成子图,是一棵树,则称这棵树为,G,的生成树或支撑树,设,G,的一棵生成树为,T,则,T,中的边称为,树枝,在,G,中而不在,T,中的边称,弦,所有弦的集合称为,生成树,T,的余树,。,e,3,e,2,e,4,e,6,e,5,e,7,e,8,e,9,e,1,e,10,e,1,e,3,e,9,e,8,e,6,e,2,e,9,e,4,e,7,e,5,e,2,e,10,10,16.,树,16.2,生成树,定理,16. 3,:,无向图,G,具有生成树当且仅当,G,是连通图。,证明,:,充分性，如果,G,无回路,则,G,本身就是它的生成树,如,G,有回路,则在回路上任取一条边并去掉后仍是连通的,如,G,仍有回路,则继续在该回路上去掉一条边,直到图中无回路为止,此时该图就是,G,的一棵生成树。,11,16.,树,16.2,生成树,推论,1,设,G,为,n,阶,m,条边的无向连通图，则,m,n-1,推论,2,设,G,是,n,阶,m,条边的无向连通图，,T,为,G,的生成树，则,T,的余树中含有,m-n+1,条边,推论,3,设,T,是连通图,G,的一棵生成树，,T,为,T,的余树，,C,为,G,中任意一个圈，则,E(T),E(C),不为空。,定理,16. 4,设,T,为无向连通图,G,中一棵生成树，,e,为,T,的任意一条弦，则,T,e,中含,G,中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈也不同。,12,16.,树,16.2,生成树,一般如果,G,有,n,个点,m,条边连通,则,m,n-1,因为,G,的生成树有,n-1,条边，,则,G,要,删除,m-(n-1),条边。,破坏了,m-(n-1),个回路，必成,G,的一棵生成树,这是,”,破圈法,”,。也可以从,m,条边中选取,n-1,条边并使它不含有回路,这是,”,避圈法,”,。,定义,16.3,此,m-(n-1),个基本回路称为图,G,的关于树,T,的基本回路系统。,i,e,b,a,h,d,c,f,g,13,16.,树,16.2,生成树,定理,16.5,设,T,是连通图,G,的一棵生成树，,e,为,T,的树枝，则,G,中存在只含有树枝,e,，其它边都是弦的割集，且不同的树枝对应的割集也不同。,定义,16.4 T,是,n,阶连通图,G,的一棵生成树。从树,T,中删去一条枝，将,T,分为两棵树，,G,的顶点集划分为两个子集，连结这两个子集的边集就是对应于这条枝的割集，称为对应于这条边的基本割集。,14,16.,树,16.2,生成树,如左图中，树枝集是,e,1,e,2,e,3,e,9,e,6,e,8,，,则,对应于,e,1,的基本割集是,e,1,e,4,对应于,e,2,的基本割集是,e,2,e,10,e,5,e,4,对应于,e,3,的基本割集是,e,3,e,5,e,10,对应于,e,9,的基本割集是,e,9,e,4,e,7,e,5,对应于,e,6,的基本割集是,e,6,e,7,e,5,对应于,e,8,的基本割集是,e,5,e,8,e,1,e,3,e,9,e,8,e,6,e,2,e,3,e,2,e,4,e,6,e,5,e,7,e,8,e,9,e,1,e,10,15,16.,树,16.2,生成树,注意：基本割集中，只有一条边是树枝。,如果有,n-1,条枝，一般可以得到,n-1,个基本割集，称为图,G,的关于生成树,T,的基本割集系统。,16,16.,树,16.2,生成树,设,G=,是一带权无向连通图,G,的生成树,T,的权,W,（,T,）,就是,T,中树枝的权之和。,记为：,W,（,T,）,=,在带权图,G,所有生成树中,权最小的那棵树称为,G,的最小生成树。,17,16.,树,16.2,生成树,求最小生成树的克鲁斯卡尔算法,(,Kruskal,),1.,在,G(n,m),中选取权最小的边,记作,e,1,置,i=1,2.,当,i=n-1,时结束,否则转,3,。,3.,设已选择边为,e,1,e,2,e,I,此时无回路。,在,G,中除这,i,条边外,选择边,e,i+1,该边使得,e,1,e,i+1,生成的子图中无回路,并,e,i+1,是满足该条件中权最小的一条边。,4.,置,i:=i+1,转,2,。,18,16.,树,16.2,生成树,例,:G,有,6,个点,10,条边,求最小生成树,。,6,14,7,10,5,12,9,1,8,16,1,1,5,1,5,6,5,6,1,9,7,选取了,5,条边,始终保持无回 路,而且是连通的,w(T)=28,19,16.,树,16.2,生成树,这种算法也可以适用于边权任意情况。,只是所求得的最小生成树不唯一。,6,14,4,10,5,12,9,1,4,16,1,1,5,1,5,6,5,6,1,9,4,4,4,4,w(T)=21,20,16.,树,16.3,根树及其应用,定义,16.6,:,设,T,是,n,（,n2,）阶有向树，若,T,中有一个顶点的入度为,0,，其余顶点的入度均为,1,，则称,T,是根树。引入次数为,O,的结点称为树根。入度为,1,出度为,0,的点称为树叶。入度为,1,出度不为零的点称为内点。,树根到一个结点的通路的长度称为该点的层数，层数最大顶点的层数称为树高,。平凡树也称为根树。,21,16.,树,16.3,根树及其应用,图中,v,1,是树根, v,2, v,4,v,7, v,10,是内点,v,3, v,5, v,6, v,8, v,9, v,11,v,12, v,13,是树叶。,习惯把有向树的根画在最上方,边的箭头全指向下,则可以省略全部箭头。上图树高为,4,。,v,1,v,11,v,12,v,9,v,6,v,5,v,13,v,7,v,8,v,4,v,3,v,2,v,10,22,16.,树,16.3,根树及其应用,定义,16.7,：,在非平凡根树,T,中,若,a,可达,b,则称,a,是,b,的祖先,b,是,a,的后,裔（后代）,如果,ab,，,那么,a,是,b,的一个真祖先而,b,是,a,的一个真后裔。,若,是,有向树的边,则称,a,是,b,的父亲,b,是,a,的儿子,同一结点的儿子称为兄弟。,23,16.,树,16.3,根树及其应用,许多家谱都可以用,有向树表示。,图中,v,1,是,v,2,的父亲，,v,2,是,v,1,的儿子, v,2, v,5, v,6,构成的子图是,T,的子树且是真子树。,v,1,是,v,5,的祖先，,v,5,是,v,1,的后裔, v,1,有,3,个儿子分别是,v,2, v,3, v,4,他们互为兄弟,。,v,1,v,11,v,12,v,9,v,6,v,5,v,13,v,7,v,8,v,4,v,3,v,2,v,10,24,16.,树,16.3,根树及其应用,1,）,在有向树中若每个结点的出度均,m,则称,T,为,m,元树,(m,叉树,)(,即每个点至多有,m,个儿子,),若,m,元树是有序的,则称为,m,元有序树。,2,）若,T,每个分支点的出度等于,m,则称,T,为,m,叉正则树。若,T,是有序的，则称为,m,叉正则有序树。,3,）若,T,是,m,叉正则树，且每个树叶的层数均为树高，则称,T,为,m,叉完全正则树。若,T,是有序的，则称为,m,叉完全正则有序树。,25,16.,树,16.3,根树及其应用,例,:,2,元树,2,元正则树,26,16.,树,16.3,根树及其应用,定义,16.8,设,T,是根树，任意,T,中结点,v,，称,v,及其后代的导出子图,T,v,为,T,的以,v,为根的根子树。,2,叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树。,定义,16.9,设,2,叉树,T,有,t,片树叶,v,1, v,2,v,t,，权分别为,w,1, w,2, w,t,，称 为,T,的权，其中,l(v,1,),是,v,i,的层数。在所有有,t,片树叶，带权,w,1, w,2, w,t,的,2,叉树中，权最小的,2,叉树称为最优,2,叉树。,27,16.,树,16.3,根树及其应用,2,2,3,5,3,5,3,3,2,2,3,2,2,3,5,38,36,47,28,16.,树,16.3,根树及其应用,Huffman,算法：,给定实数,w,1, w,2, w,t,，且,w,1,w,2, w,t,。,1,）连接权为,w,1, w,2,的两片树叶，得一个分支点，其权为,w,1,w,2,。,2,）在,w,1,+w,2,w,3, w,t,中选两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。,3,）重复,2,）直到形成,t,1,各分支点，,t,片树叶为止。,29,16.,树,16.3,根树及其应用,定义,16.10,设,1,2,n-1,n,为长为,n,的符号串，称其子串,1, ,1,2, ,1,2,n-1,分别为该符号串的长度为,1,，,2,，,n,1,的前缀。设,A=,1, ,2,m,为一个符号串集合，若对于,A,中任意的,i,j,ij,i,j,互不为前缀，则称,A,为前缀码。若符号串,i,(i,=1,2m),中只出现,0,1,两个符号，则称,A,为二元前缀码。,30,16.,树,16.3,根树及其应用,设,T,是具有,t,片树叶的,2,叉树，则,T,的每个分支点有,1,到,2,个儿子。设,v,为,T,的分支点，若,v,有两个儿子，在由,v,引出的两条边上，左边的标上,0,，右边的标上,1,。若,v,只有一个儿子，由它引出的边可以标上,0,也可以标上,1,。设,v,i,是,T,的任意一片树叶，从树根到,v,i,的通路上各边的标号按通路上的顺序组成的符号串放在,v,i,处，则,t,片树叶处,t,各符号串组成的集合为一个二元前缀码。由做法可知，树叶,v,i,处的符号串的前缀均在,v,i,所在的通路上除,v,i,处的顶点处达到，因而所得的符号串集合必为前缀码。若,T,是正则,2,叉树，则由,T,产生的前缀码是唯一的。,31,16.,树,16.3,根树及其应用,定理,16.6,由一棵给定的,2,叉正则树，可以产生唯一的一个二元前缀码。,32,16.,树,16.3,根树及其应用,二叉树的周游：,对一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树。,1,）中序行遍法：访问的次序为，左子树，树根，右子树。,2,）前序行遍法：访问的次序为，树根，左子树，右子树。,3,）后序行遍法：访问的次序为，左子树，右子树，树根。,33,16.,树,16.3,根树及其应用,(,hdi)be)a(fcg,),中序,a(b(dhi)e)(cfg,),前序,(,hid)eb)(fgc)a,后序,e,g,f,h,i,b,c,a,d,34,17.,平面图及图的着色,17.1,基本概念,先看一个例子：,有六个结点的图如上，,试问：能否转变成与其等价的，但没有任何相交线的平面上的图？,结论：不能,35,17.,平面图及图的着色,17.1,基本概念,定义,17.1,：一个图,G,，,如果能把它图示在一曲面,S,上，边与边只在顶点处相交，则称图,G,可嵌入曲面,S,。若图,G,可嵌入平面，则,称为,平面图,。画出的无边相交的图称为,G,的平面嵌入，无平面嵌入的图称为,非平面图,。,上述例的图是非平面图。,讨论定义：,（,1,）平面上的图，一开始就画成如定义所讲的图；,36,17.,平面图及图的着色,17.1,基本概念,（,2,）,原来在平面上的图形似交叉，,但经过若干次的改画后，变成符合定义所规定的图；,37,17.,平面图及图的着色,17.1,基本概念,（,3,）下列图形均为非平面图,38,17.,平面图及图的着色,17.1,基本概念,定理,17.1,若图,G,是平面图，则,G,的任何子图都是平面图。,定理,17.2,若图,G,是非平面图，则,G,的任何母图都是非平面图。,推论,K,n,（,n5,）和,K,3,n,（,n3,）都是非平面图。,定理,17.3,设,G,是平面图，则在,G,中加平行边或环后所得图还是平面图。,39,17.,平面图及图的着色,17.1,基本概念,定义,17.2,设,G,是平面图（且已经平面嵌入），由,G,的边将,G,所在的平面划分成若干个区域，每个区域称为,G,的一个面。其中面积无限的称为无限面或外部面，其中面积有限的称为有限面或内部面。包围每个面的所有边组成的回路组称为该面的边界，边界的长度称为面的次数。,40,17.,平面图及图的着色,17.1,基本概念,例：,41,17.,平面图及图的着色,17.1,基本概念,定理,17.4,平面图,G,中所有面的次数之和等于边数,m,的两倍，即,其中,r,为,G,的面数。,定义,17.3,设,G,为简单平面图，若在,G,的任意不相邻的顶点,u,，,v,之间加边,(,u,v,),，所得图为非平面图， 则称,G,为极大平面图。,42,17.,平面图及图的着色,17.1,基本概念,定理,17.5,极大平面图是连通的。,定理,17.6,设,G,为,n,（,n3,）阶极大平面图，则,G,中不可能存在割点和桥。,定理,17.7,设,G,为,n,（,n3,）,阶简单连通的平面图，,G,为极大平面图当且仅当,G,的每个面的次数均为,3,。,定义,17.4,若在非平面图,G,中任意删除一条边，所得图为平面图，则称,G,为极小非平面图。,43,17.,平面图及图的着色,17.2,欧拉公式,定理,17.8,设平面连通图,G,是具有,k,个面（包括无限面）的,(n,e),多边形图，则它一定有,n-e+k=2,成立。,证明：用数学归纳法证明，（书上对边进行归纳，这里对面进行归纳）,归纳基础：面的最小数为,k=2,，则,G,为一多边形，且,e=n=3,（,e=n=4,），,得,n-e+k=3-3+2=2,成立，,或,n-e+k=4-4+2=2,成立,；,44,17.,平面图及图的着色,17.2,欧拉公式,归纳步骤：,设,图,G,的面为,k,时，等式成立，即,n-e+k=2,成立。,要证明当面为,k,时，等式也成立就行,（,k=k+1,）,(a),先构成图,G,，,其中,点数为,n,边数为,e,面数为,k=k-1,；,(b),然后在,G,中，加入一条长度为,L,的基本路径（,L1,）,且与,G,共有二个结点，从而使,G,变为,G,；,45,17.,平面图及图的着色,17.2,欧拉公式,(c) n-e+k,=n+(L-1)-(e+L)+(k+1),=n+L-1-e-L+k+1,=n-e+k,=2,成立,定理成立,46,17.,平面图及图的着色,17.2,欧拉公式,定理,17.9,对于具有,k(k2),个连通分支的平面图,G,，有,n-m+r,=k+1,其中,n,m,r,分别为,G,的顶点数，边数和面数。,定理,17.10,设,G,是连通的平面图，且每个面的次数至少为,l,（,l3,），则,G,的边数,m,与顶点数,n,有如下关系：,推论,K,5,和,K,3,3,不是平面图,47,17.,平面图及图的着色,17.2,欧拉公式,定理,17.11,设,G,是具有,k(k2),个连通分支的平面图，且每个面的次数至少为,l,（,l3,），则,G,的边数,m,与顶点数,n,有如下关系：,48,17.,平面图及图的着色,17.2,欧拉公式,定理,17.12,：在,n3,的简单连通平面图,(n,m),中有,3n-6m,。,证明：,G,为简单连通平面图，,每一面至少用三条或更多条边构成，,=,所有面的边的总数。,因此边的总数,3k,（,包含重复计算的边）,K,是面数。,49,17.,平面图及图的着色,17.2,欧拉公式,例：,一条边是在至多二个面的边界中，,各面的实际总边数一定有,3k,（ ,2m,）（,实际边）,即有， 成立,50,17.,平面图及图的着色,17.2,欧拉公式,例：,由欧拉定理：,51,17.,平面图及图的着色,17.2,欧拉公式,例：由此也可证明，,K,5,图不是平面图,K,5,图中，,n=5,m=10,3*5-6=910, K,5,图,不为平面图,定理,17.13,设,G,是,n(n3),阶,m,条边的极大平面图，则,m,3n-6,52,17.,平面图及图的着色,17.2,欧拉公式,定理,17.14,设,G,是简单平面图，则,G,的最小度小于等于,5,。,53,17.,平面图及图的着色,17.3,定义,k,3,3,和,k,5,称为库拉托夫斯基图。,给定两个图,我们做以下的工作：,观察次数为,2,的结点：,(,),在左边图的中间联线上插入一个次数为,2,的结点，则把一条边分成了二条边；,(,),在右边图中去掉一个次数为,2,的结点，则把二条边变成一条边。,此二项工作不会改变平面图的性质。,54,17.,平面图及图的着色,17.3,定义,17.6,：设,G,1,、,G,2,是二个图，若,可以插入或删除次数为,2,的结点,，使得,G,1,和,G,2,同构，则称,G,1,、,G,2,为,2,度顶,点内同构（或同胚）。,例：下列二对图,是,2,度顶点内同构,55,17.,平面图及图的着色,17.3,定理,17.15,：（,Kuratowski,定理）,设,G,是一个图，当且仅当,G,不包含任何在,2,度顶点内与库拉托夫斯基图同构的子图,时，则,G,才是平面图。,定理,17.16,图,G,是平面图当且仅当,G,中没有可以收缩到库拉托夫斯基图的子图。,56,17.,平面图及图的着色,17.4,对偶图,只有平面图才有对偶图。,设为平面图，则的对偶图为,G*,，且,G*,也为平面图。求图的对偶图的方法如下：,(1),将图,G,所有的面,F,i,（,包括无限面）对应于,G*,的结点,f,i,；,(2),对应二个相邻的面,F,i,F,j,（即,F,i,F,j,之间有公共边,e,k,），,对于每个公共边在,f,i,f,j,之间作一条连线（即形成一条边（,f,i,f,j,）；,(3),当且仅当,e,k,只是,F,i,的边界时，,f,i,恰,存在一条自回路与,e,k,相交。,57,17.,平面图及图的着色,17.4,对偶图,所得到的图即是图,G,的对偶图，记为,G*,。,例：,58,17.,平面图及图的着色,17.4,对偶图,例：求的对偶图,59,17.,平面图及图的着色,17.4,对偶图,定理,17.17,设,G*,是连通平面图,G,的对偶图，,n*,m*,r*,和,n,m,r,分别为,G*,和,G,的顶点数，边数和面数，则,1,）,n*=r,2) m*=m,3) r*=n,4),设,G*,的顶点,v,i,*,位于,G,的面,R,i,中，则,d,G,*,(,v,i,*,)=,deg(R,i,),。,60,17.,平面图及图的着色,17.4,对偶图,定理,17.18,设,G*,是具有,k(k2),个连通分支的平面图,G,的对偶图，,n*,m*,r*,和,n,m,r,分别为,G*,和,G,的顶点数，边数和面数，则,1,）,n*=r,2) m*=m,3) r*=n-k+1,4),设,G*,的顶点,v,i,*,位于,G,的面,R,i,中，则,d,G,*,(,v,i,*,)=,deg(R,i,),。,61,17.,平面图及图的着色,17.4,对偶图,定义,17.18,：若,G,的对偶图,G*,同构于,G,，,则称,G,为,自对偶图,。,例：正则平面图的对偶图为自对偶图，,同构函数为：,f:1,2,3,4 a,b,c,d,f(1)=a,f(2)=b,f(3)=c,f(4)=d,62,17.,平面图及图的着色,17.5,图的着色,对于给平面图着色，可对应给图的对偶图的结点进行着色，只要对偶图中任何二个相邻结点的颜色不同，就可给该平面图着色。,定义,17.9,给,图,G,的正常着色（简称着色）是指对它每一个结点指定一种颜色，使得没有二个相邻结点有相同的颜色，若,用了,n,种颜色着色，则称,G,为,n,色的,，而对,G,用最少的颜色进行着色，称最少的颜色数为色数，记作,x(G),。,63,17.,平面图及图的着色,17.5,图的着色,下面先介绍,韦尔奇,鲍威尔,（,Welch.powell,）,法对图进行着色：,例：用韦尔奇,鲍威尔法对图着色,（,1,）将图中结点数依照度数的递减次序进行排列（当然这样排列不一定是唯一的）；,64,17.,平面图及图的着色,17.5,图的着色,右图根据结点度数以递减排列次序为：,(6) (5) (5) (4) (4) (4) (3) (3),（,2,）对,5,着第一种颜色，,并对与,5,不相邻的结点,1,着与,5,同样的颜色；,（,3,）对,3,和与,3,不相邻,的结点,4,、,8,着第二种颜,色,对,7,和与,7,不相邻的结,点,2,、,6,着第三种颜色，,这样全部着色完毕。,65,17.,平面图及图的着色,17.5,图的着色,定理,17.26,：,用,种颜色,可以给,任何简单连通平面图正常着色,。,定理,：对于有,n,个结点的完全图,K,n,，有,x(K,n,)=n,。,证明：,在完全图中，每一个结点与其他结点相邻接,n,个结点的着色数不能小于,n,又,n,个结点的着色数最少为,n,有,x(K,n,)=n,成立,（注意：当时,n4,，,K,n,为平面图，,n5,，,则为,K,n,非平面图）,66,17.,平面图及图的着色,17.5,图的着色,例：大学中,7,门考试，以下课程中有公共学生，,12,；,13,；,14,；,17,；,23,；,24,；,25,；,27,；,34,；,36,；,37,；,45,；,46,；,56,；,57,；,67,；问如何在尽可能少的时间段里安排,7,门考试并使得没有学生在同一时间里有两门考试。,3,2,5,4,7,6,1,安排如下：,时间段 课程,1,1,2,2,，,6,3,3,，,5,4,4,，,7,67,