农大离散数学课件第七章.ppt

图的基本概念 第八章 计算机科学广泛应用于运筹学 信息论 控制论 网络理论 化学生物学 物理学 原因在于这些学科的许多实际问题和理论问题可以概括为图论 第八 九章介绍与计算机科学关系密切的图论内容及其在实际中的应用 8 1无向图及有向图 称 a b a A b B 为A与B的无序积 记作 A B 习惯上 无序对 a b 改记成 a b 有序组 a b 均用 无序积 设A B为二集合 一 基本图类及相关概念 1 无向图 无向图 无向图G是一个二元组 其中 1 V是一个非空集 顶点集V G 每个元素为顶点或结点 2 E是无序积V V的可重子集 元素可重复出现 E 边集E G E中元素称为无向边 v4 实际中 图是画出来的 画法 用小圆圈表示V中的每一个元素 如果 a b E 则在顶点a与b之间连线段 如 a d c b e1 e1 e2 e3 e4 e5 e6 e1 e2 e3 e4 e5 e6 v1 v2 v3 v5 有向图 有向图D是一个二元组 其中 1 V是非空集 顶点集V D 2 E是笛卡尔积V V的可重子集 其元素为有向边 实际中 画法同无向图 只是要根据E中元素的次序 由第一元素用方向线段指向第二元素 2 有向图 有限图 V E均为有穷集合 零图 E 平凡图 E 且 V 1 n m 图 V n且 E m 顶与边关联 如果ek vi vj E 称ek与vi关联 或ek与vj关联 3 相关概念 顶与顶相邻 如果ek vi vj E 称vi与vj相邻 环 ek 中 若vi vj 则ek称为环 边与边相邻 如果ek和ei至少有一个公共顶点关联 则称ek与ei相邻 若ek为有向边 则称vi邻接到vj vj邻接于vi 孤立点 无边关联的顶点 平行边 无向图中 关联一对结点的无向边多于一条 平行边的条数为重数 多重图 包含平行边的图 有向图中 关联一对顶点的无向边多于一条 且始 终点相同 简单图 既不包含平行边又不包含环的图 度 1 在无向图G 中 与顶点v v V 关联的边的数目 每个环计算两次 记作 d v 二 度 2 在有向图D 中 以顶点v v V 作为始点的边的数目 称为该顶点的出度 记作 d v 出度与入度之和 称为顶点v的度 度是图的性质的重要判断依据 d v d v d v 以顶点v作为终点的边的数目 称为该顶点的入度 记作 d v 最大度 G max d v v V 最小度 G min d v v V 度与边数的关系 在任何图中 顶点度数的总和等于边数之和的两倍 握手定理的推论 任何图中 度为奇数的顶点个数一定为偶数 握手定理 出度与入度的关系 在有向图中 各顶点的出度之和等于各顶点的入度之和 度数序列 设V v1 v2 vn 为图G的顶点集 称 d v1 d v2 d vn 为G的度数序列 度数序列之和必为偶数 例8 1 3 3 2 3 5 2 3 1 4 能成为图的度数序列吗 为什么 解 由于这两个序列中 奇数个数均为奇数 由握手定理知 它们不能成为图的度数序列 例8 2已知图G中有10条边 4个3度顶点 其余顶点的度数均小于等于2 问G中至少有多少个顶点 为什么 解 图中边数m 10 由握手定理知 G中各顶点度数之和为20 4个3度顶点占去12度 还剩8度 若其余全是2度顶点 则需要4个顶点来占用8度 所以G至少有8个顶点 正则图 各顶点的度都相同的图为正则图 各顶点的度均为k的图为k次正则图 完全图 1 设G 是n阶的无向简单图 如果G中任何一个顶点都与其余n 1个顶点相邻 则G为无向完全图 记作 Kn 三 正则图与完全图 2 设D 是n阶的有向简单图 如果D中任意顶点u v V u v 即有有向边 又有有向边 则称D为n阶有向完全图 如 四 子图与母图 1 G G 若V V E E 则G是G 的母图 G 是G的子图 记作 G G 2 若G G且V V 则G 是G的生成子图 3 设V1 V 且V1 以V1为顶点集 以2端点均在V1中的全体边为边集的G的子图 称为V1导出的导出子图 4 设E1 E 且E1 以E1为顶点集 以E1中边关联的顶点的全体为顶点集的G的子图 称为E1导出的导出子图 例8 3列举下图的一些子图 真子图 生成子图 导出子图 e3 e1 e2 e4 e5 v3 v4 v1 v2 解 自己对照定义做一做 1 子图 子图的定义 举例 2 真子图 举例 3 生成子图 定义 举例 4 导出子图 定义 举例 补图 给定一个图G 以V为顶点集 以所有能使G成为完全图的添加边组成边集的图 记作 G 五 补图 如 相对补图 设G G 如果另一个图G 满足 1 E E E 2 V 中仅包含E 中的边所关联的结点 则G 是子图G 相对于G的补图 图同构 对于G G 如果存在g V V 满足 1 任意边e vi vj E 当且仅当e g vi g vj E 2 e与e 的重数相同 则说G G 由于同构图顶点之间一一对应 边之间一一对应 关联关系对应相同 所以可以看成同一个图 六 同构图 例8 4画出4个顶点3条边的所有可能非同构的无向简单图 解 直观上容易看出 下面三个图是4个顶点3条边的所有非同构的无向简单图 例8 5画出3个顶点2条边的所有可能非同构的有向简单图 解 3个顶点2条边的无向简单图只有一个 由这个图可派生出下列4个非同构的有向简单图 课堂练习 画出4个顶点4条边的无向简单图 8 2通路 回路 图的连通性 通路与回路 给定图G 设G中顶点与边的交替序列 v0e1v1e2 elvl满足 vi 1vi是ei的端点 G为有向图时 要求vi 1 vi分别为ei的始点 终点 i 1 2 l 则 为顶点v0到vl的通路 中边的数目l称为 的长度 v0 vl时 称 为回路 一 通路与回路的概念 简单通路 v0e1v1e2 ekvk为通路且边e1e2 ek互不相同 又称之为迹 可简用v0v1 vk来表示 简单回路 v0 vk 又称为闭迹 初级通路或基本通路 v0e1v1e2 ekvk为通路且顶点v0v1 vk互不相同 初级通路一定是简单通路 但简单通路不一定是一条初级通路 基本回路 v0 vk 例8 6就下面两图列举长度为5的通路 简单通路 回路 简单回路 再列举长度为3的基本通路和回路 v1 e1 e4 v2 v3 v4 v5 e3 e5 e2 e7 e6 1 2 v5 v1 e2 e5 v2 v3 v4 e1 e7 e3 e8 e6 e4 解 试对照定义 自己做一做 如 v1 1 中v1e1v2e2v5e3v1e1v2e4v3为v1到v3的通路 v1e1v2e4v3e5v4e7v5e3v1为v1到v1的一条简单回路 v1e1v2e4v3e5v4e6v2e2v5为v1到v5的一条简单通路 e1 e4 v2 v3 v4 v5 e3 e5 e2 e7 e6 1 2 中v1e2v2e5v3e7v4v1到v4的长度为了的基本通路 v1e2v2e3v5e1v1是v1到v1的长度为了的基本回路 2 v5 v1 e2 e5 v2 v3 v4 e1 e7 e3 e8 e6 e4 二 通路与回路的性质 1 在一个n阶图中 如果从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于n 1的通路 如果L n 1 则此通路的顶点数L 1 n 从而必有顶点vs 它在序列中不止出现一次 即有序列vi vs vs vj 证明 设vi vk vj为vi到vj的长度为L的一条通路 则序列中必有L 1个顶点 在路中去掉vs到vs的这些边 至少去掉一条边后仍是vi到vj的一条通路 此通路比原来 如此重复下去 必可得到一条从vi到vj的不多于n 1条边的通路 通路的长度至少少1 2 在n阶图中 如果从vi到vj vi vj 存在通路 则必存在从vi到vj的长度小于等于n 1的基本通路 3 在n阶图中 如果存在从vi到自身的回路 则从vi到自身存在长度等于n的回路 4 在n阶图中 如果从vi到自身存在一条简单回路 则从vi到自身存在长度等于n的初级回路 两顶点连通 u v为无向图G的两个顶点 u到v存在一条通路 连通图 G中任何两个顶点是连通的 否则是分离图 三 图的连通性 连通性的性质 无向图中顶点之间的连通关系是顶点集V上的等价关系 1 自反性 由于规定任何顶点到自身总是连通的 证明 2 对称性 无向图中顶点之间的连通是相互的 3 传递性 由连通性的定义可知 连通分支 无向图G中每个划分块称为G的一个连通分支 p G 表示连通分支的个数 p G 1为连通图 点割集 无向图G 为连通图 如果V V 且在G中删除V 中所有顶点 包括与该顶点关联的边 后所得子图是不连通的或是平凡图 而删除V 中任何真子集中的顶点时 所得子图仍连通 则V 是G的点割集 如果点割集中只有一个顶点 该点为割点 四 连通图的连通度 点连通度 G为无向连通图 记k G min V V 是G的点割集 称k G 为G的点连通度 由定义知 点连通度即使G不连通的需删除顶点的最少数目 完全图Kn的连通度k G n 1 存在割点的连通图连通度为1 分离图的连通度为0 边割集 设无向图G 连通 边集E E 在G中删除E 中所有边后所得子图不连通 而删除E 中的任何子集中的边后 所得子图仍连通 则E 为G的边割集 如果边割集中只有一边时 该边为割边 或桥 边连通度 设G为无向连通图 记 G min E E 是G的边割集 G 为G的边连通度 连通度的性质 k G G G 五 有向图的连通性 1 如果有向图D 中所有有向边的方向去掉后所得图为无向连通图 则说D为弱连通图 2 u v V 如果存在u到v的一条通路 则说u可达v 3 弱连通图中 任何一对顶点之间 至少有一顶点可达另一个顶点 则是单向连通的 任何两个顶点之间互相可达 称强连通 有向连通图的性质 1 强连通一定单向连通 单向连通一定弱连通 反过来都不成立 2 有向图D强连通 当且仅当D中存在一条回路 它至少经过每个顶点一次 充分性 如果D中存在回路C 它经过D中的每个顶点至少一次 则D中的任意两个顶点都在回路中 所以 D中任意两个顶点都是可达的 因而D是强连通的 证明 因为vi可达vi 1 i 1 2 n 1 让这些通路首尾相连 2 有向图D强连通 当且仅当D中存在一条回路 它至少经过每个顶点一次 必要性 D是强连通的 则D中任何两个顶点都是可达的 则得一回路 显然每个顶点在回路中至少出现一次 证明 所以vi到vi 1存在通路 不妨设D中的顶点 为v1 v2 vn 且vn到v1也存在通路 8 3图的矩阵表示 邻接矩阵 设G 是一个简单图 它有n个顶点 V v1 v2 vn 令 aij 1 E 或 vi vj E 0 E 或 vi vj E 称A G aij 为G的邻接矩阵 一 邻接矩阵及其性质 邻接矩阵的特性 在无向图中 1 邻接阵是对称阵 2 同一行或者同一列的元素和为对应顶点的度数 3 矩阵中所有元素的和为边数的2倍 在有向图中 1 同一行的元素和为对应顶点的出度 2 同一列的元素和为对应顶点的入度 3 aij 2m 边的数目 邻接矩阵可推广到多重图或带权图 这时令aij为vi到vj的边的重数或边上的权值W vi vj 邻接阵多用于有向图 关联矩阵 1 设G 为 n m 无向图 V v1 v2 vn E e1 e2 em 令 mij 1 0 称M G mij nxm为G的关联矩阵 vi关联ej vi不关联ej 二 关联矩阵及其性质 2 设D 是有向图且无环 令 mij 1 0 则称M D mij nxm为D的关联矩阵 1 D中vi是ej的始点 vi与ej不关联 vi是ej的终点 无向图的关联矩阵的性质 握手定理 有向图的关联矩阵的性质 由mij的定义知 通路数与回路数的矩阵算法 1 设A是有向图D的邻接矩阵 V v1 v2 vn Al l 1 中元素aij l 为vi到vj长度为l的通路数 通路总数 回路数 三 应用 1 求通路数与回路数 2 设A是有向图D的邻接矩阵 B1 A B2 A A2 Br A A2 Ar 则Br中元素bij r 为D中vi到vj长度小于等于r的通路数 2 求可达矩阵 可达矩阵 设D 为一有向图 V v1 v2 vn 令 pij 1 0 i j pii 1i 1 2 n 称 pij nxn为D的可达矩阵 vi可达vj 否则 例 求下图的可达矩阵 判断它是否为强连通图 V1 V4 V2 V3 V5 解 1 写出邻接矩阵 2 计算A2 A3 A4 A5 3 计算B A A2 A3 A4 A5 并求出 可达矩阵的求法 由邻接矩阵A计算A2 A A2 A A2 A n 1 B bij n 1 n n pij 1bij n 1 0 0bij n 1 0 则i j pii 1 即得可达矩阵P D pij nxn 8 4最短路径问题 带权图 对于有向图或无向图的每条边附加一个实数w e 则得带权图 如果G1是带权图G的子图 称 w e 为边e上的权 当e 时 权记作wij 记作 G 一 带权图及其最短路径问题 G 为带权图 且G中各边带的权均大于等于0 从顶点u到顶点v的所有通路中求带权最小的通路问题 称为最短路径问题 最短路径问题 如果v1v2 vn 1vn是v1到vn的最短路径 则v1v2 vn 1也必然是v1从到vn 1的最短路径 求最短路径的标号法的基本思想 标号法 1 符号说明 i li r 为顶点v1到顶点vi最短路径的权 ii lj r 为v1到vj最短路径权的上界 如果vj获得lj r 称vj在第r步获得t标号lj r r 0 如果顶点vi获得了标号li r 称vi在第r步获得p标号li r iii Pr v v已获得p标号 称之为第r步通过集 r 0 iv Tr V Pr称之为第r步未通过集 r 0 二 求最短路径问题的标号法 2 算法 开始 r 0 v1获p标号 l1 0 0 P0 v1 T0 V v1 vj j 1 的t标号 lj 0 w1j w1j 0v1与vj相邻 v1与vj不相邻 修改通过集和未通过集 Pr Pr 1 vi Tr Tr 1 vi step1 求下一个p标号顶点 顶点vi处 表明vi获得p标号 查Tr 若Tr 则算法结束 否则转step2 将lj r 标在相应 step2 修改Tr中各顶点的t标号 lj r min lj r 1 li r wij li r 是刚刚获得p标号顶点的p标号 令r r 1 转step1 例8 7求下图中顶点v0与v5之间的最短路径 v0 v2 v1 v4 v3 v5 1 2 1 4 7 5 3 2 6 解 利用标号法算法解此题 开始 r 0 v0获p标号 l0 0 0 l1 0 w01 1 通过集P0 v0 未通过集T0 v1 v2 v3 v4 v5 l2 0 w02 4 l4 0 l5 0 l3 0 w03 未通过集的t标号 第一步 r 1 计算 l1 1 1 所以i 1 P1 v0 v1 T1 v2 v