第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ 例3 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？ 例4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 例5 旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 例6 运输问题（transportation problem） 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等。 下面首先简要介绍图与网络的一些基本概念。 §2 图与网络的基本概念 2.1 无向图 一个无向图(undirected graph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组，记为。其中称为图的顶点集（vertex set）或节点集（node set）， 中的每一个元素称为该图的一个顶点（vertex）或节点（node）；称为图的边集（edge set），中的每一个元素(即中某两个元素的无序对)?记为或 ，被称为该图的一条从到的边（edge）。 当边时，称为边的端点，并称与相邻（adjacent）；边称为与顶点关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图中相邻。 边上赋权的无向图称为赋权无向图或无向网络（undirected network）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。 一个图称为有限图，如果它的顶点集和边集都有限。图的顶点数用符号或表示，边数用或表示。 当讨论的图只有一个时，总是用来表示这个图。从而在图论符号中我们常略去字母，例如，分别用和代替和。 端点重合为一点的边称为环(loop)。 一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。 2.2 有向图 定义 一个有向图（directed graph或 digraph）是由一个非空有限集合和中某些元素的有序对集合构成的二元组，记为。其中称为图的顶点集或节点集， 中的每一个元素称为该图的一个顶点或节点；称为图的弧集（arc set），中的每一个元素(即中某两个元素的有序对)?记为或，被称为该图的一条从到的弧（arc）。 当弧时，称为的尾（tail），为的头（head），并称弧为的出弧（outgoing arc），为的入弧（incoming arc）。 对应于每个有向图，可以在相同顶点集上作一个图，使得对于的每条弧，有一条有相同端点的边与之相对应。这个图称为的基础图。反之，给定任意图，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为的一个定向图。 以下若未指明“有向图”三字，“图”字皆指无向图。 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。个顶点的完全图记为。 若，，（这里表示集合中的元素个数），中无相邻顶点对，中亦然，则称为二分图(bipartite graph)；特别地，若，则，则称为完全二分图，记成。 2.4 子图 图叫做图的子图（subgraph），记作，如果，。若是的子图，则称为的母图。 的支撑子图（spanning subgraph，又成生成子图）是指满足的子图。 2.5 顶点的度 设，中与关联的边数（每个环算作两条边）称为的度(degree)，记作。若是奇数，称是奇顶点(odd point)；是偶数，称是偶顶点(even point)。关于顶点的度，我们有如下结果： (i)  (ii) 任意一个图的奇顶点的个数是偶数。 2.6 图与网络的数据结构 网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设是一个简单有向图，，并假设中的顶点用自然数表示或编号，中的弧用自然数表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图的邻接矩阵是如下定义的：是一个的矩阵，即 ，  也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有个元素中，只有个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。 例7 对于右图所示的图，可以用邻接矩阵表示为  同样，对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。 （ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中．图的关联矩阵是如下定义的：是一个的矩阵，即 ，  也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个，一个）。可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有个元素中，只有个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为  同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。 （iii）弧表示法 弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。例如，例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)上的权为8；“3”表示弧的另一个端点为3（即弧为(1,3)），“9”表示对应弧（1，3）上的权为9。又如，第5行说明节点5出发的弧有(5,3)、(5,4)，他们对应的权分别为6和7。 对于有向图，一般用表示节点的邻接表，即节点的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，，等。这种记法我们在本书后面将会经常用到。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（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。此时该网络图可以用前向星形表示法表示如下： 节点对应的出弧的起始地址编号数组（记为） 节点号 1 2 3 4 5 6  起始地址 1 3 4 6 7 9   记录弧信息的数组 弧编号 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   在数组中，其元素个数比图的节点数多1（即），且一定有，。对于节点，其对应的出弧存放在弧信息数组的位置区间为 ， 如果，则节点没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（）记录每个节点出发的弧的起始编号。 前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式： 节点对应的入弧的起始地址编号数组（记为） 节点号 1 2 3 4 5 6  起始地址 1 1 3 6 8 9   记录弧信息的数组 弧编号 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）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的数组和如下的数组即可。这相当于一种紧凑的双向星形表示法如下所示： 两种表示法中的弧的对应关系（记为） 反向法中弧编号 1 2 3 4 5 6 7 8  正向法中弧编号 4 1 2 5 7 8 3 6   对于网络图的表示法，我们作如下说明： ① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。 ② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。 ③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0和，而不含有，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。 2.7 轨与连通 ，其中，，，，与关联，称是图的一条道路(walk)，为路长，顶点和分别称为的起点和终点，而称为它的内部顶点。 若道路的边互不相同，则称为迹(trail)。若道路的顶点互不相同，则称为轨(path)。 称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。 若图的两个顶点间存在道路，则称和连通(connected)。间的最短轨的长叫做间的距离。记作。若图的任二顶点均连通，则称是连通图。 显然有： (i) 图是一条轨的充要条件是是连通的，且有两个一度的顶点，其余顶点的度为2； (ii) 图是一个圈的充要条件是是各顶点的度均为2的连通图。 §3 应用—最短路问题 3.1 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图的顶点，两城镇间的直通铁路为图相应两顶点间的边，得图。对的每一边，赋以一个实数—直通铁路的长度，称为的权，得到赋权图。的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距从近到远为顺序，依次求得到的各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令，对，令，，。 (ii) 对每个（），用  代替。计算，把达到这个最小值的一个顶点记为，令。 (iii). 若，停止；若，用代替，转(ii)。 算法结束时，从到各顶点的距离由的最后一次的标号给出。在进入之前的标号叫T标号，进入时的标号叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，至各项点的最短路也在图上标示出来了。 例9 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。  用矩阵（为顶点个数）存放各边权的邻接矩阵，行向量、、、分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ；  存放始点到第点最短通路中第顶点前一顶点的序号；  存放由始点到第点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;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]; index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end index2(temp)=index; end d, index1, index2 3.2 每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。 假设图权的邻接矩阵为，  来存放各边长度，其中：  ；  之间没有边，在程序中以各边都不可能达到的充分大的数代替；  是之间边的长度，。 对于无向图，是对称矩阵，。 Floyd算法的基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。 计算时用迭代公式：  是迭代次数，。 最后，当时，即是各顶点之间的最短通路值。 例10 用Floyd算法求解例1。 矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); b=a+a';path=zeros(length(b)); for k=1:6 for i=1:6 for j=1:6 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end b, path §4 树 4.1 基本概念 连通的无圈图叫做树，记之为。若图满足，，则称是的生成树。图连通的充分必要条件为有生成树。一个连通图的生成树的个数很多，用表示的生成树的个数，则有公式 公式 (Caylay)。 公式 。 其中表示从上删除边，表示把的长度收缩为零得到的图。 树有下面常用的五个充要条件。 定理1 （i）是树当且仅当中任二顶点之间有且仅有一条轨道。 （ii）是树当且仅当无圈，且。 （iii）是树当且仅当连通，且。 （iv）是树当且仅当连通，且，不连通。 （v）是树当且仅当无圈，，恰有一个圈。 4.2 应用—连线问题 欲修筑连接个城市的铁路，已知城与城之间的铁路造价为，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。 下面介绍构造最小生成树的两种常用算法。 prim算法构造最小生成树 设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。 prim算法如下： （i），； （ii）while     end 例11 用prim算法求右图的最小生成树。 我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下： clc;clear; M=1000; a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; a=[a;zeros(2,7)]; a=a+a';a(find(a==0))=M; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result Kruskal算法构造最小生成树 科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下: (i)选，使得。 (ii)若已选好，则从中选取，使得 ① 中无圈，且 ② 。 (iii)直到选得为止。 例12 用Kruskal算法构造例3的最小生成树。 我们用存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号改记为此边的另一序号，同时把后面边中所有序号为的改记为。此方法的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab程序如下： clc;clear; M=1000; a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; [i,j]=find((a~=0)&(a~=M)); b=a(find((a~=0)&(a~=M))); data=[i';j';b'];index=data(1:2,:); loop=max(size(a))-1; result=[]; while length(result)<loop temp=min(data(3,:)); flag=find(data(3,:)==temp); flag=flag(1); v1=data(1,flag);v2=data(2,flag); if index(1,flag)~=index(2,flag) result=[result,data(:,flag)]; end if v1>v2 index(find(index==v1))=v2; else index(find(index==v2))=v1; end data(:,flag)=[]; index(:,flag)=[]; end result §5 匹配问题 定义 若，，与无公共端点（），则称为图的一个对集；中的一条边的两个端点叫做在对集中相配；中的端点称为被许配；中每个顶点皆被许配时，称为完美对集；中已无使的对集，则称为最大对集；若中有一轨，其边交替地在对集内外出现，则称此轨为的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。 若把可增广轨上在外的边纳入对集，把内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个。 1957年，贝尔热(Berge)得到最大对集的充要条件： 定理2 是图中的最大对集当且仅当中无可增广轨。 1935年，霍尔(Hall)得到下面的许配定理： 定理3 为二分图，与是顶点集的划分，中存在把中顶点皆许配的对集的充要条件是，，则，其中是中顶点的邻集。 由上述定理可以得出： 推论1：若是（正则2分图，则有完美对集。 所谓正则图，即每顶点皆度的图。 由此推论得出下面的婚配定理： 定理4 每个姑娘都结识位小伙子，每个小伙子都结识位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。 人员分派问题等实际问题可以化成对集来解决。 人员分派问题：工作人员去做件工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ 这个问题的数学模型是：是二分图，顶点集划分为，，，当且仅当适合做工作时，，求中的最大对集。 解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。 匈牙利算法： （i）从中任意取定一个初始对集。 （ii）若把中的顶点皆许配，停止，即完美对集；否则取中未被许配的一顶点，记，。 （iii）若，停止，无完美对集；否则取。 （iv）若是被许配的，设，，，转（iii）；否则，取可增广轨，令，转（ii）。 把以上算法稍加修改就能够用来求二分图的最大对集。 最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图的每边加了权，表示干工作的效益，求加权图上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。 定义 若映射，满足， ， 则称是二分图的可行顶点标号。令 ， 称以为边集的的生成子图为相等子图，记作。 可行顶点标号是存在的。例如  。 定理5 的完美对集即为的权最大的完美对集。 Kuhn-Munkres算法 （i）选定初始可行顶点标号，确定，在中选取一个对集。 （ii）若中顶点皆被许配，停止，即的权最大的完美对集；否则，取中未被许配的顶点，令， 。 (iii)若，转（iv）；若，取 ， ，  ，。 （iv）选中一顶点，若已被许配，且，则，，转（iii）；否则，取中一个可增广轨，令 ， 转（ii）。 其中是中的相邻顶点集。 §6 Euler图和Hamilton图 6.1 基本概念 定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。 直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。 定理7 （i）是Euler图的充分必要条件是连通且每顶点皆偶次。 （ii）是Euler图的充分必要条件是连通且，是圈，。 （iii）中有Euler迹的充要条件是连通且至多有两个奇次点。 定义 包含的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或圈；含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 6.2 Euler回路的Fleury算法 1921年，Fleury给出下面的求Euler回路的算法。 Fleury算法： 1o. ，令。 2o. 假设迹已经选定，那么按下述方法从中选取边： （i）和相关联； （ii）除非没有别的边可选择，否则不是的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。 3o. 当第2步不能再执行时，算法停止。 6.3 应用 6.3.1 邮递员问题 中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。 上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。 显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。 对于非Euler图，1973年，Edmonds和Johnson给出下面的解法： 设是连通赋权图。 （i）求。 （ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。 （iii）构造完全赋权图，以为顶点集，以为边的权。 （iv）求中权之和最小的完美对集。 （v）求中边的端点之间的在中的最短轨。 （vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。 （vii）在（vi）中得的图上求Euler回路即为中国邮递员问题的解。 多邮递员问题： 邮局有位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。 kPP的数学模型如下： 是连通图，，求的回路，使得 （i），， （ii）， （iii） 6.3.2 旅行商（TSP）问题 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。 一个可行的办法是首先求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈。 （i）对于，构造新的Hamilton圈: , 它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。 （ii）转（i），直至无法改进，停止。 用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用Kruskal算法加以说明。假设是中的最优圈。则对于任何顶点，是在中的Hamilton轨，因而也是的生成树。由此推知：若是中的最优树，同时和是和关联的两条边，并使得尽可能小，则将是的一个下界。 这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。 例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表： L M N Pa Pe T  L  56 35 21 51 60  M 56  21 57 78 70  N 35 21  36 68 68  Pa 21 57 36  51 61  Pe 51 78 68 51  13  T 60 70 68 61 13   解：编写程序如下： clc,clear a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60; a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70; a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61; a(5,6)=13; a(6,:)=0; a=a+a'; c1=[5 1:4 6]; L=length(c1); flag=1; while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end end end sum1=0; for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1)); end circle=c1; sum=sum1; c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动 flag=1; while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end end end sum1=0; for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1)); end if sum1<sum sum=sum1; circle=c1; end circle,sum §7 最大流问题 7.1 最大流问题的数学描述 7.1.1 网络中的流 定义 在以为节点集，为弧集的有向图上定义如下的权函数： （i）为孤上的权函数，弧对应的权记为，称为孤的容量下界（lower bound）； （ii）为弧上的权函数，弧对应的权记为，称为孤的容量上界，或直接称为容量（capacity）； （iii）为顶点上的权函数，节点对应的权记为，称为顶点的供需量（supply／demand）； 此时所构成的网络称为流网络，可以记为 。 由于我们只讨论为有限集合的情况，所以对于弧上的权函数和顶点上的权函数，可以直接用所有孤上对应的权组成的有限维向量表示，因此有时直接称为权向量，或简称权。由于给定有向图后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。 在流网络中，弧的容量下界和容量上界表示的物理意义分别是：通过该弧发送某种“物质”时，必须发送的最小数量为，而发送的最大数量为。顶点对应的供需量则表示该顶点从网络外部获得的“物质”数量（时），或从该顶点发送到网络外部的“物质”数量（时）。下面我们给出严格定义。 定义 对于流网络，其上的一个流（flow）是指从的弧集到的一个函数，即对每条弧赋予一个实数（称为弧的流量）。如果流满足  （1） ， （2） 则称为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible network）．约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。 可见，当时，表示有个单位的流量从该项点流出，因此顶点称为供应点（supply node）或源（source），有时也形象地称为起始点或发点等；当时，表示有个单位的流量流入该点（或说被该顶点吸收），因此顶点称为需求点（demand node）或汇（sink），有时也形象地称为终止点或收点等；当时，顶点称为转运点（transshipment node）或平衡点、中间点等。此外，根据（1）可知，对于可行网络，必有  （3） 也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。 一般来说，我们总是可以把的流网络转化为的流网络进行研究。所以，除非特别说明，以后我们总是假设（即所有孤的容量下界），并将时的流网络简记为。此时，相应的容量约束（2）为 。 定义 在流网络中，对于流，如果 ， 则称为零流，否则为非零流。如果某条弧上的流量等于其容量（），则称该弧为饱和弧（saturated arc）；如果某条弧上的流量小于其容量（），则称该弧为非饱和弧；如果某条弧上的流量为 0（），则称该弧为空弧（void arc）。 7.1.2 最大流问题 考虑如下流网络：节点为网络中唯一的源点，为唯一的汇点，而其它节点为转运点。如果网络中存在可行流，此时称流的流量（或流值，flow value）为（根据（3），它自然也等于），通常记为或，即 。 对这种单源单汇的网络，如果我们并不给定和（即流量不给定），则网络一般记为。最大流问题（maximum flow problem）就是在中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。 因此，用线性规划的方法，最大流问题可以形式地描述如下：  s.t.  ， （4） . （5） 定义 如果一个矩阵的任何子方阵的行列式的值都等于，或，则称是全幺模的(totally unimodular TU，又译为全单位模的)，或称是全幺模矩阵。 定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。 7.1.3 单源和单汇运输网络 实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络化成单源单汇网络。设是的源，是的汇，具体转化方法如下： （i）在原图中增加两个新的顶点和，令其分别为新图中之单源和单汇，则中所有顶点成为之中间顶点集。 （ii）用一条容量为的弧把连接到中的每个顶点。 （iii）用一条容量为的弧把中的每个顶点连接到。 和中的流以一个简单的方式相互对应。若是中的流，则由  所定义的函数是中使得的流。反之，中的流在的弧集上的限制就是中具有相同值的流。 7.2 最大流和最小割关系 设，，，，则称为网络的一个割，其中，为尾在，头在的弧集，称  为割的容量。 定理9 是最大流，是容量最小的割的充要条件是 。 在网络中，对于轨（此轨为无向的），若，则称它为前向弧；若，则称它为后向弧。 在网络中，从到的轨上，若对所有的前向弧都有，对所有的后向弧恒有，则称这条轨为从到的关于的可增广轨。 令 ，  则在这条可增广轨上每条前向弧的流都可以增加一个量，而相应的后向弧的流可减少，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中可增广轨的存在是有意义的，因为这意味着不是最大流。 7.3 最大流的一种算法—标号法 标号法是由Ford和Fulkerson在1957年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。