图论与网络流

图论与网络应用1.2.3.B题灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。1998年全国大学生数学建模竞赛题目4.

假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳灾情巡视路线的影响。5.

6.2001建模竞赛题目（大专组）C题基金使用计划某校基金会有一笔数额为M元的基金，打算将其存入银行或购买国库券。当前银行存款及各期国库券的利率见下表。假设国库券每年至少发行一次，发行时间不定。取款政策参考银行的现行政策。校基金会计划在n年内每年用部分本息奖励优秀师生，要求每年的奖金额大致相同，且在n年末仍保留原基金数额。校基金会希望获得最佳的基金使用计划，以提高每年的奖金额。7.

请你帮助校基金会在如下情况下设计基金使用方案，并对M=5000万元，n=10年给出具体结果：

1.只存款不购国库券；

2.可存款也可购国库券；

3.学校在基金到位后的第3年要举行百年校庆，基金会希望这一年的奖金比其它年度多20%。8.银行存款税后年利率（%）国库券年利率（%）活期0.792半年期1.664一年期1.800二年期1.9442.55三年期2.1602.89五年期2.3043.149.2000“网易杯”全国大学生数学建模竞赛试题B题

钢管订购和运输

要铺设一条的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。10.一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1单位钢管的铁路运价如下表：

11.1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。12.13.2008年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（MiniSupermarket,以下记做MS）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种MS，在地点、大小类型和总量方面有三个基本要求：满足奥运会期间的购物需求、分布基本均衡和商业上赢利。2004年A题奥运会临时超市网点设计14.鸟巢国家体育馆水立方15.16.请你按以下步骤对图2的20个商区设计MS网点：1）根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面所反映的规律。2）假定奥运会期间（指某一天）每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。依据1的结果，测算图2中20个商区的人流量分布（用百分比表示）。3）如果有两种大小不同规模的MS类型供选择，给出图220个商区内MS网点的设计方案（即每个商区内不同类型MS的个数），以满足上述三个基本要求。4）阐明你的方法的科学性，并说明你的结果是贴近实际的。17.例1最短路问题（SPP－shortestpathproblem）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？例2公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。18.例3指派问题（assignmentproblem）

一家公司经理准备安排n名员工去完成n项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例4中国邮递员问题（CPP－chinesepostmanproblem）

一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？

由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

（匹配问题）19.例5旅行商问题（TSP－travelingsalesmanproblem）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商(推销员）问题。例6运输问题（transportationproblem）

某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂。假定M个产地的产量和N家工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？20.

上述问题有两个共同的特点：

一，其目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；

二，都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。

与图和网络相关的最优化问题就是网络最优化或称网络优化（networkoptimization）问题。

由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（networkflows）或网络流规划等。21.

故事的背景是十八世纪的东普鲁士，美丽的Pregel河穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七座桥，将它们连结成一个风景优美的公园。有一天，有人突发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，最后又回到原先的出发点？

22.例1

七桥问题

18世纪东普鲁士哥尼斯堡被普列格尔河分为四块，它们通过七座桥相互连接起来，问能否从某块陆地出发，经每座桥一次而且仅一次，回到出发点？ACBDABCD

任何一个点作为出发点都必须先“出”后“回”，才能行遍与该点相连的桥。行遍性问题23.对此问题，欧拉给出了一个通用判定规则：

从图的某一个顶点出发，经过每条线正好一次，最后回到原来的顶点，当且仅当这个图连成一片且每个顶点都有偶数条线和它连接。思考：能否将图的每一条线走遍，但只走一次。（不必回到原顶点）

从图的某一个顶点出发，经过每条线正好一次，当且仅当这个图连成一片且最多只有两个顶点是奇次的，且必须从某奇次点出发，到另一奇次点结束。ABCD24.

以下网络中哪一个是可以遍历的(即一笔而不重复地画成)？

25.26.一笔画问题

欧拉注意到：一个奇顶点在这种遍历式的旅行中，要么是起点，要么是终点．由于一个遍历的网络只能有一个起点和一个终点，因而这种网络的奇点数不能多于两个．27.例2

人、狼、羊、菜渡河问题一个摆渡人F希望用一条小船把一只狼W、一头羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，决不能在无人看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎样渡河才能将狼、羊、白菜都运过去？

用小圆圈（顶点）表示河岸左边的各个状态，两点连线当且仅当两状态可在规定允许下转移。FWGCFWGFWCFGCFGWCWGC00FWGCWCFWCCWFGCFWGGFG28.

一个人带三只狼和三只羊过河，一条船可容两只动物，没人在时，如果狼的数量不少于羊的数量就会吃掉羊，如何安全渡河?29.

有一天，一家人（爸爸、妈妈、2个女儿、2个儿子）和警察、小偷，想过河，船上只能装两个人，爸爸、妈妈、警察三人会划船，在过河的时候，爸爸不在的时候，妈妈会打儿子，妈妈不在的时候，爸爸会打女儿。警察不在的时候，小偷会打一家人。怎样才能使他们安全的过河？？？30.例3

化学药品存放问题某公司生产几种化学药品a,b,c,d,e,f,g，其中某些化学药品不相容，为安全，公司要把相容的药品放在不同格中，问至少应将仓库划分为多少格？

我们可以用顶点表示各个化学药品，两顶点连线当且仅当两药品不相容，便可得一个图G:adcbefg图G的点色数便是所求的最少格数为每个顶点赋一色，使凡有连线的两顶点异色，点色数即是使图得到正常点上色的最少色数。→图的正常点上色31.

地图着色问题（四色问题）：

任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。

111223344

用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”32.33.

世界近代三大数学难题：1.费尔马大定理（1637年）

在阅读丢番图《算术》拉丁文译本时，曾在第11卷第8命题旁写道：将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。

关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下。

经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁•怀尔斯和他的学生理查•泰勒于1995年成功证明。34.3.哥德巴赫猜想（1742年6月7日，德国数学家在写给著名数学家欧拉的一封信中提出）：2.四色问题1）任何不小于6的偶数，都是两个奇质数之和；

2）任何不小于9的奇数，都是三个奇质数之和。

世界近代三大数学难题：

任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。

35.路线着色问题

一个人来到他从未造访过的小镇上，驾着车到处寻找他朋友的家，即使连路名都没有。朋友说，别担心，他会指示他如何到达，先向左，再向右，接着向左……”

这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。以图为范本，如果按照"蓝—红—红,蓝—红—红,蓝—红—红..."的方式行走，不管从哪个点出发都能到黄色的点；如果是"蓝—蓝—红,蓝—蓝—红,蓝—蓝—红..."则一定能到绿点…（万能地图）36.图：是指某类具体事物和这些事物之间的联系

如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。

图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。

最短路问题、行遍性问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。37.38.例1线性方程组的解取决于：系数常数项复习：

★矩阵对线性方程组的研究可转化为对这张表的研究.线性方程组的系数与常数项按原位置可排为39.例2对随机抽取的1000人按性别（男或女）及色觉（正常或色盲）两个属性分类，得到二行二列的列联表:40.行列

由个数排成的行列的数表定义：称为行列矩阵.简称矩阵.简记为这个数称为的元素，简称为元.41.★几种特殊矩阵1.方阵(SquareMatrix):例如：是一个3阶方阵.行数与列数都等于的矩阵，也可记作注意2、矩阵的行数和列数可以不等1、矩阵是一张数表42.2.行矩阵(RowMatrix)(或行向量)

:3.列矩阵(ColumnMatrix)

(或列向量):只有一行的矩阵只有一列的矩阵43.形如的方阵,4.对角矩阵

(DiagonalMatrix):记作元素不全为0主对角线5.单位矩阵(IdentityMatrix):主对角线上元素全为1,其他元素都是0的方阵44.6.零矩阵(ZeroMatrix):注意不同阶数的零矩阵是不相等的.例如：

元素全为零的矩阵称为零矩阵，零矩阵记作或.?45.★矩阵的基本运算1.矩阵相等矩阵相等:例同型矩阵：两个矩阵的行数相等、列数也相等46.设有两个矩阵那么矩阵与的和记作，规定为2.矩阵的加减法加法：47.例说明

只有当两个矩阵是同型矩阵时，才能进行加法运算.48.减法:负矩阵：49.矩阵加法满足的运算规律:50.3.数与矩阵相乘数乘:51.数乘矩阵的运算规律：（设为矩阵，为数）矩阵相加与数乘矩阵合起来,统称为矩阵的线性运算.52.并把此乘积记作设是一个矩阵，是一个矩阵，那么规定矩阵与矩阵的乘积是一个矩阵，其中4、矩阵与矩阵相乘53.设例解求54.注意只有当第一个矩阵的列数等于第二个矩阵的行数时，两个矩阵才能相乘.例如不存在.55.矩阵乘法的运算规律（其中为数）;

若A是阶矩阵，则为A的次幂，即并且满足结合律、分配率56.矩阵不满足交换律例设则

（并非所有的矩阵都不满足交换律）矩阵是否满足交换律？57.矩阵乘法不满足消去律矩阵乘法是否满足消去律？例：有但是58.★输入矩阵的方法(1)用中括号[]把所有矩阵元素括起来；(2)同一行的不同元素之间用空格或逗号间隔；(3)用分号(;)指定一行结束；(4)也可以分成几行进行输入，用回车符代替分号；(5)数据元素可以是表达式，系统将自动计算结果；59.例：输入矩阵matlab输入格式：ans=-39-1137ans=360.61.★特殊矩阵函数函数描述举例[]空矩阵A(:,2)=[]%删除矩阵A的第2列eye单位矩阵A=eye(3)ones元素全部为1的矩阵A=ones(2,3)%A为2×3元素全为1的矩阵zeros元素全部为0的矩阵A=zeros(2,3)%A为2×3元素全为0的矩阵rand元素值为0到1之间均匀分布的随机矩阵A=rand(3)62.函数描述举例randn元素值服从均值为0方差为1的正态分布的随机矩阵A=randn(4)triu求给定矩阵的上三角阵B=triu(A)tril求给定矩阵的下三角阵B=tril(A)63.矩阵的基本运算运算功能命令形式矩阵加法和减法将两个同型矩阵相加(减)A±B

数乘将数与矩阵做乘法k*A

k是一个数,A是一个矩阵矩阵乘法将两个矩阵进行矩阵相乘A*B

A的列数与B的行数相等矩阵的左除计算A\B

A必须为方阵矩阵的右除计算A/B

B必须为方阵求矩阵行列式计算方阵的行列式det(A)

A必须为方阵64.矩阵的基本运算运算功能命令形式求矩阵的逆求方阵的逆Inv(A)或

矩阵乘幂计算AnAˆnA必须为方阵,n是正整数矩阵的转置求矩阵的转置Transpose(A)或A´

矩阵求秩求矩阵的秩rank(A)

矩阵行变换化简求A阶梯形的行最简形式rref(A)

65.66.

一、图与网络的基本概念

是由一个非空有限集合和中某些元素的无序对集合构成的二元组，记为。顶点集或节点集边集Vertex，edge67.完备图若表示集合中的元素个数），中无相邻顶点对，中亦然，则称为二分图；特别地，若则，则称为完全二分图，记成。68.

简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。图中(a),(b)为二分图，(c)为完全二分图K3,369.70.树71.最小生成树：72.73.

二、图与网络的数据结构74.75.76.（每边有两个顶点与其相关联）77.78.79.15346780.三、最短距离问题

在生产管理、交通运输和通讯领域，经常会碰到这样的问题：沿着哪条路线可以最短的时间或最少的费用把货物运往目的地？沿着哪条路线传送信息最可靠或最快捷？如何组织生产可使生产成本最低？如何制定投资计划可使利润最大？这些都可看成是在给定的加权图中，求最短路径问题。81.82.83.邻接矩阵84.85.86.87.88.89.90.91.92.93.

2v1v3v4v5v657080502031003094.95.96.97.

2v1v3v4v5v657080502031003098.例某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。99.行遍性问题100.一、中国邮递员问题二、推销员问题（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题101.e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1102.e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图

推论1设G是非平凡连通图，则G有欧拉道路的充要条件是G最多有两个奇次顶点.该推论为判别图形能否一笔画给出了依据103.中国邮递员问题-定义

邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线。这就是中国邮递员问题。

若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图.

中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回．（管梅谷1962年）——一笔画问题104.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边

割边的定义：设G连通，eE(G),若从G中删除边e后，图G-{e}不连通，则称边e为图G的割边．G的边e为割边e不含在G的圈中圈：起点与终点重合的路径顶点、边均不重复的通路105.中国邮递员问题-算法Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.

此时G的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回．1.G是欧拉图106.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10107.

若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．

解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．e3v1v2v3v4e1e2e4e52.G不是欧拉图108.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9109.

先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回．基本思想：110.（3）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．（2）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1．111.定义：设M是G的一个匹配，（1）若M渗透了G的每个顶点，则称M是G的理想匹配（2）若M是G中含边最多的匹配，则称M为G的最大匹配显然理想匹配是最大匹配，但最大匹配不一定是理想匹配理想匹配可能有多个，权最小的为最小权理想匹配。112.113.中国邮递员问题的应用与推广：1.铲雪车的行使路线问题：马里兰州维克米城被大雪覆盖，有两辆铲雪车清除积雪。如何安排行使路线，使得两辆车同时完成任务。2.容量约束中国邮递员问题：城市环保局每天要派出洒水车为城市街道洒水。由于洒水车的容量有限，中途需要返回加水，若已知每英里道路需要的水量以及洒水车的容量，问如何安排车的行使路线使总行程最短？又如：城市垃圾收集、流动餐车、道路洒盐….114.哈密尔顿图