第七讲图论PPT讲稿.ppt
第七讲 图论第1页，共38页，编辑于2022年，星期二第七讲第七讲 图论图论l图论的基本概念图论的基本概念l最短路问题及其算法最短路问题及其算法l最短路的应用最短路的应用第2页，共38页，编辑于2022年，星期二图论的基本概念图论的基本概念一、一、图的概念图的概念1 1、图的定义、图的定义2 2、顶点的次数、顶点的次数 3 3、子图、子图二、二、图的矩阵表示图的矩阵表示1 1、关联矩阵关联矩阵2 2、邻接矩阵邻接矩阵第3页，共38页，编辑于2022年，星期二定义定义有序三元组有序三元组G=(V,E,)称为一个图称为一个图.图的定义图的定义第4页，共38页，编辑于2022年，星期二定义定义定义定义第5页，共38页，编辑于2022年，星期二第6页，共38页，编辑于2022年，星期二第7页，共38页，编辑于2022年，星期二顶点的次数顶点的次数第8页，共38页，编辑于2022年，星期二例例 在一次聚会中，认识奇数个人的人数一定是偶数。第9页，共38页，编辑于2022年，星期二子图子图第10页，共38页，编辑于2022年，星期二关联矩阵关联矩阵注：假设图为简单图第11页，共38页，编辑于2022年，星期二邻接矩阵邻接矩阵注：假设图为简单图第12页，共38页，编辑于2022年，星期二第13页，共38页，编辑于2022年，星期二最短路问题及其算法最短路问题及其算法一、一、基本概念基本概念二、固定起点的最短路二、固定起点的最短路三、每对顶点之间的最短路三、每对顶点之间的最短路第14页，共38页，编辑于2022年，星期二基本概念基本概念第15页，共38页，编辑于2022年，星期二第16页，共38页，编辑于2022年，星期二固定起点的最短路固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 可采用树生长的过程来求指定顶点到其余顶点的最短路第17页，共38页，编辑于2022年，星期二第18页，共38页，编辑于2022年，星期二算法步骤：算法步骤：第19页，共38页，编辑于2022年，星期二第20页，共38页，编辑于2022年，星期二第21页，共38页，编辑于2022年，星期二u1u2u3u4u5u6u7u8第22页，共38页，编辑于2022年，星期二每对顶点之间的最短路每对顶点之间的最短路1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤(二二)算法原理算法原理 第23页，共38页，编辑于2022年，星期二算法的基本思想算法的基本思想第24页，共38页，编辑于2022年，星期二算法原理算法原理 求距离矩阵的方法求距离矩阵的方法第25页，共38页，编辑于2022年，星期二算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径第26页，共38页，编辑于2022年，星期二ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：第27页，共38页，编辑于2022年，星期二算法步骤算法步骤第28页，共38页，编辑于2022年，星期二第29页，共38页，编辑于2022年，星期二一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选址问题选址问题1、中心问题中心问题2、重心问题重心问题第30页，共38页，编辑于2022年，星期二可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题第31页，共38页，编辑于2022年，星期二第32页，共38页，编辑于2022年，星期二第33页，共38页，编辑于2022年，星期二第34页，共38页，编辑于2022年，星期二 选址问题选址问题-中心问题中心问题第35页，共38页，编辑于2022年，星期二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处。第36页，共38页，编辑于2022年，星期二 选址问题选址问题-重心问题重心问题第37页，共38页，编辑于2022年，星期二重要知识重要知识l最大流，最小代价流最大流，最小代价流l最大割最大割l哈密顿图哈密顿图l匹配问题匹配问题第38页，共38页，编辑于2022年，星期二
