81图的基本概念.ppt

图论 图论部分 第8章 图的基本概念 第9章 树 第10章 几种典型图 第8章 图的基本概念 8.1图的定义及相关术语 8.2 通路、回路、图的连通性 8.3 图的矩阵表示 8.1 图的定义及相关术语 无向图与有向图 顶点的度数 握手定理 简单图 完全图 子图 补图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A?B={(x,y) | x?A?y?B} 定义 无向图G=V,E, 其中 (1) V??为顶点集，元素称为顶点 (2) E为V?V的多重子集，其元素 称为无向边，简称边. 例如, G=V,E如图所示, 其中V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 无向图与有向图(续) 定义 有向图D=V,E, 其中 (1) V同无向图的顶点集, 元素也称为顶点 (2) E为V?V的多重子集，其元素 称为有向边，简称边. 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的 无向图与有向图(续) 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 多重图与简单图 定义 (1) 在无向图中,如果有2条或2条以上的边关联同一对顶点, 则称这些边为平行边, 平行边的条数称为重数. (2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平行边, 简称平行边, 平行边的条数称为重数. (3) 含平行边（无环）的图称为多重图. (4) 既无平行边也无环的图称为简单图. 注意:简单图是极其重要的概念 多重图与简单图(续) 例如 完全图与正则图 n阶无向完全图Kn: 每个顶点都与其余顶点相邻的n阶无向简单图. 简单性质: 边数m=n(n-1)/2, ?=?=n-1 n阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n阶有向简单图. 简单性质: 边数m=n(n-1), ?=?=2(n-1), ?+=?+=?-=?-=n-1 n阶k正则图: ?=?=k 的n阶无向简单图 简单性质: 边数m=nk/2 完全图与正则图(续) (1) 为5阶完全图K5 (2) 为3阶有向完全图 (3) 为彼得森图, 它是3 正则图 顶点和边的关联与相邻 定义 设ek=(vi, vj)是无向图G=V,E的一条边, 称vi, vj为ek的端点, ek与vi ( vj)关联. 若vi ? vj, 则称ek与vi ( vj)的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不是ek端点, 则称ek与vi 的关联次数为0. 无边关联的顶点称作孤立点. 定义 设无向图G=V,E, 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,E为无向图, 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是环 顶点的度数(续) 设D=V,E为有向图, 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) 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0