离散数学61图的基本概念

《离散数学61图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章图1第6章图6.1图的基本概念6.2图的连通性6.3图的矩阵表示6.4几种特殊的图26.1图的基本概念6.1.1无向图与有向图6.1.2顶点的度数与握手定理6.1.3简单图、完全图、正则图、圈图、轮图、方体图6.1.4子图、补图6.1.5图的同构3无序对与多重集合无序对:2个元素构成的集合,记作(a,b)无序积:AB={(x,y)

2、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={(

3、1,1),(1,2),(2,2)}多重集合:元素可以重复出现的集合重复度:元素在多重集合中出现的次数例如S={a,b,b,c,c,c},a,b,c的重复度依次为1,2,34无向图定义6.1无向图G=,其中V称为顶点集,其元素称为顶点或结点;E是VV的多重子集,称为边集,其元素称为无向边，简称边.有时用V(G)和E(G)分别表示V和E例如,G=如图所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}e1e2e3e4e5e6e7v5v1v2v3v45

4、有向图定义6.2有向图D=,其中V称为顶点集,其元素称为顶点或结点;E是VV的多重子集,称为边集,其元素称为有向边，简称边.有时用V(D)和E(D)分别表示V和E有限图:V,E都是有穷集合的图n阶图:n个顶点的图零图:E=的图平凡图:1阶零图e1e2e3e4e5e6e7dabc6顶点和边的关联与相邻设无向图G=,ek=(vi,vj)E,称vi,vj为ek的端点,ek与vi(vj)关联.若vi=vj,则称ek为环.无边关联的顶点称作孤立点.若vivj,则称ek与vi(vj)的关联次数为1;若vi=vj,则称ek与vi的关联次数为2;若vi不是边

5、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邻接于vi7顶点的度数设G=为无向图,vV,v的度数(度)d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)

6、vV}G的最小度(G)=min{d(v)

7、vV}例如d(v5)=3,d(v2)=4,d(v1)=4,

8、(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环e1e2e3e4e5e6e7v5v1v2v3v48顶点的度数(续)设D=为有向图,vV,v的出度d+(v):v作为边的始点次数之和v的入度d(v):v作为边的终点次数之和v的度数(度)d(v):v作为边的端点次数之和d(v)=d+(v)+d-(v)+(D),+(D),(D),(D),(D),(D)悬挂顶点,悬挂边例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+=4,+=0,=3,=1,=5,=3e1e2e3e4e5e

9、6e7dabc9握手定理定理6.1任何图(无向图和有向图)的所有顶点度数之和都等于边数的2倍.证图中每条边(包括环)均有两个端点,所以在计算各顶点度数之和时,每条边均提供2度,m条边共提供2m度.推论任何图(无向图和有向图)都有偶数个奇度顶点定理6.2有向图所有顶点的入度之和等于出度之和等于边数证每条边恰好提供1个入度和1个出度10图的度数列设无向图G的顶点集V={v1,v2,…,vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1,v2,…,vn}D的度数列:d(v1),d(v2),…,d(vn)D的出度列:

10、d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc11实例(2)能例1下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇数个奇数.12实例例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2