《离散数学第14章课件PPT,,屈婉玲,耿素云,张立昂主编》由会员分享，可在线阅读，更多相关《离散数学第14章课件PPT,,屈婉玲,耿素云,张立昂主编（43页珍藏版）》请在金锄头文库上搜索。
1、1 第五部分图论 本部分主要内容图的基本概念欧拉图 哈密顿图树 2 第十四章图的基本概念 主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合 元素可以重复出现的集合无序积 A B x y x A y B 3 14 1图 定义14 1无向图G 其中 1 V 为顶点集 元素称为顶点 2 E为V V的多重集 其元素称为无向边 简称边实例设V v1 v2 v5 E v1 v1 v1 v2 v2 v3 v2 v3 v2 v5 v1 v5 v4 v5 则G 为一无向图 4 有向图 定义14 2有向图D 只需注意E是V V的多重子集图2表示的是一个有向图 试写出它的V和E注意 图的数学定义与
2、图形表示 5 相关概念 1 图 可用G泛指图 无向的或有向的 V G E G V D E D n阶图2 有限图3 n阶零图与平凡图4 空图 5 用ek表示无向边或有向边6 顶点与边的关联关系 关联 关联次数 环 孤立点7 顶点之间的相邻关系 6 8 邻域与关联集 v V G G为无向图 v的关联集 v V D D为有向图 9 标定图与非标定图10 基图 相关概念 7 多重图与简单图 定义14 3 1 无向图中的平行边及重数 2 有向图中的平行边及重数 注意方向性 3 多重图 4 简单图在定义14 3中定义的简单图是极其重要的概念 8 顶点的度数 定义14 4 1 设G 为无向图 v V d v
3、 v的度数 简称度 2 设D 为有向图 v V d v v的入度d v v的出度d v v的度或度数 3 G G 4 D D D D D D 5 奇顶点度与偶度顶点 9 定理14 1设G 为任意无向图 V v1 v2 vn E m 则 证G中每条边 包括环 均有两个端点 所以在计算G中各顶点度数之和时 每条边均提供2度 m条边共提供2m度 本定理的证明类似于定理14 1 握手定理 定理14 2设D 为任意有向图 V v1 v2 vn E m 则 10 握手定理推论 推论任何图 无向或有向 中 奇度顶点的个数是偶数 证设G 为任意图 令V1 v v V d v 为奇数 V2 v v V d v
4、为偶数 则V1 V2 V V1 V2 由握手定理可知由于2m 均为偶数 所以为偶数 但因为V1中顶点度数为奇数 所以 V1 必为偶数 11 例1无向图G有16条边 3个4度顶点 4个3度顶点 其余顶点度数均小于3 问G的阶数n为几 解本题的关键是应用握手定理 设除3度与4度顶点外 还有x个顶点v1 v2 vx 则d vi 2 i 1 2 x 于是得不等式32 24 2x得x 4 阶数n 4 4 3 11 握手定理应用 12 图的度数列 1 V v1 v2 vn 为无向图G的顶点集 称d v1 d v2 d vn 为G的度数列2 V v1 v2 vn 为有向图D的顶点集 D的度数列 d v1 d
5、 v2 d vn D的入度列 d v1 d v2 d vn D的出度列 d v1 d v2 d vn 3 非负整数列d d1 d2 dn 在什么条件下是可图化的 是可简单图化的 定理14 4p277易知 2 4 6 8 10 1 3 3 3 4 是可图化的 后者又是可简单图化的 而 2 2 3 4 5 3 3 3 4 都不是可简单图化的 特别是后者也不是可图化的 13 n阶完全图与竞赛图 定义14 6 1 n n 1 阶无向完全图 每个顶点与其余顶点均相邻的无向简单图 记作Kn 简单性质 边数 2 n n 1 阶有向完全图 每对顶点之间均有两条方向相反的有向边的有向简单图 简单性质 3 n n
6、 1 阶竞赛图 基图为Kn的有向简单图 简单性质 边数 14 n阶k正则图 1 为K5 2 为3阶有向完全图 3 为4阶竞赛图 1 2 3 定义14 7n阶k正则图 k的无向简单图简单性质 边数 由握手定理得 n阶完全图Kn是n 1正则图 15 子图 定义14 8G G 1 G G G 为G的子图 G为G 的母图 2 若G G且V V 则称G 为G的生成子图 3 若V V或E E 称G 为G的真子图 4 V V V且V 的导出子图 记作G V 5 E E E且E 的导出子图 记作G E 16 例2画出K4的所有非同构的生成子图 实例 17 补图 定义14 9设G 为n阶无向简单图 以V为顶点集
7、 以所有使G成为完全图Kn的添加边组成的集合为边集的图 称为G的补图 记作 若G 则称G是自补图 例 见书P280图14 6 18 14 2通路与回路 定义14 11给定图G 无向或有向的 G中顶点与边的交替序列 v0e1v1e2 elvl vi 1 vi是ei的端点 1 通路与回路 为通路 若v0 vl 为回路 l为回路长度 2 简单通路与回路 所有边各异 为简单通路 又若v0 vl 为简单回路 3 初级通路 路径 与初级回路 圈 中所有顶点各异 则称 为初级通路 路径 又若除v0 vl 所有的顶点各不相同且所有的边各异 则称 为初级回路 圈 4 复杂通路与回路 有边重复出现 19 几点说明
8、 表示法 定义表示法 只用边表示法 只用顶点表示法 在简单图中 混合表示法环 长为1的圈 的长度为1 两条平行边构成的圈长度为2 无向简单图中 圈长 3 有向简单图中圈的长度 2 不同的圈 以长度 3的为例 20 通路与回路的长度 定理14 5在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于n 1的通路 推论在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于n 1的初级通路 路径 定理14 6在一个n阶图G中 若存在vi到自身的回路 则一定存在vi到自身长度小于或等于n的回路 推论在一个n阶图G中 若存在vi到自身的
9、简单回路 则一定存在长度小于或等于n的初级回路 21 14 3图的连通性 无向图的连通性 1 顶点之间的连通关系 G 为无向图 若vi与vj之间有通路 则vi vj 是V上的等价关系R u v V且u v 2 G的连通性与连通分支 若 u v V u v 则称G连通 V1 V2 Vk 称G V1 G V2 G Vk 为连通分支 其个数p G k k 1 k 1 G连通 22 短程线与距离 3 短程线与距离 u与v之间的短程线 u v u与v之间长度最短的通路 u与v之间的距离 d u v 短程线的长度 d u v 的性质 d u v 0 u v时d u v d u v d v u d u v
10、d v w d u w 23 无向图的连通度 1 删除顶点及删除边G v 从G中将v及关联的边去掉G V 从G中删除V 中所有的顶点G e 将e从G中去掉G E 删除E 中所有边2 点割集与边割集点割集与割点书p283定义14 15G V VV 为点割集 p G V p G 且有极小性v为割点 v 为点割集定义14 16G E EE 是边割集 p G E p G 且有极小性e是割边 桥 e 为边割集 24 点割集与割点 例3 v1 v4 v6 是点割集 v6是割点 v2 v5 是点割集吗 e1 e2 e1 e3 e5 e6 e8 等是边割集 e8是桥 e7 e9 e5 e6 是边割集吗 几点说
11、明 Kn中无点割集 Nn中既无点割集 也无边割集 其中Nn为n阶零图 若G连通 E 为边割集 则p G E 2 V 为点割集 则p G V 2 25 点连通度与边连通度 定义14 18G为连通非完全图点连通度 G min V V 为点割集 规定 Kn n 1 若G非连通 G 0 若 G k 则称G为k 连通图定义14 19设G为连通图边连通度 G min E E 为边割集 若G非连通 则 G 0若 G r 则称G是r边 连通图图中 1 它是1 连通图和1边 连通图 26 有向图的连通性 定义14 20D 为有向图vi vj vi可达vj vi到vj有通路vi vj vi与vj相互可达 性质 具
12、有自反性 vi vi 传递性 具有自反性 对称性 传递性vi到vj的短程线与距离类似于无向图中 只需注意距离表示法的不同 无向图中d vi vj 有向图中d 及d无对称性 27 有向图的连通性及分类 定义14 22D 为有向图D弱连通 连通 基图为无向连通图D单向连通 vi vj V vi vj或vj viD强连通 vi vj V vi vj易知 强连通 单向连通 弱连通判别法定理14 8D强连通当且仅当D中存在经过每个顶点至少一次的回路定理14 9D单向连通当且仅当D中存在经过每个顶点至少一次的通路 28 二部图 定义14 23设G 为一个无向图 若能将V分成V1和V2 V1 V2 V V1
13、 V2 使得G中的每条边的两个端点都是一个属于V1 另一个属于V2 则称G为二部图 或称二分图 偶图等 称V1和V2为互补顶点子集 常将二部图G记为 又若G是简单二部图 V1中每个顶点均与V2中所有的顶点相邻 则称G为完全二部图 记为Kr s 其中r V1 s V2 注意 n阶零图为二部图 29 14 4图的矩阵表示 无向图的关联矩阵 对图无限制 P288定义14 24无向图G V n E m 令mij为vi与ej的关联次数 称 mij n m为G的关联矩阵 记为M G 性质 30 有向图的关联矩阵 无环有向图 P288 定义14 25有向图D 令则称 mij n m为D的关联矩阵 记为M D
14、 4 平行边对应的列相同 性质 有向图的关联矩阵 31 有向图的邻接矩阵 无限制 定义14 26设有向图D V v1 v2 vn E e1 e2 em 令为顶点vi邻接到顶点vj边的条数 称为D的邻接矩阵 记作A D 或简记为A 性质 32 推论设Bl A A2 Al l 1 则Bl中元素 为D中长度为l的通路总数 定理14 11设A为有向图D的邻接矩阵 V v1 v2 vn 为顶点集 则A的l次幂Al l 1 中元素 为D中vi到vj长度为l的通路数 其中 为vi到自身长度为l的回路数 而 为D中长度小于或等于l的回路数 为D中长度小于或等于l的通路数 邻接矩阵的应用 为D中长度为l的回路总
15、数 33 例5有向图D如图所示 求A A2 A3 A4 并回答诸问题 1 D中长度为1 2 3 4的通路各有多少条 其中回路分别为多少条 2 D中长度小于或等于4的通路为多少条 其中有多少条回路 实例 34 1 D中长度为1的通路为8条 其中有1条是回路 D中长度为2的通路为11条 其中有3条是回路 D中长度为3和4的通路分别为14和17条 回路分别为1与3条 2 D中长度小于等于4的通路为50条 其中有8条是回路 实例求解 35 定义14 27设D 为有向图 V v1 v2 vn 令 有向图的可达矩阵 无限制 称 pij n n为D的可达矩阵 记作P D 简记为P 由于 vi V vi vi
16、 所以P D 主对角线上的元素全为1 由定义不难看出 D强连通当且仅当P D 为全1矩阵 下图所示有向图D的可达矩阵为 36 第十四章习题课 主要内容无向图 有向图 关联与相邻 简单图 完全图 正则图 子图 补图 握手定理与推论 图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示 37 基本要求 深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构 简单图 完全图 正则图 子图 补图 二部图的概念以及它们的性质及相互之间的关系记住通路与回路的定义 分类及表示法深刻理解与无向图连通性 连通度有关的诸多概念会判别有向图连通性的类型熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法 会求可达矩阵 38 1 9阶无向图G中 每个顶点的度数不是5就是6 证明G中至少有5个6度顶点或至少有6个5度顶点 练习1 证关键是利用握手定理的推论 方法一 穷举法设G中有x个5度顶点 则必有 9 x 个6度顶点 由握手定理推论可知 x 9 x 只有5种可能 0 9 2 7 4 5 6 3 8 1 它们都满足要求 方法二 反证法否则 由握手定理推论可知 G至多有4个5度
