第5章 运筹学模型
5.2 图论模型
图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。
5.2.1 图的基本概念
城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。
1.图
图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接
起来。
图5-1
由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且
使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1也可以画成图5-2的形式。 图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作
) , (E V G =。这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序
的。如果边e 连接顶点u 和v ，则记作e = {v u ,}。u 和v 称作e 的端点，e 称作u 和v 的关联边。如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之间可以有不止一条
边，端点相同的两条边称作平行边，如果一条边的两个端点重合，则称作环。不含环和平行边的图称作简单图。如图5-3中
)
, (E V G =,
V
={
6
i 1 | ≤≤i v },
E ={9j 1 | ≤≤j e }, 1e ={21,v v },
}, {322v v e =, 21 v v 和相邻，31 v v 和不相邻。
21 e e 和相邻。6v 是孤立点。7e 和8e 是平行边，9e 是环。
设P 是图) , (E V G =中以顶点u 和v 为首尾、点边交替的序列。如果序列中每一条边的
端点恰好是与它前后相邻的两个顶点，则称这 个序列p 是从u 到v 的一条链。当链的首尾相
连时，它称作圈。如果链上所有顶点都不相同， 图5-3 则称这条链是初级链。如果圈上除首尾两个定点之外所有顶点都不相同，则称这个圈是初级圈。
例如，在图5-3中，},,,,,,,,,,{452232211911v e v e v e v e v e v p =是一条从41 v v 到的链，但不是初级链。},,,,,,,,,,{112658475412v e v e v e v e v e v p =是一个圈，但不是初级圈。 在简单图中，可以用顶点序列表示链和圈。任意两个顶点间都有一条链的图称作连通图。图5-3不是连通图。
设有两个图) , (E V G =和),(111E V G =。如果E E V V ⊆⊆11,则称1G 是G 的子图，如果),(111E V G =是) , (E V G =的子图，并且V V =1，则称1G 是G 的生成子图。如果V V ⊆1， 1E 是E 中所有端点属于1V 的边组成的集合，
则称1G 是G 的关于1V 的导出子图，图5-4中的3个图均是图5-3的子图，其中（b ）是生成子图，（c ）是关于},,{5211v v v V =的导出子图。
图 5-4
我们常常可以利用图比较简便的解决某些实际问题，下面是一个例子。
例 1 有5位运动员参加游泳比赛，表5-1给出每位运动员参加的比赛项目。问如何安排比赛，才能是每位运动都不连续的参加比赛？
表 5-1
赛没有同一运动员参加，则可以把这两项紧排在一起，用一条边把代表这两个项目的顶点连起来。这样得到 图5-5，不难看出，为了解决这个问题，只需找到一条包含所有顶点的初级链。如P= {B,C,D,A,E}是一条初级链，其对应的比赛安排是：50m 蛙泳，100m 蝶泳，100m 自由泳，50m 仰泳，200m 自由泳。
图 5-5
2.有向图
在图) , (E V G =中，边是没有方向的，即},{},{u v v u =，这种图称作无向图。但是，有些关系不是对称的，用图表示这样的关系时，边是有方向的，用箭头表示，称作弧。从顶点u 指向v 的弧a 记作),(v u a =。u 称作a 的始点，v 称作a 的终点。这样的图称作有向图。
设顶点集合V ={n v v v ,...,, 21}，弧集合A ={m a a a , ... ,,21}，有向图记作) , (A V D =，和无向图类似，在有向图中也有环、平行弧、子图等概念。当然，在有向图中必须注意到弧是有方向的。例如，平行弧不仅要求两条弧的端
点相同而且要求它们的始点和始点相同，终点和终点相同。
设P 是有向图) , (A V D =中从顶点u 到v 的点弧交替的序列。
如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则
P 称D 是中的一条路。当路的首尾相连时，称
作一条回路。和无向图一样，顶点全不相同的路称作初级回路。例如，图5-6给出一个有向
图) , (A V D =，其中V ={4321,,, v v v v }，}, 81|{≤≤=i a A i ),(),,(232211v v a v v a ==， 图 5-6
},,,,,,{1435461v a v a v a v p =是一初级回路。
3. 树
