图论和网络分析算法及Matlab实现(GraphandNetworkAnalysis).ppt

涉及网络优化的数学建模问题 2、最小支撑树问题 3、 指派问题Assignment problem 4、中国邮递员问题Chinese postman problem 5 、旅行商问题Traveling salesman problem 6、运输问题Transportation problem 问题的两个共同特点 |V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶 |E|=m表示图G中边的个数为m 任一顶点相关联的边的数目称为该顶点的度 完全图：任意两点有边相连，用 表示 完全图的边，和每点的度是多少？ 3 . 链与圈 5. 树 6.图的支撑树 二、网络分析 一. 最小支撑树问题 避圈法是一种选边的过程，其步骤如下： 用避圈法解例2 二. 最短路问题 2. 方法：Dijkstra算法（Dijkstra，1959） Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271. 原理： Bellman最优化原理 若P是网络G中从Vs到Vt的一条最短路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最短路。 证明（反证）： 若P1不是从Vs到Vl的最短路，则存在另一条 Vs到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2)+W(P3)W(P1)+ W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更短的一条路，这与P使G中从Vs到Vt的一条最短路矛盾。 算法思想： 设G中从Vs到Vt的最小路 P：Vs…Vj…Vk…Vt，则P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解步骤： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 ⑵ 在计算过程中，需要把V中“经判断为最短路P途径之点i”和“尚未判断是否为最短路P途径之点j”区分开来，可设置集合I和J,前者归入I，后者归入J，并令算法初始时，I中仅包含Vs，其他点全在J中，然后随着求解过程的进行，I中的点逐渐增加（相应J中的点逐渐减少），直到终点Vt归入I（相应J=φ），此时迭代结束。I称为已标号集合,J称为未标号集合。 ⑶ 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 ⑷ 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，其中|V|=n 用标号法解例3 迭代过程 最短路问题应用 厂址选择 厂址布局 设备更新 网络线路安装 工程设计 企业管理 方法：以年号作顶点绘图，连线表示连续使用期 间，以费用作路长。 解：设 Vi —i年初购进一台新设备 aij —i年初购进之新设备使用到第j年初 ωij—i年初购进之新设备使用到第j年初之总费用 费用矩阵 方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。 可知最短费用流（相当于最短路） P： V1 V3 V6 或者是V1 V4 V6 | P| = 53万元结论：公司五年期设备更新方案有两个：A与B，总费用均为53万元。 A 方案：第1年初购置设备使用到第3年初,第3年初再购置新设备使用到第 5年末（第6年初） B 方案：第1年初购置设备使用到第4年初，第4年初再购置新设备使用到第5年末（第6年初）  三. 最大流问题 可采用线性规划的单纯型法求解 3. 基本概念与定理 （2）可增值链（增广链） （3） 截集与截量 （4） 流量与截量的关系 4. 解法 例5 用标号法求下面网络的最大流。 延伸问题 最小费用流 中国邮递员问题、欧拉回路（边） 旅行商问题、汉密尔顿圈（点） 可平面化问题 指派问题 统筹网络计划 匹配问题 数学建模竞赛涉及题目 1994全国大学生数学建模竞赛 题目要求 表 1 表 2 模型计算方法 参考答案 1998年全国大学生数学建模竞赛 乡村分布图 点的行遍性问题 线性规划模型 2005年全国大学生数学建模竞赛DVD在线租赁 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便