《第七讲图论精选文档.ppt》由会员分享，可在线阅读，更多相关《第七讲图论精选文档.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七讲 图论本讲稿第一页，共三十八页第七讲第七讲 图论图论l图论的基本概念图论的基本概念l最短路问题及其算法最短路问题及其算法l最短路的应用最短路的应用本讲稿第二页，共三十八页图论的基本概念图论的基本概念一、一、图的概念图的概念1 1、图的定义、图的定义2 2、顶点的次数、顶点的次数 3 3、子图、子图二、二、图的矩阵表示图的矩阵表示1 1、关联矩阵关联矩阵2 2、邻接矩阵邻接矩阵本讲稿第三页，共三十八页定义定义有序三元组有序三元组G=(V,E,)称为一个图称为一个图.图的定义图的定义本讲稿第四页，共三十八页定义定义定义定义本讲稿第五页，共三十八页本讲稿第六页，共三十八页本讲稿第七页，共三十八
2、页顶点的次数顶点的次数本讲稿第八页，共三十八页例例 在一次聚会中，认识奇数个人的人数一定是偶数。本讲稿第九页，共三十八页子图子图本讲稿第十页，共三十八页关联矩阵关联矩阵注：假设图为简单图本讲稿第十一页，共三十八页邻接矩阵邻接矩阵注：假设图为简单图本讲稿第十二页，共三十八页本讲稿第十三页，共三十八页最短路问题及其算法最短路问题及其算法一、一、基本概念基本概念二、固定起点的最短路二、固定起点的最短路三、每对顶点之间的最短路三、每对顶点之间的最短路本讲稿第十四页，共三十八页基本概念基本概念本讲稿第十五页，共三十八页本讲稿第十六页，共三十八页固定起点的最短路固定起点的最短路最短路是一条路径，且最短路的
3、任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 可采用树生长的过程来求指定顶点到其余顶点的最短路本讲稿第十七页，共三十八页本讲稿第十八页，共三十八页算法步骤：算法步骤：本讲稿第十九页，共三十八页本讲稿第二十页，共三十八页本讲稿第二十一页，共三十八页u1u2u3u4u5u6u7u8本讲稿第二十二页，共三十八页每对顶点之间的最短路每对顶点之间的最短路1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤(二
4、二)算法原理算法原理 本讲稿第二十三页，共三十八页算法的基本思想算法的基本思想本讲稿第二十四页，共三十八页算法原理算法原理 求距离矩阵的方法求距离矩阵的方法本讲稿第二十五页，共三十八页算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径本讲稿第二十六页，共三十八页ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：本讲稿第二十七页，共三十八页算法步骤算法步骤本讲稿第二十八页，共三十
5、八页本讲稿第二十九页，共三十八页一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选址问题选址问题1、中心问题中心问题2、重心问题重心问题本讲稿第三十页，共三十八页可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题本讲稿第三十一页，共三十八页本讲稿第三十二页，共三十八页本讲稿第三十三页，共三十八页本讲稿第三十四页，共三十八页 选址问题选址问题-中心问题中心问题本讲稿第三十五页，共三十八页S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。本讲稿第三十六页，共三十八页 选址问题选址问题-重心问题重心问题本讲稿第三十七页，共三十八页重要知识重要知识l最大流，最小代价流最大流，最小代价流l最大割最大割l哈密顿图哈密顿图l匹配问题匹配问题本讲稿第三十八页，共三十八页