离散数学68章pptppt课件

图论简介 图论是一个古老的数学分支 它起源于游戏难题的研究 图论的内容十分丰富 应用得相当广泛 许多学科 诸如运筹学 信息论 控制论 网络理论 博弈论 化学 生物学 物理学 社会科学 语言学 计算机科学等 都以图作为工具来解决实际问题和理论问题 随着计算机科学的发展 图论在以上各学科中的作用越来越大 同时图论本身也得到了充分的发展 第八章图论 第一节图的基本概念 内容 有向图 无向图的基本概念 重点 1 有向图 无向图的定义 内容 有向图 无向图的基本概念 5 图的同构的定义 2 图的表示法 有向图 无向图的顶点都用小圆圈表示 图形表示如右 图形表示如右 3 相关概念 3 相关概念 2 3 相关概念 2 孤立点 无边关联的点 3 相关概念 多重图 含有平行边的图 简单图 不含平行边和环的图 如例1的 1 中 为孤立点 为悬挂点 为悬挂边 为环 为平行边 重数2 为多重图 4 完全图 例如 二 顶点的度数 握手定理 1 顶点的度数 简称度 二 顶点的度数 握手定理 1 顶点的度数 简称度 最大度 最小度 如例1的 2 中 2 握手定理 定理1 定理2 三 子图 补图 1 子图定义 三 子图 补图 导出子图 例3 上图中 1 6 都是 1 的子图 其中 2 6 为真子图 1 5 为生成子图 2 补图定义 如例3中 四 图的同构 定义 例4 解 只有如下3个图 解 只有如下4个图 第二节路径和回路 1 内容 图的通路 回路 连通性 2 图的连通性的概念 3 短程线 距离的概念 一 路径 回路 1 路径 回路 一 路径 回路 2 简单路径 简单回路 简单路径 迹 同一条边不出现两次基本路径 链 同一顶点不出现两次 简单回路 闭迹 没有相同边的回路基本回路 通过各顶点不超过一次的回路 一 路径 回路 例1 1 长度3 长度6 长度6 例1 1 基本路径 简单路径 复杂通路 例1 2 长度3 长度4 长度7 例1 2 基本回路 圈 基本回路 圈 复杂回路 4 性质 定理1 4 性质 定理2 二 图的连通度 1 连通 可达 2 短程线 距离 距离 短程线的长度 3 无向图的连通 3 无向图的连通 4 有向图的连通 例2 强连通 单向连通 例2 单向连通 弱连通 非连通图 8 2路径与回路 2 内容 欧拉 哈密尔顿路径 赋权图中的最短路径 重点 1 欧拉图的定义 无向图是否具有欧拉回路的判定 了解 无向图是否具有哈密尔顿回路的判定 一 欧拉回路问题的提出 1736年 瑞士数学家欧拉 哥尼斯堡七桥问题 二 定义 欧拉通路 欧拉迹 欧拉回路 欧拉闭迹 欧拉图 存在欧拉回路的图 注意 1 欧拉通路与欧拉回路不同 2 欧拉图指具有欧拉回路 并非通路 的图 3 欧拉通路 回路 必是简单通路 回路 4 连通是具有欧拉通路 回路 的必要条件 三 无向图是否具有欧拉通路或回路的判定 例1 以下图形能否一笔画成 例1 以下图形能否一笔画成 例2 两只蚂蚁比赛问题 四 有向图是否具有欧拉通路或回路的判定 例3 判断以下有向图是否欧拉图 二 哈密尔顿图 一 问题的提出 1859年 英国数学家哈密尔顿 周游世界游戏 二 哈密尔顿图 哈密尔顿通路 哈密尔顿回路 哈密尔顿图 存在哈密尔顿回路的图 注意 1 哈密尔顿通路与哈密尔顿回路不同 3 哈密尔顿通路 回路 必是初级通路 回路 4 连通是具有哈密尔顿通路 回路 的必要条件 注意 三 判定 采用尝试的办法 例1 判断下图是否具有哈密尔顿回路 通路 例1 判断下图是否具有哈密尔顿回路 通路 例1 判断下图是否具有哈密尔顿回路 通路 哈密尔顿回路存在的两件个充分条件 定理8 2 13设是具有个顶点的简单无向图 若在G中每一对顶点的次数之和大于n 则在G中存在一条哈密尔顿回路 推论8 2 13在简单无向图中 若每一顶点的次数则在G中存在一条哈密尔顿回路 70 三 最短路径 定义设G V E 是无向简单图 如果对E中每条边e都有一个实数w e 附着其上 则称G为权图 称w e 为边e的权 设P是G的一条路 P上所带权的总和称为路P的权 有时记为G V E W 71 设权图G中每条边的权均大于等于0 u v为G中任意的两个顶点 从u到v的所有路中权最小的路称为u到v的最短路径 求给定的两顶点之间的最短路径问题称为最短路径问题 最短路径算法 由E W Dijkstra 迪克斯特拉 于1959年给出的标号法 Dijkstra算法 三 最短路径 72 问题 图G V E W 1 V 求1到V其它点的最短距离 设S为最短距离已经确定的集合 T为最短距离未确定的集合 算法描述如下 1 初始话 S 1 T V S 2 求1经过S中的点 到T中点的最短距离 记为D i D i w 1 i 3 选T中D i 值最小的点i 记为k 把k加入S T V S 4 对T中的点i更新D i 若D k W i k D i D i D k W i k 5 T为空集 算法结束 三 最短路径 73 例用Dijkstra求下图中a到d的最短路径 a b c d e f a 6 2 2 f 3 7 9 3 b 5 9 5 c e 9 d 6 7 7 6 74 四 最短路径 例求下图中a到f的最短路径 A b d c e f6 8 3图的矩阵表示 内容 邻接矩阵 关联矩阵 可达矩阵 重点 1 有向图的邻接矩阵 2 有向图 无向图的关联矩阵 了解 有向图的可达矩阵 一 有向图的邻接矩阵 解 2 性质 1 2 3 3 的元素的意义 设 则 表示 从结点和两者引出的边 如果能共同终止于一些结点 则就是这些终止结点的数目 特别地 时 对角线上的元素就是结点的引出次数 4 的元素的意义 设 则 表示 从一些结点引出的边 如果能同时终止于和 则就是这样的结点数目 特别地 时 对角线上的元素就是结点的引出次数 1 令 矩阵乘法 其中 其中 2 设 二 无向图的关联矩阵 解 2 性质 1 2 每列之和为2表示每条边只有两个顶点 每行之和表示对应点的度数 2 性质 三 有向简单图 无环 的关联矩阵 其中 解 2 性质 1 2 3 四 有向图的可达性矩阵 了解 四 有向图的可达性矩阵 了解 可达性矩阵 8 7树 一 无向树及生成树 内容 无向树 生成树 重点 1 无向树的定义 包括等价定义 2 无向树的性质 本章中所谈回路均指简单回路或基本回路 一 无向树 1 无向树 连通且不含回路的无向图 平凡树 平凡图 仅有一个结点的简单图 森林 例1 例1 2 树的六个等价定义 2 树的六个等价定义 3 性质 2 定理 非平凡树至少2片树叶 由握手定理 例2 画出所有的6个顶点的非同构的树 1 例2 画出所有的6个顶点的非同构的树 2 例2 画出所有的6个顶点的非同构的树 3 例2 画出所有的6个顶点的非同构的树 4 例2 画出所有的6个顶点的非同构的树 5 二 生成树 树枝 弦 余树 例4 上图中 2 是 1 的生成树 3 是 2 的余树 注意 1 生成树不唯一 2 余树不一定是树 2 连通图的性质 3 最小生成树 最小生成树 各边权和最小的生成树 求最小生成树的方法 解 解 解 解 注意 第八章小结与例题 一 无向图与有向图 1 基本概念 一 无向图与有向图 2 运用 1 灵活运用握手定理及其推论 2 判断两个图是否同构 3 画出满足某些条件的子图 补图等 二 通路 回路 图的连通性 1 基本概念 二 通路 回路 图的连通性 2 运用 1 判断有向图或无向图中通路 回路 的类型 2 求短程线和距离 3 判断有向图连通的类型 三 欧拉图 1 基本概念 欧拉通路 欧拉回路 欧拉图 2 运用 判定无向图是否具有欧拉通路或回路 四 哈密尔顿图 1 基本概念 哈密尔顿通路 哈密尔顿回路 哈密尔顿图 2 运用 判断无向图是否具有哈密尔顿通路或回路 五 图的矩阵表示 1 基本概念 2 运用 1 关联矩阵的行和 顶点度数间的关系 六 无向树及生成树 1 基本概念 2 运用 4 求生成树 最小生成树 七 应用 1 赋权图的最短路径 迪克斯特拉算法 2 最小生成树 克鲁斯克尔算法 1 2 3 简单图 多重图 不是 4 5 6 简单图 多重图 不是 1 可以 2 不可以 3 可以 4 不可以 5 不可以 解 有7条 强连通 单向连通 弱连通 单向连通 强连通 强连通 例5 画一个欧拉图 使它具有 1 偶数个顶点 偶数条边 2 奇数个顶点 奇数条边 解 解 例5 画一个欧拉图 使它具有 3 偶数个顶点 奇数条边 4 奇数个顶点 偶数条边 解 解 解 图 的哈 回路 1 解 不是欧拉图 不是哈密尔顿图 解 是欧拉图 是哈密尔