图论_最短路问题.pptVIP

* 数学实验 空军工程大学理学院应用数学教研室 最短路问题 实验目的 实验内容 2、会用Matlab软件求最短路 1、了解最短路的算法及其应用 1、图 论 的 基 本 概 念 2、最 短 路 问 题 及 其 算 法 3、最 短 路 的 应 用 4、建模案例：最优截断切割问题 5、实验作业 图 论 的 基 本 概 念 一、 图 的 概 念 1、图的定义 2、顶点的次数 3、子图 二、 图 的 矩 阵 表 示 1、 关联矩阵 2、 邻接矩阵 返回 定义 有序三元组G=(V,E, )称为一个图. 图的定义 定义 定义 返回 顶点的次数 例 在一次聚会中，认识奇数个人的人数一定是偶数。 返回 子图 返回 关联矩阵 注：假设图为简单图 返回 邻接矩阵 注：假设图为简单图 返回 最 短 路 问 题 及 其 算 法 一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路 返回 基 本 概 念 返回 固 定 起 点 的 最 短 路 最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树． 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路． 算法步骤： TO MATLAB (road1) u1 u2 u3 u4 u5 u6 u7 u8 返回 每 对 顶 点 之 间 的 最 短 路 1、求距离矩阵的方法 2、求路径矩阵的方法 3、查找最短路路径的方法 （一）算法的基本思想 （三）算法步骤 返回 算法的基本思想 返回 算法原理—— 求距离矩阵的方法 返回 算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径． 返回 i j 算法原理—— 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为： 返回 V=是有穷非空集，称为顶点集， 其中的元素叫图G的顶点. E称为边集，其中的元素叫图G的边. 是从边集E到顶点集V中的有序或无序的元素 偶对的集合的映射，称为关联函数. 设G=(V,E,)，其中 V={v1 ,v2 , v3 , v4}， E={e1, e2 , e3, e4, e5}, . G的图解如图. 在图G中，与V中的有序偶(vi， vj)对应的边e，称为图的有向边（或弧），而与V中顶点的无序偶vivj相对应的边e，称为图的无向边.每一条边都是无向边的图，叫无向图；每一条边都是有向边的图，称为有向图；既有无向边又有有向边的图称为混合图. 若将图G的每一条边e都对应一个实数w(e)，称w(e)为边的权，并称图G为赋权图. 规定用记号和分别表示图的顶点数和边数. 常用术语： 端点相同的边称为环． 若一对顶点之间有两条以上的边联结，则这些边称为重边． 有边联结的两个顶点称为相邻的顶点，有一个公共端点的边 称为相邻的边． 边和它的端点称为互相关联的． 既没有环也没有平行边的图，称为简单图． 任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n 为顶点的数目． ( 7)若V=XY，XY=，X中任两顶点不相邻，Y中任两顶 点不相邻，称G为二元图；若X中每一顶点皆与Y中一切顶点 相邻，称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶 点数目． 定义　（１）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)． 　　　　（２）在有向图中，从顶点v引出的边的数目称为v的出度， 记为d+(v)，从顶点v引入的边的数目称为的入度，记为d-(v)， d(v)=d+(v)+d-(v)称为v的次数． 定理１　 推论１　任何图中奇次顶点的总数必为偶数． 定义　设图G=(V,E,),G1=(V1,E1,) 若V1V，E1E,且当eE1时，(e)= (e),则称G1是G的子图． 特别的，若V1=V，则G1称为G的生成子图． 设V1V，且V1，以V1为顶点集、两个端点都在V1中的 图G的边为边集的图G的子图，称为G的由V1导出的子图，记为G[V1]. (3)设E1E,且E1,以E1为边集,E1的端点集为顶点集的图G的子图, 称为G的由