图论模型的构建.ppt

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

1、图论模型的构建江苏省苏州中学 章维铣一绪言一绪言 图论是数学的一个有趣的分支。图论是数学的一个有趣的分支。17361736年数学家欧年数学家欧拉（拉（EulerEuler 1707 170717831783）发表了一篇论文，用图的方发表了一篇论文，用图的方法解决了著名的七桥问题，是图论建模的经典例子。法解决了著名的七桥问题，是图论建模的经典例子。图论建模是指对一些客观事物进行抽象、化简，图论建模是指对一些客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程，就是抓住并用图来描述事物特征及内在联系的过程，就是抓住问题的本质，把问题抽象为点、边、权的关系。建立问题的本质，把问题抽象为点、边

2、、权的关系。建立图论模型的目的和建立其它的数学模型一样，都是为图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题。许多看似无从入手的问题，通过性或是构造性问题。许多看似无从入手的问题，通过图论建模，往往能转化为我们熟悉的经典问题。图论建模，往往能转化为我们熟悉的经典问题。二图论建模方法二图论建模方法1.要素的选取要素的选取 在建立模型之前，我们首先要对研究对象进在建立模型之前，我们首先要对研究对象进行

3、全面的调查，将原型理想化、简单化；然后对行全面的调查，将原型理想化、简单化；然后对原型进行初步的分析，分清其中的各个要素及求原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。当的模型来描述这些要素及联系。【例1】渡河问题渡河问题 一个人带了一只狼、一只羊和一筐白菜想要过河。河上有一只小船，每次除了人以外，只能带一样东西。另外，如果人不在时狼就会吃掉羊，羊就要吃白菜。问怎样安排渡河，才能做到既把所有东西都带过河，而且在河上往返次数最少？问题的要素有三点：（1）人及他所带的3样东西；（2）人不

4、在时狼就会吃掉羊，羊就要吃白菜，即人在渡河时，一岸上不能同时留下狼和羊或羊和白菜；（3）人每次至多带一样东西渡河，并要保证岸上的安全。问题的求解目标：求河上往返次数最少的渡河方案。对于要素（1），用字母m代表人，w代表狼，s代表羊，v代表白菜。要素（2）、（3）可抽象为开始时设人和其他三样东西在河的左岸，这种情况用集合mwsv表示。在过河过程中左岸出现的情况有以下16种：wmsv mws mwv msv wsv mw ms mvws wv sv m s v w 剔除下述6种可能发生狼吃羊，羊吃白菜的情况：（注意照顾右岸的情况）wsv ws sv mw mv m将剩下的10种情况作为图G的顶点，

5、图G的边是按下述规则来连接的：如果情况A经过一次渡河可以变成情况B，就在情况A与情况B之间连一条边。根据这一规则，构造的图G如下面所示：问题的求解目标就归结为：在图G中找一条连接顶点mwsv与，并且包含边数最少的路径。把图的边长设为1，那么渡河问题归结为求顶点mwsv到顶点的最短路径问题。【例【例2 2】方形柱体堆砌】方形柱体堆砌 有4个正立方体，它们的6个侧面各着以绿、蓝、红、黄4种颜色之一，如图1-2所示。现在要把这4个正方体堆成一方形柱体，堆成的方形柱体每个侧面4种颜色都有。求解任务：1、这4个正方体能否堆成符合要求的方形柱体？2、若能，找出一种堆砌方法。【方形柱体堆砌问题分析方形柱体堆

6、砌问题分析】一个正方体有6个面，所以4个正方体可以堆砌出为数十分可观的不同状态。就是确定了4个正方体依，次序从上到下排列，只考虑两两接触面不同，也有64=1296种排列，这里还没有考虑4个侧面的不同组合。若考虑到后者，又会衍生出许多各异的形式，先令第个正方体保持不动，正方体个有4个侧面，故有43=64种状态。因此即使在从上到下按序排列情况下，仍然有129664=82944种状态。若用穷举法求这类问题，将是不胜其烦的。为此，我们必须寻找解决问题的更好途径。为此，我们必须寻找解决问题的更好途径。对符合要求的方形柱体来讲，交换任意两个正方体的上下位置，得到的方形柱体仍是符合要求的，即它的4个侧面都有

7、4种颜色。它的每一对对面由4个正方体各一个对面组成，因此问题的要素是4个正方体各3个对面的颜色的构成，于是从每个对面的着色考虑。用字母b,g,r,y分别表示蓝、绿、红、黄4种颜色，并作为图的4个 顶点，4个正方体的各三个对面依各对面的颜色连以边，并分别标以e1、e2、e3、e4，比如第一个正方体有一对面着蓝、黄两色，则从顶点b到y引一条边标以e1,另两对面为红对红、红对绿，故联结r,e和r,g,均标以 e1。同样地根据第二、三、四正方体的各对面着色分别连以边并分别标以e2、e3、e4。则得图G，如图13所示。【方形柱体堆砌问题分析】【方形柱体堆砌问题分析】e4bygre1e1e1e1e2e2e

8、2e3e3e3e4e4从图中，能找到两个Hamiltion回路，每个回路的4条边分别是 e1,e2,e3,e4。(见下页)e4bygre1e1e1e2e2e2e3e3e3e4e42.2.选择合适的理论体系选择合适的理论体系 图由点、边、权三部分组成，根据这三部分的性图由点、边、权三部分组成，根据这三部分的性质的不同，就有着不同的图论模型，有着不同的理论质的不同，就有着不同的图论模型，有着不同的理论和算法，也就构成了不同的理论体系。图论建模依据和算法，也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。的是图论的基本理论和基本算法。例如二分图把整个点集例如二分图把整个点集V分为两

9、个子集，规定子分为两个子集，规定子集内部的点之间没有边，因此二分图就有着不同于一集内部的点之间没有边，因此二分图就有着不同于一般图的特殊性质，而它的匹配算法也就比一般图的算般图的特殊性质，而它的匹配算法也就比一般图的算法简单；此外还有树、有向无环图等，它们属于不同法简单；此外还有树、有向无环图等，它们属于不同的理论体系，有着各自不同的性质，适于用不同的算的理论体系，有着各自不同的性质，适于用不同的算法求解。法求解。权的加入使图论模型和求解目标变得更加复杂多样 有的权则表示容量或是流量，它们的运算特征是有的权则表示容量或是流量，它们的运算特征是“串联求最值，并联求和串联求最值，并联求和”，即一条

10、路径上最大或是最小，即一条路径上最大或是最小的权决定了整条路径的权，而求解目标则是求图中或是的权决定了整条路径的权，而求解目标则是求图中或是两点之间所有路径的权的加和。两点之间所有路径的权的加和。还有的图不仅包含边权（边集还有的图不仅包含边权（边集E E到实数集到实数集R R的映的映射），还包含点权（点集射），还包含点权（点集V V到实数集到实数集R R的映射）；或是包的映射）；或是包含好几类不同性质的权。含好几类不同性质的权。有的权表示长度或是时间等等，它们的运算特有的权表示长度或是时间等等，它们的运算特征是征是“串联求和，并联求最值串联求和，并联求最值”，即一条路径的权由这，即一条路径的权

11、由这条路径上每条边的权相加得到，求解目标往往是求图中条路径上每条边的权相加得到，求解目标往往是求图中或是两点之间所有路径的权的最优值。或是两点之间所有路径的权的最优值。以上这些差异形成了图论模型的多样化，使图论模型可以广泛地适应各类问题，但这些丰富的选择同时也增加了图论建模的难度。权的运算也会产生一些变形，例如权的运算由简权的运算也会产生一些变形，例如权的运算由简单的相加、求最值扩展到相乘，或是更复杂的函数计单的相加、求最值扩展到相乘，或是更复杂的函数计算等等。算等等。【例3】机器人布阵机器人布阵有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地

12、上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。墙 Wall草地 Grass 空地 Empty【模型一】在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：问题的求解目标是寻求图G的最大独立集，即求G的独立数(G)。一般图的(G)是很难计算的，除非对于一些特殊的图。如完全图K Kn的独立数为n,二分完全图Km,n的独立数为maxm,n。显然这一模型不是属于一些特殊的图，给我们设

13、计算法带来很大的麻烦。【模型二】我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把水平方向的这些块编上号；同样，把竖直方向的块也编上号。123451234水平方向的块编号竖直方向的块编号把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二分图的最大匹配问题。比较前面的两个模型：模型一过于简单，比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充没有给问题的求解带来任何便利；模

14、型二则充分抓住了问题的内在联系，巧妙地建立了二分分抓住了问题的内在联系，巧妙地建立了二分图模型。为什么会产生这种截然不同的结果呢图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中选取不充分，模型二则保留了原型中“棋盘棋盘”这个重要的性质。由此可见，要素的选取，分这个重要的性质。由此可见，要素的选取，分析角度的不同影响了理论体系的选择。这

15、两点析角度的不同影响了理论体系的选择。这两点都是图论建模至关重要的步骤。都是图论建模至关重要的步骤。【例【例4 4】奇怪的数列】奇怪的数列 编编程程输输入入3 3个个整整数数n n，p p，q q，寻寻找找一一个个由由整整数数组组成成的的数数列列（a a1 1，a a2 2，a an n），要要求求：其其中中任任意意连连续续p p项项之之和和为为正正数数，任任意意连连续续q q项项之之和和为为负负数数。00n100n100，0p0p，qnqn，若若不不存存在在这这样样的的整整数数数数列列，则则输输出出NONO；否否则则输输出出满满足足条条件件的的一一个数列即可。个数列即可。【输入格式】【输入格

16、式】输输入入文文件件名名为为num.innum.in，仅仅一一行行分分别别表表示示n n，p p，q q，之之间间用用一个空格隔开。一个空格隔开。【输出格式】【输出格式】输输出出文文件件名名为为num.outnum.out，只只有有一一行行，有有解解即即输输出出这这个个数数列列，每个数之间用一个空格隔开。否则输出每个数之间用一个空格隔开。否则输出NONO。【奇怪的数列奇怪的数列分析】从从形形式式上上看看，这这道道题题与与图图论论风风马马牛牛不不相相干干，题题中中既既未未出出现现图图论论中中常常见见的的“车车站站”，“城城市市”等等顶顶点点，也也未未出出现现“公公路路”，“铁铁路路”等等边边，更

17、更未未出出现现“长长度度”，“传传输输时时间间”等等权权。仅仅以以数数学学角角度度考考虑虑，按按常常规规思思想想来来分分析析如如何何表表示示“连连续续几几项项之之和和”这这一一要要点点，直直接接将将第第i i个个整整数数a ai i开开始始的的k k个个整整数数之之和和描描述述成成多多项项式式a ai i+a ai i+1+1+a ai i+k-1+k-1的的话话，问问题题就就很很难难再再往往下下思思考考和和解解决决了了。所所以以，我我们们不不防防换换个个角角度度，暂暂且且撇撇去去每每一一项项数数究究竟竟为为何何值值的的具具体体细细节节，而而将将注注意意力力集集中中至至连连续续性性这这一一特特

18、点点上上。设设s si i表表示示数数列列前前i i个个整整数数之之和和，即即s si i=a=a1 1+a+a2 2+a ai i。其中其中s s0 0=0(0in)=0(0in)。显然根据题意，有：显然根据题意，有：s si i s si i+p+p (0in-p)(0in-p)s si i+q+q s sj j(0i(0i，jn)jn)，则则从从s si i往往s sj j引引出出一一条条有有向向边边。例例如如对对于于n=6n=6，p=5p=5，q=3q=3的的情情况况，我我们可以建立图们可以建立图4 4S1S0S4S2S6S5S3图4【奇怪的数列奇怪的数列分析】构造这样的有向图很简单，

19、过程如下：构造这样的有向图很简单，过程如下：fillcharfillchar(g(g，sizeofsizeof(g)(g)，0)0)；有向图的邻接矩阵初始化有向图的邻接矩阵初始化 fillcharfillchar(d(d，sizeofsizeof(d)(d)，0)0)；各顶点的入度序列初始化各顶点的入度序列初始化 for ifor i：=0 to n do =0 to n do 根据两组不等式构造有向图根据两组不等式构造有向图 begin begin if i+p=n then begin if i+p=n then begin gi+p gi+p，i=1i=1；di=di+1 di=di+1

20、；end end；if i+q=n then begin if i+q=n then begin gi gi，i+q=1i+q=1；di+q=di+q+1 di+q=di+q+1；end end；end end；【奇怪的数列奇怪的数列分析】显然，按照上面的定义，如果建立的图可以拓扑排序，其显然，按照上面的定义，如果建立的图可以拓扑排序，其顶点的拓扑序列可以对应满足条件的整数数列；反之，不顶点的拓扑序列可以对应满足条件的整数数列；反之，不存在这样的整数数列。存在这样的整数数列。算法框架为：算法框架为：对图进行拓扑排序；对图进行拓扑排序；if if 图有回路图有回路 then then 无解退出无

21、解退出 else else 生成拓扑序列生成拓扑序列 order0ordernorder0ordern；如果得到了一个拓扑序列，该如何转换成如果得到了一个拓扑序列，该如何转换成s s数组呢？因为拓数组呢？因为拓扑序列中顶点对应的扑序列中顶点对应的s s值是递减的，其中值是递减的，其中s s0 0=0=0。如果如果orderi=0orderi=0，则依次设定则依次设定s sorderorder00=i=i，s sorderorder11=i-1=i-1，s sorderorderi-1i-1=1=1，s sorderorderii=0=0，s sorderorderi+1i+1=-1=-1，s

22、sorderordernn=i-n=i-n。例如，对于图例如，对于图4 4所示的有向图，可以得到表所示的有向图，可以得到表1 1：【奇怪的数列奇怪的数列分析】i0123456orderi2503614sorderi210-1-2-3-4所所以以，得得到到s s0 0=0=0，s s1 1=-3=-3，s s2 2=2=2，s s3 3=-1=-1，s s4 4=-4=-4，s s5 5=1=1，s s6 6=-2=-2。再再根根据据s s的的定定义义，由由：a ai i=(a=(a0 0+a+a1 1+a ai i-1-1+a ai i)-(a(a0 0+a+a1 1+a ai i-1-1)=

23、)=s si i-s si i-1-1 ，求求出出：a a1 1=s=s1 1-s-s0 0=-3=-3，a a2 2=s=s2 2-s-s1 1=5=5，a a3 3=s=s3 3-s-s2 2=-3=-3，a a4 4=s=s4 4-s-s3 3=-3=-3，a a5 5=s=s5 5-s-s4 4=5=5，a a6 6=s=s6 6-s-s5 5=-3=-3。显显然然这这个个整整数数数数列列的的任任意意连连续续5 5个个整整数数之之和和为为正正，任任意意连续连续3 3个整数之和为负。由拓扑序列构造整数数列的算法如下：个整数之和为负。由拓扑序列构造整数数列的算法如下：fillcharfil

24、lchar(s(s，sizeofsizeof(s)(s)，0)0)；for i for i：=0 to n do=0 to n do if if orderi0 orderi0 then then for for j j：=i i downtodownto 0 0 do do sorderjsorderj+1sorderjsorderj+1 else break else break；for j for j：=i+1 to n do sorderji-j=i+1 to n do sorderji-j；for ifor i：=1 to n do aisi-si-1=1 to n do aisi-

25、si-1；通通过过以以上上分分析析可可知知，本本题题的的关关键键还还在在于于建建模模：把把s si i作作为为顶顶点点，s s的的大大小小关关系系作作为为边边，并并按按照照其其递递减减顺顺序序设设定定边边的的权权值值，应应用用拓拓扑扑排排序序这这一一经经典典算算法法很很完完美美地地解解决决了了该该题题，这这种种创创造造性性的的构构思思在在解解题题过过程程中中起起了了关关键键性性的的作作用。用。三三.模型的优化模型的优化 建立图论模型是为了解决问题，但有时往往建立图论模型是为了解决问题，但有时往往会遇到这样的情况：在建立起一个模型之后，却会遇到这样的情况：在建立起一个模型之后，却不知该如何分析、

26、求解，或是发现建立起的模型不知该如何分析、求解，或是发现建立起的模型无法表现原型的某些重要的性质等等。图论模型无法表现原型的某些重要的性质等等。图论模型建立的过程，是一个不断完善的过程，在建模过建立的过程，是一个不断完善的过程，在建模过程中，结合对问题更深层次的分析，结合算法设程中，结合对问题更深层次的分析，结合算法设计，实现模型的优化。计，实现模型的优化。【例【例5】障碍物探测车】障碍物探测车 有一个登陆舱（POD）,里边装有许多障碍物探测车（MEV），将在火星表面登陆。着陆后，探测车离开登陆舱向相距不远的先期达到的传送器(Transmitter)移动。MEV一边移动，一边采集岩石（Rock

27、）标本，岩石由第一个访问到它的 MEV采集，每块岩石只能被采集一次。但是这之后，.问题可简述为：在问题可简述为：在P P Q Q的矩形中，每个格子的地形可的矩形中，每个格子的地形可能是下列三种之一：能是下列三种之一：（1 1）障碍：无法通过；）障碍：无法通过；（2 2）平地：平坦无物，可通过；）平地：平坦无物，可通过；（3 3）石块：可通过，第一次通过时可采到一块岩石；）石块：可通过，第一次通过时可采到一块岩石；求求M M条的路径（条的路径（M M给定），使得路径能够覆盖到石块数给定），使得路径能够覆盖到石块数总和最大，路径要满足的条件是：总和最大，路径要满足的条件是：（1 1）每条路径都是从

28、）每条路径都是从(1,1)(1,1)到到(P,Q)P,Q)，途中每步只能向途中每步只能向东或向南走一格；东或向南走一格；（2 2）路径不通过障碍。）路径不通过障碍。样例输入图示。（探测车数样例输入图示。（探测车数M=2）样例输出图示：样例输出图示：(覆盖到石块数为覆盖到石块数为3)【障碍物探测车分析】【障碍物探测车分析】1 1本题的难点就在于多辆探测车之间的配合问题，本题的难点就在于多辆探测车之间的配合问题，而对于只有一辆探测车的退化情况，应用动态规划而对于只有一辆探测车的退化情况，应用动态规划可得到最优解可得到最优解:用二维数组用二维数组map1.p,1.q 0f 0.2map1.p,1.q

29、 0f 0.2表示火星表示火星表面情况：表面情况：mapi,j=0mapi,j=0表示位置（表示位置（i,ji,j）为平地；为平地；mapi,j=1mapi,j=1表示位置（表示位置（i,ji,j）为障碍；为障碍；mapi,j=2mapi,j=2表示位置（表示位置（i,ji,j）为岩石。为岩石。设设Si,jSi,j表示探测车从（表示探测车从（1 1，1 1）位置移动到（）位置移动到（i,ji,j）位置所能够采集到的岩石标本数目的最大值。则有位置所能够采集到的岩石标本数目的最大值。则有动态规划方程如下：动态规划方程如下：Si,j=Maxsi-1,j,si.j-1,mapi,j=0;0,mapi,

30、j=1;(1ip,1jq)Maxsi-1,j,si.j-1+1;mapi,j=2;边界条件：边界条件：si,0=0,s0,j=0 (1ip,1jq)2.当当m2时，对时，对 m辆探测车各使用一次上述的动态规辆探测车各使用一次上述的动态规划算法，就可以得到一个较优解。由于这种简单的贪划算法，就可以得到一个较优解。由于这种简单的贪心没有顾及到各探测车之间的配合，所以不能保证得心没有顾及到各探测车之间的配合，所以不能保证得到最优解，如下面的例子：到最优解，如下面的例子：以上两个算法都是基于一般意义 的图GV,E这一模型上考虑的，如果将一辆探测车的运动看作一条流，因为探测车的数目一定，所以总的流量是确

31、定的。而解的优劣，即采集的标本数量的多少，就只能体现在单位流量的“费用”上了。因此选择使用最小费用最大流的方法求解。3.3.网络流模型网络流模型将图将图G扩充为一个可以求解的网络模型：扩充为一个可以求解的网络模型：（1）在建图时，可以略去所有障碍物位置，以及与）在建图时，可以略去所有障碍物位置，以及与(1,1)、(p,q)不连通的位置，也可看作障碍物（探测车不会经过）不连通的位置，也可看作障碍物（探测车不会经过）。其余的位置（平地和岩石）都作为图。其余的位置（平地和岩石）都作为图G的顶点。的顶点。顶点集顶点集V=Vi,j1ip,1jq,mapi,j1；有向边集有向边集E=vi,j,vi+1,j

32、vi,jV,vi+1,jV vi,j,vi,j+1vi,jV,vi,j+1V。（2 2）根据题意再把图）根据题意再把图G G扩充为扩充为 网络网络N=N=V,E,C,RV,E,C,R,C,C代表代表网络中各边的容量，网络中各边的容量，R R代表各边上单位流量的代表各边上单位流量的费用。由于探测车的移费用。由于探测车的移动路线可以任意重叠，动路线可以任意重叠，所以这些边的容量所以这些边的容量C=C=，费用费用R=2R=2。（3）如何体现“采集岩石标本”的特征，对于岩石顶点，先到的探测车采到标本，对后到的探测车来说就是平地，一个顶点怎样来扮演两种不同的角色？我们把岩石顶点Vi,j分出一个顶点VI,

33、j,并增加 3条边：1)边Vij,Vij，容量C(Vij,Vij)=1,表示标本只能采集一次，费用R(Vij,Vij,)=0;2)边Vij,Vij+1和边Vij,Vi+1j，容量都是1，费用都是1。这样，每采集一块岩石，对应的流的代价就会减少1；同时，受容量的限制，每块岩石也最多被采集一次。（4 4）最后再为网络添加源点和汇点：因为）最后再为网络添加源点和汇点：因为m m辆探测车都从辆探测车都从（1 1，1 1）出发，所以源点）出发，所以源点s s只引出一条边只引出一条边s,V1,1s,V1,1,容量容量为为,费用为费用为0 0；类似，如果；类似，如果mapp,q=0,mapp,q=0,即（即

34、（p,qp,q）处是平处是平地，则汇点地，则汇点t t也只引入一条边也只引入一条边Vp,q,tVp,q,t,容量为容量为，费用，费用为为0 0；如果；如果mapp,q=2,mapp,q=2,即该处是岩石，则多引一条边即该处是岩石，则多引一条边Vp,q,tVp,q,t,容量为容量为1 1，费用也为，费用也为1 1。这样就完成了使用最小费用最大流算法的建模。这样就完成了使用最小费用最大流算法的建模。四四.结束语结束语 以上分析了图论模型建立中的两个要点和图论模型优以上分析了图论模型建立中的两个要点和图论模型优化的方法。在实际的建模过程中，它们是密不可分的：化的方法。在实际的建模过程中，它们是密不可

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

36、这时，即使建立的模型再怎么巧妙、坏原型的关键性质，这时，即使建立的模型再怎么巧妙、经典，也是经不住考验的。经典，也是经不住考验的。图论算法和理论十分独特精妙，图论模型的建立和图论算法和理论十分独特精妙，图论模型的建立和优化十分灵活。因此，对图论模型的研究并非一朝一夕优化十分灵活。因此，对图论模型的研究并非一朝一夕的事，需要持之以恒。的事，需要持之以恒。独立集概念在图G中，选其中的一些顶点构成一个集合U，如果集合U中任意两个顶点在G中不相邻，称U是图G的一个独立集。对于独立集 U,任意再增加一个顶点就破坏它的独立性，则称这独立集为G的一个极大独立集。极大独立集不是唯一的，而且连顶点数都不尽相同。顶点数最多的极大独立集，称其为最大独立集。（下图有两个独立集且都是极大独立集）墙 Wall草地 Grass 空地 Empty