图论模型的建立与转化

图论模型的建立与转化

关键字：图论模型、建立、转化

摘要

本文主要写图论模型的建立与转化，共分四部分：

第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。

第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。

第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点→边、点→点、边→边，其中详细分析了第二类。

第四部分总结了全文，并指出了进一步研究图论模型的必要性

目录

一．引言 (2)

二．图论模型的建立 (2)

I.要素的取舍 (2)

II.选择合适的理论体系 (4)

三．图论模型的转化 (7)

I.拆分转化 (7)

II.补集转化 (10)

四．结语 (11)

正文

一.引言

信息学竞赛以解题为主，整个解题过程中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。

图论建模是指对一些客观事物进行抽象、化简，并用图1来描述事物特征及内在联系的过程。

建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具；

但图论模型和其它模型在它们的研究方法上又有着很大的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。

我们学习图论，一般都是通过书籍，但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。

在建立图论模型的过程中，我们常常会遇到一些困难，例如难以建立点、边、权关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。

二.图论模型的建立

在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。

I.要素的取舍

在用图论模型描述研究对象时，为了更突出与求解目标息息相关的要素，降低思考的复杂度，就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。

【例1】导线排布Line[7]：

题目（文档附件：导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解目标是构造一种符合所给的导线交叉情况的导线排布方案。

起先，我们对题目描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的1在本文中，“图”专指由若干不同顶点与连接其中某些顶点的边所组成的图形[6]，不包括一般的示意图。

例子，但竞赛时我们不可能花更多的时间在熟悉题目上了，这时只有尽快地把我们不熟悉的、难于思考的原型转化成我们熟知的、便于思考的模型。

先来分析求解目标：所谓的构造导线排布方案，也就是找出每根导线两个端点的编号；而编号要满足的条件就是导线交叉的情况。

那么下一步我们就来分析一下编号与导线交叉之间的关系。记第i 根导线两端点的标号为Ai 和Bi （Ai

共同点是A1>B1，A2>B2，A1>A2（根据编号规则），不同的是(a)满足A2>B1，B1>B2，(b)满足B1>A2，而(c)满足B2>B1。显然，这是一种偏序关系（有点不确切，它只满足反对称和传递性，但不是自反的），而我们的任务就是根据这种偏序关系求得全序关系，即拓扑排序。

我们用图中的有向边来表示偏序关系，若有向边构成环，则问题无解。以上三种情况对应的有向图如图二所示，若两导线交叉，则如(a)；若不交叉，则必是(b)、(c)其中之一，至于选择哪一个，就要看它们中哪一个不会导致无解。

若(b)无解，就表示图中除了B1→A2这条边之外，还存在着一条A2→B1的路径，可能的两种情况如图三(1)(2)中红色有向边所示：(1)表示有编号大于2的导线（(1)中的导线3）与导线1交叉；(2)表示虽然它们都不与导线1交叉，但其中有选择图二(c)表示的。

显然，如果情况(1)出现，那么选择(b)必然无解；但如果(1)不出现，那么(2)就可以改成图三(3)（即改用(b)表示导线1、3不交叉，而不是用(c)），这样就有解了。也就是说，如果导线i 与导线j(i

(a)A1>A2>B1>B2

(b)A1>B1>A2>B2

(c)A1>A2>B2>B1

图 一

1 2

3

4

1

2

3

4

1

2

3

4

(a)

(b)

(c)

图 二

A1 B1 A2

B2 A1 B1 A2

B2 A1 B1 A2 B2

(1)

(2) (3)

图 三

A1 B1 A2 B2 A3

B3 A1 B1 A2 B2 A3

B3

A1 B1 A2 B2 A3 B3

类似的，我们可以分析出：如果导线i 和j (i

(L 1=i ，L m =j)，使得导线L k -1与导线L k (1

图四(1)画出了(c)无解的情况，此时导线1与3不交叉，m=3，L=(1,2,3)；图四(2)表示导线1与3不交叉，导线1与2，2与3，1与4交叉，此时用(b)或(c)表示导线1与3不交叉都无解，所以整个问题无解。 分析到这里，图论模型和算法实际上已经出来，具体的实现就不多说了。 上面的分析看似冗长，但实际上，分析的过程如行云流水，十分自然，究其原因，就是我们舍去了原型中一些与求解目标无关的因素，而仅用一个有向图来表示交叉关系。比起紧紧抱住圆圈、导线这些细节不放，直接分

析原型的方法来，分析模型的思维复杂度自然要小得多。

在建模过程中，忽略掉原型中与求解目标关系不大的要素，能够适当地简化问题。但事物都是一分为二的，如果简化得过了度，反而会使模型变得不够准确，甚至是不正确的，因此，只有在“简明”和“准确”之间找到平衡点，才能建立起具有最佳效果的模型。

II.

选择合适的理论体系

图由点、边、权三部分组成，根据这三部分的性质的不同，就有着不同的图论模型，有着不同的理论和算法，也就构成了不同的理论体系。

例如二部图把整个点集V 分为两个子集，规定子集内部的点之间没有边，因此二部图就有着不同于一般图的特殊性质，而它的匹配算法也就比一般图的算法简单；此外还有树、有向无环图等，它们属于不同的理论体系，有着各自不同的性质，适于用不同的算法求解。

而权的加入则使图论模型和求解目标变得更加复杂多样了。

有的权表示长度或是时间等等，它们的运算特征是“串联求和，并联求最值”，即一条路径的权由这条路径上每条边的权相加得到，求解目标往往是求图中或是两点之间所有路径的权的最优值。

有的权则表示容量或是流量，它们的运算特征是“串联求最值，并联求和”，即一条路径上最大或是最小的权决定了整条路径的权，而求解目标则是求图中或是两点之间所有路径的权的加和。

以上只是基本的几类权，它们还会产生一些变形，例如权的运算由简单的相加、求最值扩展到相乘，或是更复杂的函数计算等等。

还有的图不仅包含边权（边集E 到实数集R 的映射），还包含点权（点集V 到实数集R 的映射）；或是包含好几类不同性质的权。

以上这些差异形成了图论模型的多样化，使图论模型可以广泛地适应各类问题，但这些丰富的选择同时也增加了图论建模的难度。对于有些题目，我们可能很自然地就联想到某种图论模型，例如看到表达式，就会联想起表达式树；但对于另一些题目，分析的角度不同，就会得出不同的模型，产生不同的效果。 【例2】 奶牛排队Cows on Parade （文档附件：Finals95.htm ）（USACO'95决赛）：

[问题简述]：求一个长度为2 n + n-1的01序列，要求序列中包含所有长度为n 的01排列(共

(1)

(2) 图四 A1 B1 A2 B2

A3 B3 A1 B1

A2 B2 A3 B3

A4 B4

个2 n

)。当n=3时，序列如左图所示。 与此类似的还有“鼓轮设计”一题（见参考书籍[9]P95），不同的是前者要求排成一线，而后者要求排成一圈，显然，只要后者解决了，前者也就解决了。所以这里也以排成一圈为求解目标。 [模型A] 如果以每个长度为n 的01排列为点，以它们之间的重叠关系为边，就构成了一个有向图（如图五所示）。求

解目标就是在这个图上找一个回路（图中蓝色部分），使得通过每点一次且仅一次——Hamilton 回路问题。 [模型B]

如果以01排列之间的重叠部分为点，以01排列为边，就构成了一个如图六所示的有向图，求解目标就是在这个图上找一个回路，使得不重复地遍历每条边——Euler 回路问题。 从图六中不难看出，图上每点都是连通的，而且入度和出度都等于2，因此图中存在Euler 回路，也并不难求（算法及相关理论见参考

书籍[6]P152或[8]P246或[9]P95）。相较之下，Hamilton 回路问题是NP

完全问题，也就是说，模型A 的建立并没有给问题的解决带来任何便利。

由此可见，不同理论体系的图论模型很可能会产生完全不同的效果。

例2中不同模型的建立是由于分析角度的不同，而在下面的例3中，则是因为对原型的分析深浅不同的缘故。 【例3】 最少路径覆盖（题目见参考书籍[1]P274或[3]P429）：

有向无环图G(V ,E)的一个路径覆盖是指一个路径集合P ，满足图中的每点属于且仅属于集合中的一条路径。求一个包含路径数最少的路径覆盖（如图七所示）。

[解法A] 网络流模型（见图八）：

设p=|P |，则上图中p min =2，有三种方案：

①{1→3→4→5，2} ②{2→3→4→5，1} ③{1→3→4，2→5}

图 七 1 3 2 4 5

图 八

1' 1,1 3' 1,1 4' 1,1 5' 1,1

2' 1,1

1'' 3'' 4'' 5''

2'' s

t

10 0 0

图 五 000 001 100 111 0 0 1 1 1 0 011 110 010 101 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0

000 001 011 111 110 101 010 100

图 六

00 01 11 1 1 1 0 0 1

1．把点i(i ∈V)拆成两点i'和i''，添加弧（即有向边）(i', i'')，容量上界C i', i''=1，下界B i', i ''=1； 2．加源点s 和汇点t ，添加弧(s, i' )和(i'', t)，C s, i' = C i'', t =+∞，B s, i' = B i'', t =0； 3．把边集E 中的弧(i, j)改为弧(i'', j')，C i'', j '=+∞，B i'', j '=0。

建立了新图G'之后，原图G 中的一条路径就相当与G'中的一条流路径。因为我们规定G'中C i', i''= B i', i''=1，所以原图G 中的点i 属于且仅属于一条路径，因此G 中包含路径最少的一个路径覆盖方案就相当于G'中的一个最小流方案。

[解法B] 二部图模型

设路径覆盖P={P 1，P 2，……，P p-1，P p }，P i (1≤ i ≤p)表示集合P 中的一条路径；记V i = P i ∩V ，E i = P i ∩E ，即V i 为 P i 中的点，E i 为 P i 中的边，显然|V i |=|E i |+1。

例如在图七中，第①种方案为P={1→3→4→5，2}，其中P 1=1→3→4→5，所以V 1={1，3，4，5}，E 1={(1,3)，(3,4)，(4,5)}。

因为P 是一个路径覆盖，所以V 1∪V 2∪……∪V p-1∪V p =V ，且V i ∩V j =?(1≤i,j ≤p ，i ≠j)。这些条件加上一点集合方面的知识，我们不难有以下的推导：

∑∑∑∑====-=∴+=+==∴≠≤≤?=?=???p

i i

p

i i p i i p

i i

j i p E V p E p E V V j i p j i V V V V V V 1

11

121)

1(),1(，

，，且，

又∵E i ∩E j =?(1≤i,j ≤p ，i ≠j), ∴∑∑===

p

i i

p

i i E

E 1

1

，

记M=∑=p

i i E 1

，则M 需要满足“V 中的每一点最多只与M 中的两条弧相连：一条入弧和一条

出弧”，并且只要M 满足这个条件，它与路径覆盖就是一一对应的。

有了以上的分析之后，我们就可以建立起一个二部图模型（见图九）了： 1．把点i(i ∈V)拆成两点i'和i''；

2．把边集E 中的弧(i, j)改为无向边(i'', j')。

在新图G'中, 点i'为入点，原图G 中所有以点i 为弧头的弧都改成了与i'相连的无向边；同样的，点i''为出点，G 中所有以点i 为弧尾的弧都改成了与i''相连的无向边。这时，原图G 上的M 就相当于二部图G'上的一个匹配。

上面我们已经分析出M 与P 是一一对应的，且|P |=|V |-|M |，而|V |又是定值，所以只要求出二部图G'上的最大匹配，也就求得原图G 的最小路径覆盖了。

比较上面两个解法的时空效率和编程复杂度，不难看出解法B 要明显优于解法A 。这是因为解法B 对原型进行更深入的分析，只抽取了原型中较关键的要素来建立模型，所以求解起来更为简单、方便。

图 九

5'

5''

4' 4'' 3' 3'' 2' 2'' 1' 1''

另外值得注意的一点是：解法A 中用到了网络流算法。由于这类算法一般编程复杂度大，易错，而且算法的系数较大，所以它在竞赛中的表现往往不十分出色。但是网络流模型可以容纳的要素很多，特别是权的类型众多：不仅有表示容量和流量的权，还有表示费用的权；容量不仅有上界，还可以有下界……有了这些多变的因素，再加上网络流算法一般都属有效算法，所以网络流模型在现实问题的解决和图论问题的研究中有着十分广泛的应用。在下面的例题中，也还有不少用到了网络流模型。

从上面的例子中，我们已经了解到了选择合适的理论体系的重要性。有时，可能会有多个看似都正确的模型可供选择，只有仔细分辨出它们之间细微但又关键的差别，才能够选出适于求解的模型。这就要求我们既要熟悉图论的算法和理论，也要对原型有着清楚的认识。

无论是要决定要素的取舍，还是面对着不同理论体系的选择，总的原则都是：准确、清晰、简明。

“准确” ：指模型应当忠于原型，不可扭曲原型本来的性质，也不可默认原型具有一些假设的、未经证明的性质；

“清晰” ：就像程序具有可读性一样，图论模型也具有清晰度，以结构清晰的模型为分析对象，思考复杂度就会降低很多；

“简明” ：指模型中含有的要素简单明了，不繁杂，模型也是便于分析求解的，有这一要求主要是因为图论中很多算法和理论都相当高深和复杂，很难运用和变通，因此尽量不要采用。

三. 图论模型的转化

在建立图论模型解决问题时，我们往往会遇到这样的情况：在很轻松地建立起一个模

型之后，却不知该如何分析，求解，或是发现建立起的模型无法表现原型的一个很重要的性质。这时，我们必须要放弃现有的模型吗？不，如果运用一些方法和技巧的话，现有的模型很可能就会转化为能够准确描述原型，而又易于求解的新模型。

在这些方法和技巧中，

有一些只适用于特定的图论

模型，例如把多叉树转化为

二叉树（见图十）处理的技

巧。此外，还有另一些作用

范围更广的方法和技巧，下面将讨论的“拆分转化”就

是其中之一。

“拆分转化”可分为三类：点→边、点→点、边→边。其中第一类很常用，但拆法较简单；第二类不仅常用，而且灵活多变；第三类的拆法和作用则与第二类很相似。所以下面将详述第二类，简述第一、三类。

1． 点→边：

“拆点为边”是“拆分转化”中十分常用的一类，当要求现有模型中的点具有边的性质时，“拆点为边”就是一个好办法。

图 十

1 2 3 4 5 (1)

2 3 4

5 ……

在例3中建立模型A 时，我们把每个点拆成了一条有上下界容量的边，以满足“每个点经过且只经过一次”的要求。另外，我们在求解点有容量的网络流时，为了得到标准的网络流模型，往往也把点拆成边，把点上的容量限制转移到对应的边上。

在实际应用中，“拆点为边”的例子很多，“拆法”也大同小异：把每点i 拆成两个点i'和i''；以i 为弧头的弧都改为以i'为弧头，以i 为弧尾的弧都改为以i''为弧尾（这些弧上的权以及原有属性是保留还是更改，则视情况而定）；并且添加一条i'指向i''的弧，把点i 具有的

属性赋给这条弧（参见图十一，其中蓝色的弧为添加的弧）。

2． 点 点：

这是“拆分转化”的第2类：把一个点拆成若干个点。它主要用于把一个点拥有的好几个不同的性质分离开，分别赋给几个新的点，使每个点的性质单一，再通过一些改造来统一处理它们。

例如在例3中建立模型B 时，为了表示任意一点i 最多允许与一条入弧和一条出弧相连，我们把i 拆成了一个入点i'和一个出点i''，并且通过把所有的入弧都连到i'上，所有的出弧都连到i''上的措施，使每点都只与一条边相连，这样，用匹配算法就可以统一处理了。

拆点的方式多种多样，远不止上面一种，下面的例子中用到的就与例3不同。 【例4】 障碍物探测器Mars explorer （文档附件：Mars.html ）（IOI ’97）：

[问题简述]：

在P ?Q 的矩形中，每个格子的地形可能是下列三种之一：

1．障碍：无法通过； 2．平地：平坦无物，可通过；

3．石块：可通过，第一次通过时可采到一块岩石；

求M 条的路径（M 给定），使得路径能够覆盖到石块数总和最大，路径要满足的条件是：

1．每条路径都是从(1,1)到(P,Q)，途中每步只能向东或向南走一格； 2．路径不通过障碍；

[建立网络流模型]：

我们按照常规思路把每条路径看作流量为1的流路径，并根据路径要满足的两个条件，建立如下模型：

1．把每个格子看作点，并引两条弧，分别指向其东侧和南侧相邻的点（如果有的话），弧的流量表示通过这条弧的路径数，所以容量为+∞（≥m 就可以了）；

图 十一

有向边：i j i' i'' j'

j"

无向边：i

j i' i'' j'

j"

i

j S O O

O O

O O T 图 十二

2．删去与障碍点相连的弧。

但这只是一个初步的模型，它很显然没能区分“平地”和“石块”。难点主要就在于：岩石只有第一次通过时可以采到，之后这个格子就变成平地了。因此，就需要把含有岩石的点i 拆成两个点：i'和i''，分别表示岩石和平地。具体改造步骤（如图十三所示）如下：

1．i''继承与i 相连的所有入弧和出弧，且容量不变，收益为0； 2．从i''引出一条弧，指向i'，令其容量为1，收益为1； 3．i'继承与i 相连的所有出弧，容量改为1（>1也可以），收益为0；

经过上述转化之后，原问题的求解目标就对应于新模型上流量为M 的最大收益流2。

上面举的两个例子都是把一个点拆成两个点，但这与“拆点为边”是截然不同的。这里是为了把一个点具有的各种性质分离开，有几种性质需要分离，就要拆成几个点；而“拆点为边”是为了使点具有边的性质，所以总是固定地把一个点拆成两个，并在两个新点之间添边。

3． 边 边：

这是“拆分转化”的第3类：把一条边拆成若干条边。它和上面的第2类一样，也是用于因素分离。下面就只简单地举例分析一下。 【例5】 容量有上下界的网络流：

这是一个标准的网络流问题，许多书上都有该问题的解法和相关证明，所以这里就只简述一下把原图转化为一般的最大流模型的过程3：

1．加两个新顶点：附加源s'和附加汇t'，作为新的源和汇；

2．把原图上的弧(i,j)拆成三条新弧：(i,j)、(s',j)、(i,t')，令C'i,j =C i,j -B i,j ，C's',j =C'i, t'=B i ,j （C i ,j 、B i ,j 分别为原图上弧(i,j)的容量上、下界，C'i ,j 、C's',j 和C'i, t'为新弧的容量上界）； 3．在原来的源和汇之间添加两条容量为+∞的新弧：(s,t)和(t,s)。

在以上三步中，第二步最为关键，它实现了把原图上的容量上界和下界分离开的目的（如图十四(a)所示）。图十四(b)和(c)分别是转化前的原图和转化后的新图。

2 后面我们将通过“补集转化”把最大收益流转化为最小费用流求解。

3

至于如何根据新模型上的最大流求得原图的可行流，请见参考书籍[6]P68或[8]P165。

(a)

(b)

(c)

图 十四

i

j

b,c

i

j

c-b

s' t' b b s

u

5,3 v t

3,1

4,1 5,2 4,2 s

u 2 v t 2 3

3

2

t' s' +∞

+∞ 2 4 3 3

3 3

新模型：

蓝色的点表示“岩石” 黑色的点表示“平地” 灰色的点表示“障碍” 蓝色边的容量为1 黑色边的容量为+∞

图 十三

s t

i' i i''

更进一步地，如果点（或边）的性质随着时间的推移而变化着，我们也可以用类似于第2类或第3类的方式把它们拆成许多点（或边），以表示不同时刻不同性质的点。下面我们就来看一看这类“拆分转化”是如何应用到例6上的。

【例6】家园Homeland（CTSC '99，下面只简述建模的过程，具体算法分析请见文档附件：homeland..doc）：

仔细分析了题意之后，不难想到建立网络流模型来解决这题：

1．以太空站为点；

2．以往返于太空站之间太空船为边；

3．以船的最大载客量为容量上界；

求解目标就是在最短时间内把固定流量（人）从源（地球）送到汇（月球）。但这里的时间不同于费用，而且边随着时间t的变化存在于不同的点对之间。因此按时间拆点就很有必要：把每个点都拆成t个点；把边按照时刻的不同分配在相应的新点对间。

如此一来，原本动态变化着的模型就被转化成了静态不变的新模型了。

从上面举的几个例子可以看出，要分离的性质不同，拆点（边）的方式也就随之不同，只有准确地分析出点（边）要表示的性质，才能转化得到合适的模型。

通过对这三类点和边的“拆分转化”的分析和总结不难发现，它们的目的和应用范围各异，但方法都是一个“拆”字。在它们的应用上，我们完全不必拘泥于具体形式，只要是建模的需要、解题的需要，就可以按需“拆分”。只要“拆分”得当，上面的三类“拆分转化”就可以应用得更广。

除了“拆分转化”之外，“补集转化”也是一种不依赖于特定模型的转化方法。

前面在例4的分析中，我们留下了一个问题：把流量固定的最大收益流转化为最小费用流求解。这就要求对边权进行一定的修改：改所有表示“平地”的点对之间的弧（图十三中黑色的弧）的费用为1；改所有指向“岩石”或从这些点指出的弧（蓝色的弧）的费用为0。这样，原模型上每条流路径的收益就等于P+Q-2（该路径的长度）减去路径上的费用的差。如此也就实现了把最大收益转化为最小费用的目的。

这种用某个特定值减去原权值的转化技巧，我们就称作权的“补集转化”。

既然有权的“补集转化”，自然也有点和边的“补集转化”。点和边的“补集转化”是指用全集（如图的点集、边集或是其它集合）减去某个特定的集合（如题目给定的集合或求解目标集合等）的转化技巧。下面我们就通过具体例子来分析一下。

【例7】最大独立集问题及其等价问题：

最大独立集的问题描述如下：给定无向图G(V,E)，其中A?V，且E?{(i,j)∣i,j∈A}=?，求A，使得∣A∣最大。它还有两个与之等价的问题：

1．最小覆盖问题：

一般地，我们都把最大独立集转化为最小覆盖集，然后根据逻辑运算定律求解（见参考书籍[6]P57）：令B=V－A，则B?V，且对于任意一条边(i,j)∈E，有i∈B或j∈B，所以B

是图G(V,E)的最小覆盖集。在这个转化过程中就用到了点的“补集转化”——用点集V减去求解目标集合A，以得到新的目标集合B。

2．最大完全子图问题：

[问题描述] 给定无向图G(V,E)，其中C?V，对于任意两个点i,j∈C，且i≠j，有(i,j)∈E，求C，使得∣C∣最大。

当我们已经知道并且能够证明这个问题是NP 完全问题（见参考书籍[3]P658）时，只要能够把它转化为最大独立集问题求解，也就证明了后者是NP 难度的，而这一步转化中就要用到边的“补集转化”：令全集U={(i,j)∣i,j ∈V}，E'=U －E ，则在无向图G'(V ,E')中，有C ?V ，且E ?{(i,j)∣ i,j ∈C}=?，所以C 也是图G'的最大独立集。

例如图十五G'中，黑色的点构成了最大独立集，而白色的点就是最小覆盖集；图G 的点集与G'一样，而边集E 则是E'的补集，图中黑色的点构成了该图的最大完全子图的点集。

从上面的例子可以看出，“补集转化”往往都是等价转化，而且往往都会使求解目标产生一定的变化。无论是点、边还是权的“补集转化”，目的都是使模型向着更便于思考和求解的方向转化。

除了上面分析的“拆分转化”和“补集转化”外，图论模型的转化方法和技巧还有很多，而且它们还可以综合起来运用，就像在例4中一样，经过了几次模型的转化，最终得到了需要的图论模型。

四. 结语

本文主要分析了图论模型建立中的两个要点和图论模型转化的几种方法技巧。在实际

的建模过程中，它们是密不可分的：正确提取原型中的要素；对应到特定理论体系中相应的元素上；建立起初步的模型；然后根据需要进行适当的转化。至此，一个适于求解的图论模型才建立成功。在这其中，无论是对建模原则的把握，还是模型转化方法的运用，都遵循着一点：原型本身的性质决定了模型。如果硬要把原型套到不合适的模型上去，往往反而会破坏原型的关键性质，这时，即使建立的模型再怎么巧妙、经典，也是经不住考验的。

图论算法和理论十分独特精妙，然而难于随心所欲地运用；图论模型的建立和转化十分灵活，因而难于掌握。因此，对图论模型的研究并非一朝一夕的事，需要持之以恒。本文只是我个人对图论建模的一点浅显认识，也只是一个开始。我相信，随着认识的进一步加深，集思广益，图论模型一定有更广阔、更精彩的应用。

【附录】

本文的重点在于图论建模，而模型的解答、解释和检验等不在本文讨论范围之内。文中设计到的图论算法和理论在下列书籍中都有详细介绍，因此文中也只加以简要的分析。

【参考书目】

G'

G

图 十五

1

2

3

4 5 6 1 2

3

4 5 6

[1]吴文虎、王建德，实用算法的分析与程序设计，电子工业出版社，1998

[2]任善强、雷鸣，数学模型，重庆大学出版社，1998

[3]潘金贵、顾铁成等，现代计算机常用数据结构和算法，南京大学出版社，1994

[4]吴文虎、王建德，国际国内青少年信息学（计算机）竞赛试题解析（1994～1995），清华

大学出版社，1997

[5]吴文虎、赵鹏，1993～1996美国计算机程序设计竞赛试题与解析，清华大学出版社，1999

[6]吴文虎、王建德，青少年国际和全国信息学（计算机）奥林匹克竞赛指导——图论的算法

与程序设计，清华大学出版社，1997

[7]1999国家集训队资料

[8]谢政、李建平，网络算法与复杂性理论，国防科技大学出版社，1995

[9]倪兆中，集训队作业论文选编，1998

安徽徐静

2000.1.15

数学建模中常见的十大模型

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的

图论模型简介

图论模型简介 一、图及其矩阵表示 1、起源：哥尼斯堡七桥问题： 欧拉为了解决这个问题，建立数学模型：陆地——点，桥——边，得到一个有四个“点”，七条“边”的“图”。问题转化为能否从任一点出发一笔画出七条边再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画判定法则：图是连通的，且每个顶点都与偶数条边相关联（这种图称为欧拉图）。由此可以得出结论：七桥问题无解。

2、基本概念： 图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。 邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。 无向图（graph）：边无方向的图；有向图（digraph）：边有方向的图。 路(path)：由相邻边组成的序列，其中中间顶点互不相同。 圈(cycle)：首、尾顶点相同的路，即闭路。 连通图（connected graph）：图中任意两顶点间都存在路的图。 树（tree）：无圈连通图 完全图（complete graph）：任意两个顶点之间都有边相连的无向图，记为K n。 竞赛图（tournament）：由完全图给每条边定向而得到的有向图。 二部图（bipartite graph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。 网络（Network）：边上赋了权的有向图。

3、图的矩阵表示 无向图 有向图 0100010 11001011 011000 1 00???????????????? ???? ? ? ? ? ????????0110010100000100100000110

数学建模中的图论方法

数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。

图论 模型

251 图论模型 图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。 图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. K?nig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。 9.1 图的基础理论 9.1.1 图的基本概念 所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。E 是边的集合，称为边集。边一般用(,)i j v v 表示，其中 ,i j v v 属于顶点集V 。 以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。 如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 (,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =. 2 3 v 45 v 3 4 (a) (c) 图9.1 图的示意图 1.无向图和有向图 如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。 如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点i v 和j v 的弧记为,i j v v ??，其中i v 称为起点，j v 称为终点。显然此时弧,i j v v ??与弧,j i v v ??是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为(,)D V A =，其中V 为顶点集，A 为弧集。 例如图9.1 (C)可以表示为(,)D V A =，顶点集1234{,,,}V v v v v =，弧集为1223{,,,, A v v v v =????243441,,,,,}v v v v v v ??????。 对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用G 表示。 例9.1 设12345{,,,,}V v v v v v =，12345{,,,,}E e e e e e =，其中

数学建模中常见的十大模型讲课稿

数学建模中常见的十 大模型

精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除

数学建模常用算法模型

数学模型的分类 按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握） 解决预测类型题目。由于属于灰箱模型，一般比赛期间不优先使用。 满足两个条件可用： ①数据样本点个数少，6-15个 ②数据呈现指数或曲线的形式 2、微分方程预测（高大上、备用） 微分方程预测是方程类模型中最常见的一种算法。近几年比赛都有体现，但其中的要求，不言而喻。学习过程中 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式推导转化为原始数据的关系。 3、回归分析预测（必掌握） 求一个因变量与若干自变量之间的关系，若自变量变化后，求因变量如何变化； 样本点的个数有要求： ①自变量之间协方差比较小，最好趋近于0，自变量间的相关性小； ②样本点的个数n＞3k+1，k为自变量的个数；

数学建模常用算法模型

按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）

3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握）

图论模型的建立与转化

图论模型的建立与转化 关键字：图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化，共分四部分： 第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点→边、点→点、边→边，其中详细分析了第二类。 第四部分总结了全文，并指出了进一步研究图论模型的必要性 目录 一．引言 (2) 二．图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三．图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四．结语 (11)

正文 一.引言 信息学竞赛以解题为主，整个解题过程中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简，并用图1来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具； 但图论模型和其它模型在它们的研究方法上又有着很大的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。 我们学习图论，一般都是通过书籍，但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。 在建立图论模型的过程中，我们常常会遇到一些困难，例如难以建立点、边、权关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时，为了更突出与求解目标息息相关的要素，降低思考的复杂度，就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]： 题目（文档附件：导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先，我们对题目描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的1在本文中，“图”专指由若干不同顶点与连接其中某些顶点的边所组成的图形[6]，不包括一般的示意图。

数学建模中常见的十大模型

数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。

8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。

图论模型及其解答

各种图论模型及其解答 摘要： 本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。 符号约定： Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。 一、引言 图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下： 原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解 整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况： ①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图 ②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图 如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。 综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。 例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友M：点表示人，连线表示当且仅当该两个人是朋友 A：问题转化为任何一个图一定存在两个顶点的度相等 二、图论模型 接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。 2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这

第九章 图论模型

第九章 图论模型 现实世界的许多实际问题都可以用图形来解释或说明.例如通讯网络就可以用图的形式直观的表现出来：点可以表示通讯中心，而边表示通讯线路.图论模型是应用十分广泛的数学模型,它已经在物理、化学、控制论、信息论、科学管理和计算机等领域.由于它具有图形直观，方法简单容易掌握的特点，因此在实际、生活和数学建模中，有许多问题可以运用图论的理论和方法解决. §9.1图论起源 图论起源于18世纪欧拉对哥尼斯堡七桥问题的研究.哥尼斯堡是18世纪东普鲁士的一个城市，城中有一条普雷格尔河，河中有两个岛，河上有七座桥，如图1所示. 图1 当时那里的居民热终于思考这样一个问题，一个人能否经过七座桥且每座桥只走过一次，最后回到出发点.能否用数学的方法解决这个问题一贯成为当时居民的一个悬而未决的问题. 1736年欧拉创造性的将陆地用点表示，桥用边表示，从而将这个问题转化为如图2所示的一笔画问题，即能否从某个点开始一笔画出这个图形，最后回到原点而不重复.欧拉证明了这个问题是不可能的. 图2 欧拉解决七桥问题时，其方法超出了常用的数学方法，充分发挥自己的想象力，用了全新的思想方法，从而使得问题得到完美解决.由于这一项开创性的工作，产生了“图论”这门崭新学科，欧拉被认为是图论的创始人. A B C D A B C D 1 e 2 e 5e 6e 7 e 4 e 3 e

§9.2基本概念 定义1 图G 由两个点集合V 以及边集合E 组成，记为(),G V E =，其中： (1)V 是顶点构成的集合； (2)E 是连接某些顶点对构成的边组成的集合. 例1 {}1234,,,V v v v v =，{}12232434,,,E e e e e =，画出图(),G V E =. 图3 注：图分为无向图和有向图. 定义2 若图(),G V E =的边均没有方向，这样的图成为无向图.例如图2，图3为无向图.无向图的边称为无向边，无向边是由两个顶点构成的无序对，无序对通常用圆括号表示. 例2 () ,i j v v 表示一条无向边，(),i j v v 与() ,j i v v 是同一条边. 定义3 若图(),G V E =的边均有方向，这样的图称为有向图.有向图的边称为有向边，有向边是由两个顶点构成的有序对，有序对通常用尖括号表示.有向边又称为弧. 例3 ,i j v v 表示一条有向边，,i j v v 与,j i v v 是两条不同的有向边. 定义4 一条边的端点称为与这条边关联，反之，一条边称为与它的端点关联.与同一条边关联的两个端点是邻接的.如果两边有一个公共端点，则这两条边是邻接的。两个端点重合为一点的边称为圈，不与任何边关联的点成为孤立点. 例4 如图4所示，理解定义4 图4 注：若图(),G V E =中V 和E 为有限集，称图G 为有限图,没有任何边的图为空图，只有一个点的图称为平凡图。一个图既无圈又没有两边连接同一对点的图称为简单图。 例5 结合图5理解上述概念。 5 v 4 v 3 1 v 2 v 3 v 4v 12 e 23 e 24 e 34 e

maab图论程序算法大全

图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1)

for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量

数学建模中常见的十大模型

数学建模中常见的十大 模型 集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。

8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。

图论模型建立与转化

图论模型的建立与转化 安徽徐静 关键字：图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化，共分四部分： 第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点→边、点→点、边→边，其中详细分析了第二类。 第四部分总结了全文，并指出了进一步研究图论模型的必要性。 目录 一．引言 (2) 二．图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三．图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四．结语 (11)

正文 一.引言 信息学竞赛以解题为主，整个解题过程中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简，并用图[1]来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具； 但图论模型和其它模型在它们的研究方法上又有着很大的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。 我们学习图论，一般都是通过书籍，但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。 在建立图论模型的过程中，我们常常会遇到一些困难，例如难以建立点、边、权关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时，为了更突出与求解目标息息相关的要素，降低思考的复杂度，就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]： 题目（文档附件：导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先，我们对题目描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的例子，但竞赛时我们不可能花更多的时间在熟悉题目上了，这时只有尽快地把我们不熟悉的、难于思考的原型转化成我们熟知的、便于思考的模型。 先来分析求解目标：所谓的构造导线排布方案，也就是找出每根导线两个端点的编号；而编号要满足的条件就是导线交叉的情况。 那么下一步我们就来分析一下编号与导线交叉之间的关系。记第i根导线两端点的标号为Ai和Bi（AiB1，A2>B2，A1>A2（根据编号规则），不同的是(a)满足A2>B1，B1>B2，

数学建模常用模型有哪些[1]

数学建模常用模型有哪些？？？ 1蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 作用： 应用数学去解决各类实际问题时，建立数学模型是十分关键的一步，同时也是十分困难的一步。建立教学模型的过程，是把错综复杂的实际问题简化、抽象为合理的数学结构的过程。要通过调查、收集数据资料，观察和研究实际对象的固有特征和内在规律，抓住问题的主要矛盾，建立起反映实际问题的数量关系，然后利用数学的理论和方法去分析和解决问题。这就需要深厚扎实的数学基础，敏锐的洞察力和想象力，对实

数学建模图论

第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现 了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到

实用标准文案 起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP－shortest path problem）