图是指某类具体事物和这些事物之间的联系,最短路径问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。图论对建模和解决实际问题都用处极大,数学专业的《数据结构》《离散数学》《运筹学》课程都会重点介绍它。 % l3 `+ M* H$ c$ j: p% z, c0 Y( k
【1】图与网络模型及方法:图与网络的基本概念& .图在数据结构中的多种表示法:描述了图论中的常见问题eg最短路径问题、指派问题、中国邮递员问题、旅行商问题... 5 T, ^) @4 B. k4 ~: N1 W/ G: p) F: K
1 概论 " M9 Y. y D. O! e4 c# O9 l+ n图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼斯堡的七座桥”。1847 年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年,凯莱在计数烷 的同分异构物时,也发现了“树”。哈密尔顿于 1859 年提 出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈. 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来,问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。1 i) V: x* H+ [9 z% b0 ~ # [, W8 ?$ O7 ^1 O( r" S: \ H% G
' n Q$ Q2 [2 S4 ?: _! d
& Q- Z1 u$ L( R, m0 N: D ~, O
当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。欧拉为了解 决这个问题,采用了建立数学模型的方法。他将每一块陆地用一个点来代替,将每一座 桥用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。 问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特 点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将 这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问 题,而且开创了图论研究的先河。6 ?) U+ A3 T3 V/ T6 h
$ {8 f$ w9 Z% \
图与网络是运筹学(Operations Research)中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等 诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 9 H3 |4 g, P1 d; x+ f: A3 M 7 s# Q1 F! g4 ~例 1 最短路问题(SPP-shortest path problem) 6 A( W1 s" Q4 |一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的 公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运 行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。 X1 b9 @1 l6 H! }8 [3 m/ r- \; u' y; S+ Y+ s
例 2 公路连接问题 $ S, N/ J- g# W# a1 O- |某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两 个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总 成本最小?. X. @* N+ {% w2 e/ O
1 p$ G9 P) `5 c" E8 p9 z/ _3 `2 N
例 3 指派问题(assignment problem) + ?2 j! U0 S# _& J一家公司经理准备安排 N 名员工去完成 N 项任务,每人一项。由于各员工的特点 不同,不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以 使总回报最大?5 d: u& c0 [# ^& M: A# ?
o+ R; p! I' L' u7 a5 \: D
例 4 中国邮递员问题(CPP-chinese postman problem) $ m; w; e% y" X( r' c5 `一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从 邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国管 梅谷教授 1960 年首先提出的,所以国际上称之为中国邮递员问题。9 g6 z( v) q! z3 e: c1 |8 ]; S* ~
. n4 {9 [ K# g( b' |
例 5 旅行商问题(TSP-traveling salesman problem)5 B/ V( S5 r$ R* l
一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线 (从驻地出发,经过每个城市恰好一次,最后返回驻地)?这一问题的研究历史十分悠 久,通常称之为旅行商问题。+ N R9 s' I9 h j5 B
. s' p- k! g1 x) M0 E
例 6 运输问题(transportation problem) ) S$ b) m6 W2 l6 @: K某种原材料有 M 个产地,现在需要将原材料从产地运往 N 个使用这些原材料的工 厂。假定 M 个产地的产量和 N 家工厂的需要量已知,单位产品从任一产地到任一工厂 的运费已知,那么如何安排运输方案可以使总运输成本最低? 4 P' e3 t' v& I% S' M+ ^6 a% p % r2 R" n# j# }. e上述问题有两个共同的特点:一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization) 问题;二是它们都易于用图形的形式直观地描述和表达,数学上把这种与图相关的结构 称为网络(network)。与图和网络相关的最优化问题就是网络最优化或称网络优化 (netwok optimization)问题。所以上面例子中介绍的问题都是网络优化问题。由于多 数网络优化问题是以网络上的流(flow)为研究的对象,因此网络优化又常常被称为网络流(network flows)或网络流规划等。# W, c p% k! X- u
; P- z) C9 h1 V$ s" B. Q
下面首先简要介绍图与网络的一些基本概念。 . R* {$ [) L2 `* r7 _" `% N1 P7 i1 ^% _
' {' k6 X+ v( {' ~( q B ; k1 e8 t! x: g) i8 o0 `' t) N2 图与网络的基本概念 . [8 V6 M, X" r" E9 h6 S' h2.1 无向图0 ?1 N1 i' N) F5 m0 I+ i 6 g4 f; d! \3 ~% H, N& P% J$ d* h s
2 _- m+ ~ N3 l5 c, J/ F9 q边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和 网络不作严格区分,因为任何图总是可以赋权的。 3 |( }' x% ]6 w7 o) s% ^ e" P' I- ~
一个图称为有限图,如果它的顶点集和边集都有限。图G 的顶点数用符号|V | 或 ν (G) 表示,边数用| E |或ε (G)表示。% b) l( K" V" k$ `. t3 L R
3 j9 H" w$ f$ {5 A+ ?" v# z
当讨论的图只有一个时,总是用G 来表示这个图。从而在图论符号中我们常略去 字母G ,例如,分别用V,E,ν 和ε 代替V (G),E(G),ν (G) 和ε (G)。 : S! I$ Y% E, }2 x0 P8 \9 N6 D6 q( U
端点重合为一点的边称为环(loop)。 一个图称为简单图(simple graph),如果它既没有环也没有两条边连接同一对顶点。 d& g& H2 x" j: l' F/ M7 Q2 |8 z I' W
2.2 有向图6 h. t* g) X2 p, h, Z ) m: i# q% _2 N' J2 a2 d" p 5 H6 J: P- w9 j, z F: [7 A对应于每个有向图 D ,可以在相同顶点集上作一个图G ,使得对于 D 的每条弧, G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。反之,给定任意图G , 对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这 样的有向图称为G 的一个定向图。 以下若未指明“有向图”三字,“图”字皆指无向图。) _* _5 \- `1 w6 X- v9 V
; _. K( R) ^! S. [4 V. V3 R
2.3 完全图、二分图" P% e- E9 l2 u
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点 的完全图记为 。1 v& o, W( [8 m# x7 n8 a/ k- O3 K: C7 u
9 u6 C3 C3 E3 r ' r o. v' i; y: g
% b4 Q$ M u+ C( ]2.4 子图; _/ x6 }1 w3 V/ }
图 H 叫做图 G 的子图(subgraph),记作 H ⊂ G ,如果 V (H ) ⊂V (G) , E(H) ⊂ E(G) 。若 H 是G 的子图,则G 称为 H 的母图。 G 的支撑子图(spanning subgraph,生成子图)是指满足V(H) =V(G) 的子 图 H 。+ e$ [! t% x2 [+ u1 K; u