《离散数学》课程PPT教学课件（讲稿）第7章 图的基本概念（7.1）无向图及有向图

图论

1 图论

图论部分 ■第7章图的基本概念 ■第8章一些特殊的图 ■第9章树

2 图论部分 ◼ 第7章 图的基本概念 ◼ 第8章 一些特殊的图 ◼ 第9章 树

第7章图的基本概念 71无向图及有向图 72通路、回路、图的连通性 73图的矩阵表示

3 第7章 图的基本概念 7.1 无向图及有向图 7.2 通路、回路、图的连通性 7.3 图的矩阵表示

71无向图及有向图 无向图与有向图 顶点的度数 握手定理 简单图 完全图 子图 ■补图

4 7.1 无向图及有向图 ▪无向图与有向图 ▪顶点的度数 ▪握手定理 ▪简单图 ▪完全图 ▪子图 ▪补图

无向图与有向图 多重集合:元素可以重复出现的集合 无序积:A&B={(xy)|x∈AyEB 定义无向图G=,其中 (1)≠为顶点集,元素称为顶点 (2)E为Ⅳ&的多重子集,其元素e 称为无向边,简称边 例如,G=如图所示, 其中{2v2,…, E={(v1,1),(v1,2),(以2,3),(以2,3),(以2,v5),(v1,s),(v4,)

5 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: AB={(x,y) | xAyB} 定义 无向图G=, 其中 (1) V为顶点集，元素称为顶点 (2) E为VV的多重子集，其元素 称为无向边，简称边. 例如, G=如图所示, 其中V={v2 , v2 , …,v5 }, E={(v1 ,v1 ), (v1 ,v2 ), (v2 ,v3 ), (v2 ,v3 ), (v2 ,v5 ), (v1 ,v5 ), (v4 ,v5 )}

无向图与有向图(续) 定义有向图D=,其中 (1)W同无向图的顶点集,元素也称为顶点 (2)E为×的多重子集,其元素 称为有向边,简称边 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图,试写出它的V和E 注意:图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的

6 无向图与有向图(续) 定义 有向图D=, 其中 (1) V同无向图的顶点集,元素也称为顶点 (2) E为VV的多重子集，其元素 称为有向边，简称边. 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的

无向图与有向图(续) 通常用G表示无向图,D表示有向图,也常用G泛指 无向图和有向图,用e表示无向边或有向边 VO,E(G),V(D,E(D):G和D的顶点集,边集 n阶图:n个顶点的图 有限图:VE都是有穷集合的图 零图:E=⑦ 平凡图:1阶零图 空图:V=

7 无向图与有向图(续) 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E= 平凡图: 1 阶零图 空图: V=

顶点和边的关联与相邻 定义设k=(v以是无向图G=,v"EV,kH∈E,若(v∈E,则称 相邻;若ek2至少有一个公共端点,则称eke7相邻 对有向图有类似定义.设e=(v》是有向图的一条边,又称v是 e的始点,v是e的终点,v邻接到vv邻接于1

8 顶点和边的关联与相邻 定义 设ek=(vi , vj )是无向图G=的一条边, 称vi , vj为ek的端 点, ek与vi ( vj )关联. 若vi  vj , 则称ek与vi ( vj )的关联次数为1; 若vi = vj , 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不 是ek端点, 则称ek与vi 的关联次数为0. 无边关联的顶点称作 孤立点. 定义 设无向图G=, 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邻接于vi

邻域和关联集 设无向图G,v∈VG v的邻域N(v)={∈(∧(u,y)∈E(ONM≠-y} v的闭邻域N(v)=N()U{吵 v的关联集I(v)={ele∈E(O)∧e与v关联} 设有向图D,v∈VD) v的后继元集(v){u∈(D)入M>∈E(GM≠ v的先驱元集rn(v){uu∈(D)A,D>E(G)M≠v v的邻域ND(v)=Tb(v)∪I(v) v的闭邻域N2(v)=N2(叫)儿∪{v

9 邻域和关联集 N (v) (v) D +  N (v) N (v) {v} D = D  (v) D −  N (v) (v) (v) D D D + − =   设无向图G, vV(G) v的邻域 N(v)={u|uV(G)(u,v)E(G)uv} v的闭邻域 = N(v)∪{v} v的关联集 I(v)={e|eE(G)e与v关联} 设有向图D, vV(D) v的后继元集 ={u|uV(D)E(G)uv} v的先驱元集 ={u|uV(D)E(G)uv} v的邻域 v的闭邻域

顶点的度数 设G=为无向图,veV v的度数(度)d():作为边的端点次数之和 悬挂顶点:度数为1的顶点 悬挂边:与悬挂顶点关联的边 2 G的最大度A(G=max{(ve吟 G的最小度8(G=min{(v∈吟23 5 例如(v5)=3,以(2)=4,d(v1)=4, A(G)=4,(G)=1 v4是悬挂顶点,e7是悬挂边,e1是环 10

10 顶点的度数 设G=为无向图, vV, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G的最大度(G)=max{d(v)| vV} G的最小度(G)=min{d(v)| vV} 例如 d(v5 )=3, d(v2 )=4, d(v1 )=4, (G)=4, (G)=1, v4是悬挂顶点, e7是悬挂边, e1是环