第14章图的基本概念.ppt

《第14章图的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8/2/202112:17PMDiscreteMath.,ChenChen1离散数学DiscreteMathematics8/2/202112:17PMDiscreteMath.,ChenChen2第十四章图的基本概念§11.1图§11.2通路与回路§11.3图的矩阵表示§11.4图的运算8/2/202112:17PMDiscreteMath.,ChenChen311.1图无向图与有向图顶点的度数握手定理图的同构简单图完全图子图补图8/2/202112:17PMDiscreteMath.,Che

2、nChen4无序对与多重集合无序对:2个元素构成的集合,记作(a,b)无序积:AB={(x,y)

3、xAyB}例如A={a,b,c},B={1,2}AB=BA={(a,1),(b,1),(c,1),(a,2),(b,2),(c,2)}AA={(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)}BB={(1,1),(1,2),(2,2)}多重集合:元素可以重复出现的集合重复度:元素在多重集合中出现的次数例如S={a,b,b,c,c,c},a,b,c的重复度依次为1

4、,2,38/2/202112:17PMDiscreteMath.,ChenChen5无向图定义11.1无向图G=为一个有序的二元组,其中V称为顶点集,其元素称为顶点或结点;E是VV的多重子集,称为边集,其元素称为无向边，简称边.有时用V(G)和E(G)分别表示V和E.图形表示：用小圆圈（或实心点）表示顶点，用顶点间的连线表示无向边，用有方向的连线表示有向边。将图的集合定义转化成图形表示后，常用ek表示无向边(vi,vj)(或有向边)，并称顶点或边用字母标定的图为标定

5、图，否则称为非标定图.定义11.2有向图D=,其中V称为顶点集,其元素称为顶点或结点;E是VV的多重子集,称为边集,其元素称为有向边，简称边.有时用V(D)和E(D)分别表示V和E.8/2/202112:17PMDiscreteMath.,ChenChen6有向图有限图:

6、V(G)

7、,

8、E(G)

9、均为有限数的图.例11.1(2)D=如右下图所示,E={a,a,a,b,a,b,a,d,其中V={a,b,c,d},d,c,c,d,c,b}.例11

10、.1(1)G=如图所示,E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),其中V={v1,v2,…,v5}(v2,v5),(v1,v5),(v4,v5)}.平凡图:1阶零图.零图:E=的图.n阶图:n个顶点的图.用

11、V(G)

12、,

13、E(G)

14、分别表示G的顶点数和边数.8/2/202112:17PMDiscreteMath.,ChenChen7顶点和边的关联与相邻设无向图G=,ek=(vi,vj)E,称vi,vj为ek的端点,ek与vi(vj)关联.若vi

15、=vj,则称ek为环.无边关联的顶点称作孤立点.若vivj,则称ek与vi(vj)的关联次数为1;若vi=vj,则称ek与vi的关联次数为2;若vi不是边e的端点,则称e与vi的关联次数为0.设vi,vjV,ek,elE,若(vi,vj)E,则称vi,vj相邻;若ek,el有一个公共端点,则称ek,el相邻.对有向图有类似定义.设ek=vi,vj是有向图的一条边,又称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi8/2/202112:17PMDiscreteMat

16、h.,ChenChen8邻域和关联集设无向图G,vV(G)v的邻域N(v)={u

17、uV(G)(u,v)E(G)uv}v的闭邻域v的邻域v的先驱元集v的后继元集={u

18、uV(D)E(G)uv}={u

19、uV(D)E(G)uv}设有向图D,vV(D)v的关联集I(v)={e

20、eE(G)e与v关联}=N(v)∪{v}v的闭邻域8/2/202112:17PMDiscreteMath.,ChenChen9简单图定义11.3在无向图中,关联同一对顶点的

21、2条或2条以上的边,称为平行边,平行边的条数称为重数.在有向图中,具有相同始点和终点的2条或2条以上的边称为有向平行边,简称平行边,平行边的条数称为重数.含平行边的图称为多重图既无平行边也无环的图称为简单图例11.1(续)8/2/202112:17PMDiscreteMath.,ChenChen10顶点的度数定义11.4(1)设G=为无向图,vV,v的度数(度)d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)

22、v