数模培训_图论模型new.ppt

南京信息工程大学数理学院 费文龙 图 论 模 型 主讲：费文龙 F feiwl@ 图论模型 图论基本概念 最短路径算法 最小生成树算法 遍历性问题 二分图与匹配 1、图论的基本概念 图的定义 我们今后只讨论有限简单图： 图的矩阵表示 2、最短路径算法 Dijkstra算法 指标（a为起点）??? 设T为V的子集，P=V-T且a∈T，对所有t∈T，设 l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T中其他的结点，则称l(t)为t关于集合P的指标，若不存在这样的路径，这记l(t)=∞ 注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。 定理1? 若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。 定理2? 设 T为V的子集，P=V-T，设??? (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成,??? (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即:l(x)=min(l(t)) (t T),??? (3)令P=P {x},T=T-{x},l(t)表示T中结点t关于P的指标,则? l(t)=min{l(t),l(x)+w(x,t)} Dijkstra算法（求a点到其他点的最短路径） 1、初始化，P={a}，T=V-{a}，对每个结点t计算指标 l(t)=w(a,t) 2、设x为T中关于P有最小指标的点,  即:l(x)=min(l(t)) (t∈T), 3、若T=Ф,则算法结束;???? 否则,令P=P U{x},T=T-{x}????????? 按照公式l(t)=min{l(t),l(x)+w(x,t)}, 计算T中每一个结点t关于P的指标. 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵） 改进Dijkstra算法（求a点到其他点的最短路径） 1、初始化，P={a}，T=V-{a}，对每个结点t计算指标 l(t)=w(a,t) ,pro(t)=a; 2、设x为T中关于P有最小指标的点,  即:l(x)=min(l(t)) (t∈T); 3、若T=Ф,则算法结束;???? 否则,令P‘=P U{x},T’=T-{x}????????? 按照公式l‘(t)=min{l(t),l(x)+w(x,t)}, 计算T’中每一个结点t‘关于P’的指标.  若 l(x)+w(x,t) l(t), pro(t)=x; 4、P代替P,T代替T,重复步骤2,3 （ 其中：w(x,y)为图的权矩阵） 例 求下图中A点到其他点的最短路. A B C D E F G H A 0 2 ∞ ∞ ∞ ∞ 6 ∞ B 2 0 7 ∞ ∞ 1 3 ∞ C ∞ 7 0 4 3 ∞ ∞ ∞ D ∞ ∞ 4 0 5 ∞ ∞ 2 E ∞ ∞ 3 5 0 2 ∞ 2 F ∞ 1 ∞ ∞ 2 0 1 ∞ G 6 3 ∞ ∞ ∞ 1 0 4 H ∞ ∞ ∞ 2 2 ∞ 4 0 Floyd算法（求任意两点的最短路径） 例 求下图中任意两点间的最短路. 0 1 2 3 4 5 6 7 0 0 2 8 1 ∞ ∞ ∞ ∞ 1 2 0 6 ∞ 1 ∞ ∞ ∞ 2 8 6 0 7 5 1 2 ∞ 3 1 ∞ 7 0 ∞ ∞ 9 ∞ 4 ∞ 1 5 ∞ 0 3 ∞ 8 5 ∞ ∞ 1 ∞ 3 0 4 6 6 ∞ ∞ 2 9 ∞ 4 0 3 7 ∞ ∞ ∞ ∞ 8 6 3 0 例 设备更新问题 3、最小生成树 例 选址问题 4、遍历性问题 一、欧拉图 G=(V,E)为一连通无向图 经过G中每条边至少一次的回路称为巡回； 经过G中每条边正好一次的巡回称为欧拉巡回； 存在欧拉巡回的图称为欧拉图。 二、中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？ 这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。 解法： 若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。 若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。 具体解法：Fle