图论与网络模型.doc

《图论与网络模型.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论与网络模型一、最短路径问题1、问题在加权图中求两点之间的路径，使该路径上的边权之和最小。例如，求下图中从到其他顶点的最短路径。2、模型，其中为边的权。3、算法（1）求给定两点之间最短路径的Dijkstra算法，计算复杂性为，其中。例如，对于上图，当与不相邻，即边时，取。1)标号,,,,,,,。取固定标号顶点集合为，临时标号顶点集合为由=可知，到的最短路径为，权为10。令，。2）令11由=可知，到的最短路径为权为14。令，重复上述步骤，可分别得到的最短路径。(2)求任意两点之间最短路径的Floyd算法，计算复杂性为。记权矩阵为，其中。令

2、，即。利用迭代计算，其中，，即为到的最短路径的权。若，则不存在到的路径。特别地，若存在，使，则即为到的最短路径的权。4、应用（1）最可靠路径；（2）工序的关键路径（PT图，PERT图）；（3）选址问题（应急服务设施的中心点，非应急服务设施的重心点）；（4）点带权的最短路径。二、最小生成树问题1、问题在加权连通图中求生成树，使该树上的边权之和最小。2、模型113、算法（1）Kruskal算法（避圈法）；（2）Prim算法；（3）破圈法。计算复杂性均为。三、网络最大流问题1、问题在单源单汇具有容量上限的网络中求从源到汇的流量最大的可行流。2、

3、模型设上的流量，表示网络的流量，则可建立如下线性规划模型3、算法（1）Ford-Fulkerson算法，计算复杂性与容量有关，而与点数和边数无关；（2）Edmonds-Karp算法，计算复杂性为其中，；（3）单纯形法，非多项式算法，可利用Lindo/Lingo(或Xpress-MP,GAMS,AMPL,Ziena,Matlab)软件编程计算。4、应用11（1）最小割集；（2）最小流；（3）多端最大流；（4）增益流；（5）点具有容量的最小流；（6）最小费用流，只要在最大流模型中将目标改为即可得最小费用流的线性规划模型。还可进一步考虑目标函数

4、非线性的情况。如下图所示，图中弧旁的数字分别为容量和单位流量费用。5、进一步讨论约束条件中的容量值若为整数，求解上述线性规划，必得整数最大流，即各条边上的流量值为整数。四、图的独立集、覆盖集与支配集问题1、匹配（边独立集）（1）问题求图中边数最多的不相邻边之集，即最大匹配。最大匹配的边数称为匹配数。（2）算法1）求非偶图最大匹配的“开花”算法，计算复杂性为。或引入0-1变量，当与配对时，否则，可建立如下11线性0-1规划模型，利用软件编程计算。其中{所有与相邻的点}，称为点的邻集。2）求偶图最大匹配的匈牙利算法，计算复杂性为。或引入0-1

5、变量，当与配对时，；否则，，可建立如下线性0-1规划模型，利用软件编程计算。，，（3）应用111）问题求加权偶图中权和最大或最小的最大匹配，即最优匹配。2）模型若求权和最大的最优匹配，则只要在上述模型中将目标改为即可得其线性0-1规划模型，其中，当时，取,否则，取；若求权和最小的最优匹配，则只要在上述模型中将目标改为即可得其线性0-1规划模型，其中，当时，取，否则，取=，。3）算法a)kuhn-Munkras算法，计算复杂性为；b）利用软件编程计算。（4）推广一人承担多项工作或一项工作由多人承担的指派问题，只要将上述模型中的约束条件适当修

6、改即可。2、边覆盖集（1）问题求图中边数最少的覆盖所有点的边之集，即最小边覆盖集。最小边覆盖集的边数称为边覆盖数。（2）算法通过最大匹配求得。或引入0-1变量，当属于边覆盖集时，否则，可建立如下线性0-1规划模型，利用软件编程计算。113、（点）覆盖集（1）问题求图中点数最少的覆盖所有边的点之集，即最小（点）覆盖集。最小（点）覆盖集的点数称为（点）覆盖数。（2）算法求所有极小（点）覆盖集的逻辑算法：）。或引入0-1变量，当属于（点）覆盖集时，否则,，可建立如下线性0-1规划模型，利用软件编程计算。4、（点）独立集（1）问题求图中点数最多的

7、不相邻点之集，即最大（点）独立集。最大（点）独立集的点数称为（点）独立数。（2）算法求出最小（点）覆盖集，其补集即为最大（点）独立集。或引入0-1变量，当属于（点）独立集时，；否则,，建立如下模型，利用软件编程计算。5、支配集（1）问题求点数最少的点之集，使图中每个点或属于该点集，或与该点集中至少一点相邻，即最小支配集。11最小支配集的点数称为支配数。（2）算法求所有极小支配集的逻辑算法：）。或引入0-1变量，当属于支配集时，；否则，，可建立如下线性0-1规划模型，利用软件编程计算。五、中国邮路问题（CPP）1、问题求Euler图中的Eu

8、ler回路。2、算法Fleury算法，计算复杂性为。3、应用（1）问题在加权连通图中求经过每条边至少一次的权和最小的回路，即中国邮路。（2）模型对于无向加权连通图，设为从到经过的次数，则可建立