数学建模图论算法总结

第十二章 图论在数学建模中的应用

图论是数学的一个既有古老的历史渊源而又十分年轻的分支，是一门生气勃勃、

广大前途的学科。它既很强的理论性，与数学的一些分支如数论、几何学及运筹学等都有密切联系，又有广泛的应用价值，图论在化学、统计学、生物学、信息论、计算机科学中都有很强的实际应用背景，并且饶有趣味，引人入胜。图论方法是建立数学模型的重要方法之一。利用图论知识，通过建立图论模型，解决实际问题是学习图论课程的重要目的之一。本章我们通过大量的实例，系统介绍如何利用图论知识建立数学模型，解决实际问题的基本方法和技巧，培养分析问题、解决问题的能力。

12.1图论在数学建模中的一些简单应用

本节将通过对在社会生产活动中有很强实际应用背景的一些简单实例的分析，展示如何利用图论知识，通过数学建模方法将实际问题转化为图论问题加以解决的基本方法和技巧。

例1.相识问题

1958年美国《数学月刊》发表了一个数学问题：在6人的集会上，总能找到或者3个人互相都认识，或者3个人谁也不认识谁，假定认识是相互的。 这个表面看来似乎无法下手的问题，可以通过图论法轻易获得解决。 分析与建模：用6个点（记为u1,u2,?,u6）表示6个人，若两个人互相认识，就在相应的两个点之间

----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- 建模十大算法总结：

1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。

2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。

3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。

4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。

6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有

建模十大算法总结：

1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。

2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab 作为工具。

3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo 、Lingo 、MATLAB 软件实现。

4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。

6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。

7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

1/25

图论中的常用经典算法

第一节 最小生成树算法

一、生成树的概念

若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。

对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。

由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。如下图：

但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

二、求图的最小生成树算法

严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成

线性优化问题

min?fTx,?A*x?b,, ?s.t?Aeq*x?beq,?lb?x?ub.?其中c,x,b,beq,lb,ub位列向量；c称为价值向量；b称为资源向量；A,Aeq为矩阵。 Matlab中求解线性规划的命令为 [x,fval]=linprog(f,A,b)

[x,fval]=linprog(f,A,b,Aeq,Abq)

[x,fval]=linprog(f,A,b,Aeq,Abq,lb,ub)

中，x返回的是决策向量的取值；fval返回的是目标函数的最优值；f为价值向量；A和b对应的是线性不等式约束；Aeq和beq对应的是线性等式约束；lb和ub对应的是决策向量的下界向量和上界向量。 例1.2 求解下列线性规划问题

maxz?2x1?3x2?5x3

?x1?x2?x3?7?2x?5x?x?10?123 s..t??x1?3x2?x3?12??x1,x2,x3?0解：（1）化为Matlab标准型

minw??2x1?3x2?5x3

?x1???2,5,?1?????10?s.t???x2???12? 1,3,1???????x3?(2)求解Matlab程序如下： f=[-2;-3;5];

a=[-2,5,-1;1,3,1]

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

1/25

图论中的常用经典算法

第一节 最小生成树算法

一、生成树的概念

若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。

对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。

由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。如下图：

但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

二、求图的最小生成树算法

严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成

图论方法建模1 2 3 4 军用物资的运送 图的基本概念 简易公路建设方案 前线弹药供应

1 欧拉七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)有一条 名叫普莱格尔(Pregel)的河流横经其中，河上有7 座桥，将河中的两个岛和河岸连结。北岸

中心岛

东区

城中的居民经常沿 河过桥散步，于是 提出了一个问题： 能否一次走遍7座 桥，而每座桥只许 通过一次，最后仍 回到起始地点?

南岸

1736年欧拉把这个问题的物理背景变换并简化为一种 数学设计(称作图):即把每一块陆地用一个点来代 替，将每一座桥用连接相应的两个点的一条线来代替， 从而相当于得到一个图。欧拉证明了这个问题没有解， 并指出欧几里得几何并不适用于这个问题，因为桥不 涉及“大小”,也不能用“量化计算”来解决。

1 军用物资的运送孙子曰：“善用兵者，役不在籍，粮不三载，取用于 国，因粮于敌，故军食可足也。”

游击队之歌我们都是神枪手，每一颗子弹消灭一个敌人， 我们都是飞行军，哪怕那山高水又深。 在密密的树林里，到处都安排同志们的宿营地， 在高高的山岗上，有我们无数的好兄弟。 没有吃，没有穿，自有那敌人送上前， 没有枪，没有炮，敌人给我们造。 我们生长在这里，每一寸土地都是我们自己的， 无论谁要强

建模十大经典算法

1、蒙特卡罗算法。

该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。

2、数据拟合、参数估计、插值等数据处理算法。

比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。

3、线性规划、整数规划、多元规划、二次规划等规划类问题。

建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。 4、图论算法。

这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。

这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7、网格算法和穷举法。

网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴