运筹学模型

第5章运筹学模型。

5.2 图论模型。

图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到2023年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的**。

由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。

本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。

5.2.1 图的基本概念。

城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。

1.图。图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge）组成。

通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。

同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接起来。

图5-1由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：

图5-1也可以画成图5-2的形式。图 5-2

设图的顶点集合={}边的集合={}把图记作。这里大括号内的元素是没有顺序的，而小括号（）内的元素是有顺序的。如果边e连接顶点和，则记作e = 和称作e的端点，e称作和的关联边。

如果和之间有一条边，即{}e，则称和相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。

两个顶点之间可以有不止一条边，端点相同的两条边称作平行边，如果一条边的两个端点重合，则称作环。不含环和平行边的图称作简单图。如图5-3中相邻，不相邻。

相邻。是孤立点。和是平行边，是环。

设是图中以顶点和为首尾、点边交替的序列。如果序列中每一条边的。

端点恰好是与它前后相邻的两个顶点，则称这。

个序列p是从到的一条链。当链的首尾相。

连时，它称作圈。如果链上所有顶点都不相同图5-3

则称这条链是初级链。如果圈上除首尾两个定点之外所有顶点都不相同，则称这个圈是初级圈。

例如，在图5-3中，是一条从的链，但不是初级链。是一个圈，但不是初级圈。

在简单图中，可以用顶点序列表示链和圈。任意两个顶点间都有一条链的图称作连通图。图5-3不是连通图。

设有两个图和。如果则称是的子图，如果是的子图，并且，则称是的生成子图。如果，是中所有端点属于的边组成的集合，则称是的关于的导出子图，图5-4中的3个图均是图5-3的子图，其中（b）是生成子图，（c）是关于的导出子图。

图 5-4我们常常可以利用图比较简便的解决某些实际问题，下面是一个例子。

例 1 有5位运动员参加游泳比赛，表5-1给出每位运动员参加的比赛项目。问如何安排比赛，才能是每位运动都不连续的参加比赛？

表 5-1解用顶点表示比赛项目，分别记作a,b,d,c,e。如果两项比赛没有同一运动员参加，则可以把这两项紧排在一起，用一条边把代表这两个项目的顶点连起来。这样得到图5-5，不难看出，为了解决这个问题，只需找到一条包含所有顶点的初级链。

如p= 是一条初级链，其对应的比赛安排是：50m蛙泳，100m蝶泳，100m自由泳，50m仰泳，200m自由泳。

图 5-52.有向图。

在图中，边是没有方向的，即，这种图称作无向图。但是，有些关系不是对称的，用图表示这样的关系时，边是有方向的，用箭头表示，称作弧。从顶点指向的弧记作。

称作的始点，称作的终点。这样的图称作有向图。

设顶点集合={}弧集合={}有向图记作，和无向图类似，在有向图中也有环、平行弧、子图等概念。当然，在有向图中必须注意到弧是有方向的。例如，平行弧不仅要求两条弧的端点相同而且要求它们的始点和始点相同，终点和终点相同。

设是有向图中从顶点到的点弧交替的序列。如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则称是中的一条路。当路的首尾相连时，称作一条回路。

和无向图一样，顶点全不相同的路称作初级回路。例如，图5-6给出一个有向图，其中图 5-6

是一初级回路。

3. 树。无圈的连通图称作树(tree)。设为一个连通图，如果树是的生成子图，则称作生成树。图5-7给出3棵树，其中（b）和（c）都是图5-1的生成树。

图 5-7不难证明树有下列性质：

性质1 树的边数等于顶点数减1。

性质2 树的任意两个顶点之间有且只有一条初级链。

性质3 在树中任意去掉一条边，就得到一个非连通图。

性质4 在树中任意两个顶点之间添加一条边，恰好产生一个初级圈。

5.2.2 最小生成树。

设图，对每一条边，指定一个实数，我们称这样的图为赋权图，记作，其中是边集合到实数集的映射，实数称作边的权。当时，常把记作。类似地，对有向图的每一条弧指定一个实数，得到赋权有向图，记作，称作弧的权，当时，常把记作。

在实际应用中，权可以有各种各样的含义，如距离、时间、费用、运输量、流量等。

1．最小生成树的概念。

设是一个连通的赋权图，是的生成树，把中所有边的权之和称作树的权，记作，即，中权和最小的生成树称作最小生成树。

2．最小生成树的算法。

kruskal于2023年给出一个求最小生成树的算法：避圈法。其基本方法如下：

1) 画出图中的全部顶点。

2) 按边权的大小从小到**边（n个顶点需n-1步），并且每一步都不能构成圈。

例 2 现有5个城市，打算用铁路把它们连接起来。这5个城市之间哪两个可以修建铁路以及铁路的长度如图5-8所示（每一条边旁边有一个数字，即表示这段铁路的长度）。试给出修建铁路的方案，使铁路总长度最短。

图 5-8解此题提出的问题是求给定赋权图的最小生成树。做题步骤如图5-9所示：

图 5-9注意，在第四步，可以不取，而取，得到另一棵最小生成树，其权和为12。如图5-10所示。可见最小生成树不唯一。

计算在每一步都要判断添加的边是否构成圈。这在图不很复杂时，直接观察并不困难。但在使用计算机时，则必须进一步给出形式化的方法，计算的具体步骤如下：

kruskal算法。

1. 按权从小到大排列边。

令图 5-10

2. 令s←φ,k←1(φ表示空集)。

3. 设，则转6；否则令，执行4。

4. 对所有。

令。5. 若|s|= n-1,则是s最小生成树的边集合，计算结束；否则执行6。（|s|表示s中元素的个数）

6. 若k=m，则说明图是非连通的，停止计算；否则令k←k+1，转3。

5.2.3最短路问题。

1. 最短路的概念。

设为连通图，图中各边有权（其中表示之间没有边），为图中任意两点，所谓最短路问题就是求一条路，使它为从到的所有路中总权最小的路。即：最小。

2. 图的矩阵表示。

对于赋权图，由其边的权，构造矩阵，其中：

称矩阵为赋权图的权矩阵。

例如图5-11的权矩阵为：

图5-113．最短路的算法。

1）由图写出其权矩阵。

2）由matlab软件求最短路。

3）软件计算程序为：

function[d,r]=floyd(a)

n=size(a,1);

d=afor i=1:n

for j=1:n

r(i,j)=j;

endend

rfor k=1:n

for i=1:n

for j=1:n

if d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);

r(i,j)=r(i,k);

endendendk

drend例 3求下图5-12从到的最短路。（无向图）

图 5-12

解首先由图写出其权矩阵：

再给出指令 [d，r]=floyd(a)

最后由matlab软件得出结论：

最短距离（下列数据可揭示图中任意两点的最短距离）d =

最短路径（下列数据可揭示图中任意两点的最短路径）r =

则到的最短路为：

例 4 有一批货要从1运到8，运输路线如图5-13所示，弧旁的数字是这段路的单位运费。试给出总运费最小的运输路线。（有向图）

运筹学模型

运筹学模型

运筹学模型

数学建模运筹学模型一

其他用户还读了