第七章 图与树.ppt

,第二级,第三级,第四级,第五级,欧拉简介,欧拉（,Leonhard Euler,公元,1707-1783,年）,1707,年出生在瑞士的巴塞尔（,Basel,）城，,13,岁就进巴塞尔大学读书，,15,毕业，,16,获得硕士学位，得到当时最有名的数学家约翰,伯努利的精心指导，欧拉是有名的数学家和自然科学家。,欧拉从,19,岁开始发表论文，直到,76,岁，据统计他那不倦的一生，共写下了,886,本书籍和论文，其中分析、代数、数论占,40%,，几何占,18%,，物理和力学占,28%,，天文学占,11%,，弹道学、航海学、建筑学等占,3%,，彼得堡科学院为了整理他的著作，足足忙四十七年。,1725,年约翰,伯努利的儿子丹尼尔,伯努利赴俄国，并向沙皇喀德林一世推荐了欧拉，这样，在,1727,年,5,月,17,日欧拉来到了彼得堡。,1733,年，年仅,26,岁的欧拉担任了彼得堡科学院数学教授。,1735,年，欧拉解决了一个天文学的难题（计算慧星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，三天便完成了。然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才,28,岁。,1741,年欧拉应普鲁士彼德烈大帝的邀请，到柏林担任科学院物理数学所所长，直到,1766,年，后来在沙皇喀德林二世的诚恳敦聘下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明。不幸的事情接踵而来，,1771,年彼得堡的大火灾殃及欧拉住宅，带病而失明的,64,岁的欧拉被围困在大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全部化为灰烬了。,在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑板上疾书他发现的公式，然后口述其内容，由他的学生特别是大儿子,A,欧拉（数学家和物理学家）笔录。欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，竟达,17,年之久。,欧拉的记忆力和心算能力是罕见的，他能够复述年青时代笔记的内容，心算并不限于简单的运算，高等数学一样可以用心算去完成。有一个例子足以说明他的本领，欧拉的两个学生把一个复杂的收敛级数的,17,项加起来，算到第,50,位数字，两人相差一个单位，欧拉为了确定究竟谁对，用心算进行全部运算，最后把错误找了出来。欧拉在失明的,17,年中；还解决了使牛顿头痛的月离问题和很多复杂的分析问题。,欧拉的风格是很高的，拉格朗日是稍后于欧拉的大数学家，从,19,岁起和欧拉通信，讨论等周问题的一般解法，这引起变分法的诞生。等周问题是欧拉多年来苦心考虑的问题，拉格朗日的解法，博得欧拉的热烈赞扬，,1759,年,10,月,2,日欧拉在回信中盛称拉格朗日的成就，并谦虚地压下自己在这方面较不成熟的作品暂不发表，使年青的拉格朗日的工作得以发表和流传，并赢得巨大的声誉。他晚年的时候，欧洲所有的数学家都把他当作老师，著名数学家拉普拉斯（,Laplace,）曾说过：,欧拉是我们的导师。,欧拉充沛的精力保持到最后一刻，,1783,年,9,月,18,日下午，欧拉为了庆祝他计算气球上升定律的成功，请朋友们吃饭，那时天王星刚发现不久，欧拉写出了计算天王星轨道的要领，还和他的孙子逗笑，喝完茶后，突然疾病发作，烟斗从手中落下，口里喃喃地说：,我死了,，欧拉终于,停止了生命和计算,。,欧拉的一生，是为数学发展而奋斗的一生，他那杰出的智慧，顽强的毅力，孜孜不倦的奋斗精神和高尚的科学道德，永远是值得我们学习的。欧拉还创设了许多数学符号，例如,（,1736,年），,e,（,1748,年），,sin,和,cos,（,1748,年），,tg,（,1753,年），,x,（,1755,年），,（,1755,年），,f(x,),（,1734,年）等。,图论起源：,哥尼斯堡七桥问题,在,18,世纪,普鲁士的哥尼斯堡镇被普雷格尔河分成,4,个部分。包括河两岸、中心岛以及两条支流之间所夹的部分,河上建有,7,座桥连接着小镇的,4,部分。,第七章 图论基础,7.1,图的基本概念,一、图的定义及有关术语,1,、图的定义 图是二元组,G=,其中,V,是节点集合，,E,是边集合。,2,、专业术语,无向边，有向边，平行边，自回路（环，其边的方向没有意义），邻接点，邻接边，孤立点，,3,、图的分类,有向图、无向图和混合图，简单图（不含平行边，自回路），完全图（每对节点之间有边相连）多重图（含平行边），边权图与点权图，平凡图（一个点）与零图（多个点，无边）,二、节点度,1,、节点度定义,deg(v,i,),表示与节点,v,i,相关连的边的条数，其中含环节点度加,2,。,2,、有向图节点度,节点入度：在有向图中，射入一个节点的边数称为该节点入度，记为,deg,(v,i,),；,节点出度：射出一个节点的边数为该节点的出度，记为,deg,+,(v,i,),；,节点度：,deg(v,i,)=deg,(v,i,)+deg,+,(v,i,),3,、节点的最大度和最小度,4,、定理,K,n,边的条数,:|,E|=n(n-1)/2,其中,n,为节点数,5,、任何图中，度数为奇数的节点必定是偶数个。,三、补图与子图,1,、补图定义,设图,G=,，其补图 ，为把,G,变成完全图后所增加的边的集合。,2,、子图定义,设图,G=,，如果有图,G,=,，其中,V,V,E,E,，则称,G,是,G,的子图。其中，如果,V,=V,E,E,，则称,G,为,G,的生成子图。,7.2,路、回路、图的连通性,一、路与回路,1,、路定义,设图,G=,，,v,0,v,1,v,n,V,e,0,e,1,e,n,E,e,i,为节点,v,i,和节点,v,i-1,之间的边，交替序列,v,0,e,1,v,1,e,2,e,n,v,n,，,为连接,v,0,和,v,n,之间的路。其中,v,0,为路的起点，,v,n,为路的终点。,(1),回路 如果,v,0,v,n,，这条路称回路。,(2),迹 若一条路中所有边不同，则称为迹。,(3),通路若一条路中所有点不同，则称为通路。,(4),圈 所有节点都不相同的回路叫圈。,例,1,v,1,到,v,4,的路：,v,1,e,1,v,5,e,5,v,4,，,v,1,e,2,v,2,e,6,v,3,e,4,v,4,2,、可达,设图,G=,，若,v,i,到,v,j,有路，,则称,v,i,可达,v,j,。,二、图的连通性,connectedness,1,、无向图的连通性,节点连通性,若节点,v,i,到,v,j,有路节点有路（可达），则节点是连通的。,例,2,：无向图节点之间的连通关系是等价关系。,(2),把无向图节点划分成若干非空子集,V,1,V,2,V,k,称子图,G(V,1,),G(V,2,),G(V,k,),是原图,G,的连通分支，令,W(G),为原图的连通分支数。其中,G,只有一个连通分支，则图,G,是连通图。,2,有向图,(1),连通性,强连通,:,在有向图,G=,中，如果任何一对节点之间相互可达，则该图为强连通。,单侧连通,:,若任意两个节点至少有一个可以到达，则称该图是单侧连通。,弱连通,:,若该有向图去掉方向后仍然连通，则该图是弱连通。,注：强连通必然单侧连通，单侧连通必然弱连通。,(2),有向图的分图,强分图：最大的强连通子图。,单侧分图：最大的单侧连通子图。,弱分图：最大的弱连通子图。,例,2,：,强分图：,v,1,v,2,v,3,v,4,v,5,v,6,单侧分图：,v,1,v,2,v,3,v,4,v,5,v,6,弱分图：,v,1,v,2,v,3,v,4,v,5,v,6,(3),强连通性质,一个有向图是强连通的,当且仅当,G,中有一个回路，它至少包含每个节点一次。,在一个有向图,G=,中，它的每个节点位于且只位于一个强分图中。,证明：设节点,v,在不同强分图,S,1,和,S,2,中，则,S,1,中所有节点与,v,可以相互到达，,S,2,中所有节点与,v,可以相互到达，则,S1,和,S2,中节点通过,v,可以相互到达。,三、无向图割集,1,、点割集,设无向联通图,G=,，若有,V,1,V,1,V,，图,G,删除,V,1,的所有节点后，所得子图不联通，删除,V,1,任何真子集后所得子图联通。其中,|V,1,|=1,则该结点称为割点。,K(G)=,min|V,i,|,V,i,是图点割集,为,G,点的联通度。,例,3,：,v,1,v,3,v,3,v,4,v,1,v,3,v,4,K(G)=2,例,4:,2,、边割集,设无向联通图,G=,，若有,E,1,E,1,E,，图,G,删除,E,1,的所有节点后，所得子图不联通，删除,E,1,任何真子集后所得子图联通。其中,|E,1,|=1,则该边称为割边或桥。,(G)=,min|E,i,|,E,i,是图边割集,为,G,边的联通度。,接上例,e,6,，,e,7,e,5,，,e,7,e,1,e,3,e,8,例,5:,e,4,为割边，,v,3,是割点，,K(G)=1,7.3,图的矩阵表示,一、邻接矩阵,adjacency matrix,1,、定义,设,G=,是一个简单图，,V=v,0,v,1,v,n,，则,n,阶方阵：,A(G)=(,a,ij,),nn,为邻接矩阵。,例,1,：求下图邻接矩阵（无向图）,A=,例,2,：求下图邻接矩阵（有向图）,总结：,对于无向图，行或列中,1,的个数就是该点的度数；,对于有向图，行中,1,的个数是该节点的出度，列中,1,的个数是该节点的入度；,简单无向图的邻接矩阵为对称的，有向图的邻接矩阵未必。,2,、应用,设,A(G),为图,G,的邻接矩阵，则,(,A(G),l,中第,i,行，,j,列的元素,(,a,l,ij,),等于,G,中连接,v,i,和,v,j,长度为,l,路的条数。,二、可达性矩阵,reachability,matrix,1,、定义,设,G=,是一个简单图，,V=v,0,v,1,v,n,，则,n,阶方阵,P(G)=(,p,ij,),nn,为可达矩阵。其中：,2,、求法,P=A+A,1,+A,2,A,n,对邻接矩阵用,warshall,算法,例,3,：,P(G)=,3,、应用（利用主对角线是否为,1,，判断图有无回路问题）,OS,判断死锁问题,设,4,个进程，分别为,P,1,P,2,P,3,P,4,4,种资源，,R,1,R,2,R,3,R,4,在,t,时刻，进程对资源的占有和申请情况如图所示。,P,1,拥有资源,R,4,，又去申请资源,R,1,P,2,拥有资源,R,1,，又去申请资源,R,2,P,3,拥有资源,R,2,，又去申请资源,R,3,P,4,拥有资源,R,3,，又去申请资源,R,4,递归调用,设过程集合,P,1,P,2,P,3,P,4,P,5,调用关系为,P,1,调用,P,2,P,2,调用,P,4,P,3,调用,P,1,P,4,调用,P,5,P,5,调用,P,2,P=,三、关联矩阵,incidence matrix,1,、无向图的关联矩阵,设,G=,是一个简单无向图，,V=v,0,v,1,v,n,，,E=e,0,e,1,e,t,则,M(G)=(,m,ij,),nt,为结点与边的关联矩阵。其中：,例,4,：,M=,性质：,边关联两个节点，所以,M(G),中每一列只含两个,1,；,每一行中元素的和对应该节点的度数；,一行中元素全为,0,，则为孤立节点；,两个平行边其对应的两列相同,。,2,、有向图的关联矩阵,设,G=,是一个简单有向图，,V=v,0,v,1,v,n,，,E=e,0,e,1,e,t,则,M(G)=(,m,ij,),nt,为结点与边的关联矩阵。其中：,例,5,：,M=,7.4,欧拉图和汉密尔顿图,一、欧拉图（,E,图）,1,、无向欧拉图,(1),、定义,给定无孤立节点图,G,，若存在一条路，经过图中每边一次且仅一次，该路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路；具有欧拉回路的图称作欧拉图。,(2),、判断,H,路：无向图,G,具有一条欧拉路，当且仅当,G,是连通的，且只有两个奇数度节点。,H,回路：无向图,G,具有一条欧拉回路，当且仅当,G,是连通的，并且所有节点度数全为偶数。,(3),、应用,中国一笔画问题,2,、有向图欧拉路,(1),、定义,给定无孤立节点有向图,G,，经过图中每边一次且仅一次的一条单向路,(,回路,),，称为单向欧拉路,(,回路,),。,(2),、判断,有向图,G,具有一条单向欧拉回路，当且仅当,G,是连通的，并且每节点的入度等于出度；具有一条单向欧拉路，当且仅当,G,是连通的，并且有一个节点的入度比出度多一，还有一节点出度比入度多一，而其余节点的入度等于出度。,(3),、应用,鼓风机设计问题,二、汉密尔顿图（,H,图）,1,、定义,给定图,G,，若存在一条路经过图中的每点恰好一次，这条路称作汉密尔顿路，若存在一条回路经过图中的每点恰好一次，这回路称作汉密尔顿回路。,2,、判断,(1),、必要条件,若图,G,含有,H,回路，则对于结点,V,的每一个非空子集,S,均有,W(G-S)|S|,成立。,(2),、充分条件,设,G,具有,n,个节点的简单图，如果,G,中每一对节点度数之和大于等于,n,，则在,G,中存在一条汉密尔顿回路。,(,充分条件,),设,G,具有,n,个节点的简单图，如果,G,中每一对节点度数之和大于等于,n-1,，则在,G,中存在一条汉密尔顿路。,7.4,平面图,planer graph,一、基本概念,1,、定义,设,G=,是一个无向图，如果能够把,G,的所有节点和边画在平面上，且使得任何两条边除了端点外没有其他的交点，称图,G,为平面图。（如 交通道路的设计问题）,例,1,：,2,、典型的非平面图,(K,5,K,3,3,),3,、平面图术语,平面图的面（有限面，无限面）,面的次数,deg(r,i,),例,2,：,r,1,是一个无限面，,r,2,正常的面，,r,3,包含一个悬挂边的面，这使面次数增,2,。,二、平面图的性质,1,、有限平面图，面的次数之和等于其边数的两倍。,2,、欧拉定理,一个连通的平面图,G,，共有,v,个节点,e,条边和,r,个面，则有下面的欧拉公式成立：,v-e+r,=2,3,、平面图判定定理（非平面）,设,G,是,v,个节点,e,条边的联通简单平面图，如果,v3,则,e3v-6,。,证明：设,v=3,时，,e=2,可见,e3v-6,成立；,e3,时，,deg(r,i,)3,又因为,v-e+r,=2,，所以,2+e-v(2e)/3,，所以,e3v-6,例,3,：,对于,K5,有,3*5-6=99,，该图满足定理但不是平面图。,7.6,对偶图、图的着色,起源于地图地着色问题，地图相邻国家不上同一种颜色，最少需要多少种颜色。,100,多年前，英国地格色里提出了四色猜想，,1879,年肯普给出了这个猜想的第一个证明，但是,1890,年希五德发现这个证明是错的，他指出用五种颜色，提出五色定理，后来四色猜想一直是当时的数学家们感兴趣的问题而未解决的难题，到,1976,年，美国数学家阿佩尔和黑肯宣布，用计算机证明了四色猜想是成立的，所以,1976,年后把四色猜想改成四色定理了。,一、对偶图,dual graph,1,、定义,设平面图,G=,若图,G,*,=,满足如下条件：,(1),在任意面,r,i,内部取一个点,v,*,i,V,*,;,(2),设边,e,k,是面,r,i,和,r,j,的公共边，则,e,*,k,=(v,*,i,v,*,j,),，并且,e,*,k,与,e,k,相交,其中：,v,*,i,v,*,j,V,*,。,(3),如果,e,k,是面,r,i,内的悬挂边，,在面,r,i,内取点,v,*,i,，则,v,*,i,存在一个环与,e,k,相交。,2,、性质,G,*,的节点数等于,G,的面数,G,*,的边条数等于,G,边条数,二、图的着色,1,、图色数,图,G,中对每个结点着上不同颜色，使得每对相邻接结点着的颜色不同，则图,G,中需要的最少颜色数称为该图的着色数，记为,x(G,),。,例,1,：,x(G,)=3,例,2,：对于,n,个结点的完全图,K,n,，有,x(K,n,)=n,。,图的着色相当于对其对偶图结点的着色。,2,、韦尔奇,.,饱威尔法,(1),将图,G,中的节点按照度数的递减次序进行排列；,(2),用第一种颜色对第一个点着色，并且按排列次序，对与前面着色点不邻接的每一点着上同样的颜色；,(3),用第二种颜色对尚未着色的点重复,2,，如此反复，直到所有点均着色。,例,3,：,deg(v,1,)=5,deg(v,5,)=5,deg(v,7,)=3,deg(v,3,)=3,deg(v,4,)=3,deg(v,6,)=2,deg(v,2,)=2,7.7,无向树,一、基本概念,1,、定义,一个连通且无回路的无向图称为树；,树叶：度数为一的节点；,分枝点或内点：度数大于一的结点,2,、树的等价定义,给定图,T,，下面树的定义等价：,(1),无回路的连通图；,(2),无回路且,e=v-1,，其中,e,是边数，,v,是结点数；,(3),连通且,e=v-1,；,(4),无回路，但增加一条边，得到一个且仅有一个回路；,(5),任意边为割边的连通图；,(6),每一对结点之间有一条且仅有一条路。,3,、性质,任一棵树中至少有两片树叶。,证明：因为,T,是联通图，所以任意,deg(v,i,),1,，如果图中每个节点度数都大于等于,2(,没有树叶,),，所以矛盾。若图中只有一个树叶，其它节点度数都大于等于,2,，则 ，也得出矛盾。,二、生成树,spanning tree,1,、定义,若图,G,的生成子图是一棵树，则该树称为,G,的生成树。,(,归纳法,),2,、性质,连通图至少有一颗生成树。,(,用构造生成树的方法证明,),一条回路和任何一颗生成树的补至少有一条公共边。,一个边割集和任何生成树至少有一条公共边。,三、最小生成树,1,、定义,设,G,是联通的边权图，,G,的某一生成树,T,有一个树权,C(T),，它是,T,的所有边权的和。,2,、最小生成树,在图,G,的所有生成树中，树权最小的那棵生成树称为最小生成树。,3,、最小生成树算法,破圈法：（普里目算法）去权值最大的边，去的时候注意保证图的联通性。,避圈法：（,Kruskal,）加入权值最小的边，加的时候注意不出现回路。,7.8,有向树,directed tree,一、基本概念,1,、定义,如果一棵有向树有且只有一个结点入度为,0,，其余结点的入度为,1,，称这种有向树为根树；入度为,0,的点称为根，出度为,0,的点称为叶，其余点称为内点或分枝点；从根到任意结点,v,的单向通路长度（边条数）称为,v,的层次；树的次序一般是从上到下、从左到右。,2,、递归定义,树根包含一个或多个子结点，这些子结点中的某一个又可以称为根，其他所有结点又被分成有限个子根树。,画法：,1,、向上生长；,2,、向下生长。,二、,m,叉树,1,、定义,在根树中，若每一个结点的出度小于或等于,m,，称这棵树为,m,叉树；,如果每一个结点的度数恰好为,0,或,m,，称这棵树为完全,m,叉树；,若所有树叶的层次相同，称为正则,m,叉树。,2,、性质,完全,m,叉树，其叶结点数为,t,，分支点数为,i,，则,(m-1)i=t-1,。,3,、二叉树的通路长度,根树中，一个结点的通路长度，就是从树根到此结点的通路的边数；,分枝点的通路长度称为内部通路长度，树叶的通路长度称为外部通路长度。,若完全二叉树有,n,个分枝点，且内部通路长度的总和为,I,，外部通路长度的总和为,E,，则,E=I+2n,。,三、最优树,optimal tree,这部分课件没做，按照上课讲解的最有二叉树,