数模培训—图论模型.pptVIP

南京信息工程大学数理学院 费文龙 图 论 模 型 （离散数学） 主讲：张红雷 hongleixz@126.com 图论模型 一、引例（渡河问题） 二、图的基本概念 三、最短路径问题 四、其它问题 二、图的基本概念 我们今后只讨论有限简单图： 图的矩阵表示 三、最短路径算法 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)为图的权矩阵） 例 求下图中u0点到其他点的最短路. Floyd算法（求任意两点的最短路径） 弗洛伊德算法 其它应用—选址问题 1、最小生成树 2、遍历性问题 （1）欧拉图 G=(V,E)为一连通无向图 经过G中每条边至少一次的回路称为巡回； 经过G中每条边正好一次的巡回称为欧拉巡回； 存在欧拉巡回的图称为欧拉图。 （2）哈密尔顿图 G=(V,E)为一连通无向图 经过G中每点一次且正好一次的路径称为哈密尔顿路径； 经过G中每点一次且正好一次的回路称为哈密尔顿回路； 存在哈密尔顿回路的图称为哈密尔顿图。 旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路） 对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。 TSP问题的解法属于NP完全问题，一般只研究其近似解法 最邻近算法 (1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2) 找出与必威体育精装版加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3) 重复(2)直到所有的结点都加入到路径中.(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路. 其他数值算法： 人工神经元方法， 遗传算法等等 工作安排问题之一 例 求下图所示二部图G的最大匹配. 工作安排问题之二 4、网络流问题 最小费用流问题 5、关键路径问题（拓扑排序） 系统监控问题之二 7、着色模型 物资储存问题 时间表问题 着色方法 从v1到v3的最短路长度 。 从v5到v2的最短路长度 路径：∵ ∴v1到v3的最短路路经为:P13=P(v1, v2, v5, v4, v3) 路径：∵ ∴v5到v2的最短路路经为:P52=P(v5, v4, v1, v2) v1 v2 v5 v4 v3 v5 v3 v4 v2 v1 5 3 4 3 6 - 4 1 2 -2 U(5)= 0 0 0 0 0 4 5 3 8 3 1 6 -2 3 7 2 -1 -1 3 -4 1 0 4 1 -1 S(5)= 1 2 3 4 5 2 3 3 3 3 3 3 4 5 2 3 5 4 2 1 2 1 2 1 1 练习1：求各点间最短路径及长度 答案： 练习 2某公司在六个城市c1, …,c6中有分公司，