《数学模型与数学实验》课程书籍文献（数学建模算法大全）第05章 图与网络

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

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

中任何 例3 ment problem 成顶任条，每人一顶 使总回报最大？ 例4中国邮递员问题(Cpp一chinese postman problem) 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从 邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国管 梅谷教授1960年首先提出的，所以国际上称之为中因邮递员问题。 例5 之为旅行商问题 例 种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工 厂。假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂 的运费己知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求 某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化(optimization) 可题； 是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构 称为网络(network)。与图和网络相关的最优化问题就是网络最优化或构 网络优 所 ,上面例子中 )为研究的对多 网络 §2图与网络的基本概念 2.1无图 个无向图(undirected graph)G是由一个非空有限集合V(G)和'(G)中某些元素 的无序对集合E(G)构成的二元组，记为G=(V(G),E(G)。其中 V(G)={,2,v,}称为图G的顶点集(vertex set)或节点集(node set,V(G)中 的每一个元素v,i=l,2.,n)称为该图的一个顶点(vertex)或节点(node): E(G)={e,e2,en}称为图G的边集(edge set),E(G)中的每一个元素e,(卿V(G) 中某两个元素y,y,的无序对)记为e=(y,y)或e=y,=yy,(k=1,2,m) 被称为该图的一条从y,到y,的边(edgc)。 当边e=,y,时，称y,为边e:的端点，并称y,与y相邻(adjacent):边e称 为与顶点y,',关联(incident)。如果某两条边至少有一个公共端点，则称这两条边在 图G中相 边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和 网络不作严格区分， 因为任何图总是可以赋权的 -69-

-69- 中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两 个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总 成本最小？ 例 3 指派问题（assignment problem） 一家公司经理准备安排 N 名员工去完成 N 项任务，每人一项。由于各员工的特点 不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以 使总回报最大？ 例 4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从 邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管 梅谷教授 1960 年首先提出的，所以国际上称之为中国邮递员问题。 例 5 旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线 （从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠 久，通常称之为旅行商问题。 例 6 运输问题（transportation problem） 某种原材料有 M 个产地，现在需要将原材料从产地运往 N 个使用这些原材料的工 厂。假定 M 个产地的产量和 N 家工厂的需要量已知，单位产品从任一产地到任一工厂 的运费已知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求 某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization） 问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构 称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多 数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网 络流（network flows）或网络流规划等。 下面首先简要介绍图与网络的一些基本概念。 §2 图与网络的基本概念 2.1 无向图 一个无向图(undirected graph)G 是由一个非空有限集合V (G) 和V (G) 中某些元素 的无序对集合 E(G) 构成的二元组，记为 G = (V (G),E(G)) 。其中 ( ) { , , , } 1 2 n V G = v v L v 称为图G 的顶点集（vertex set）或节点集（node set）， V(G) 中 的每一个元素 v (i 1,2, ,n) i = L 称为该图的一个顶点（vertex）或节点（node）； ( ) { , , , } 1 2 m E G = e e L e 称为图G 的边集（edge set），E(G) 中的每一个元素 k e (即V(G) 中某两个元素 i j v ,v 的无序对) 记为 ( , ) k i j e = v v 或 k i j j i e = v v = v v (k =1,2,L,m) ， 被称为该图的一条从 i v 到 j v 的边（edge）。 当边 k i j e = v v 时，称 i j v ,v 为边 k e 的端点，并称 j v 与 i v 相邻（adjacent）；边 k e 称 为与顶点 i j v ,v 关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在 图G 中相邻。 边上赋权的无向图称为赋权无向图或无向网络（undirected network）。我们对图和 网络不作严格区分，因为任何图总是可以赋权的

个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号V或 (G)表示，边数用引E引或(G)表示。 当过论的图口有 个时，总是用G来表示这个图。从而在图论符号中我们常略去 字母G,例如，分别用V,E,y和代替V(G,E(G),(G)和(G) 端点重合为 个图 环 有向图 ,如果它既没有环也没有两条边连接同一对顶点。 22 个有向图(di cted graph或dig nh)G是由一个非空有限集合V和V中 某些元素的有序对集合A构成的 元组，记为G=(W,40。其中V={，2，.，v,}称 为图G的顶点集或节点集，V中的每一个元素y,(i=1,2,.,n)称为该图的一个顶点 或节点：A={a,a,an}称为图G的弧集(are set),A中的每一个元素a(即V中 某两个元素y,Y,的有序对)记为a=(y,y,)或a=yy,(k=1,2,.,n),被称为该图 的一条从y,到y,的弧(ac)。 当弧a=vy,时，称y,为a,的尾(tail),y,为a的头(head),并称弧a为y,的 出弧(outgoing arc),为y,的入弧(incoming arc)。 对于它的每个边，给 点指定 个顺序，从而确定 条弧，由此得到 样的有向图称为G的一个定 23完全图 一分分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点 的完全图记为K。 若V(G)=XUY,X∩Y=Φ，XIY卡0（这里|X表示集合X中的元素个 数)，X中无相邻项点对，Y中亦然，则称G为二分图((bipartite graph):特别地，若 x∈X,y∈Y,则xy∈E(G),则称G为完全二分图，记成Kw。 24子图 图H叫做图G的子图(subgraph),记作HcG,如果V(H)cV(G) E(H)CE(G)。若H是G的子图，则G称为H的母图 G的支撑子图(spanning subgraph,又成生成子图)是指满足V(H)=/(G)的子 图H。 25顶点的度 设v∈V(G),G中与v关联的边数（每个环算作两条边）称为v的度(degree),记 作d().若d(v)是奇数，称v是奇顶点(odd point)):d(v)是偶数，称v是偶顶点(eve point)。 关于顶点的度， 我们有如下结果 0∑d(v)-2 (D任意一个图的奇顶点的个数是偶数。 2.6图与网络的数据结构 -70

-70- 一个图称为有限图，如果它的顶点集和边集都有限。图G 的顶点数用符号|V | 或 ν (G) 表示，边数用| E |或ε (G)表示。 当讨论的图只有一个时，总是用G 来表示这个图。从而在图论符号中我们常略去 字母G ，例如，分别用V,E,ν 和ε 代替V (G),E(G),ν (G) 和ε (G)。 端点重合为一点的边称为环(loop)。 一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。 2.2 有向图 定义 一个有向图（directed graph 或 digraph）G 是由一个非空有限集合V 和V 中 某些元素的有序对集合 A 构成的二元组，记为G = (V, A)。其中 { , , , } 1 2 n V = v v L v 称 为图G 的顶点集或节点集， V 中的每一个元素 v (i 1,2, ,n) i = L 称为该图的一个顶点 或节点； { , , , } A = a1 a2 L am 称为图G 的弧集（arc set），A 中的每一个元素ak (即V 中 某两个元素 i j v ,v 的有序对) 记为 ( , ) k i j a = v v 或a v v (k 1,2, ,n) k = i j = L ，被称为该图 的一条从 i v 到 j v 的弧（arc）。 当弧 k i j a = v v 时，称 i v 为ak 的尾（tail）， j v 为ak 的头（head），并称弧ak 为 i v 的 出弧（outgoing arc），为 j v 的入弧（incoming arc）。 对应于每个有向图 D ，可以在相同顶点集上作一个图G ，使得对于 D 的每条弧， G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。反之，给定任意图G ， 对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这 样的有向图称为G 的一个定向图。 以下若未指明“有向图”三字，“图”字皆指无向图。 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点 的完全图记为 Kn 。 若V (G) = X UY ， X IY = Φ ，| X ||Y |≠ 0（这里| X |表示集合 X 中的元素个 数）， X 中无相邻顶点对，Y 中亦然，则称G 为二分图(bipartite graph)；特别地，若 ∀x ∈ X,∀y ∈Y ，则 xy ∈ E(G)，则称G 为完全二分图，记成 K|X |,|Y | 。 2.4 子图 图 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 。 2.5 顶点的度 设v ∈V (G) ，G 中与v 关联的边数（每个环算作两条边）称为v 的度(degree)，记 作d(v)。若d(v)是奇数，称v 是奇顶点(odd point)；d(v)是偶数，称v 是偶顶点(even point)。关于顶点的度，我们有如下结果： (i) ∑∈ = v V d(v) 2ε (ii) 任意一个图的奇顶点的个数是偶数。 2.6 图与网络的数据结构

网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的 网的且休表 绍计 肌上用来描述图与 用表 在 构的 个简单 向图，n,A上m ,并假设 先 顶点用自然 1 表示或 4中 用自然数1, ,m 编号 对于有多重边或无向网络的情 况，我们只 论完 单有向图的表示方法之后，给出一些说明 郊接矩阵是如下定义的：C y的形式存储在计算机中.图 C=(cr)nxn∈{0，l}, 1,(,)∈A C= 10.(i.）EA 也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1：否则为0： 可以看出 这种 非常 ,只有 非零 中查找弧的时间 图2有向图 例7对于图2所示的有向图，可以用邻接矩阵表示为 01100 00010 01000 00101 00110 只是此时一 用多个矩阵表示这些权 关联矩阵表示法是将图以关联矩阵(incidence matrix)的形式存储在计算机中.图 G=(W,A)的关联矩阵B是如下定义的：B是一个n×m的矩阵，即 B=(b)mm∈{-l0,1} -71

-71- 网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的 算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说， 算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介 绍计算机上用来描述图与网络的 5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、 弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设 G = (V, A)是一个简单有向图，|V |= n,| A |= m ，并假设V 中的顶点用自然数1,2,L,n 表示或编号， A 中的弧用自然数1,2,L,m 表示或编号。对于有多重边或无向网络的情 况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图 G = (V, A)的邻接矩阵是如下定义的：C 是一个n × n 的0 −1矩阵，即 n n ij n n C c × = ( ) × ∈{0,1} ， ⎩ ⎨ ⎧ ∉ ∈ = 0, ( , ) . 1, ( , ) , i j A i j A cij 也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为 1；否则为 0。 可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 2 n 个元素中，只有m 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络 中查找弧的时间。 图 2 有向图 例 7 对于图 2 所示的有向图，可以用邻接矩阵表示为 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 同样，对于网络中的权，也可以用类似邻接矩阵的n × n 矩阵表示。只是此时一条 弧所对应的元素不再是 1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以 用多个矩阵表示这些权。 （ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中．图 G = (V, A)的关联矩阵 B 是如下定义的： B 是一个n × m 的矩阵，即 n m B bik n m × = ( ) × ∈{−1,0,1}

1,eV,k=(亿，)∈A b4={-1,3j∈V,k=(j,)eA 0.其它 也就是说，在关联矩阵中，每行对应于图的个节点，每列对应天 一条弧。如 的元素为0 对应的元素为 应的 则关联矩 + 1) 这 法也 个非零元所有 个为非零元 小里网络比较稀疏 示法也会浪费大量 关联矩阵有许多特别重要的理论性质， 这种表不化中是 重的令 例8对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，（，3)，(2.4， (3,2),(4,3),(4,5),(5,3)和(5,4)，则关联矩阵表示为 1 1000000 -101-10000 0 -10 1-10-10 00-10 10-1 00000-11 1 同样，为 中的 也可以通过 联矩 的扩展来表示 如果网络中 每条弧有 所 所对如 ,我们可以 应的 矩阵增加相应的 ，把每 ()弧表表示 弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表，也就是 图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m个有 储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对 应地用额外的存储单元表示。例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4，(3,2)， (4,3),(4,5),(5,3)和(54)上的权分别为8,9,6,4,0,3,6和7，则弧表表示如表1 所示。 112 445 5 4 权896■4 0☐36 为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按 照这样的顺序存储的。 (iv)邻接表表示法 邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的 接表，也就是图的所有节点的邻接表的集合：而对每个节点， 的邻接衣是它的月 有出 :表表不法就 是对图的每个 节点，用 单向链表列出从该节点 .J 组表示。例如 所示的图， -72

-72- ⎪ ⎩ ⎪ ⎨ ⎧ − ∃ ∈ = ∈ ∃ ∈ = ∈ = 0, . 1, , ( , ) , 1, , ( , ) , 其它 j V k j i A j V k i j A bik 也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如 果一个节点是一条弧的起点，则关联矩阵中对应的元素为 1；如果一个节点是一条弧的 终点，则关联矩阵中对应的元素为 −1；如果一个节点与一条弧不关联，则关联矩阵中 对应的元素为 0。对于简单图，关联矩阵每列只含有两个非零元（一个 +1，一个 −1）。 可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有nm 个元素中，只 有2m 个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于 关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 例 8 对于例 7 所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)， (3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − − − − − 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中 每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的 行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条 弧所对应的权存储在增加的行中。 （iii）弧表表示法 弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是 图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m 个存 储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对 应地用额外的存储单元表示。例如，例 7 所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)， (4,3)，(4,5)，(5,3)和(5,4)上的权分别为 8，9，6，4，0，3，6 和 7，则弧表表示如表 1 所示。 表 1 起点 1 1 2 3 4 4 5 5 终点 2 3 4 2 3 5 3 4 权 8 9 6 4 0 3 6 7 为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按 照这样的顺序存储的。 （iv）邻接表表示法 邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的 邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所 有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有 弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的 另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数 组表示。例如，例 7 所示的图，邻接表表示为

1 28 3g0 2 460 3 240 4 30 530 36 470 这是，个5维指针数组 上面表 个节点的邻接 表如第对手 行中的示的另 的数 对应上的超 的 表示对应1.2)上的 权为8：“3”表示弧的另 个端点为3（即弧为13)，g”表示对应弧（1,3)上的权 为9。又如，第5行说明节点5出发的弧有(5,3)、(5.4)，他们对应的权分别为6和7。 对于有向图G=(V,A),一般用A)表示节点i的邻接表，即节点i的所有出弧构 成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子， 41)={2,3 A5)={3,4}等。 示法 星形(sar)表示法的思想与邻接表表示法的思想有 一定的相似之处。对每个节点 它也是记录从该节点出发的所有，但它不是采用单向链表而是采用 个单 的数组表 示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2 出发的所有孤，依此类推，最后存放从节点n出发的所有孤。对每条弧，要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了 一个顺序和编号 只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出 发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号） 在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星 2. 为8,9,6,4， 表2节点对应的出弧的起始地址编号数组 节点号 456 起始地址poin)134579 表3记录弧信息的数组 终占 3 权89640367 在数组poim中，其元素个数比图的节点数多1（即n+1),且一定有poin(）=1 poi(n+I)=m+1。对于节点i,其对应的出弧存放在弧信息数组的位置区间为 [point(i),point(i+1)-1], 如果poim()=poim1i+),则节点i没有出孤。这种表示法与弧表表示法也非常相 73

-73- 这是一个 5 维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接 表，如第 1 行对应于第 1 个节点的邻接表（即第 1 个节点的所有出弧）。每个指针单元 的第 1 个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如 第 1 行中的“2”表示弧的另一个端点为 2（即弧为（1,2）），“8”表示对应弧(1,2)上的 权为 8；“3”表示弧的另一个端点为 3（即弧为(1,3)），“9”表示对应弧（1，3）上的权 为 9。又如，第 5 行说明节点 5 出发的弧有(5,3)、(5,4)，他们对应的权分别为 6 和 7。 对于有向图G = (V, A)，一般用 A(i) 表示节点i 的邻接表，即节点i 的所有出弧构 成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子， A(1) = {2,3}， A(5) = {3,4}等。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点， 它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表 示。也就是说，在该数组中首先存放从节点 1 出发的所有弧，然后接着存放从节点 2 出发的所有孤，依此类推，最后存放从节点n 出发的所有孤。对每条弧，要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号， 只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出 发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。 在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星 形（forward star）表示法。 例如，在例 7 所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5）， （5,3）和（5,4）上的权分别为 8，9，6，4，0，3，6 和 7。此时该网络图可以用前向 星形表示法表示为表 2 和表 3 。 表 2 节点对应的出弧的起始地址编号数组 节点号i 1 2 3 4 5 6 起始地址 point(i) 1 3 4 5 7 9 表 3 记录弧信息的数组 弧编号 1 2 3 4 5 6 7 8 起点 1 1 2 3 4 4 5 5 终点 2 3 4 2 3 5 3 4 权 8 9 6 4 0 3 6 7 在数组 point 中，其元素个数比图的节点数多 1（即n +1），且一定有 point(1) = 1， point(n +1) = m +1。对于节点i ，其对应的出弧存放在弧信息数组的位置区间为 [ point(i), point(i +1) −1]， 如果 point(i) = point(i +1) ，则节点i 没有出弧。这种表示法与弧表表示法也非常相

似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中 亮被编号后有序存放，并增加一个数组(DO1)记录每个节点出发的弧的起始编号 前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形(reverse star) 表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推 后存放 人节点n的 不节点的 地址（即弧的编号。例如，例7所示的图。 可以用反向 示为表4和表5 表4节点对应的入弧的起始地址编号数组 节点号i 2 3 4 56 起始地址rpoint() 3 689 表5记录弧信息的数组 3 。 起点31 45524 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧 则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以 只用一个数组(tc心)记录一条弧在两种表示法中的对应关系即可。例如，可以在采用 前向星形表示法的基础上，加上上面介绍的poi数组和如下的race数组即可.这相 当于一种紧凑的双向星形表示法，如表6所示。 表6两种表示法中的弧的对应关系 反向法中弧编号 12345678 正向法中弧编号race() 41257836 对于网络图的表示法，我们作如下说明 和都 表表示法在实际算法实现中都是经常采用的。星形表示法的 储 快指 且增加或除 需的计算工作量很少 类型 在星形 C语 化中 考虑的 当不是简单图 而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示 法是不能采用的。 甘 法则可以很方便地推广到可以处理平行弧的情形 ③上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有 方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半 信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0和+1，而不含有-1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示 法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。 27轨与连通 W=eye2evg,其中e,∈EG),1si≤k,y,eV(G),0≤j≤k,e与 -74

-74- 似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中， 弧被编号后有序存放，并增加一个数组（ point ）记录每个节点出发的弧的起始编号。 前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star） 表示法：首先存放进入节点 1 的所有孤，然后接着存放进入节点 2 的所有弧，依此类推， 最后存放进入节点n 的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有 关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录 每个节点的入孤的起始地址（即弧的编号）。例如，例 7 所示的图，可以用反向星形表 示法表示为表 4 和表 5。 表 4 节点对应的入弧的起始地址编号数组 节点号i 1 2 3 4 5 6 起始地址 rpoint(i) 1 1 3 6 8 9 表 5 记录弧信息的数组 弧编号 1 2 3 4 5 6 7 8 终点 2 2 3 3 3 4 4 5 起点 3 1 1 4 5 5 2 4 权 4 8 9 0 6 7 6 3 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧， 则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以 只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用 前向星形表示法的基础上，加上上面介绍的 rpoint 数组和如下的trace 数组即可。这相 当于一种紧凑的双向星形表示法，如表 6 所示。 表 6 两种表示法中的弧的对应关系 反向法中弧编号 j 1 2 3 4 5 6 7 8 正向法中弧编号 trace( j) 4 1 2 5 7 8 3 6 对于网络图的表示法，我们作如下说明： ① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的 优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN 语言 等）也容易实现。邻接表表示法对那些提供指针类型的语言（如 C 语言等）是方便的， 且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工 作量较大（需要花费O(m) 的计算时间）。有关“计算时间”的观念是网络优化中需要 考虑的一个关键因素。 ② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示 法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。 ③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有 方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半 信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0 和 +1，而不含有 −1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示 法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。 2.7 轨与连通 k k W v e v e Le v = 0 1 1 2 ，其中e E(G) i ∈ ，1 ≤ i ≤ k ，v V (G) j ∈ ，0 ≤ j ≤ k ， i e 与

y,y,关联，称W是图G的一条道路(wak,k为路长，顶点，和y分别称为W的起 点和终点，而，称为它的内部顶点。 若道路W的边互不相同，则W称为迹(ri).若道路W的顶点互不相同，则W称 为轨(pat 一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做 圈(cy 图G的两个顶点，v间存在道路 则称 ,间的最短到 的长叫阿的距高，记作dL。若闲G的任点均造道则G是通 显然有 图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度 为2 图C是一个圈的充要条件是C是各顶点的度均为2的连通图 $3应用一最短路问题 3.】两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。 以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G 对G的每一边e,赋以一个实数w(e)一直通铁路的长度，称为e的权，得到赋权图G。 G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点，。 间的具最小权的轨。这条轨叫做，。间的最短路，它的权叫做4，。间的距离，亦记 作d(4o,o) 求最短路已有成熟的算法：迪克斯特拉(Dijkstr)算法，其基本思想是按距山从 近到远为顺序，依次求得到G的各顶点的最短路和距离，直至V。(或直至G的所有 (令(4)=0，对v≠4。，令()=0，S。={4,},1=0 (而对每个ve5(5=V八S),用 min(v)./(u)+w(u) 代替)。计算(}，把达到这个最小值的一个顶点记为1，令 S1=S,U{u}. (的.若i=V-l,停止：若iV-1,用i+1代替i,转（。 算法结束时，从山，到各顶点v的距离由v的最后一次的标号(v)给出。在v进入S, 之前的标号()叫T标号，进入S,时的标号()叫P标号。算法就是不断修改各顶 点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由米 的边在图上标明，则算法结束时，4至各项点的最短路也在图上标示出来了。 例9某公司在六个城市G,C2,c,中有分公司，从C,到c,的直接航程票价记在 下述矩阵的（亿，）位置上。(0表示无直接航路)，请帮助该公司设计一张城市C到其它

-75- i i v ,v −1 关联，称W 是图G 的一条道路(walk)，k 为路长，顶点 0 v 和 k v 分别称为W 的起 点和终点，而 1 2 1 , , , k − v v L v 称为它的内部顶点。 若道路W 的边互不相同，则W 称为迹(trail)。若道路W 的顶点互不相同，则W 称 为轨(path)。 称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做 圈(cycle)。 若图G 的两个顶点u, v 间存在道路，则称u 和v 连通(connected)。u, v 间的最短轨 的长叫做u, v 间的距离。记作d(u,v) 。若图G 的任二顶点均连通，则称G 是连通图。 显然有： (i) 图 P 是一条轨的充要条件是 P 是连通的，且有两个一度的顶点，其余顶点的度 为 2； (ii) 图C 是一个圈的充要条件是C 是各顶点的度均为 2 的连通图。 §3 应用—最短路问题 3.1 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间， 找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。 对G 的每一边e ，赋以一个实数 w(e) —直通铁路的长度，称为e 的权，得到赋权图G 。 G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点 0 0 u ,v 间的具最小权的轨。这条轨叫做 0 0 u ,v 间的最短路，它的权叫做 0 0 u ,v 间的距离，亦记 作 ( , ) 0 0 d u v 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0 从 近到远为顺序，依次求得u0 到G 的各顶点的最短路和距离，直至 0 v （或直至G 的所有 顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该 算法。 (i) 令l(u0 ) = 0，对 u0 v ≠ ，令l(v) = ∞ ， { } S0 = u0 ，i = 0。 (ii) 对每个 Si v ∈ （ Si V Si = \ ），用 min{l(v),l(u) w(uv)} i u S + ∈ 代 替 l(v) 。计算 min{l(v)} i v∈S ，把达到这个最小值的一个顶点记为 ui+1 ， 令 { } Si+1 = Si U ui+1 。 (iii). 若i =|V | −1，停止；若i <|V | −1，用i +1代替i ，转(ii)。 算法结束时，从u0 到各顶点v 的距离由v 的最后一次的标号l(v) 给出。在v 进入 Si 之前的标号l(v) 叫 T 标号，v 进入 Si 时的标号l(v) 叫 P 标号。算法就是不断修改各顶 点的 T 标号，直至获得 P 标号。若在算法运行过程中，将每一顶点获得 P 标号所由来 的边在图上标明，则算法结束时，u0 至各项点的最短路也在图上标示出来了。 例 9 某公司在六个城市 1 2 6 c , c ,L, c 中有分公司，从 i c 到 j c 的直接航程票价记在 下述矩阵的(i, j) 位置上。（∞表示无直接航路），请帮助该公司设计一张城市 1 c 到其它

城市间的票价最便宜的路线图。 「050∞402510] 5001520025 601501020∞ 40201001025 252010055 1025025550 用矩阵a,(n为顶点个数)存放各边权的邻接矩阵，行向量pb、index,、index, 日分别用来存P标号信息、标号顶点顺序、标号顶点索引、最短通路的值其中分 p0=当第项点已标号 (0当第顶点未标号 index,()存放始点到第i点最短通路中第i项点前一项点的序号 d()存放由始点到第i点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab程序如下： a2:3i9a2:-20a2:23a1,6-10: ngth(a))=0;pb(1)=1;index1-1;index2-ones(1,length(a)); d(t A+ cmpb=find cemp)=1; 2-iidlindex ndex2 (mp)(,index1)) =d(te nindexl,index2 赋权邻接矩阵，其分量为 ,-7,eE 0. 其它 -76

-76- 城市间的票价最便宜的路线图。 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ∞ ∞ ∞ ∞ ∞ ∞ 10 25 25 55 0 25 20 10 0 55 40 20 10 0 10 25 15 0 10 20 50 0 15 20 25 0 50 40 25 10 用矩阵an×n （n 为顶点个数）存放各边权的邻接矩阵，行向量 pb、 1 index 、 2 index 、 d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分 量 ⎩ ⎨ ⎧ = 当第 顶点未标号 当第 顶点已标号 i i pb i 0 1 ( ) ； ( ) 2 index i 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； d(i) 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的 Matlab 程序如下： clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;temp=1; while sum(pb)<length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; temp2=find(d(index1)==d(temp)-a(temp,index1)); index2(temp)=index1(temp2(1)); end d, index1, index2 3.2 两个指定顶点之间最短路问题的数学表达式 假设有向图有 n 个顶点，现需要求从顶点 1 到顶点 n 的最短路。设W = wij n×n ( ) 为 赋权邻接矩阵，其分量为 ⎩ ⎨ ⎧ ∞ ∈ = , 其它 w(v v ), v v E w i j i j ij

决策变量为x。,当x。=1,说明弧y,y,位于顶点1至顶点n的路上：否则xn=0。其 数学规划表达式为 min∑w,y 1,i=1 st Ex-Ex=-1.i=n 0,i≠l,n xy=0或1 例10在图3中，用点表示城市，现有A,B,B,CC,C,D共7个城市。点与 连线 的数字表 路的长度。现计划从城市 93 D 图37个城市可的连线图 编写LNGO程序如下： mode cities/A,Bl,B2,C1,C2,C3,D/: 2c9c62'6c1.21c1,B1c2,B1c3,B2c1, endset 4331231134: ):!城市的个数 品a end 例1（无向图的最短路问题）求图4中到的最短路。 例0处理的问偶 -7-

-77- 决策变量为 ij x ，当 xij = 1，说明弧 i j v v 位于顶点 1 至顶点 n 的路上；否则 xij = 0。其 数学规划表达式为 ∑v v ∈E ij ij i j min w x s.t. ⎪ ⎩ ⎪ ⎨ ⎧ ≠ − = = ∑ − ∑ = ∈ = ∈ = i n i n i x x n v v E j ji n v v E j ij i j j i 0, 1, 1, 1, 1 1 1 xij = 0 或1 例 10 在图 3 中，用点表示城市，现有 A, B1, B2 ,C1,C2 ,C3 , D 共 7 个城市。点与 点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 A 到城市 D 铺设一条天然气管道，请设计出最小价格管道铺设方案。 图 3 7 个城市间的连线图 编写 LINGO 程序如下： model: sets: cities/A,B1,B2,C1,C2,C3,D/; roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1, B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; endsets data: w=2 4 3 3 1 2 3 1 1 3 4; enddata n=@size(cities); !城市的个数; min=@sum(roads:w*x); @for(cities(i)|i #ne#1 #and# i #ne#n: @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i))); @sum(roads(i,j)|i #eq#1:x(i,j))=1; @sum(roads(i,j)|j #eq#n:x(i,j))=1; end 例 11（无向图的最短路问题）求图 4 中 1 v 到 11 v 的最短路。 分析 例 10 处理的问题属于有向图的最短路问题，本例是处理无向图的最短路问 题，在处理方式上与有向图的最短路问题有一些差别，这里选择赋权邻接矩阵的方法编 写 LINGO 程序