图论和网络分析算法及Matlab实现(Graph-and-Network-Analysis)课件课.pptVIP

图论与网络分析

(GraphTheoryandNetworkAnalysis);涉及网络优化的数学建模问题;2、最小支撑树问题;3、指派问题

Assignmentproblem;4、中国邮递员问题

Chinesepostmanproblem;5、旅行商问题

Travelingsalesmanproblem;6、运输问题

Transportationproblem;问题的两个共同特点;一、图论的基本概念;|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶

|E|=m表示图G中边的个数为m

任一顶点相关联的边的数目称为该顶点的度

完全图：任意两点有边相连，用表示

完全图的边，和每点的度是多少？

;2.关联与相邻;Date;3.链与圈;4.有向图与无向图;v1;Date;5.树;v1;6.图的支撑树;二、网络分析;一.最小支撑树问题;避圈法是一种选边的过程，其步骤如下：;对G中各边按权大小顺序排列，不妨设为W1≤W2≤…≤Wm;用避圈法解例2;最小支撑树问题的应用例子;二.最短路问题;2.方法：Dijkstra算法（Dijkstra，1959）

Dijkstra,E.W.(1959).Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik1,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

;由图G建立一步可达距离阵D=(dij)n×n;用标号法解例3;Date;迭代过程;最短路问题应用;最短路问题的应用例子;解：设

Vi—i年初购进一台新设备

aij—i年初购进之新设备使用到第j年初

ωij—i年初购进之新设备使用到第j年初之总费用

;Date;Date;费用矩阵;方法：以年号作顶点绘图，连线表示连续使用期间，以

费用作路长。;Date;可知最短费用流（相当于最短路）

P：V1V3V6或者是V1V4V6

|P|=53万元

结论：公司五年期设备更新方案有两个：A与B，总费用均为53万元。

A方案：第1年初购置设备使用到第3年初,第3年初再购置新设备使用到第5年末（第6年初）

B方案：第1年初购置设备使用到第4年初，第4年初再购置新设备使用到第5年末（第6年初）

;三.最大流问题;可采用线性规划的单纯型法求解;3.基本概念与定理;（2）可增值链（增广链）;（3）截集与截量;例4对于下图，若V1={vs，v1}，请指出相应的截集与截量。;（4）流量与截量的关系;4.解法;步骤：;Date;1．算法思想;寻找一可增路pl，l＝1;例5用标号法求下面网络的最大流。;最大流问题的应用例子;延伸问题;数学建模竞赛涉及题目;1994全国大学生数学建模竞赛;题目要