-68-
第五章 图与网络模型及方法
§1 概论
图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼
斯堡的七座桥”。1847 年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857
年，凯莱在计数烷
22 +nn
HC 的同分异构物时，也发现了“树”。哈密尔顿于 1859 年提
出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年
来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和
方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济
学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示
这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到
了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了
一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问
题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结
起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
图 1 哥尼斯堡七桥问题
当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解
决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座
桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特
点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将
这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问
题，而且开创了图论研究的先河。
图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的
问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等
诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都
是图与网络的基本问题。
我们首先通过一些例子来了解网络优化问题。
例 1 最短路问题（SPP－shortest path problem）
一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的
公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运
行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例 2 公路连接问题
某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其
