离散数学-图论基础.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 图论基础,Graphs,02 三月 2026,第一节 图的基本概念,一个图,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),02 三月 2026,图的基本概念,图,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,2,v,3,(,b),v,1,v,2,v,3,(,c),02 三月 2026,图的基本概念,若,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,1,v,2,v,3,(,a),v,1,v,2,v,3,(,b),v,1,v,2,v,3,(,c),02 三月 2026,图的基本概念,若将图,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),02 三月 2026,图的基本概念,若图,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),02 三月 2026,图的基本概念,在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数,把重数作为分配给边（弧）上的数，称为,权,(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,02 三月 2026,图的基本概念,在无向图,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,02 三月 2026,图的基本概念,在有向图,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,02 三月 2026,图的基本概念,在图,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,02 三月 2026,问题,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,问题,2,：是否存在这种情况：,2,个或以上的人群中，至少有,2,个人在此人群中的朋友数一样多？,02 三月 2026,结点的次数,二、结点的次数,定义：在有向图,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),02 三月 2026,结点的次数,定义：在无向图,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,v,2,v,3,(,b),v,4,02 三月 2026,结点的次数,在图,G,中的任意一条边,e,E，,都对其联结的结点贡献度数2,定理：,在无向图,G=,中，,d(v),=2|E|,通常，将度数为奇数的结点称为,奇度结点,将度数为偶数的结点称为,偶度结点,定理：,在无向图,G=,中，奇度结点的个数为偶数个,02 三月 2026,结点的次数,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,在建立一个图模型时，一个基本问题是决定这个图是什么,什么是结点？什么是边,？,在这个问题里，我们,用结点表示对象,人；,边通常表示两个结点间的关系,表示,2,个人意见一致。也就是说，意见一致的,2,个人（结点）间存在一条边。,02 三月 2026,结点的次数,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他,5,个结点相关联。也就是说，每个结点的度为,5,。,由定理可知：,奇度结点的个数为偶数个。,现在是否能够得出结论了？,02 三月 2026,结点的次数,类似问题：,晚会上大家握手言欢，握过奇数次手的人数一定是偶数,碳氢化合物中，氢原子个数是偶数,是否有这样的多面体，它有奇数个面，每个面有奇数条棱？,02 三月 2026,结点的次数,问题,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,。,02 三月 2026,结点的次数,问题,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,),中至少有一个等号成立，命题成立。,02 三月 2026,结点的次数,定义：在无向图,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,02 三月 2026,子图,三、子图,定义：给定无向图,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,02 三月 2026,子图,例如：,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,02 三月 2026,子图,定义：对于图,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,=,02 三月 2026,子图,例如：,v,2,v,1,G=,v,3,v,4,v,5,G=V,或,E,的诱导子图,v,2,v,3,v,4,v,5,02 三月 2026,补图,定义：设,G,1,=,和,G,2,=,是,G=,的子图，若,E,2,=,E-E,1,，,且,G,2,是,E,2,的诱导子图,，即,G,2,=,则称,G,2,是,相对于,G,的,G,1,的补图,02 三月 2026,补图,图,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,02 三月 2026,补图,定义：给定图,G,1,=，,若存在图,G,2,=,且,E,1,E,2,=,，及图,是完全图,则称,G,2,是相对于完全图的,G,1,的补图,，记作,G,2,=G,1,02 三月 2026,补图,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,02 三月 2026,图的同构,四、图的同构,定义：给定图,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,02 三月 2026,图的同构,例,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,02 三月 2026,图的同构,例,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,02 三月 2026,图的同构,可以给出,图的同构的必要条件,：,结点数相等,边数相等,度数相等的结点数相等,要注意的是，这不是充分条件,02 三月 2026,图的同构,例,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,是不同构的。,02 三月 2026,第二节 路,(,链,),与回路,(,圈,),一、路,(,链,),与回路,(,圈,),定义：给定图,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,和,v,m,为链（路）的,始结点,和,终结点,链的,长度,为边（弧）的数目,m,若,v,0,=,v,m,，该链（路）称为,圈（回路,circuit,）,02 三月 2026,链和圈,在链中：,若任意,e,i,只出现一次，则称该链（路）为,简单链,（路）,若任意,v,i,只出现一次，则称该链（路）为,基本链,（路）,基本链必定是简单链,在圈中：,若任意,e,i,只出现一次，则称该圈,（,回路）为,简单圈,（,回路）,若任意,v,i,只出现一次，则称该圈,（,回路）为,基本圈,（,回路）,02 三月 2026,链和圈,例,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,),是一个基本圈，也是一个简单圈,02 三月 2026,链和圈,链和圈可以只用边的序列表示,上例中：,(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,v,4,),可表示为,(e,2,e,4,e,1,e,3,e,8,),也可表示为,(v,2,v,3,v,1,v,2,v,5,v,4,),02 三月 2026,链和圈,定理：,在一个图中，若从结点,v,i,到结点,v,j,存在一条链（路），则必有一条从,v,i,到,v,j,的基本链（路）,证明：1)若从,v,i,到,v,j,给定的链本身就是基本链，定理成立,2)若从,v,i,到,v,j,给定的链不是基本链，则,至少含有一个结点,v,k,，它在该链中至少出现两次以上,。,也就是说，经过,v,k,有一个圈,，于是可以从原有链中去除,中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）,02 三月 2026,链和圈,问题：,在一个图中，若从结点,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,在一个圈上，,但是却不在一个基本圈上,02 三月 2026,链和圈,定理：在一个具有,n,个结点的图中，,任何基本链（路）的长度不大于,n-1,任何基本圈,（,回路）的长度不大于,n,证明：1)根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为,m,的基本链中，不同的结点数为,m+1,又因为图中仅有,n,个结点，故,m+1,n,，即,m,n-1,2)根据基本圈的定义可知，长度为,k,的基本圈中，不同的结点数为,k，,图中共有,n,个结点，所以,k,n,02 三月 2026,可达,二、连通图,定义：在一个图中，若从,v,i,到,v,j,存在任何一条链则称,从,v,i,到,v,j,是可达的,(accessible),，简称,v,i,可达,v,j,规定：,每个结点,v,i,到自身都是可达的,02 三月 2026,连通无向图,（一）连通无向图,对于无向图,G=,而言，可证明“可达性”是一个,_,关系。,它对,V,给出一个划分，每个块中的元素形成一个诱导子图。,两个结点间是可达的，当且仅当它们属于同一个子图称这样的子图为,G,的,连通分图,，,G,的连通分图的个数记为,(,G),若,G,中只有一个连通分图，则称,G,是,连通图,(即任意两结点可达)否则称,G,为,非连通图,，或,分离图,等价,02 三月 2026,连通无向图,定义：在无向图,G=,中,若任意两个结点可达，则称,G,是,连通的,(connected),，称,G,为,连通无向图,；否则称,G,是非连通的，称,G,为,非连通图,或,分离图,。,若,G,的子图,G,是连通的，且不存在包含,G,的更大的,G,的子图,G,是连通的，则称,G,是,G,的,连通分图,(connected components),，简称分图。,G,中连通分图的个数记为,(,G),。,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,定义：,从图,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,02 三月 2026,连通无向图,定义：,从图,G=,中删除结点集,S,，,是指,V-S,E-,与,S,中结点相连结的边,而得到的子图，记做,G-S,G-v,3,v,1,v,4,v,5,v,2,G,02 三月 2026,连通无向图,定义：,从图,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,02 三月 2026,连通无向图,定义：,从图,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,02 三月 2026,连通无向图,定义：给定连通无向图,G=，S,V,若,(,G-S),(,G)=1,且对任意,T,S，,(,G-T)=,(,G),则称,S,是,G,的一个,分离结点集,(cut-set of nodes),若,S,中仅含有一个元素,v，,则称,v,是,G,的,割点,(cut-node),02 三月 2026,连通无向图,例,7.2.4G,如下图所示，,S=v,1,v,3,v,2,v,1,v,5,v,6,v,4,G,v,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),02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,例,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,1,v,5,v,6,v,4,G-v,3,(,G-v,3,)=1,02 三月 2026,连通无向图,例,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,的分离结点集,02 三月 2026,连通无向图,例,7.2.5G,如下图所示，,S=v,2,v,1,v,4,v,5,v,3,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,的割点,02 三月 2026,连通无向图,定义：给定连通无向图,G=，T,E,若,(,G-T),(,G)=1,且对任意,F,T，,(,G-F)=,(,G),则称,T,是,G,的一个,分离边集,(cut-set of edges),若,T,中仅含有一个元素,e，,则称,e,是,G,的,割边,(cut-edge),，或桥,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,例,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,的分离边集,02 三月 2026,连通无向图,例,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,的割边,02 三月 2026,连通无向图,定义：对连通的非平凡图,G=，,称,(,G),=,min|S|S,是,G,的分离结点集为,G,的,结点连通度,(node-connectivity),它表明产生分离图需要删去结点的最少数目,对分离图,G,而言，,(,G)=0,对存在割点的连通图,G,而言，,(,G)=1,S,V,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,定义：对连通的非平凡图,G=，,称,(,G),=,min|T|T,是,G,的分离边集为,G,的,边连通度,(edge-connectivity),它表明产生分离图需要删去边的最少数目,对分离图,G,而言，,(,G)=0,对存在割边的连通图,G,而言，,(,G)=1,对无向完全图,K,n,，,(,K,n,)=?,T,E,n-1,02 三月 2026,连通无向图,例,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,02 三月 2026,连通无向图,定理：对于任何一个无向图,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,02 三月 2026,连通无向图,若,(,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),02 三月 2026,连通无向图,定理：一个连通无向图,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,02 三月 2026,连通无向图,同理可以证明：,定理：一个连通无向图,G,中的边,e,是割边，充要条件是,存在两个结点,u,和,w，,使得联结,u,和,w,的每条链都经过,e,定理：一个连通无向图,G,中的边,e,是割边，充要条件是,e,不包含在,G,的任何基本圈中,证明：教材,P172,（定理,7.8),02 三月 2026,乌拉姆猜想（,1929,）,左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。,数学描述：有图,G,1,=V,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,02 三月 2026,连通有向图,（二）连通有向图,对于有向图,G=,而言，,结点间的可达性不再是等价关系,，它仅仅是,自反的和可传递的，一般不是对称的,定义：对于给定的有向图,G，,要略去,G,中每条边的方向，便得到一个无向图,G，,称,G,是,G,的,基础图,02 三月 2026,连通有向图,定义：在简单有向图,G,中，,若任何两个结点间都是可达的，则称,G,是,强连通,的,若任何两个结点间，至少是从一个结点可达另一个结点，则称,G,是,单向连通,的,若,G,的基础图是连通的，则称,G,是,弱连通,的,02 三月 2026,连通有向图,例,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,是弱连通的,02 三月 2026,连通有向图,由定义可知：,若,G,是强连通的，则它必定是单向连通的反之未必真,若,G,是单向连通的，则它必是弱连通的反之未必真,02 三月 2026,连通有向图,定理：有向图,G,是强连通的，当且仅当,G,中有一回路，它至少通过每个结点一次,证明：1)充分性：若,G,中存在一条回路，它至少通过每个结点一回，则,G,中任何两个结点都是互相可达的，所以,G,是强连通的。,2)必要性：若,G,是强连通的，则,G,中任何两个结点都是互相可达的，因此可以做出一条回路经过,G,中所有结点，,否则，必有某结点,v,不在该回路上,，v,与回路上的各结点不可能都互相可达。与,G,是强连通的矛盾,02 三月 2026,连通有向图,定义：在简单有向图,G,中,具有强连通性质的极大子图，称为,强分图,具有单向连通性质的极大子图，称为,单向分图,具有弱连通性质的极大子图，称为,弱分图,02 三月 2026,连通有向图,例,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,中的任意一个结点，恰位于一个强分图中,02 三月 2026,连通有向图,定理：简单有向图,G,中的任意一个结点，恰位于一个强分图中,证明：由强分图的定义可知，,G,中每个结点位于一个强分图中,假设,G,中存在结点,v,位于两个强分图,G,1,和,G,2,中,则由强分图的定义可知，,G,1,中的每个结点与,v,互相可达，,G,2,中的每个结点也与,v,互相可达,故,G,1,中的每个结点与,G,2,中的每个结点通过,v，,能够互相可达，这与,G,1,和,G,2,是两个强分图矛盾,因此,G,中每个结点只能位于一个强分图中,02 三月 2026,连通有向图,例,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,中的每个结点和每条弧,至少位于一个单向分图中,02 三月 2026,连通有向图,例,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,6,定理：简单有向图,G,中的每个结点和每条弧 恰位于一个弱分图中,02 三月 2026,结点间的距离,三、结点间的距离,定义：在图,G,中，若结点,u,可达结点,v，,它们之间可能存在不止一条链（路）。在所有链中，,最短链的长度,称为结点,u,和,v,之间的,距离,（或短程线、测地线）。记做：,d,02 三月 2026,结点间的距离,距离满足下面性质：,d,0,d=0,d+d,d,若,u,不可达,v，,则,d=+,即使,u,和,v,互相可达，,d,未必等于,d,02 三月 2026,有向图在计算机中的应用,四、有向图在计算机中的应用,这里给出一个简单有向图在计算机中的应用 利用资源分配图来纠正和发现死锁,02 三月 2026,有向图在计算机中的应用,在多道程序的计算机系统中，同一时间内有多个程序需要同时执行。,每个程序都共享计算机资源：如,CPU、,内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。,当一个程序需要使用某种资源的时候，要向操作系统发出请求，操作系统必须保证这个请求得到满足，才能运行该程序,02 三月 2026,有向图在计算机中的应用,对资源的请求可能发生冲突，发生,死锁,。例如：,程序,P,1,占有资源,r,1,，,请求资源,r,2,程序,P,2,占有资源,r,2,，,请求资源,r,1,有冲突的请求必须要解决，可以利用有向图来模拟对资源的请求，从而帮助发现和纠正“死锁”状态,02 三月 2026,有向图在计算机中的应用,令,P,t,=P,1,P,2,P,3,P,4,是,t,时刻运行的程序集合,R,t,=r,1,r,2,r,3,r,4,是,t,时刻所需要的的资源集合,P,1,占有资源,r,4,，,请求资源,r,1,P,2,占有资源,r,1,，,请求资源,r,2,和,r,3,P,3,占有资源,r,2,，,请求资源,r,3,P,4,占有资源,r,3,，,请求资源,r,1,和,r,4,可得到