第14讲 图的有关概念,节点的度数.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,14,讲 图的有关概念,节点的度数,主要内容,:,1.,图的有关概念,.,2.,节点的度数,.,3.,子图与图的同构,.,Chapter 7,图论,图论的创始人是瑞士数学家,L.Euler,，他于,1736,年首次建立“图”模型解决了,Kningsberg,七桥问题,.,图论的应用领域非常广泛，它已经渗透到诸如语言学、逻辑学、物理学、化学、电信工程、信息论、控制论、经济管理等各个领域，特别是在计算机科学中的,数据结构、计算机网络、计算机软件、算法理论、操作系统、分布式系统、编译程序以及数据挖掘,等方面都扮演着重要角色,.,7.1,图的基本概念,哥尼斯堡,(,Kningsberg,),七桥问题,:,问题是,:,是否可从某一个地方出发，经过七座桥，每座桥只经过一次，然后又回到原出发点,.,程序调用的图论模型,:,e,8,:,v,3,可调用,v,2,;,e,1,:,v,2,可调用,v,1,;,e,4,:,v,5,可调用,v,5,自身,.,单行道,;,好感,?,1.,图的定义,由前面的,2,个例子可以得出,Definition,图,G,(graph,),主要由,2,部分组成,:,(1),节点集合,V,其中的元素称为,节点,(vertex,或,node).,(2),边集合,E,其中的元素称为,边,(edge).,通常将图,G,记为,G,=(,V,E,).,几点说明,:,(a),节点又可以称为点、顶点或结点,常用一个实心点或空心点表示,但在实际应用中还可以用诸如方形、圆形、菱形等符号,为了方便可以在这些符号的旁边或内部写上表意名称,.,(,计算机学科中常称节点,.),(b),边及其的表示,.,无向边,?,b,3,=,AB,=,BA,=,A,B,(,可重,).,有向边,(,弧,)?,所有边都是无向边的图称为,无向图,(graph,undirected graph),所有边都是有向边的图称为,有向图,(digraph,directed graph).,(c),图的拓扑不变性质,.,需要注意的是,我们讨论的图不但与节点位置无关,而且与边的形状和长短也无关,.,有,n,个节点的图称为,n,阶,(order),图,有,n,个节点,m,条边的图称为,(,n,m,),图,.,在图,G,=(,V,E,),中,称,V,=,的图为,空图,(empty graph),记为,若,V,但,E,=,的图称为,零图,(discrete graph),n,阶零图可记为,N,n,仅一个节点的零图称为,平凡图,(trivial graph).,2.,邻接,Def,设,G,=(,V,E,),是图,对于任意,u,v,V,若从节点,u,到节点,v,有边,则称,u,邻接到,(adjacent to),v,或称,u,和,v,是邻接的,(adjacent).,无向图,?,有向图,?,(,无向图的两条边邻接是指它们有公共端点,.),3.,关联,Def,设,G,=(,V,E,),是图,e,E,e,的两个端点分别为,u,和,v,则称边,e,与节点,u,以及边,e,与节点,v,是,关联,的,(incident).,显然,图的任意一条边都关联两个节点,.,关联相同两个节点的边称为吊环,可简称,环,(loop).,关联的起点相同与终点也相同的边称为,多重边,(multiple edges),或平行边,其边数称为边的,重数,(multiplicity).,例子见书,Figure 7-4(a)(b).,4.,简单图,(1)简单图,Def,设,G,=(,V,E,),是图,若,G,中既无吊环又无多重边,则称,G,是,简单图,(simple graph).,简单图的例子,?,彼得森,(Petersen,18311910),图,它是一个有着特殊性质的简单图,后面会多次出现,.,(2),完全无向图,Def,设,G,=(,V,E,),是,n,阶简单无向图,若,G,中任意节点都与其余,n,-1,个节点邻接,则称,G,为,n,阶,完全无向图,(complete graph),记为,K,n,.,K,5,:,将,n,阶完全无向图,K,n,的边任意加一个方向所得到的有向图称为,n,阶,竞赛图,.,(3),补图,Def,设,G,=(V,E,),是,n,阶简单无向图,由,G,的所有节点以及由能使,G,成为,K,n,需要添加的边构成的图称为,G,的,补图,记为,(,u,和,v,在,G,中不邻接,u,和,v,在 中邻接,),7.2,节点的度数,边与节点的,关联次数,?,Def,设,G,=(,V,E,),是无向图,v,V,称与节点,v,关联的所有边的关联次数之和为节点,v,的,度数,(degree),记为,deg(,v,).,一个环算,2,度,?,Def,设,G,=(,V,E,),是有向图,v,V,称以,v,为,起点的边的数目为节点的,出度,(out-degree),记为,deg,+,(,v,),以,v,为终点的边的数目为节点的,入度,(in-degree),记为,deg,-,(,v,),称,deg,+,(,v,)+deg,-,(,v,),为节点,v,的,度数,记为,deg,(,v,).,一个环算,2,度,?,下面的定理是,L.Euler,在,1736,年证明的图论中的第一定理,常称为“,握手,(?),定理”,.,Theorem,在任何,(,n,m,),图,G,=(,V,E,),中,其所有节点度数之和等于边数,m,的,2,倍,即,Corollary,在任意图,G,=(,V,E,),中,度数为奇数的节点个数必为偶数,.,Proof,由定理及其推论很容易知道,在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数,.(,环的解释,?,),在任意有向图中,显然有,Theorem,在任意有向图中,所有节点的出度之和等于入度之和,.,在任意图中,度数为,0,的节点称为,孤立点,(isolated vertex),度数为,1,的节点称为,悬挂点,(pendant vertex).,例,7-1(P200),证明,:,对于任意,n,(,n,2,),个人的组里,必有两个人有相同个数的朋友,.,Proof,将组里的每个人看作节点,两个人是朋友当且仅当对应的节点邻接,于是得到一个阶简单无向图,G,进而,G,中每节点的度数可能为,0,1,2,n,-1,中一个,.,当,G,中无孤立点时,于是每节点的度数可能为1,2,n,-1.,由于共有,n,个节点,于是必有两节点度数相同,.,当,G,中有孤立点时,这时每节点的度数只可能为,0,1,2,n,-2.,同样由于共,n,有个节点,因此必有两节点度数相同,.,若一个无向图,G,的每节点度数均为,k,则称,G,为,k,-,正则图,(,k,-regular graph).,例子,?,例,7-2(P200),设无向图,G,是一个,3-,正则,(,n,m,),图,且,2,n,3=,m,求,n,和,m,各是多少,?,Hint,根据握手定理有,3,n,=2,m,.,Def 7-9,任意图,G,=(,V,E,):,有向图,G,=(,V,E,):,例子,?,对于无向图,G,=(,V,E,),V,=,v,1,v,2,v,n,称,deg(,v,1,),deg(,v,2,),deg(,v,n,),为的,度数序列,.,对于有向图,还可以定义其出度序列和入度序列,.,例,7-3,是否存在一个无向图,G,其度数序列分别为,(1)7,5,4,2,2,1.,(2)4,4,3,3,2,2.,Solution(1),由于序列,7,5,4,2,2,1,中,奇数个数为奇数,根据握手定理的推论知,不可能存在一个图其度数序列为,7,5,4,2,2,1.,(2),因为序列,4,4,3,3,2,2,中,奇数个数为偶数,可以得到一个无向图,(,见图,7-11),其度数序列为,4,4,3,3,2,2.,7.3,子图、图的运算和图同构,1.,子图,可以通过一个图的子图去考察原图的有关性质以及原图的局部结构,.,Def,设,G,=(,V,E,),和,H,=(,W,F,),是图,若,W,V,且,F,E,则称,H,=(,W,F,),是,G,=(,V,E,),的,子图,(,subgraph,).,若,H,=(,W,F,),是,G,=(,V,E,),的子图且,W,=,V,则称,H,=(,W,F,),是,G,=(,V,E,),的,生成子图,(spanning,subgraph,).,例,7-4,(,一个图的子图较多,),常见的,4,种产生,G,=(,V,E,),的子图的方式如下,:,(1),G,W,设,W,V,则以,W,为节点集合,以两端点均属于,W,的所有边为边集合构成的子图,称为,由,W,导出的子图,(induced,subgraph,by,W,),记为,G,W,.,(2),G,W,设,W,V,导出子图,G,V,W,记为,G,W,是在,G,中去掉所有,W,中的节点,同时也要去掉与,W,中节点关联的所有边,.,通常将,G,v,记为,G,-,v,.,(3),G,F,设,F,E,则以,F,为边集合,以,F,中边的所有端点为节点集合构成的子图,称为,由,F,导出的子图,(induced,subgraph,by,F,),记为,G,F,.,(4),G,F,设,F,E,则从,G,中去掉,F,中的所有边得到的生成子图记为,G,F,.,简单图,G,=(,V,E,),的补图,G,+,U,:(,与子图无关,),2.,图的运算,图的运算就是通过一定的操作,产生“新”的图,.,前面的子图的产生实际上就是图的运算,但它们都是在一个图中进行讨论的,.,也便于用代数方法讨论图,.,在有些问题的讨论中,还会出现两个图之间的一些运算,.,我们在此仅给出定义,请参见有关文献,.,Def,(1),(2),(3),(4),思考,图的每种运算的性质有哪些,?,它与集合的并、交、差、,(,补,),及环和,(,对称差,),运算的性质有什么不同,?,3.,图同构,由于图的拓扑性质,有可能两个表面上看起来不同的图本质上是同一个图,这就是图同构的问题,.,Def(,见书,),直观理解,:,G,1,G,2,是指其中一个图仅经过下列两种变换可以变为另一个图,:,(a),挪动节点的位置；,(b),伸缩边的长短,.,无向图,:,不同构的例子,P204 5.,有向图,:,对于两个有向图同构的判断,特别要注意边的方向的一致性,.,思考,给出至少,4,个两个图同构的必要条件,.,Ulam,猜想,?,