图论在数学建模中应用

图论及其应用主讲：刘飞月大连大学数学建模工作室图论最基本的概念线(edge)：两个事物间具有的关系。

图(Graph)：由点及连接线所构成的图形，用G=(V,E)表示。点(vertex)：代表事物。图的基本概念一、图的定义及其表示定义1图G是一个三元组，其中V是一个非空的结集合，E是边的集合，从边集合E到结点无序偶或有序偶集合上的函数。常记为：例1

设

则是一个图 有关图的一些术语和概念点与边的关联

:点是边的一个端点点与点的相邻:两点被同一边相连边与边的相邻:两边至少有一个公共端点环边:两端点重合的边重边:连接两点的两条或两条以上的边称为这两点的重边简单图:既无环边也无重边的图完全图:任意两点间都有一条边的简单图度的概念度（次）：节点v相连的边的数目，表示为d（v）。设图G=<V,E>为无向图或有向图，则G中所有点的度数之和是边数之和的2倍。奇数度节点：节点的度的数目为奇数的点；偶数度节点：节点的度的数目为偶数的点。关于度的定理定理图G中所有节点的度数和是边数的2倍。推理任意图，奇数度节点的个数总和为偶数。最短路问题赋权图：

对图G的每条边e，赋以一个实

数称为边e的权。每条边都赋有权的图称为赋权图.

权在不同问题中会有不同的含义，例如交通网络中，权可能表示运费，里程或道路的造价等。

给定赋权图G及G中两点u，v，求u到v的具有最小权的路（称为u到v的最短路）

注：赋权图中路的权也称路的长，最短（u，v）路的长也称为u，v的距离，记为

最短路问题是一个优化问题属于网络优化和组合优化的范畴，对这种优化问题的解答一般是一个算法，Dijkstra是最基本的一个算法。最短路问题:dijkstra算法思想：设赋权图G中所有边具有非负权，dijkstra算法的目标是求出是求出G中某个指定顶点到其他所有点的最短路。它依据的基本原理是：若路是从到的最短路，则必是从的最短路。基于这一原理，算法由近及远逐次求出到其他各点的最短路。例Dijkstra算法步骤G中从

到其余各点的最短路第一步：令,。第二步：对每个令

取使得

记

令第三步：令

如果，则停止，输出各

点标号并反向追溯最短路；否则，转第二步。

算法中步骤(1)和(3)是清楚的,现在对2给以说明。

表示从

到

的不包含

中其它结点的最短通路的长度,但

不一定是从

到

的距离,因为从

到

可能有包含

中另外结点的更短通路。

首先我们证明“若

是

中具有最小

值的结点,则

是从

到

的最小距离”,用反证法。若另有一条含有

中另外结点的更短通路,不妨设这个通路中第一个属于

的结点是

,于是

,但这与题设矛盾。可见以上断言成立。在下图中求到其它各点的最短路

Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。

Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），但是形式上简单些。Floyd算法算法的基本步骤（1）输入权矩阵（2）计算

其中（3）中元素

就是vi到vj的最短路长优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单.

缺点：时间复杂度比较高，不适合计算大量数据。树及其性质：不含圈的图称为森林，不含圈的连通图称为树。生成树：设是的一个子图，如果是一棵树，且，则称是的一个生成树。每个连通图都有生成树。树的性质（下例命题等价）：是树；中无环边且任二顶点之间有且仅有一条路；中无圈且；连通且；连通且对任何不连通；无圈且对任何恰有一个圈；kruskal算法1.算法思想先从图G中找出权最小的一条边（具有最小耗费的边）作为最小生成树的边，然后逐次从剩余边中选边添入最小生成树中。选边原则：每次挑选不与已边构成圈的边中权最小的一条直至选出条边为止。算法步骤第一步：取使得，令。第二步：取使得（1）不含圈；（2）是满足（1）的权最小的边。第三步：当时，输出最小生成树，算法停止，否则令，转第二步。

第一步我们要做的事情就是将所有

的

边的长度排

序，用

排序的结果作为我们

选

择

边

的

依

据。这里再次体现

了贪心算

法

的思想。

资源排序，对局部最优的资源进行选择。

排序完成后，我们率先选择了边AD。这样我们的图就变成了。第二步，在剩下的边中寻找。我们找到了CE。这里边的权重也是5依次类推我们找到了6,7,7。完成之后，图变成了这个样子。

下一步就是关键了。下面选择那条边呢？BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图：到这里所有的边点都已经连通了，一个最小生成树构建完成。Kruskal算法的实现及其复杂度分析：Kruskal的计算主要在第二步.算法共需执行次第二步，在第次执行第二步时，须比较集合中所有边的以求得一条权最小的边，并检验该边是否与已有边构成圈，如果构成圈，还需要再找新的最小权边，这是比较浪费的。在实际应用Kruskal算法时，一般先将所有的边按权由小到大排序，每次执行算法第二步时，不必再比较边的权，而是直接选取此前尚未考虑过的权最小的边，检验它是否与已有边构成圈即可，这样可以省去许多次重复比较。接下来的问题如何检验所选边是否与已有边构成圈？Prim算法算法思想：先从图G中找出权最小的一条边作为最小生成树的边，在算法任一轮循环中，设已经选出的边导出的子图为G1,从G1的顶点向G1以外顶点的连边权集合E1，则选择E1中权值最小的边向G1中添加，如此反复循环直至选出边为止。算法步骤：第1步：任，令第2步：求到间权最小的边，设属于的端点为，令第3步：当时，输出最小生成树，算法停止；否则令，转第2步。算法的计算复杂度：Prim算法的主要计算量在第2步。在算法第轮循环执行第步时，中有个顶点，中有个顶点，故到间最多有条边，从这些边中选出一条权最小的边，需要次比较。算法需循环执行第2部次，因此总的计算量为由此，Prim算法的计算复杂度为标号Prim算法算法思想：给图中的顶点赋以标号，该标号与边的权有关，在执行Prim算法的过程中，通过修改顶点标号和比较顶点的标号大小，来选择满足Prim要求的最小权边。顶点的标号记为，用表示边的权。若两点间没有边，则算法步骤：第一步：任取，令第二步：对，若，则令第三步：选取使得。设，使得，令，。第四步：当时，输出最小生成树，算法停止；否则，令，转第二步停止算法的计算复杂度分析：算法的主要计算量在第2步和第3步。算法第一次执行第三步至多需做次比较，第二次执行第三步至多需做次比较，，因此执行第三步至多共需要做：次比较；同样执行第二步共需不超过次比较，于是标号Prim算法的时间复杂度为。标号Prim算法将Prim算法每次循环中比较到间所有边的权改为，并比较中顶点的标号，因此节省了计算量。Euler图与Hamilton图：欧拉通路（路径）：走遍图G每一条边一次仅且一次的通路。欧拉回路：走遍图G每一条边一次仅且一次的回路。具有欧拉回路的图称为欧拉图。汉密尔顿通路（路径）：走遍图G每个顶点一次且仅一次的通路。汉密尔顿回路：走遍图G每个顶点一次仅且一次的回路。具有哈密尔顿回路的图称为哈密尔顿图。判别条件无向连通图G具有一条欧拉路径当且

仅当G具有零个或两个奇数次数的顶点。若无奇数度顶点（全为偶度顶点），则通路为回路；若仅有两个奇数度顶点，则它们是每条欧拉通路的端点。求Euler图中的Euler闭迹--Fleury算法：对于复杂一些的图，即使判定出它有Euler闭迹，也未必能很快地找出一条Euler闭迹。在许多大规模应用中，需要借助于算法来找图的Euler闭迹——Fleury算法。基本思想：从图中一个顶点出发，用深度优先方法找图的迹，在任何一步，尽可能不要用剩余图的割边，除非没有别的选择。Fleury算法的步骤：第1步：任取，令，第2步：设迹已取定.从中选取一条边使得（1）和相关联；（2）不选的割边，除非没有别的选择。第3步：当第2步不能再执行时，停止。中国邮递员问题：问题（管梅谷，1960）：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次后，回到邮局。请为他选择一条路线，使其所行路程尽可能短。图论模型：求赋权连通图中含所有边且权最小的闭途径。这样的闭途径称为最优邮路基本思想：

（1）若G是Euler图，则G的Euler闭迹便是最优邮路，可用Fleury算法求得。（2）若G不是Euler图，则含有所有边的闭途径必须重复经过一些边。此可以构造一个Euler图。如何构造Euler图：闭途径重复经过一些边，实质上可看成给图G添加了一些重复边（其权值与原边的权相等），最终消除了奇度顶点形成一个Euler图。因此这种情况下求最优邮路可分为两步。首先给图G添加一些重复边得到Euler图G1，使得添加边的权之和最小，（其中）；用FLeury算法求得G1的一条Euler闭迹。这样便得到G的一条最优邮路。问题是：如何给图G添加重复边得到Euler图G1，使得添加边的权之和最小Edmons-Johnson方法：第1步：若G中无奇度顶点，令G1=G，转第2步；否则转第3步。第2步：求G1中的Euler闭迹，并按该Euler闭迹输出G的最优邮路；