离散数学 第3章 图的基本概念.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机数学基础,(,上,),第,2,编,图 论,第三章 图的基本概念,3.1,图的概念与性质,一、图的定义与表示,1,。图,由结点的集合,V,和边的集合,E,组成的有序对,称为图,G,。,2,。,有向图、无向图,每条边都是有向边的图称为有向图，每条边都是,无向边的图称为无向图，否则称为混合图。,3,。孤立点、零图,不与其它结点相关联的结点称为孤立点，全部由,孤立点构成的图叫做零图。,4,。边的重数,具有相同始点和终点的边称为平行边，平行边的,条数称为边的重数。,5,。,n,阶图,具有,n,个结点的图称为,n,阶图，具有,n,个结点和,m,条边的图称为,(,n,m,),图,6,。结点的度数,图中与某结点,v,相关联的边数,(,自回路算两条边,),，,称为该结点的度数，记作,deg(v),。,其中以,v,为始点的边,数称为出度,deg,+,(v),，以,v,为终点的边数成为入度,deg,-,(v),因此有,图,G,中结点的最大、最小度数记做,(G),、,(G,),二、图的基本概念与握手定理,1,。握手定理,图,G,中所有结点的度数之和等于边数的二倍。,推论,1,在任何图中，度数为奇数的结点数必为偶数。,推论,2,在有向图中，所有结点的入度之和等于所有结点的出度之和。,例题,1,：,已知图,G,中有,1,个,1,度结点，,2,个,2,度结点，,3,个,3,度结,点，,4,个,4,度结点，则,G,的边数是,。,解：,例题,2,：,设图,G=,，,则下列结论成立的是,。,A)B),C)D),例题,3,：,设简单连通无向图,G,有,12,条边，,G,中有,2,个,1,度结点,2,个,2,度结点，,3,个,4,度结点，其余结点度数为,3,，求,G,中,有多少个结点。试作一个满足该条件的简单无向图。,解,:,设,G,中有,x,个结点，则,3,度的结点有,x-7,。,根据握手定理有，,解得,故,G,中有,9,个结点。,满足条件的图如下：,2,。简单图,不含平行边和环,(,自回路,),的图称为简单图。,在简单图中，任何结点的度数都小于等于,n-1,。这,是判断一个度数序列能否构成简单图的主要依据。,3,。二部图,若将无向图,G,的结点集分为两部分，而每一部分中,任何两个结点之间都没有边相连，则,G,称为二部图。,4,。完全图,每一对结点之间都有边相连的无向简单图称为无,向完全图，每一对结点之间都有方向相反的两条边相,连的有向简单图称为有向完全图。,具有,n,个结点的无向完全图,Kn,的边数为：,例题,4,：,设图,G,是有,n,个结点的无向完全图，则,G,的边数为,。,A)n(n-1)B)n(n+1),C)D),C,5,。正则图,若无向简单图,G,中每个结点的度数都为,k,，则,G,称,为,k-,正则图。,6,。赋权图,若图,G,中的每一条边都有一个表示长度的实数，,则图,G,称为赋权图或网络。图,G,为无向图称为无向赋权,图，图,G,为有向图称为有向赋权图。,7,。补图,由图,G,中的所有结点和构成完全图需添加的边所组成的图称为,G,的补图，记作 。,例题,5,：,已知图的结点集 以及图,G,和图,D,的,边集合分别为：,试作图,G,和图,D,，,写出各结点的度数，回答图,G,、图,D,是简单图还是多重图？,解：,a d a d,b c b c,图,G,图,D,图,G,：,图,D,：,图,G,不,是简单无向图，图,D,是简单有向图。,8,、子图,1,。已知图,G=,，,如果,则,G=,称为,G,的子图。,2,。如果 ，则称,G,为,G,的真子图。,3,。如果 ，则称,G,为,G,的生成子图。,三、图的同构,如果图,G,中的结点集,V,与图,G,中的结点集,V,具有,一一对应的关系，并且对应的边都具有相同的重数，,则称,G,与,G,同构，记作 。,因此，两图同构必须满足下列条件：,结点数相同，,边数相同，,度数相同的结点数相同。,上述条件是两图同构的必要条件，但不是充分条,件，也就是说，两个图即使满足上述条件也不一定同,构。如果把其中一个图中的结点重新排列，边跟着结,点移动，并且可以任意弯曲，能够与另一图完全,重合，那么这两个图是同构的。,四、通路与回路,1,。通路、回路,在,G=,中，如果从结点,v,0,依次经过边和结,点可以到达,v,n,，,则称,v,0,与,v,n,间存在通路，或,v,0,与,v,n,连,通，记作,v,0,v,n,，如,v,0,v,n,则称为回路。通路经过,的边数称为通路的的长度。,2,。简单通路、简单回路,没有重复边的通路称为简单通路，没有重复边,的回路称为简单回路。,3,。基本通路、基本回路,没有重复结点的通路称为基本通路，没有重复,结点的回路称为基本回路。,例题,6,：,设,G,如图，已知通路,试回答它们各是简单通路、简单回路、基本通路,和基本回路。,解：,是简单通路，基本通路，,是简单回路，但不,是基本回路，,是简单回路，基本回路，,是简单通,路，但不是基本通路。,v1,v2 v5,v3 v4,一、连通性,若在无向图,G,中，任何两个不同的结点都是连通的,则称,G,是连通图。,无向图中结点的连通关系具有自反性、对称性和,传递性，所以结点的连通关系是等价关系。,若图,G,不是连通图，但如果把,G,分成几个部分，每,一个部分都是连通的，则每一个部分称为一个连通子,图，每一个连通子图,G,称为,G,的一个连通分支。,G,中相互连通的结点一定在同一连通分支中。,无向图,G,的连通分支数记作,W(G),。,3.2,图的连通性,例如,G,：,G,不是连通图，但可以划分为三个连通分支。,是一个连通分支，是一个连,通分支，是一个连通分支。,称为,V,的一个划分。,二、有向连通图,1,。强连通图、单侧连通图、弱连通图,在有向简单图,D,中，,(1),若任何两个结点间都可以到达则称为强连通图,(2),若任何两个结点间，总有一个结点可以到达另一,个结点，则称为单侧连通图，,(3),若在不考虑边的方向的情况下图是连通的，则称为弱连通图。,连通图举例,强连通图 单侧连通图 弱连通图,2,。两个定理,定理,6,一个有向图是强连通的充分必要条件是存在一条至少经过每个结点一次的回路。,定理,7,在有向图中，它的每个结点必位于且仅位于一个强分图中。,例题,7,：,设,V,a,b,c,d,与,V,能构成强连通图的边集,E,(),(A),(B),(C),(D),三、连通度,1,。点割集,在无向连通图,G=,中，若删除结点集,V(,包括,所有与,V,中的结点关联的边,),，得到子图,G,V,。若,V,是使,G,V,不连通的最小点集，则称,V,是,G,的一个点,割集。若,V,中只有一个结点则称为割点。,换句话说，点割集是指使图,G,从连通图变成不连,通图需要删除的最小点集。,例如，,G,：,删除,v,1,后,G,1,删除,v,3,后,G,2,删除,v,1,v,3,后,G,3,因此，,v,1,不是点割集，,W(G,1,)=1,，,v,3,是点割集，又是割点，,W(G,2,)=2,v,1,v,3,不是点割集，因为它不是最小点集。,例题,8,：,给定图,G,，,则图,G,的点割集,是,。,2,。边割集,在无向连通图,G=,中，若删除边集,E,，,得到,子图,G,E,。若,E,是使,G,E,不连通的最小边集，则称,E,是,G,的一个边割集。若,E,中仅一条边则称为割边。,换句话说，边割集是指使图,G,的从连通图变成不,连通图需要删除的最小边集。,例如，,G,：,删除边,(v,1,v,2,),后,G,1,删除,(v,1,v,2,),(v,2,v,3,),后,G,2,删除,(v,3,v,5,),后,G,3,因此，,(v,1,v,2,),不是边割集，,W(G,1,)=1,，,(v,1,v,2,),(v,2,v,3,),是边割集，,W(G,2,)=2,，,(v,3,v,5,),是边割集，也是割边，,W(G,3,)=2,。,3,。连通度,(,一,),点连通度,若,G,是无向连通图，,V,是,G,的结点数最少的点割集,或,G,V,是平凡图,(,孤点,),，则,V,中的结点数称为,G,的点,连通度，记作 。,因此，,(1),若,G,是平凡图，则,V=,，,，,(2),若,G,是完全图，去掉,n-1,个结点才能成为平凡,图，所以 ，,(3),若,G,存在割点，则 ，,(4),若,G,是非连通图，则 。,(,二,),边连通度,若,G,是无向连通图，,E,是,G,的边数最少的边割集，,则,E,中的边数称为,G,的边连通度，记作 。,因此，,(1),若,G,是平凡图，则,E=,，,，,(2),若,G,存在割边，则 ，,(3),若,G,是非连通图，则 。,(,三,),之间的关系,在无向图,G,中，一定有：,即点连通度不大于边连通度，边连通度不大于结,点的最小度数。,3.3,图的矩阵表示,一、无向图的邻接矩阵,对于无向图,G=,，若,|V|=n,，作,n,阶方阵,A(G),其中的 表示 相关联的边数。,例如图,G,如下，,可以看出，,A(G),是对称矩阵。,主对角线上的元素表示各结点的自回路数。,二、有向图的邻接矩阵,对于有向图,D=,，若,|V|=n,，作,n,阶方阵,A(D),其中的 表示从 的边数。,从下例中可以看出,A(D),不再是对称矩阵。,矩阵中所有元素之和等于有向图中的边数。,第 行元素之和表示结点 的出度，,第 列元素之和表示结点 的入度，,图,D,：,例题,9,：,设有向图,D,的邻接矩阵为,A,(,D,)=,，,那么,E,。,例题,10,：,有向图的邻接矩阵,(D)=,中第 行元素的,和 是中的结点 的,。,三、计算边数,在邻接矩阵,A(D),中，,为长度为,1,的边数。,在,A,2,(D),中，为长度为,2,的边数。,一般地说，在,中，为长度为 的边,数。,位置 上的数表示从 长度为 的边数。,在,A(D)+A,2,(D)+,A,k,(D,),中，为长度小于等,于,k,的边数之和，位置 上的数表示从 长度小,于等于,k,的边数之和。,例如，在前例中,长度为,2,的边共有,5,条，从 的回路有,1,条。,长度小于等于,2,的边共有,9,条。,例题,11,：,设有向图,D=,，,求,D,中,v,2,到,v,4,长度分别为,1,，,2,，,3,的通路的条数。,解：,例题,12,：,已知图,D,的邻接矩阵为,求从,v,2,到,v,4,长度为,2,和从,v,3,到,v,3,长度为,2,的通路条数，,并将它们具体写出,.,解：,例题,13,：,设有向图,D=,，,其中,求,D,的邻接矩阵；,判断图,D,是强连通图、单侧连通图还是弱连通图。,解：,