图论建模案例

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

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

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

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

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

例1.相识问题

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

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

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

中心岛

东区

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

南岸

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

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

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

图论

内容提要

第一章 图的基本概念

图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。

第二章 图的连通性

割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。

第三章 匹配问题

匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。

第四章 欧拉图与哈密尔顿图

欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。

第五章 支配集、独立集、覆盖集与团

支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。

第六章 图的着色问题

点着色；边着色；平面图；四色猜想；色多项式；色数的应用。

第七章 网络流理论

有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。

主要参考书

[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [

一、选择题（每小题2分，共50分）

1、设D??V,E?为有向图，则有（ A ）

(A) E?V?V (B) E?V?V (C)V?V?E (D) V?V?E

2、设G??V,E?为无环的无向图，V＝6，E?16，则G 是（D ）

(A) 完全图 (B) 零图 (C) 简单图 (D) 多重图

3、含有5个结点，3条边的不同构的简单图有（ C ）

(A) 2个 (B) 3个 (C) 4个 (D) 5个

4、设图G有n个结点，m条边，且G中每个结点的度数不是k就是k?1，则G中度为k的结点的个数是（ D ）

(A) n/2个 (B) n(n?1)个 (C)nk个 (D) n(k?1)?2m个

5、给定下列序列，哪一个可以构成无向简单图的结点度数序列（ B ）

(A) (1,1,2,2,3)

图 论

第一节 图的基本概念

引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A？

结论：1736年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在后面的应用中，我们将专门讨论这个问题。 定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy属于V。

分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时与是不同的，如的起点为VX，终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。

相邻：若两个结点U、V之间有一条边连接，则称这两个结

一、图论的基础概念

以下概念不是定义，也不一定完全，只是一些常用的概念，比较通俗化。在以后具体的算法中再适当加入概念。

图： 由点和线组成的图形。 顶点： 图中的结点。

无向图： 边没有正反方向。

完全图： 在N个顶点的无向图中，边最大为n*（n-1）/2称为无向完全图 度： 与结点相连的边数。 有向图： 边有正反方向。

入度（出度）：连入（出）的边数。（对于有向图来说） 奇顶点：结点的度是奇数的点。

路径：如果从a到b可达（包括直接到达或者中间有其他结点）那么从a到b就有一条路径。一条路径就

是一种走法，路径的边数叫做路径长度。一条路径上的n个顶点的集合叫做连通集。

回路（环）：从a?b????a

简单路径：存在从a?b???e此条路径中每个结点不同。

有根图：有结点到其他任意结点连通，则此结点为根，一个图可以有多根。 连通图：若图中任意两个结点可以连通，则此图为连通图（无向图）。 强连通图：任意i到j都有从i到j的路径。（有向图） 强连通分支：强连通的最大子图。

道路：可以一笔画成的图，并且不重不漏。

*充分必要条件：图是连通的，且奇顶点的个数等于0或2

并且当且仅当

图论实验三个案例

单源最短路径问题 1.1 Dijkstra算法

Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。设v是图中的一个顶点，记l(v)为顶点

v到源点v1的最短距离，

Dijkstra算法：

?vi,vj?V，若

(vi,vj)?E，记vi到

vj的权

wij??。

① S?{v1},l(v1)?0；?v?V?{v1},l(v)??,i?1,S?V?{v1}； ② S??，停止，否则转③；

③

l(v)?min{l(v),d(vj,v)}，

vj?S，?v?S；

④ 存在vi?1，使l(vi?1)?min{l(v)}，v?S； ⑤ S?S?{vi?1}，S?S?{vi?1}，i?i?1，转②；

实际上，Dijkstra算法也是最优化原理的应用：如果v1v2?vn?1vn是从v1到vn的最短路径，则v1v2?vn?1也必然是从v1到vn?1的最优路径。

在下面的MATLAB实现代码中，我们用到了距离矩阵，矩阵第i行第j行元素表示顶点vi到

vj的权

wij，若vi到

vj无边，则

wij?realmax，其中realmax

工厂生产计划安排

摘要

某工厂生产两种产品,现希望做出合理的安排使得获利最大。考虑的两种产品有不同工作时间，不同的利润，以及不同的加班时间，现为了充分的利用资源，使利益最大化，这里采用目标规划模型。通过lingo编程求解，以安排最合理的计划。

关键词 目标规划模型 最优化 加班时间

一、问题重述

某工厂生产两种产品,每件产品I可获利10元，每件产品II可获利8元。每生产一件产品I，需要3小时；每生产一件产品II，需要2.5小时。每周总的有效时间为120小时。若加班生产，则每件产品I的利润降低1.5元；每件产品II的利润降低1元。现希望在允许的工作及加班时间内取最大利润，要合理的安排生产计划。

二、模型假设

（1）一周内没有断电等意外事故发生；

（2）工厂的工作时间严格按照《劳动法》[1]执行。

三、符号说明

符号 意义 i?1,2,3,4分别表示生产产品1不加班用时，xi 生产产品2不加班用时，生产产品1加班用时，生产产品2加班用时 计划最大利润 z 四、模型分析

五、模型的建立与求解

5.1、模型准备

参考《劳动法》得知：工厂每天工作时间不超过8小时，每周工作时间不超过44小时。现在由于该工厂每周工作有效时间为120小时，

1

基于层次分析法的护岸框架最优方案选择

【摘要】长期以来，四面六边透水框架在河道整治等工程中，因其取材方便、自身稳定性、透水性、阻水性好、适合地形变化等特性优点而被广泛的应用。但是，在抛投和使用过程中，存在被水流冲击而翻滚移位、结构强度的不足、难以合理互相钩连的问题，使框架群不能达到理想的堆砌效果。本文主要探讨如何合理设计改进现有护岸框架，以最大程度减少框架群被水流冲击翻滚移位的情况，增加框架群在使用过程中互相钩连程度和结构强度，达到减速促淤效果。

针对问题，我们结合四面六边透水框架本身的优势特性，在原有框架的基础上进行改进设计，根据三角形稳定性的特性，通过应用机理分析，进行物理图形构造，设计出三种供选方案。

模型一：构建四面六边带触脚框架模型（图5.2），该模型在四面六边透水框架的基础上，运用触脚设计，较好的融合增强四面六边透水框架本身的优点特性，使框架达到不易翻滚，并与其他的框架自然地相互钩连。

模型二：构建六面九边带触脚框架模型（图5.6），该模型是对模型一的改进，综合模型一和原型模型的结构，不仅具备良好的亲水性、阻水性和稳定性，而且触脚比模型一更多，使框架更加稳定，不易翻滚、框架群之间也更容易钩连；同时，模型二施工简单，更容易构造

最佳捕鱼方案

? 会。

2012年 数学建模联赛

承 诺 书

我们仔细阅读了 数学建模联赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为： 参赛队员 (打印并签名) ：1. 2. 3.