《《图的基本概念》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图的基本概念》PPT课件.ppt（58页珍藏版）》请在金锄头文库上搜索。
1、第14章 图的基本概念 离 散 数 学 中国地质大学本科生课程 本章内容 14 1 图 14 2 通路与回路 14 3 图的连通性 14 4 图的矩阵表示 14 5 图的运算 基本要求 作业 14 1 图的基本概念 q 图的定义 q 图的一些概念和规定 q 简单图和多重图 q 顶点的度数与握手定理 q 图的同构 q 完全图与正则图 q 子图与补图 无序积与多重集合 q 元素可以重复出现的集合称为多重集合或者多重集 某元 素重复出现的次数称为该元素的重复度 例如 在多重集合 a a b b b c d 中 a b c d的重复度分别为2 3 1 1 定义14 1 一个无向图是一个有序的二元组 记
2、作G 其中 1 V 称为顶点集 其元素称为顶点或结点 2 E称为边集 它是无序积V V的多重子集 其元素称为无向 边 简称边 定义14 2 一个有向图是一个有序的二元组 记作D 其中 1 V 称为顶点集 其元素称为顶点或结点 2 E为边集 它是笛卡儿积V V的多重子集 其元素称为有向 边 简称边 无向图和有向图 说明q 可以用图形表示图 即用小圆圈 或实心点 表示顶 点 用顶点之间的连线表示无向边 用有方向的连线 表示有向边 例14 1 例14 1 1 给定无向图G 其中 V v1 v2 v3 v4 v5 E v1 v1 v1 v2 v2 v3 v2 v3 v2 v5 v1 v5 v4 v5
3、2 给定有向图D 其中 V a b c d E 画出G与D的图形 图的一些概念和规定 q G表示无向图 但有时用G泛指图 无向的或有向的 q D只能表示有向图 q V G E G 分别表示G的顶点集和边集 q 若 V G n 则称G为n阶图 q 若 V G 与 E G 均为有限数 则称G为有限图 q 若边集E G 则称G为零图 此时 又若G为n阶图 则称G 为n阶零图 记作Nn 特别地 称N1为平凡图 q 在图的定义中规定顶点集V为非空集 但在图的运算中可能产 生顶点集为空集的运算结果 为此规定顶点集为空集的图为空 图 并将空图记为 标定图与非标定图 基图 q 将图的集合定义转化成图形表示之后
4、 常用ek表示无向边 vi vj 或有向边 并称顶点或边用字母标定 的图为标定图 否则称为非标定图 q 将有向图各有向边均改成无向边后的无向图称为原来图的 基图 q 易知标定图与非标定图是可以相互转化的 任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图 关联与关联次数 环 孤立点 q 设G 为无向图 ek vi vj E 称vi vj为ek的端点 ek与vi或ek与vj是彼此相关联的 若vi vj 则称ek与vi或ek与vj的关联次数为1 若vi vj 则称ek与vi的关联次数为2 并称ek为环 若端点vl不与边ek关联 则称ek与vl的关联次数为0 q 设D 为有向图 ek E 称
5、vi vj为ek的端点 若vi vj 则称ek为D中的环 q 无论在无向图中还是在有向图中 无边关联的顶点均称为孤立 点 相邻与邻接 q 设无向图G vi vj V ek el E 若 et E 使得et vi vj 则称vi与vj是相邻的 若ek与el至少有一个公共端点 则称ek与el是相邻的 q 设有向图D vi vj V ek el E 若 et E 使得et 则称vi为et的始点 vj为et的终 点 并称vi邻接到vj vj邻接于vi 若ek的终点为el的始点 则称ek与el相邻 邻域 q 设无向图G v V 称 u u V u v E u v 为v的邻域 记做NG v 称NG v v
6、 为v的闭邻域 记做NG v 称 e e E e与v相关联 为v的关联集 记做IG v q 设有向图D v V 称 u u V E u v 为v的后继元集 记做 D v 称 u u V E u v 为v的先驱元集 记做 D v 称 D v D v 为v的邻域 记做ND v 称ND v v 为v的闭邻域 记做ND v 举例 NG v1 D d v2 v5 NG v1 v1 v2 v5 IG v1 e1 e2 e3 c D d a c ND d a c ND d a c d 简单图与多重图 定义14 3 在无向图中 关联一对顶点的无向边如果多于1条 则称这些边为平行边 平行边的条数称为重数 在有向
7、图中 关联一对顶点的有向边如果多于1条 并且这些 边的始点和终点相同 也就是它们的方向相同 则称这些边 为平行边 含平行边的图称为多重图 既不含平行边也不含环的图称为简单图 例如 在图14 1中 a 中e5与e6是平行边 b 中e2与e3是平行边 但e6与e7不是平行边 a 和 b 两个图都不是简单图 顶点的度数 定义14 4 设G 为一无向图 v V 称v作为边的端点 次数之和为v的度数 简称为度 记做 dG v 在不发生混淆时 简记为d v 设D 为有向图 v V 称v作为边的始点次数之和为v的出度 记做d D v 简记作 d v 称v作为边的终点次数之和为v的入度 记做d D v 简记作
8、 d v 称d v d v 为v的度数 记做d v 图的度数的相关概念 q 在无向图G中 最大度 G max d v v V G 最小度 G min d v v V G q 在有向图D中 最大出度 D max d v v V D 最小出度 D min d v v V D 最大入度 D max d v v V D 最小入度 D min d v v V D q 称度数为1的顶点为悬挂顶点 与它关联的边称为悬挂边 度为偶数 奇数 的顶点称为偶度 奇度 顶点 图的度数举例 d v1 4 注意 环提供2度 4 1 v4是悬挂顶点 e7是悬挂边 d a 4 d a 1 环e1提供出度1 提供入度1 d a
9、 4 1 5 5 3 4 在a点达到 0 在b点达到 3 在b点达到 1 在a和c点达到 握手定理 定理14 1 设G 为任意无向图 V v1 v2 vn E m 则 说明任何无向图中 各顶点度数之和等于边数的两倍 证明G中每条边 包括环 均有两个端点 所以在计算G中各顶点度数之和时 每条边均提供2度 当然 m条边 共提供2m度 定理14 2 设D 为任意有向图 V v1 v2 vn E m 则 握手定理的推论 推论任何图 无向的或有向的 中 奇度顶点的个数是偶数 证明设G 为任意一图 令 V1 v v V d v 为奇数 V2 v v V d v 为偶数 则V1 V2 V V1 V2 由握手
10、定理可知 由于2m和 所以为偶数 但因V1中顶点度数为奇数 所以 V1 必为偶数 问题研究 问题 在一个部门的25个人中间 由于意见不同 是否可能每个 人恰好与其他5个人意见一致 解答 不可能 考虑一个图 其中顶点代表人 如果两个人意见 相同 可用边连接 所以每个顶点都是奇数度 存在奇数个度 数为奇数的图 这是不可能的 说明 1 很多离散问题可以用图模型求解 2 为了建立一个图模型 需要决定顶点和边分别代表什么 3 在一个图模型中 边经常代表两个顶点之间的关系 度数列 设G 为一个n阶无向图 V v1 v2 vn 称d v1 d v2 d vn 为G的度数列 对于顶点标定的无向图 它的度数列是
11、唯一的 反之 对于给定的非负整数列d d1 d2 dn 若存在V v1 v2 vn 为顶点集的n阶无向图G 使得d vi di 则称d 是可图化的 特别地 若所得图是简单图 则称d是可简单图化的 类似地 设D 为一个n阶有向图 V v1 v2 vn 称 d v1 d v2 d vn 为D的度数列 另外称d v1 d v2 d vn 与d v1 d v2 d vn 分别为D的 出度列和入度列 度数列举例 按顶点的标定顺序 度数列为 4 4 2 1 3 按字母顺序 度数列 出度列 入 度列分别为 5 3 3 3 4 0 2 1 1 3 1 2 可图化的充要条件 定理14 3 设非负整数列d d1
12、d2 dn 则d是可图化的当 且仅当 证明必要性 由握手定理显然得证 充分性 由已知条件可知 d中有偶数个奇数度点 奇数度点两两之间连一边 剩余度用环来实现 53 31 定理14 3的证明 由握手定理可知必然性显然 下面证明充分性 由已知条件可知 d中有2k 0 k n 2 个奇数 不妨设它们为d1 d2 dk dk 1 dk 2 d2k 可用多种方法做出n阶无向图G V v1 v2 vn 比如边集如下产生 在顶点vr与vr k之间连边 r 1 2 k 若di为偶数 令d i di 若di为奇数 令d i di 1 得d d 1 d 2 d n 则d i均为偶数 再在vi处做出d i 2条环
13、i 1 n 将所得各边集合在一起组成E 则G的度数列为d 其实 di为偶数时 d vi 2 d i 2 2 di 2 di 当di为奇数时 d vi 1 2 d i 2 1 d i 1 di 1 di 这就证明了d是可图化的 可图化举例 由定理14 3立即可知 3 3 2 1 3 2 2 1 1 等是不可图化的 3 3 2 2 3 2 2 2 1 等是可图化的 定理14 4 定理14 4 设G为任意n阶无向简单图 则 G n 1 证明因为G既无平行边也无环 所以G中任何顶点v至多与其余的n 1个顶点均相邻 于是d v n 1 由于v的任意性 所以 G n 1 例14 2 判断下列各非负整数列哪
14、些是可图化的 哪些是可简 单图化的 1 5 5 4 4 2 1 不可图化 2 5 4 3 2 2 可图化 不可简单图化 若它可简单图化 设所得图为G 则 G max 5 4 3 2 2 5 这与定理14 4矛盾 例14 2 3 3 3 3 1 可图化 不可简单图化 假设该序列可以简单图化 设G 以该序列为度数列 不妨设V v1 v2 v3 v4 且 d v1 d v2 d v3 3 d v4 1 由于d v4 1 因而v4只能与v1 v2 v3之一相邻 于是v1 v2 v3不可能都是3度顶点 这是矛盾的 因而 3 中序列也不可简单图化 4 d1 d2 dn d1 d2 dn 1 且 为偶数 可
15、图化 不可简单图化 例14 2 5 4 4 3 3 2 2 可简单图化 下图中两个6阶无向简单图都以 5 中序列为度 数列 图的同构 定义14 5 设G1 G2 为两个无向图 若存在双射函数f V1 V2 对于vi vj V1 vi vj E1 当且仅当 f vi f vj E2 并且 vi vj 与 f vi f vj 的重数相同 则称G1与G2是同构的 记做G1 G2 说明 1 类似地 可以定义两个有向图的同构 2 图的同构关系看成全体图集合上的二元关系 3 图的同构关系是等价关系 4 在图同构的意义下 图的数学定义与图形表示 是一一对应的 图的同构举例 彼得森 Petersen 图 完全
16、图 定义14 6 设G为n阶无向简单图 若G中每个顶点均与其余的n 1 个顶点相邻 则称G为n阶无向完全图 简称n阶完全图 记做 Kn n 1 设D为n阶有向简单图 若D中每个顶点都邻接到其余的n 1个 顶点 又邻接于其余的n 1个顶点 则称D是n阶有向完全图 设D为n阶有向简单图 若D的基图为n阶无向完全图Kn 则称D 是n阶竞赛图 完全图举例 n阶无向完全图的边数为 n n 1 2 n阶有向完全图的边数为 n n 1 n阶竞赛图的边数为 n n 1 2 K53阶有向完全图4阶竞赛图 正则图 定义14 7 设G为n阶无向简单图 若v V G 均有d v k 则称G为k 正则图 举例n阶零图是0 正则图 n阶无向完全图是 n 1 正则图 彼得森图是3 正则图 说明n阶k 正则图中 边数m kn 2 当k为奇数时 n必为偶数 子图 定义14 8 设G G 为两个图 同为无向图或 同为有向图 若V V且E E 则称G 是G的子图 G为G 的母图 记作G G 若V V或E E 则称G 为G的真子图 若V V 则称G 为G的生成子图 设G 为一图 V1 V且V1 称以V1为顶点集 以G 中两个
