第五章图与网络模型及方法 §1概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼 斯堡的七座桥”。1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年,凯莱在计数烷CnH2n2的同分异构物时,也发现了“树”。哈密尔顿于1859年提 出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈,近几十年 来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和 方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会 学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问 题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。当 然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功。欧拉为了解决 这个问题,采用了建立数学模型的方法。他将每一块陆地用一个点来代替,将每一座桥 用连接相应两点的一条线来代替,从而得到一个有四个“点”,七条“线”的“图”。问 题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点 给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联,将这个 判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问题, 而且开创了图论研究的先河 图与网络是运筹学( Operations Research)中的一个经典和重要的分支,所研究的 问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等 诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都 是图与网络的基本问题 我们首先通过一些例子来了解网络优化问题。 例1最短路问题(SPP- shortest path problem) 名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的 公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运 行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路 例2公路连接问题 某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其 中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
-44- 第五章 图与网络模型及方法 §1 概论 图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼 斯堡的七座桥”。1847 年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年，凯莱在计数烷 CnH2n+2 的同分异构物时，也发现了“树”。哈密尔顿于 1859 年提 出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年 来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和 方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会 学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问 题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥 用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问 题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点， 给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个 判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题， 而且开创了图论研究的先河。 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的 问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等 诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都 是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例 1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的 公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运 行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例 2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其 中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总 成本最小? 例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)问题。所以上面例子中介绍的问题都是网络优化问题。由于多 数网络优化问题是以网络上的流(fow)为研究的对象,因此网络优化又常常被称为网 络流( network flows)或网络流规划等。 下面首先简要介绍图与网络的一些基本概念。 §2图与网络的基本概念 21无向图 个无向图( undirected graph)G是由一个非空有限集合V(G)和V(G)中某些元素 的无序对集合E(G)构成的二元组,记为G=(V(G),E(G)。其中 V(G)={v1,V2…,vn}称为图G的顶点集( vertex set)或节点集( node set),(G)中 的每一个元素v(i=1,2,…,n)称为该图的一个顶点( vertex)或节点(node) E(G)={e1,e2…;em}称为图G的边集( edge set),E(G)中的每一个元素e(即(G) 中某两个元素v的无序对)记为ek=(,")或ek=V"=""1(k=1,2,…,m), 被称为该图的一条从v到v,的边(edge)。 当边e=""时,称v,"为边e的端点,并称v与v相邻( adjacent;:边e称 为与顶点v,关联( (incident)。如果某两条边至少有一个公共端点,则称这两条边在 图G中相邻 边上赋权的无向图称为赋权无向图或无向网络( undirected network)。我们对图和 网络不作严格区分,因为任何图总是可以赋权的 个图称为有限图,如果它的顶点集和边集都有限。图G的顶点数用符号|或
-45- 个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总 成本最小？ 例 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 v 称为图 G 的顶点集（vertex set）或节点集（node set）， V (G) 中 的每一个元素 v (i 1,2, ,n) i = 称为该图的一个顶点（vertex）或节点（node）； ( ) { , , , } 1 2 m E G = e e 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, ,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 | 或
v(G)表示,边数用E或E(G)表示 当讨论的图只有一个时,总是用G来表示这个图。从而在图论符号中我们常略去 字母G,例如,分别用V,E,v和E代替(G),E(G)V(G)和E(G) 端点重合为一点的边称为环(lop) 一个图称为简单图( simple graph),如果它既没有环也没有两条边连接同一对顶点 2.2有向图 定义一个有向图( directed graph或 digraph)G是由一个非空有限集合V和V中 某些元素的有序对集合A构成的二元组,记为G=(V,A)。其中V={v1,v2…vn}称 为图G的顶点集或节点集,V中的每一个元素v(i=1,2,…,n)称为该图的一个顶点 或节点;A={a12a2,…,an}称为图G的弧集( arc set),A中的每一个元素a4(即V中 某两个元素v,",的有序对)记为ak=(V,)或ak=vv(k=12…,m),被称为该图 的一条从v到v,的弧(arc) 当弧ak=v"时,称为ak的尾(tai,v,为a的头(head),并称弧ak为v,的 出弧( outgoing arc),为v,的入弧( Incoming arc) 对应于每个有向图D,可以在相同顶点集上作一个图G,使得对于D的每条弧 G有一条有相同端点的边与之相对应。这个图称为D的基础图。反之,给定任意图G, 对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这 样的有向图称为G的一个定向图。 以下若未指明“有向图”三字,“图”字皆指无向图。 23完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图 complete graph)。n个顶点 的完全图记为Kn。 若I(G)=XUY,X∩Y=Φ,|X‖Y≠0(这里X|表示集合X中的元素个 数),X中无相邻顶点对,Y中亦然,则称G为二分图( bipartite graph);特别地,若 vx∈X,vy∈Y,则xy∈E(G),则称G为完全二分图,记成kwpn 24子图 图H叫做图G的子图( subgraph),记作HcG,如果V(H)cV(G) E(H)cE(G)。若H是G的子图,则G称为H的母图 G的支撑子图( spanning subgraph,又成生成子图)是指满足V(H)=V(G)的子 25顶点的度 设v∈V(G),G中与v关联的边数(每个环算作两条边)称为v的度( degree,记 作d(v)。若d(v)是奇数,称v是奇顶点( odd point);d(v)是偶数,称v是偶顶点(even poin)。关于顶点的度,我们有如下结果 ∑(v)=2s (i)任意一个图的奇顶点的个数是偶数。 26图与网络的数据结构 网络优化研究的是网络上的各种优化模型与算法.为了在计算机上实现网络优化的 46-
-46- (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 v 称 为图 G 的顶点集或节点集， V 中的每一个元素 v (i 1,2, ,n) i = 称为该图的一个顶点 或节点； { , , , } A = a1 a2 am 称为图 G 的弧集（arc set）， A 中的每一个元素 k a (即 V 中 某两个元素 i j v , v 的有序对) 记为 ( , ) k i j a = v v 或 a v v (k 1,2, ,n) k = i j = ，被称为该图 的一条从 i v 到 j v 的弧（arc）。 当弧 k i j a = v v 时，称 i v 为 k a 的尾（tail）， j v 为 k a 的头（head），并称弧 k a 为 i v 的 出弧（outgoing arc），为 j v 的入弧（incoming arc）。 对应于每个有向图 D ，可以在相同顶点集上作一个图 G ，使得对于 D 的每条弧， G 有一条有相同端点的边与之相对应。这个图称为 D 的基础图。反之，给定任意图 G ， 对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这 样的有向图称为 G 的一个定向图。 以下若未指明“有向图”三字，“图”字皆指无向图。 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点 的完全图记为 Kn 。 若 V (G) = X Y ， X Y = ，| 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 图与网络的数据结构 网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络优化的
算法,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说, 算法的好坏与网络的具体表示方法,以及中间结果的操作方案是有关系的。这里我们介 绍计算机上用来描述图与网络的5种常用表示方法:邻接矩阵表示法、关联矩阵表示法、 弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中,我们首先假设 G=(,A)是一个简单有向图,Fn,AFm,并假设V中的顶点用自然数1,2,…,n 表示或编号,A中的弧用自然数1,2,…,m表示或编号。对于有多重边或无向网络的情 况,我们只是在讨论完简单有向图的表示方法之后,给出一些说明 (i)邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵( adjacency matrix)的形式存储在计算机中。图 G=(,A)的邻接矩阵是如下定义的:C是一个n×n的0-1矩阵,即 C=(c1)nxn∈{0,1}", (i,j)∈A 0,(,)A 也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为1:否则为0。 可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有n2个元素中,只有m 个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络 中查找弧的时间。 例7对于右图所示的图,可以用邻接矩阵表示为 01100 00010 01000 00101 00110 同样,对于网络中的权,也可以用类似邻接矩阵的n×n矩阵表示。只是此时一条 弧所对应的元素不再是1,而是相应的权而已。如果网络中每条弧赋有多种权,则可以 用多个矩阵表示这些权 (i)关联矩阵表示法 关联矩阵表示法是将图以关联矩阵( incidence matrⅸ)的形式存储在计算机中.图 G=(,A)的关联矩阵B是如下定义的:B是一个n×m的矩阵,即 B=(bk)nxm∈{-1,0,1} 1,∈V,k=(i,j)∈A, b={-1,∈F,k=(1)∈A 0,其它 也就是说,在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如 果一个节点是一条弧的起点,则关联矩阵中对应的元素为1:如果一个节点是一条弧的 终点,则关联矩阵中对应的元素为-1:;如果一个节点与一条弧不关联,则关联矩阵中 对应的元素为0。对于简单图,关联矩阵每列只含有两个非零元(一个+1,一个-1) 可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有mm个元素中,只 有2m个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于 -47
-47- 算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说， 算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介 绍计算机上用来描述图与网络的 5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、 弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设 G = (V, A) 是一个简单有向图， |V |= n,| A |= m ，并假设 V 中的顶点用自然数 1,2, ,n 表示或编号， A 中的弧用自然数 1,2, ,m 表示或编号。对于有多重边或无向网络的情 况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图 G = (V, A) 的邻接矩阵是如下定义的： C 是一个 nn 的 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 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络 中查找弧的时间。 例 7 对于右图所示的图，可以用邻接矩阵表示为 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 同样，对于网络中的权，也可以用类似邻接矩阵的 nn 矩阵表示。只是此时一条 弧所对应的元素不再是 1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以 用多个矩阵表示这些权。 （ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中．图 G = (V, A) 的关联矩阵 B 是如下定义的： B 是一个 nm 的矩阵，即 n m B bik n m = ( ) {−1,0,1} ， − = = = 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)和(54),则关联矩阵表示为 11000000 101-10000 0-101-10-10 00-10110-1 100000-1 同样,对于网络中的权,也可以通过对关联矩阵的扩展来表示。例如,如果网络中 每条弧有一个权,我们可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的 行中。如果网络中每条弧赋有多个权,我们可以把关联矩阵增加相应的行数,把每一条 弧所对应的权存储在增加的行中。 (ⅲi)弧表示法 弧表表示法将图以弧表( arc list)的形式存储在计算机中。所谓图的弧表,也就是 图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需2m个存 储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对 应地用额外的存储单元表示。例如,例7所示的图,假设弧(1,2),(1,3),(24),(3,2) (4,3),(4,5),(5,3)和(54)上的权分别为8,9,6,4,0,3,6和7,则弧表表示如下: 起点 536 为了便于检索,一般按照起点、终点的字典序顺序存储弧表,如上面的弧表就是按 照这样的顺序存储的 (ⅳv)邻接表表示法 邻接表表示法将图以邻接表( adjacency lists)的形式存储在计算机中。所谓图的 邻接表,也就是图的所有节点的邻接表的集合:而对每个节点,它的邻接表就是它的所 有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有 弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的 另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数 组表示。例如,例7所示的图,邻接表表示为 这是一个5维指针数组,每一维(上面表示法中的每一行)对应于一个节点的邻接 表,如第1行对应于第1个节点的邻接表(即第1个节点的所有出弧)。每个指针单元 的第1个数据域表示弧的另一个端点(弧的头),后面的数据域表示对应弧上的权。如 第1行中的“2”表示弧的另一个端点为2(即弧为(1,2),“8”表示对应弧(1,2)上的
-48- 关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 例 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 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 所示的图，邻接表表示为 这是一个 5 维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接 表，如第 1 行对应于第 1 个节点的邻接表（即第 1 个节点的所有出弧）。每个指针单元 的第 1 个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如 第 1 行中的“2”表示弧的另一个端点为 2（即弧为（1,2）），“8”表示对应弧(1,2)上的