图与网络优化及网络分析-经济模型讲义教案.docVIP

图与网络优化 十七，十八世纪时，出现了一些有趣的问题，如迷宫问题、博弈问题、回路问题及棋盘上马的行走线路之类的游戏问题，吸引了许多学者。学者们将这些看起来无足轻重的问题抽象为数学问题，从而开辟了图论这门新学科的研究。从以下例子中可以初步领略图论这门学科的起源与发展。 例10-1 在18世纪的东欧有个小城哥尼斯堡（今俄罗斯加里宁格勒），在城中有一条河——普雷格尔河流贯全城，在河的两岸及河中心的两个小岛之间有7座小桥相通，如图10-1所示。当时哥尼斯堡的居民中热衷于讨论这样一个话题：一个人怎样才能一次走遍七座桥，且每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，没有人能够找到这样的走法，但是又无法说明这种走法不存在。这就是著名的哥尼斯堡七桥问题。 图10-1 哥尼斯堡七桥问题示意图 1736年欧拉（Euler）发表了图论方面的第一篇论文。欧拉用A、B、C、D表示4个城区，用7条线表示7座桥，将哥尼斯堡七桥问题抽象为一个图论模型，如图10-2所示，从而将哥尼斯堡七桥问题抽象为一个数学问题：能否从某一点出发，经过图中每条边一次且仅一次，并回到出发点，即一笔画问题，也称之为欧拉回路。 欧拉论证了这样的回路是不存在的，并且将问题进行了一般化处理，即对于任意多的城区和任意多的桥，给出了是否存在欧拉回路的判定规则： （1）如果连接奇数桥的顶点多于两个，则不存在欧拉回路； （2）如果只有两个点连接奇数桥，可以从这两个地方之一出发，找到欧拉回路； （3）如果没有一个点连奇数桥，则无论从哪里出发，都能找到欧拉回路。 例10-2 （环球旅行问题）1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。如图10-3所示。它与七桥问题不同的是，前者是要在图中找一条经过每边一次且仅一次的路，通称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，通称为哈密尔顿回路。哈密尔顿根据这个问题的特点，给出了一种解法，如图10-4所示。 例10-3 （中国邮路问题）中国邮路问题由我国数学家管梅谷先生在1962年首先提出：一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？ 图10-5 中国邮路问题的图模型 如果将这个问题抽象成图论的语言，就是给定一个各点相互连通的图，如图10-5所示，连通图的每条边的权值为对应的街道的长度（距离），要在图中求一回路，使得回路的总权值（总长度）最小。该问题与哥尼斯堡七桥问题的显著区别是邮递员要完成任务可能必须在某些街道上重复走若干次。 图论的第一本专著是匈牙利数学家O.Koing写的“有限图与无限图的理论”发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年年之久，总的来说这一时期图论的发展是缓慢的。直到20世纪中期，随着计算机的发展与离散数学问题具有越来越重要的地位，使得作为提供离散模型的图论得以迅速发展，成为运筹学的一个重要分支。 §10.1 图与网络的基本概念 一、无向图 设是一个有个顶点的非空集合：；是一个有条无向边的集合：，则称和这两个集合构成了一个无向图，记为无向图。中任一条边若连接顶点和，则记该边为（或），并称与为无向边的两个端点，且边与顶点及相关联，顶点和顶点相邻。对于图，有时为说明问题，顶点集和无向边集也可以分别表示为和。 一般用和表示图中顶点个数和边的条数。 实际上无向图是一个由顶点和无向边构成的一个网络结构。一般我们可以作出其几何图，并直接对几何图进行分析。请看以下几个无向图的几何图。 图10-6 简单图 图10-7 完备图 图10-8 带平行边的无向图 平行边——若无向图的两条不同的边和具有相同的端点，则称和为的平行边。如图10-8中的和为平行边，和也是平行边。 简单图——若无向图中不存在平行边，则称为简单图。图10-5、图10-6都是简单图。 完备图——若无向图中的任意两个顶点之间都恰好有一条边相关联，则称为一个完备图。图10-7是一个完备图。 子图——若两个无向图和满足，则称图是图的子图，记为。显然图10-6是图10-7和图10-8的子图。 生成子图——若图是图的子图，且满足，则称图是图的生成子图。显然生成子图的顶点不能减少，图10-6也是图10-7和图10-8的生成子图。 导出子图——设无向图，对于非空边集，将图中所有与中的边相关联顶点的全体记为，则称子图为图的导出子图。 如在图10-8中取，相应的，从而得到导出子图，见图10-9。 图10-9 生成子图