离散数学-图论基础名师优质课获奖市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,第七章 图论基础,Graphs,第1页,第一节 图基本概念,一个图,G,定义为一个三元组：,G=,V,非空有限集合，,V,中元素称为,结点,(node),或,顶点,(vertex),E,有限集合（能够为空），,E,中元素称为,边,(edge),从,E,到,V,有序对或无序正确,关联映射,(associative mapping),v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),第2页,06 五月 2025,图基本概念,图,G=,中每条边都与图中无序对或有序对联络,若边,e,E,与无序对结点,v,a,v,b,相联络，即,(,e)=,v,a,v,b,（v,a,v,b,V）,则称,e,是,无向边,（或边、棱）,若边,e,E,与有序对结点,相联络，即,(,e)=（v,a,v,b,V）,则称,e,是,有向边,（或,弧,）,v,a,是,e,起始结点,，,v,b,是,e,终止点,v,1,v,2,v,3,(,a),v,1,v,2v,3,(,b),v,1,v,2,v,3,(,c),第3页,06 五月 2025,图基本概念,若,v,a,和,v,b,与边（弧）,e,相联结，则称,v,a,和,v,b,是,e,端结点,v,a,和,v,b,是,邻接结点,，记作：,v,a,adj v,b,(adjoin),也称,e,关联,v,a,和,v,b,，,或称,v,a,和,v,b,关联,e,若,v,a,和,v,b,不与任何边（弧）相联结，则称,v,a,和,v,b,是,非邻接结点,，记作：,v,a,nadj v,b,关联同一个结点两条边（弧），称为,邻接边,（弧）,关联同一个结点及其本身边，称为,环,(cycle),，环方向没有意义,v,1v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),第4页,06 五月 2025,图基本概念,若将图,G,中每条边（弧）都看作联结两个结点则,G,简记为：,每条边都是弧图，称为,有向图,(directed graph),（如图,b）,每条边都是无向边图，称为,无向图,(undirected graph),（如图,a）,有些边是弧，有些边是无向边图，称为,混合图,（如图,c）,v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),第5页,06 五月 2025,图基本概念,若图,G,中任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称,G,为,简单图,（如图,c）,若图,G,中某两个结点之间多于一条无向边（或多于一条同向弧），则称,G,为,多重图,（如图,a,b）,两个结点间多条边（同向弧）称为,平行边（弧）,，平行边（弧）条数，称为,重数,v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),第6页,06 五月 2025,图基本概念,在多重图表示中，可在边（弧）上标注正整数，以表示平行边（弧）重数,把重数作为分配给边（弧）上数，称为,权,(weight),将权概念普通化，使其不一定是正整数，则得到加权图概念：,给每条边（弧）都赋予权图，叫做,加权图,(weighted graph),记作,G=，,W,是各边权之和,v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),1,1,1,1,1,1,2,2,1,1,第7页,06 五月 2025,图基本概念,在无向图,G=,中，,V,中每个结点都与其余全部结点邻接，即(,v,a,)(,v,b,)(,v,a,v,b,V,v,a,v,b,E,)，如图(,a),则称该图为,无向完全图,(complete graph),，记作,K,|V|,若|,V|=n，,则|,E|=C,=n(n-1)/2,v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),2,n,第8页,06 五月 2025,图基本概念,在有向图,G=,中，,V,中任意两个结点间都有方向相反两条弧，即(,v,a,)(,v,b,)(,v,a,v,b,V,E,E,)，如图(,a),则称该图为,有向完全图,，记作,K,|V|,若|,V|=n，,则|,E|=P =n(n-1),v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),2,n,第9页,06 五月 2025,图基本概念,在图,G=,中，若有一个结点不与其它任何结点邻接则该结点称为,孤立结点,，,如图(,a),中,v,4,仅有孤立结点图，称为,零图,，零图,E=,，,如图(,b),仅有一个孤立结点图，称为,平凡图,(,trivial graph,),，,如图(,c),v,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,(,c),v,4,第10页,06 五月 2025,问题,问题,1,：是否存在这种情况：,25,个人中，因为意见不一样，每个人恰好与其它,5,个人意见一致？,问题,2,：是否存在这种情况：,2,个或以上人群中，最少有,2,个人在此人群中朋友数一样多？,第11页,06 五月 2025,结点次数,二、结点次数,定义：在有向图,G=,中，对任意结点,v,V,以,v,为起始结点弧条数，称为,出度,(out-degree),（引出次数），记为,d,v),以,v,为终止点弧条数，称为,入度,(in-degree),（引入次数），记为,d,-,(v),v,出度和入度和，称为,v,度数,(degree),（次数），记为,d(v)=d,+,(v)+d,-,(v),v,1,v,2,v,3,(,a),第12页,06 五月 2025,结点次数,定义：在无向图,G=,中，对任意结点,v,V,结点,v,度数,d(v),，等于联结它边数,若,结点,v,上有环，则该结点因环而增加度数2,记,G,最大度数,为：,(,G)=max d(v)|,v,V,记,G,最小度数,为：,(,G)=min d(v)|,v,V,v,1,v,2,v,3,(,a),v,1,v2,v,3,(,b),v,4,第13页,06 五月 2025,结点次数,在图,G,中任意一条边,e,E，,都对其联结结点贡献度数2,定理：,在无向图,G=,中，,d(v),=2|E|,通常，将度数为奇数结点称为,奇度结点,将度数为偶数结点称为,偶度结点,定理：,在无向图,G=,中，奇度结点个数为偶数个,第14页,06 五月 2025,结点次数,问题,1,：是否存在这种情况：,25,个人中，因为意见不一样，每个人恰好与其它,5,个人意见一致？,在建立一个图模型时，一个基本问题是决定这个图是什么,什么是结点？什么是边,？,在这个问题里，我们,用结点表示对象,人；,边通常表示两个结点间关系,表示,2,个人意见一致。也就是说，意见一致,2,个人（结点）间存在一条边。,第15页,06 五月 2025,结点次数,问题,1,：是否存在这种情况：,25,个人中，因为意见不一样，每个人恰好与其它,5,个人意见一致？,这么我们能够知道，假如存在题目所述情况，那么每个结点都与其它,5,个结点相关联。也就是说，每个结点度为,5,。,由定理可知：,奇度结点个数为偶数个。,现在是否能够得出结论了？,第16页,06 五月 2025,结点次数,类似问题：,晚会上大家握手言欢，握过奇数次手人数一定是偶数,碳氢化合物中，氢原子个数是偶数,是否有这么多面体，它有奇数个面，每个面有奇数条棱？,第17页,06 五月 2025,结点次数,问题,2,：是否存在这种情况：两个人或以上人群中，最少有两个人在此人群中朋友数一样多？,以人为结点，仅当二人为朋友时，在此二人之间连一边，得一“情谊图”,G(V,E),，设,V=v,1,v,2,v,n,，不妨设各结点次数为,d(v,1,)d(v,2,)d(v,n,)n-1,。,假设命题不成立，则全部些人朋友数都不一样多，则,0,d(v,1,)d(v,2,)d(v,n,)n-1,。,第18页,06 五月 2025,结点次数,问题,2,：是否存在这种情况：两个人或以上人群中，最少有两个人在此人群中朋友数一样多？,若,0,d(v,1,)d(v,2,)d(v,n,)n-1,，则有：,因为,d(v,1,)0,，则有,d(v,2,)1,，,d(v,3,)2,，,，,d(v,n,)n-1,；又因为,d(v,n,)n-1,，所以：,d(v,n,)=n-1,因为,d(v,n,)=n-1,，则每个结点皆与,v,n,相邻，则,d(v,1,)1,。于是有：,d(v,2,)2,，,d(v,3,)3,，,，,d(v,n,)n,，矛盾。,故假设不成立，即,d(v,1,)d(v,2,)d(v,n,),中最少有一个等号成立，命题成立。,第19页,06 五月 2025,结点次数,定义：在无向图,G=,中，若每个结点度数都是,k，,即(,v,)(,v,V,d(v)=k,)，则称,G,为,k,度正则图,(regular graph),v,1,v,2,v,6,v,3,3度正则图,v,4,v,5,v,7,v,8,v,9,v,10,3度正则图,v,1,v,5,v,6,v,2,v,3,v,4,第20页,06 五月 2025,子图,三、子图,定义：给定无向图,G,1,=，G,2,=,若,V,2,V,1,，,E,2,E,1,，则称,G,2,是,G,1,子图,(subgraph),，记作,G,2,G,1,若,V,2,V,1,，,E,2,E,1,，且,E,2,E,1,，则称,G,2,是,G,1,真子图,，记作,G,2,G,1,若,V,2,=,V,1,，,E,2,E,1,，则称,G,2,是,G,1,生成子图,(spanning subgraph),，记作,G,2,G,1,V,2,=,V,1,第21页,06 五月 2025,子图,比如：,v,2,v,1,(,a),v,3,v,4,v,5,(,a),真子图,v,2,v,3,v,4,v,5,(,a),生成子图,v,2,v,3,v,4,v,5,v,1,第22页,06 五月 2025,子图,定义：对于图,G=，G,1,=G，G,2,=G,1,和,G,2,都是,G,生成子图，称为,平凡生成子图,定义：设,G,2,=,是,G,1,=,子图,对任意结点,u,v,V,2,，,若有,u,v,E,1,，,则有,u,v,E,2,，,则,G,2,由,V,2,唯一地确定，则称,G,2,是,V,2,诱导子图,记作,G,V,2,，,或,G,2,=,若,G,2,中无孤立结点，且由,E,2,唯一地确定，则称,G,2,是,E,2,诱导子图,，记作,G,E,2,，,或,G,2,=,第23页,06 五月 2025,子图,比如：,v,2,v,1,G=,v,3,v,4,v,5,G=,V,或,E,诱导子图,v,2,v,3,v,4,v,5,第24页,06 五月 2025,补图,定义：设,G,1,=,和,G,2,=,是,G=,子图，若,E,2,=,E-E,1,，,且,G,2,是,E,2,诱导子图,，即,G,2,=,则称,G,2,是,相对于,G,G,1,补图,第25页,06 五月 2025,补图,图,G,1,和,G,2,互为相对于,G,补图,G,1,v,2,v,1,v,3,v,4,v,5,G,2,v,2,v,3,v,4,v,5,G,v,2,v,1,v,3,v,4,v,5,第26页,06 五月 2025,补图,定义：给定图,G,1,=，,若存在图,G,2,=,且,E,1,E,2,=,，及图,是完全图,则称,G,2,是相对于完全图,G,1,补图,，记作,G,2,=G,1,第27页,06 五月 2025,补图,G,2,=G,1,v,2,v,1,G,1,v,3,v,4,v,5,v,2,v,1,K,5,v,3,v,4,v,5,G,2,v,2,v,3,v,4,v,5,v,1,第28页,06 五月 2025,图同构,四、图同构,定义：给定图,G,1,=，G,2,=,若存在双射函数,f:V,1,V,2,，,使得对于任意,u,v,V,1,有,u,v,E,1,f(u),f(v),E,2,（,或,E,1,E,2,）,则称,G,1,与,G,2,同构,(isomorphic),，记作,G,1,G,2,第29页,06 五月 2025,图同构,例,7.1.1,证实下面两个图,G,1,=，G,2,=,同构,证实：,V,1,=v,1,v,2,v,3,v,4,V,2,=a,b,c,d,结构双射函数,f:V,1,V,2,，f(v,1,)=a，f(v,2,)=bf(v,3,)=c，f(v,4,)=d,可知，边,v,1,v,2,v,2,v,3,v,3,v,4,v,4,v,1,被分别映射成,a,b,b,c,c,d,d,a,，故,G,1,G,2,v,2,v,1,G,1,v,3,v,4,b,a,d,c,G,2,第30页,06 五月 2025,图同构,例,7.1.2,证实下面两个有向图是同构。,G,1,e,a,b,c,d,证实：如图所表示，,G,1,=,，,G,2,=,，结点编号如图所表示。,结构函数,f:V,1,V,2,，,使得,f(a)=1,f(b)=3,f(c)=4,f(d)=5,f(e)=2,则,被分别映射成,故,f,是双射函数，所以,G,1,与,G,2,同构,G,1,3,1,2,4,5,第31页06 五月 2025,图同构,能够给出,图同构必要条件,：,结点数相等,边数相等,度数相等结点数相等,要注意是，这不是充分条件,第32页,06 五月 2025,图同构,例,7.1.3,证实下面两个无向图是不一样构,G,1,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,G,2,a,b,c,d,e,f,g,h,v,1,是,3,度结点，故,f(v,1,),只能是,c,或,d,或,g,或,h,。,若,f(v,1,)=c,，因为,v,2,、,v,4,和,v,5,与,v,1,邻接，所以,f(v,2,),、,f(v,4,),和,f(v,5,),应该分别为与,c,邻接,b,、,d,和,g,不过，,v,2,、,v,4,和,v,5,中，只有一个,3,度结点，而,b,、,d,、,g,中却有,2,个,3,度结点，故,f(v,1,)c,。,同理可说明，,f(v,1,),也不可能是,d,、,g,和,h,。所以这么,f,是不存在。,所以,G,1,和,G,2,是不一样构。,第33页,06 五月 2025,第二节 路,(,链,),与回路,(,圈,),一、路,(,链,),与回路,(,圈,),定义：给定图,G=，,令,v,0,v,1,v,m,V，e,1,e,2,e,m,E,称交替序列,v,0,e,1,v,1,e,2,v,2,e,m,v,m,为连接,v,0,到,v,m,链（路）,称,v,0,和,vm,为链（路）,始结点,和,终止点,链,长度,为边（弧）数目,m,若,v,0,=,v,m,，该链（路）称为,圈（回路,circuit,）,第34页,06 五月 2025,链和圈,在链中：,若任意,e,i,只出现一次，则称该链（路）为,简单链,（路）,若任意,v,i,只出现一次，则称该链（路）为,基本链,（路）,基本链必定是简单链,在圈中：,若任意,e,i,只出现一次，则称该圈,（,回路）为,简单圈,（,回路）,若任意,v,i,只出现一次，则称该圈,（,回路）为,基本圈,（,回路）,第35页,06 五月 2025,链和圈,例,7.2.1,下列图中：,v,3,v,1,v,4,v,5,v,2,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,P,1,=(,v,1,e,1,v,2,e,7,v,5,),也能够表示为：,P,1,=(,e,1,e,7,),是一个基本链，也是一个简单链,P,2,=(,v,2,e,2,v,3,e,3,v,3,e,4,v,1,e,1,v,2,),也能够表示为：,P,2,=(,e,2,e,3,e,4,e,1,),是一个简单圈，但不是基本圈,P,3,=(,v,4,e,6,v,2,e,7,v,5,e,8,v,4,e,6,v,2,e,2,v,3,),是一个链,P,4,=(,v,2,e,7,v,5,e,8,v,4,e,6,v,2,),是一个基本圈，也是一个简单圈第36页,06 五月 2025,链和圈,链和圈能够只用边序列表示,上例中：,(,v,2,e,2,v,3,e,3,v,3,e,4,v,1,e,1,v,2,),也可表示为,(,e,2,e,3,e,4,e,1,)(,v,4,e,6,v,2,e,7,v,5,e,8,v,4,e,6,v,2,e,2,v,3,),也可表示为,(,e,6,e,7,e,8,e,6,e,2,),对于,简单图,来说，链和圈能够仅用结点序列表示,v,3,v,1,v,4,v,5,v,2,e,1,e,2,e,4,e,5,e,6,e,3,e,8,图中：(,v,2,e,2,v,3,e,4,v,1,e,1,v,2,e,3,v,5,e,8,v4,),可表示为,(,e,2,e,4,e,1,e,3,e,8,),也可表示为,(,v,2,v,3,v,1,v,2,v,5,v,4,),第37页,06 五月 2025,链和圈,定理：,在一个图中，若从结点,v,i,到结点,v,j,存在一条链（路），则必有一条从,v,i,到,v,j,基本链（路）,证实：1)若从,v,i,到,v,j,给定链本身就是基本链，定理成立,2)若从,v,i,到,v,j,给定链不是基本链，则,最少含有一个结点,v,k,，它在该链中最少出现两次以上,。,也就是说，经过,v,k,有一个圈,，于是能够从原有链中去除,中全部出现边（弧）。对于原链中所含全部圈都做此处理，最终将得到一条基本链（路）,第38页,06 五月 2025,链和圈,问题：,在一个图中，若从结点,v,i,到结点,v,j,存在一个圈，则必有一个从,v,i,到,v,j,基本圈吗？,例,7.2.2,若,u,和,v,是一个圈上两个结点，,u,和,v,一定是某个基本圈上结点吗？,(,习题,7-16),答：不一定,v,a,u,d,c,b,本图中，,u,和,v,在一个圈上，,不过却不在一个基本圈上,第39页,06 五月 2025,链和圈,定理：在一个含有,n,个结点图中，,任何基本链（路）长度小于,n-1,任何基本圈,（,回路）长度小于,n,证实：1)依据基本链定义可知，出现在基本链中结点都是不一样。所以在长度为,m,基本链中，不一样结点数为,m+1,又因为图中仅有,n,个结点，故,m+1,n,，即,m,n-1,2)依据基本圈定义可知，长度为,k,基本圈中，不一样结点数为,k，,图中共有,n,个结点，所以,k,n,第40页,06 五月 2025,可达,二、连通图,定义：在一个图中，若从,v,i,到,v,j,存在任何一条链则称,从,v,i,到,v,j,是可达,(accessible),，简称,v,i,可达,v,j,要求：,每个结点,v,i,到本身都是可达,第41页,06 五月 2025,连通无向图,（一）连通无向图,对于无向图,G=,而言，可证实,“可达性”是一个,_,关系,。,它对,V,给出一个划分，每个块中元素形成一个诱导子图。,两个结点间是可达，当且仅当它们属于同一个子图称这么子图为,G,连通分图,，,G,连通分图个数记为,(,G),若,G,中只有一个连通分图，则称,G,是,连通图,(即任意两结点可达)不然称,G,为,非连通图,，或,分离图,等价,第42页,06 五月 2025,连通无向图,定义：在无向图,G=,中,若任意两个结点可达，则称,G,是,连通,(connected),，称,G,为,连通无向图,；不然称,G,是非连通，称,G,为,非连通图,或,分离图,。,若,G,子图,G,是连通，且不存在包含,G,更大,G,子图,G,是连通，则称,G,是,G,连通分图,(connected components),，简称分图。,G,中连通分图个数记为,(,G),。,第43页,06 五月 2025,连通无向图,例,7.2.3,v,3,v,1,v,4,v,5,v,2,v,3,v,1,v,4,v,5,v,2,G,1,G,2,G,1,是连通图，,(,G,1,)=1,G,2,是非连通图，,(,G,2,)=2,第44页,06 五月 2025,连通无向图,定义：,从图,G=,中删除结点集,S,，,是指,V-S,E-,与,S,中结点相连结边,而得到子图，记做,G-S,G-v,3,v,3,v,1,v,4,v,5,v,2,G,v,3,v,1,v,4,v,5,v,2,v,3,v,1,v,4,v,5,v,2,第45页,06 五月 2025,连通无向图,定义：,从图,G=,中删除结点集,S,，,是指,V-S,E-,与,S,中结点相连结边,而得到子图，记做,G-S,G-v,3,v,1,v,4,v,5,v,2,G,第46页,06 五月 2025,连通无向图,定义：,从图,G=,中删除边集,T,，,是指,V,不变,E-T,而得到子图，记做,G-T,G-e,1,e,3,e,4,v,3,v,1,v,4,v,5,v,2,G,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,3,v,1,v,4,v,5,v,2,第47页,06 五月 2025,连通无向图,定义：,从图,G=,中删除边集,T,，,是指,V,不变,E-T,而得到子图，记做,G-T,G-e,1,e,3,e,4,v,3,v,1,v,4,v,5,v,2,G,e,2,e,5,e,6,e,7,第48页,06 五月 2025,连通无向图,定义：给定连通无向图,G=，S,V,若,(,G-S),(,G)=1,且对任意,T,S，,(,G-T)=,(,G),则称,S,是,G,一个,分离结点集,(cut-set of nodes),若,S,中仅含有一个元素,v，,则称,v,是,G,割点,(cut-node),第49页,06 五月 2025,连通无向图,例,7.2.4G,以下列图所表示，,S=v,1,v,3,v,2,v,1,v,5,v,6,v,4,Gv,3,v,2,v,1,v,5,v,6,v,4,G-S,v,3,v,2,v,5,v,6,v,4,G-S,(,G)=1，,(,G-S)=2,(,G-S),(,G),第50页,06 五月 2025,连通无向图,例,7.2.4G,以下列图所表示，,S=v,1,v,3,v,2,v,1,v,5,v,6,v,4,G,v,3,(,G)=1，,(,G-S)=2,(,G-S),(,G),(,G-v,1,)=1,v,2,v,5,v,6,v,4,G-v,1,v,3,第51页,06 五月 2025,连通无向图,例,7.2.4G,以下列图所表示，,S=v,1,v,3,v,2,v,1,v,5,v,6,v,4,G,v,3G)=1，,(,G-S)=2,(,G-S),(,G),(,G-v,1,)=1,v,2,v,1,v,5,v,6,v,4,G-v,3,(,G-v,3,)=1,第52页,06 五月 2025,连通无向图,例,7.2.4G,以下列图所表示，,S=v,1,v,3,v,2,v,1,v,5,v,6,v,4,G,v,3,v,2,v,5,v,6,v,4,G-S,(,G)=1，,(,G-S)=2,(,G-S),(,G),(,G-v,1,)=1,(,G-v,3,)=1,S,是,G,分离结点集,第53页,06 五月 2025,连通无向图,例,7.2.5G,以下列图所表示，,S=v,2,v,1,v,4,v,5,v3,G,v,2,(,G)=1，,(,G-S)=2,(,G-S),(,G),v,1,v,4,v,5,v,3,G-S,v,2,是,G,割点,不存在其它,G,割点,第54页,06 五月 2025,连通无向图,定义：给定连通无向图,G=，T,E,若,(,G-T),(,G)=1,且对任意,F,T，,(,G-F)=,(,G),则称,T,是,G,一个,分离边集,(cut-set of edges),若,T,中仅含有一个元素,e，,则称,e,是,G,割边,(cut-edge),，或桥,第55页,06 五月 2025,连通无向图,例,7.2.6G,以下列图所表示，,T=e,1,e,2,(,G)=1，,(,G-T)=2,(,G-T),(,G),v,1,v,3,v,4,G,v,2,e,1,e,4,e,2,e,3,v,1,v,3,v,4,G-T,v,2,e,4,e,3,第56页,06 五月 2025,连通无向图,例,7.2.6G,以下列图所表示，,T=e,1,e,2,(,G)=1，,(,G-T)=2,(,G-T),(,G),v,1,v,3,v,4,G,v,2,e,1,e,4,e,2,e,3,v,1,v,3,v,4,G-e,1,v,2,e,4,e,2,e,3,(,G-e,1,)=1,第57页,06 五月 2025,连通无向图,例,7.2.6G,以下列图所表示，,T=e,1,e,2,(,G)=1，,(,G-T)=2,(,G-T),(,G),v,1,v,3,v,4,G,v,2,e,1,e,4,e,2,e,3,(,G-e,1,)=1,(,G-e,2,)=1,v,1,v,3,v,4,G-e,2,v,2,e,1,e,4,e,3,第58页,06 五月 2025,连通无向图,例,7.2.6G,以下列图所表示，,T=e,1,e,2,(,G)=1，,(,G-T)=2,(,G-T),(,G),v,1,v,3,v,4,G,v,2,e,1,e,4,e,2,e,3,v,1,v,3,v,4,G-T,v,2,e,4,e,3,(,G-e,1,)=1,(,G-e,2,)=1,T,是,G,分离边集,第59页,06 五月 2025连通无向图,例,7.2.7G,以下列图所表示，,T=e,1,(,G)=1，,(,G-T)=2,(,G-T),(,G),v,1,v,3,v,4,G,v,2,e,1,e,2,e,3,v,1,v,3,v,4,G-T,v,2,e,2,e,3,e,1,是,G,割边,e,2,和,e,3,都是,G,割边,第60页,06 五月 2025,连通无向图,定义：对连通非平凡图,G=，,称,(,G),=,min|S|S,是,G,分离结点集,为,G,结点连通度,(node-connectivity),它表明产生分离图需要删去结点最少数目,对分离图,G,而言，,(,G)=0,对存在割点连通图,G,而言，,(,G)=1,S,V,第61页,06 五月 2025,连通无向图,例,7.2.8,求,G,1,和,G,2,结点连通度,v,2,v,1,v,5,v,6,v,4,G,1,v,3,(,G,1,)=2,(,G,2,)=1,v,1,v,4,v,5,v,3,G,2,v,2,第62页,06 五月 2025,连通无向图,定义：对连通非平凡图,G=，,称,(,G),=,min|T|T,是,G,分离边集,为,G,边连通度,(edge-connectivity),它表明产生分离图需要删去边最少数目,对分离图,G,而言，,(,G)=0,对存在割边连通图,G,而言，,(,G)=1,对无向完全图,K,n,，,(,K,n,)=?,T,En-1,第63页,06 五月 2025,连通无向图,例,7.2.9,求,G,1,和,G,2,边连通度,(,G,1,)=2,(,G,2,)=1,v,1,v,3,v,4,G,1,v,2,e,1,e,4,e,2,e,3,v,1,v,3,v,4,G,2,v,2,e,1,e,2,e,3,第64页,06 五月 2025,连通无向图,定理：对于任何一个无向图,G，,有,(,G),(,G),(,G),证实：1)若,G,是分离图，则,(,G),=,(,G)=0，,而,(,G),0,2)若,G,是连通图，先证实,(,G),(,G),若,G,是平凡图，则,(,G)=0,=,(,G),若,G,不是平凡图，则当删去全部联结一个含有最小度结点边（除了环）后，便产生了一个分离图，所以,(,G),(,G),再证实,(,G),(,G),若,(,G)1，,则,G,存在一个割边，显然,(,G),=,(,G)=1,v,3,v,1,v,4,v,5,v,2,v,1,v,1,v,3,v,4,G,v,2,e,1,e,2,e,3,v,1,v,3,v,4,G ,e,1,v,2,e,2,e,3,v,1,v,3,v,4,G,v,2,e,1,e,2,e,3,v,1,v,3,v,4,G ,e,1,v,2,e,2,e,3,v,3,v,4,G ,v,1,v,2,e,3,第65页,06 五月 2025,连通无向图,若,(,G),2，,则删去某,G),条边后，,G,就成为分离图,若只删除,(,G)-1,条边，则仍得到连通图且存在一割边,e=u,v,对于,(,G)-1,条边中每一条边，选取一个不一样于,u,和,v,结点，把这些结点删去，将必须最少删去,(,G)-1,条边,若这么会产生分离图，则,(,G),(,G)-1,(,G),若这么产生仍是连通图且,e,是割边，再删除结点,u,或,v,必将产生分离图，所以,(,G),(,G),v,1,v,3,v,4,G,v,2,e,1,e,4,e,2,e,3,v,1,v,3,v,4,G ,v,2,e,2,e,3,v,1,v,4,G ,v,3,总而言之，有,(,G),(,G),(,G),第66页,06 五月 2025,连通无向图,定理：一个连通无向图,G,中结点,v,是割点，充要条件是,存在两个结点,u,和,w，,使得联结,u,和,w,每条链都经过,v,证实：1)充分性：若,G,中联结,u,和,w,每条链都经过,v，,删去,v，,则在子图,G-v,中，,u,和,w,必定不可达，故,v,是,G,割点,2)必要性：若,v,是,G,割点，删去,v，,则子图,G-v,中最少有两个连通分图,G,1,=,和,G,2,=,，,任取两个结点,u,V,1,，w,V,2,，u,和,w,不可达。故,G,中联结,u,和,w,每条链必经过,v,第67页,06 五月 2025,连通无向图,同理能够证实：,定理：一个连通无向图,G,中边,e,是割边，充要条件是,存在两个结点,u,和,w，,使得联结,u,和,w,每条链都经过,e,定理：一个连通无向图,G,中边,e,是割边，充要条件是,e,不包含在,G,任何基本圈中,证实：教材,P172,（定理,7.8),第68页,06 五月 2025,乌拉姆猜测（,1929,）,左右两张相片，捂住左边相片一部分，也捂住右边相片对应部分，比如都捂住左眼，能看到相片大部分形象一致；再分别捂住左右相片另一个对应部分，比如右耳，结果能看到相片大部分依然一致。如此轮番地观察各次对应暴露部分，都会看到相同形象，那么谁都会相信这两张照片是同一个人或孪生弟兄留影。,数学描述：有图,G,1V,1,E,1,和,G,2,=V,2,E,2,，,V,1,=v,1,v,2,v,n,，,V,2,=u,1,u,2,u,n,（,n3,）。假如,G,1,-v,i,G,2,-u,i,，,i=1,2,n,，则,G,1,G,2,第69页,06 五月 2025,连通有向图,（二）连通有向图,对于有向图,G=,而言，,结点间可达性不再是等价关系,，它仅仅是,自反和可传递，普通不是对称,定义：对于给定有向图,G，,要略去,G,中每条边方向，便得到一个无向图,G，,称,G,是,G,基础图,第70页,06 五月 2025,连通有向图,定义：在简单有向图,G,中，,若任何两个结点间都是可达，则称,G,是,强连通,若任何两个结点间，最少是从一个结点可达另一个结点，则称,G,是,单向连通,若,G,基础图是连通，则称,G,是,弱连通,第71页,06 五月 2025,连通有向图,例,7.2.10,判断,G,1,、,G,2,和,G,3,是强连通？单向连通？弱连通？,G,1,是强连通,v,1,v,3,v,4,G,1,v,2,v,1,v,3,v,4,G,2,v,2,v,1,v,3,v,4,G,3,v,2,G,2,是单向连通,G,3,是弱连通,第72页,06 五月 2025,连通有向图,由定义可知：,若,G,是强连通，则它必定是单向连通反之未必真,若,G,是单向连通，则它必是弱连通反之未必真,第73页,06 五月 2025,连通有向图,定理：有向图,G,是强连通，当且仅当,G,中有一回路，它最少经过每个结点一次,证实：1)充分性：若,G,中存在一条回路，它最少经过每个结点一回，则,G,中任何两个结点都是相互可达，所以,G,是强连通。,2)必要性：若,G,是强连通，则,G,中任何两个结点都是相互可达，所以能够做出一条回路经过,G,中全部结点，,不然，必有某结点,v,不在该回路上,，v,与回路上各结点不可能都相互可达。与,G,是强连通矛盾,第74页,06 五月 2025,连通有向图,定义：在简单有向图,G,中,含有强连通性质极大子图，称为,强分图,含有单向连通性质极大子图，称为,单向分图,含有弱连通性质极大子图，称为,弱分图,第75页,06 五月 2025,连通有向图,例,7.2.11,求,G,强分图、单向分图和弱分图,v,3,v,2,v,1,G,v,4,v,5,v,6,v,3,v,2,v,1,v,4,v,5,v,6,G,强分图有：,定理：,简单有向图,G,中任意一个结点，恰位于一个强分图中,第76页,06 五月 2025,连通有向图,定理：,简单有向图,G,中任意一个结点，恰位于一个强分图中,证实：由强分图定义可知，,G,中每个结点位于一个强分图中,假设,G,中存在结点,v,位于两个强分图,G,1,和,G,2,中,则由强分图定义可知，,G,1,中每个结点与,v,相互可达，,G,2,中每个结点也与,v,相互可达,故,G,1,中每个结点与,G,2,中每个结点经过,v，,能够相互可达，这与,G,1,和,G,2,是两个强分图矛盾,所以,G,中每个结点只能位于一个强分图中,第77页,06 五月 2025,连通有向图,例,7.2.11,求,G,强分图、单向分图和弱分图,G,单向分图有：,v,3,v,2,v,1,G,v,4,v,5,v,6,v,3,v,2,v,1,v,4,v,5,v,5,v,6,定理：,简单有向图,G,中每个结点和每条弧,最少位于一个单向分图中,第78页,06 五月 2025,连通有向图,例,7.2.11,求,G,强分图、单向分图和弱分图,G,弱分图有：,v,3,v,2,v,1G,v,4,v,5,v,6,v,3,v,2,v,1,v,4,v,5,v,6,定理：,简单有向图,G,中每个结点和每条弧 恰位于一个弱分图中,第79页,06 五月 2025,结点间距离,三、结点间距离,定义：在图,G,中，若结点,u,可达结点,v，,它们之间可能存在不止一条链（路）。在全部链中，,最短链长度,称为结点,u,和,v,之间,距离,（或短程线、测地线）。记做：,d,第80页,06 五月 2025,结点间距离,距离满足下面性质：,d,0,d=0,d+d,d,若,u,不可达,v，,则,d=+,即使,u,和,v,相互可达，,d,未必等于,d,第81页,06 五月 2025,有向图在计算机中应用,四、有向图在计算机中应用,这里给出一个简单有向图在计算机中应用,利用资源分配图来纠正和发觉死锁,第82页,06 五月 2025,有向图在计算机中应用,在多道程序计算机系统中，同一时间内有多个程序需要同时执行。,每个程序都共享计算机资源：如,CPU、,内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。,当一个程序需要使用某种资源时候，要向操作系统发出请求，操作系统必须确保这个请求得到满足，才能运行该程序,第83页,06 五月 2025,有向图在计算机中应用,对资源请求可能发生冲突，发生,死锁,。比如：,程序,P,1,占有资源,r,1,，,请求资源,r,2,程序,P,2,