树17平面图及图着色.ppt

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