离散数学-图论基础

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 图论基础,Graphs,09 十月 2024,第一节 图的基本概念,一个图,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),09 十月 2024,图的基本概念,图,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),09 十月 2024,图的基本概念,若,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),09 十月 2024,图的基本概念,若将图,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),09 十月 2024,图的基本概念,若图,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),09 十月 2024,图的基本概念,在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数,把重数作为分配给边（弧）上的数，称为,权,(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,09 十月 2024,图的基本概念,在无向图,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,09 十月 2024,图的基本概念,在有向图,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,09 十月 2024,图的基本概念,在图,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,09 十月 2024,问题,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,问题,2,：是否存在这种情况：,2,个或以上的人群中，至少有,2,个人在此人群中的朋友数一样多？,09 十月 2024,结点的次数,二、结点的次数,定义：在有向图,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),09 十月 2024,结点的次数,定义：在无向图,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,09 十月 2024,结点的次数,在图,G,中的任意一条边,e,E，,都对其联结的结点贡献度数2,定理：,在无向图,G=,中，,d(v),=2|E|,通常，将度数为奇数的结点称为,奇度结点,将度数为偶数的结点称为,偶度结点,定理：,在无向图,G=,中，奇度结点的个数为偶数个,09 十月 2024,结点的次数,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,在建立一个图模型时，一个基本问题是决定这个图是什么,什么是结点？什么是边,？,在这个问题里，我们,用结点表示对象,人；,边通常表示两个结点间的关系,表示,2,个人意见一致。也就是说，意见一致的,2,个人（结点）间存在一条边。,09 十月 2024,结点的次数,问题,1,：是否存在这种情况：,25,个人中，由于意见不同，每个人恰好与其他,5,个人意见一致？,这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他,5,个结点相关联。也就是说，每个结点的度为,5,。,由定理可知：,奇度结点的个数为偶数个。,现在是否能够得出结论了？,09 十月 2024,结点的次数,类似问题：,晚会上大家握手言欢，握过奇数次手的人数一定是偶数,碳氢化合物中，氢原子个数是偶数,是否有这样的多面体，它有奇数个面，每个面有奇数条棱？,09 十月 2024,结点的次数,问题,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,。,09 十月 2024,结点的次数,问题,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,),中至少有一个等号成立，命题成立。,09 十月 2024,结点的次数,定义：在无向图,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,09 十月 2024,子图,三、子图,定义：给定无向图,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,09 十月 2024,子图,例如：,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,09 十月 2024,子图,定义：对于图,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,=,09 十月 2024,子图,例如：,v,2,v,1,G=,v,3,v,4,v,5,G=,V,或,E,的诱导子图,v,2,v,3,v,4,v,5,09 十月 2024,补图,定义：设,G,1,=,和,G,2,=,是,G=,的子图，若,E,2,=,E-E,1,，,且,G,2,是,E,2,的诱导子图,，即,G,2,=,则称,G,2,是,相对于,G,的,G,1,的,补图,09 十月 2024,补图,图,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,09 十月 2024,补图,定义：给定图,G,1,=，,若存在图,G,2,=,且,E,1,E,2,=,，及图,是完全图,则称,G,2,是相对于完全图的,G,1,的,补图,，记作,G,2,=G,1,09 十月 2024,补图,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,09 十月 2024,图的同构,四、图的同构,定义：给定图,G,