图论与网络模型.doc

《图论与网络模型.doc》由会员分享，可在线阅读，更多相关《图论与网络模型.doc（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

3、d-Fulkerson算法，计算复杂性与容量有关，而与点数和边数无关； （2）Edmonds-Karp算法，计算复杂性为其中，； （3）单纯形法，非多项式算法，可利用Lindo/Lingo(或Xpress-MP,GAMS,AMPL,Ziena,Matlab)软件编程计算。4、应用 （1）最小割集； （2）最小流； （3）多端最大流； （4）增益流； （5）点具有容量的最小流； （6）最小费用流，只要在最大流模型中将目标改为 即可得最小费用流的线性规划模型。还可进一步考虑目标函数非线性的情况。 如下图所示，图中弧旁的数字分别为容量和单位流量费用。5、进一步讨论 约束条件中的容量值若为整数，求解上

4、述线性规划，必得整数最大流，即各条边上的流量值为整数。 四、图的独立集、覆盖集与支配集问题1、匹配（边独立集） （1）问题 求图中边数最多的不相邻边之集，即最大匹配。最大匹配的边数称为匹配数。 （2）算法 1）求非偶图最大匹配的“开花”算法，计算复杂性为。或引入0-1变量，当与配对时，否则，可建立如下线性0-1规划模型，利用软件编程计算。 其中所有与相邻的点，称为点的邻集。 2）求偶图最大匹配的匈牙利算法，计算复杂性为。或引入0-1变量，当与配对时，；否则，可建立如下线性0-1规划模型，利用软件编程计算。 ， （3）应用 1）问题 求加权偶图中权和最大或最小的最大匹配，即最优匹配。2）模型 若

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

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

7、求点数最少的点之集，使图中每个点或属于该点集，或与该点集中至少一点相邻，即最小支配集。最小支配集的点数称为支配数。 （2）算法 求所有极小支配集的逻辑算法：）。或引入0-1变量，当属于支配集时，；否则，可建立如下线性0-1规划模型，利用软件编程计算。 五、中国邮路问题（CPP）1、问题 求Euler图中的Euler回路。2、算法 Fleury算法，计算复杂性为。3、应用 （1）问题 在加权连通图中求经过每条边至少一次的权和最小的回路，即中国邮路。 （2）模型 对于无向加权连通图，设为从到经过的次数，则可建立如下线性整数规划模型，利用软件编程计算。 对于有向加权连通图，若所有顶点的入度和出度均大

8、于零，则其模型只要在上述模型中将第二个约束条件改为，即可得。否则，不存在有向中国邮路。 (3)算法 1）奇偶点图上作业法；2）最小权匹配算法，计算复杂性为；3）利用软件编程计算。4、推广 多邮递员中国邮路问题（）六、旅行推销商问题（TSP）1、问题 求Hamilton图中的Hamilton回路。2、算法 DFS法，计算复杂性为。3、应用 （1）问题 在加权连通图中求经过每个点至少一次的权和最小的回路，即推销商回路（TSP回路）。 （2）模型 先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否则，则可建立如下线性0-1规划模型，先求得该加权完全图权和最小Hamilton回路，再转化为原

9、加权连通图的TSP回路。 或1， （3）算法 1）分枝定界法，非多项式算法；2）最小生成树法；3）代换法；4）插入法；5）最近邻法；6）神经网络法；7）模拟退火法；8）蚂蚁算法，2）8）均为近似算法。 4、推广 多旅行推销商问题七、图的着色问题 1、点着色 （1）问题 求给图的点着色，且使邻点异色的最少颜色数。 （2）算法 1）图收缩法，非多项式算法；2）Welch-Powell算法，为近似算法；3）引入0-1变量，当着第种颜色时，；否则；，设颜色种数为，可建立如下线性混合整数规划模型，利用软件编程计算。 2、边着色 求给图的边着色，且使邻边异色的最少颜色数。边着色可转化为点着色。或引入0-1变量，当着第种颜色时，；否则；，设颜色种数为，可建立如下线性混合整数规划模型，利用软件编程计算。 3、面着色 求给平面图的面着色，且使邻面异色的最少颜色数。面着色也可转化为点着色。11