图与网络模型

1、图与网络模型及方法图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次， 再回到起点。实际上任何这样的尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应

2、两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉证明了它是“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。一、图与网络的基本概念1.1 无向图一个无向图g是由一个非空有限集合)(gv和)(gv中某些元素的无序对集合)(ge构成的二元组，记为)(),(gegvg。 其中,)(21nvvvgv称为图g的顶点集，)(gv中的每一个元素), 2, 1(nivi称为该图的一个顶点；,)(21meeege称为图g的边集，)(ge中的每一个元素ke (即)(gv中 某 两 个 元 素jivv ,的 无 序 对 ) 记

3、 为),(jikvve或ijjikvvvve),2, 1(mk，被称为该图的一条从iv 到jv 的边。当边jikvve时，称jivv ,为边ke 的端点，并称jv 与iv 相邻；边ke 称为与顶点jivv ,关联。如果某两条边至少有一个公共端点，则称这两条边在图g中相邻。边上赋权的无向图称为赋权无向图或无向网络。我们对图和网络不作严格区分，因为任何图总是可以赋权的。一个图称为 有限图 ，如果它的顶点集和边集都有限。图g的顶点数用符号|v或)(g表示，边数用| e或)(g表示。当讨论的图只有一个时， 总是用g来表示这个图。从而在图论符号中我们常略去字母g，例如，分别用,ev和代替)(),(),(

4、ggegv和)(g。端点重合为一点的边称为 环。一个图称为 简单图 ，如果它既没有环也没有两条边连接同一对顶点。1.2 有向图定义一个有向图g是由一个非空有限集合v和v中某些元素的有序对集合a构成的二元组，记为),(avg。其中,21nvvvv称为图g的顶 点 集 ，v中 的 每 一 个 元 素),2 , 1(nivi称 为 该 图 的 一 个 顶 点 ；,21maaaa称为图g的弧集，a中的每一个元素ka (即v中某两个元素jivv ,的有序对 ) 记为),(jikvva或),2 , 1(nkvvajik， 被称为该图的一条从iv 到jv 的弧。当弧jikvva时，称iv 为ka 的尾，jv

5、 为ka 的头，并称弧ka 为iv 的出弧，为jv 的入弧。对应于每个有向图d ，可以在相同顶点集上作一个图g，使得对于 d 的每条弧，g有一条有相同端点的边与之相对应。这个图称为d 的基础图。反之，给定任意图g，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为g的一个定向图。以下若未指明“有向图”三字， “图”字皆指无向图。1.3 完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图。n 个顶点的完全图记为nk 。若yxgv)(，yx，0|yx（这里| x表示集合 x 中的元素个数）， x 中无相邻顶点对，y 中亦然，则称g为二分图；特别地

6、，若yyxx,，则)(gexy，则称g为完全二分图，记成| |,|yxk。1.4 子图图 h 叫做图g的子图 ， 记作gh， 如果)()(gvhv，)()(gehe。g的支撑子图（又叫生成子图）是指满足)()(gvhv的子图 h 。1.5 顶点的度设)(gvv，g中与 v关联的边数（每个环算作两条边）称为v 的度，记作)(vd。若)(vd是奇数，称 v是奇顶点；)(vd是偶数，称 v是偶顶点。关于顶点的度，我们有如下结果：(i) vvvd2)(ii) 任意一个图的奇顶点的个数是偶数。1.6 图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法为了在计算机上实现网络优化的算法，必须有一种

7、方法（即数据结构）在计算机上来描述图与网络。矩阵是研究图的一种有力工具，这里我们介绍用来描述图与网络的两种常用表示方法：邻接矩阵表示法、关联矩阵表示法。在 下 面 的 讨论 中 ， 我 们 首先 假 设),(avg是一 个 简 单 有 向 图 ，manv| ,|，并假设v中的顶点用自然数n,2 ,1表示或编号，a中的弧用自然数m,2 , 1表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。（i）邻接矩阵表示法图),(avg的邻接矩阵是如下定义的：c是一个nn的10矩阵，即nnnnijcc 1 , 0)(，.),(,0,),(, 1ajiajici

8、j也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为 0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有2n个元素中， 只有 m个为非零元。 如果网络比较稀疏， 这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。例 1 对于右图所示的图，可以用邻接矩阵表示为0110010100000100100000110同样，对于网络中的权， 也可以用类似邻接矩阵的nn矩阵表示。 只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。（ii）关联矩阵表示法图),(avg的关联矩阵 b 是如下定义的： b 是一个

9、mn的矩阵，即mnmnikbb 1 , 0, 1)(，.,0,),(, 1,),(, 1其它aijkvjajikvjbik也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元 （一个1，一个1） 。可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有nm个元素中，只有m2个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的

10、理论性质，因此它在网络优化中是非常重要的概念。例 2 对于例 1 所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为1110000010110100010110100000110100000011同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。1.7 路与连通kkveevevw2110，其

11、中)(geei，ki1，)(gvvj，kj0，ie与iivv,1关联，称w是图g的一条 通路，k为路长，顶点0v 和kv 分别称为w的起点和终点，而121,kvvv称为它的内部顶点。若通路w的边互不相同， 则w称为迹。 若通路w的顶点互不相同， 则w称为路。称一条 通路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的路叫做 圈。若图g的两个顶点vu,间存在通路，则称 u 和 v连通。vu, 间的最短路的长叫做vu, 间的距离。记作),(vud。若图g的任二顶点均连通，则称g是连通图。显然有：(i) 图 p 是一条路的充要条件是p 是连通的，且有两个一度的顶点，其余顶点的度为 2；(ii

12、) 图c是一个圈的充要条件是c是各顶点的度均为2 的连通图。二、 应用最短路问题2.1 两个指定顶点之间的最短路径最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一个算法。最短路问题有很多算法，其中最基本的一个是 dijkstra 算法。1. 算法思想若路kkuuuup110是从0u 到ku 的最短路，则110kuuup必是0u 到1ku的最短路。基于这一原理，算法由近及远地逐次求出0u 到其它各点 的最短路。下面通过例子说明具体做法。u0 u1 u2 u3 u4 u5 u6 u7 12223313444566778（1）令00us，00svs，求0u 到0s

13、 中最近点的最短路，结果找到1u 。（2）令:100uss，00svs，求0u 到0s 中最近点的最短路。此时除了考虑0u 到0s 的直接连边外，还要考虑0u 通过1u 向0s 的连边，即选取0s 中一点u使得),(),(min),(0,000vuwuuduudsvsu。(*) 结果找到2u 。一般地，若,10kkuuus以及相应的最短路已找到。则可应用(*)式来选取新的u，获得0u 到u的最短路。2算法实现标号法其基本思想是按距0u 从近到远为顺序，依次求得0u 到g的各顶点的最短路和距离，直至0v （或直至g的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该

14、算法。(i) 令0)(0ul，对0uv，令)(vl，00us，0i。(ii) 对每个isv（iisvs） ，用)()(),(minuvwulvlisu代替)(vl。计算)(minvlisv，把达到这个最小值的一个顶点记为1iu，令11iiiuss。(iii). 若1|vi，停止；若1|vi，用1i代替i，转(ii) 。算法结束时，从0u 到各顶点 v的距离由 v的最后一次的标号)(vl给出。在 v进入is 之前的标号)(vl叫 t 标号， v进入is 时的标号)(vl叫 p 标号。算法就是不断修改各项点的t 标号，直至获得 p 标号。若在算法运行过程中，将每一顶点获得 p 标号所由来的边在图上

15、标明， 则算法结束时，0u 至各项点的最短路也在图上标示出来了。例 3 某公司在六个城市621,ccc中有分公司，从ic 到jc 的直接航程票价记在下述矩阵的),(ji位置上。 （表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。055252510550102025251001020402010015252015050102540500用矩阵nna（ n为顶点个数）存放各边权的邻接矩阵， 行向量pb、1index 、2index 、d分别用来存放 p 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量顶点未标号当第顶点已标号当第iiipb01)(；)(

16、2iindex存放始点到第i点最短通路中第i顶点前一顶点的序号；)(id存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的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=one

17、s(1,length(a); d(1:length(a)=m;d(1)=0;temp=1; while sum(pb)=2 index=index(1); end index2(temp)=index; endd, index1, index2 2.2 每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用dijkstra 算法。具体方法是：每次以不同的顶点作为起点，用dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为)(3no。第二种解决这一问题的方法是由 floyd r w 提出的算

18、法，称之为floyd 算法。假设图g权的邻接矩阵为0a ，nnnnnnaaaaaaaaaa2122221112110来存放各边长度，其中：0iiani,2, 1；ijaji,之间没有边， 在程序中以各边都不可能达到的充分大的数代替；ijijwaijw 是ji,之间边的长度，nji,2 ,1,。对于无向图，0a 是对称矩阵，jiijaa。floyd 算法的基本思想是：递推产生一个矩阵序列nkaaaa,10，其中),(jiak表示从顶点iv 到顶点jv 的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：),(),(),(min(),(111jkakiajiajiakkkkk是迭代次

19、数，nkji,2, 1,。最后，当nk时，na 即是各顶点之间的最短通路值。例4 用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

20、); 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 2.3 应用案例：截断切割问题“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的） ，通常要经过 6 次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面不平行时，因调整刀具需额外费用e。设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用

21、最少。用以下实例验证你的方法：待加工长方体的长、宽、高分别为10、14.5、19 和 3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1 元， r 和 e的数据有以下 4 组：a. r=1,e=0; b. r=1.5,e=0; c. r=8,e=0; d. r=1.5;2e15. （一） 问题分析及模型建立1. 问题分析这是一个最优化问题，求切割顺序，使总的加工费用最少。决策变量为切割顺序，用621,xxxx来表示切割顺序，ix 表示第 i 次切割，可以用1，2，, ， 6，分别表示左、右、前、后、上、下方向的切割，621,xxx互不相同，

22、可以取1，2，, ， 6,的任意全排列。目标函数：加工费用，由切割费用和刀具调整费用构成。该问题已经比较明确，问题中的已知条件有：（1） 待加工长方体与成品长方体对应表面平行；（2） 切割费用与切割面的面积成正比， 具体地说就是垂直切割费用为1 元/cm2，水平切割费用为 r 元/cm2，且仅当先后两次垂直切割的切割面不平行时，才需要调整刀具，调整刀具的费用为e。（3） 水平工作台接触的长方体底面是事先指定的；（4） 不考虑第一次切割前的刀具调整费用。2. 建立模型用图论建立模型并求其解。分两种情况分别讨论：情形一： e=0时，构造一个赋权有向图g（v，e） 。把整个加工过程中长方体工作的所有

23、可能状态作为顶点，若长方体工件可以由顶点 u 所代表的状态， 经过一次切割变为顶点v 所代表的状态，则作一条从 u 到 v 的有向边，同时把此次切割的费用作为该边的权。可以用 0，1 组成的 6 维数组来代表各种状态或顶点，左、右、前、后、 上、 下侧多余的块已被切除， 分别对应这个数组的第1， 2， , ，6 分量取 1，还未被切去时，相应分量取0。例如， （0，0，, ， 0）代表原长方体，（1，1，, ， 1）代表最终的成品长方体， （0，1，1，0，0，1）代表原长方体右侧、前面和下面的多余块被截去后余下的新尺寸长方体，顶点集,61,2,i ,0,654321iaaaaaaav共有64

24、26个顶点。在中的任何一条从顶点（0，0，, ， 0）到顶点（ 1，1，, ， 1）的有向路径代表一连串切割施于原长方体，长方体的状态变化过程，对应的一连串切割就是一种加工方式，该有向路径的权便是加工费用。反之，任何一种加工方式都对应于中的一条有向路径。求最小费用的加工方式就转化为求赋权有向图g （v， e） 中从顶点 （0， 0， , ，0）到顶点（ 1，1，, ， 1）的最短路径。因此，只考虑平行切割边距大者先切的加工方式，从而在加工过程中工件的状态数减少。对两平行切割只考虑边距大者先切割所导致的长方体工件的状态，可以用0，1，2 组成的 3 维数组来代表各种状态，（x，y，z）表示左右、

25、前后、上下分别被切去x，y，z 刀。例如，（0，0，0）代表原长方体，（2，2，2）代表成品长方体，（0，2，1）代表原长方体的前面、后面已经被切去，上下侧厚的那一块已经被切去余下的新尺寸长方体。顶点集1,2,3i ,2,0,321iaaaav共有 27 个顶点，这些顶点代表待加工长方体在加工过程中的27 种状态。若待加工长方体可以由顶点u 代表的状态， 经过一次切割变为顶点v 代表的状态，则作一条从u 到 v 的有向边，同时把该次切割的费用作为该边的权。如此得到一个规模更小的赋权有向图g（ v，e） 。问题转化为求赋权有向图g（ v，e）中从顶点（ 0，0，0）到顶点（2，2，2）的最短路径

26、，可以用dijkstra 算法求解。若要求出所有的最优加工方式，则需要从顶点（0，0，0）到顶点（2，2，2）的全部最短路径，共有两条，其费用为437.5元。路径一： （2，2，2）（ 1，2，2）（ 1，2，1）（ 1，1，1）（ 0，1，1）（ 0，1，0）（ 0，0，0） ；路径二： （2，2，2）（ 1，2，2）（ 1，2，1）（ 1，1，1）（ 1，1，0）（ 0，1，0）（ 0，0，0） ；所对应的加工方式为：前下左后上右，前左下后上右。情形二： e 0 时。此时，两次切割之间可能需要调整刀具，其加工费用与当前最后一次垂直切割的方向有关，上述情形一的结论依然成立，可以构造一个赋权有

27、向图g （v ，e ） ，把数次切割以后待加工物体所处的状态和这些切割中最后一次垂直切割的方向合在一起作为一个顶点，若待加工长方体可以由顶点u代表的状态，经过一次切割变为顶点v 代表的状态，则作一条从u 到 v 的有向边，同时把该次切割的费用（若需要调整刀具，包括调整刀具的费用）作为该边的权。一个顶点用一个四维数组表示，前三个分量取值0，1 或 2 表示状态，第四个分量为0，1 或 2，分别表示从开始切割到该状态为止，没有垂直切割，最后一次垂直切割的方向为左右或前后，例如（1，2，0，1）代表原长方体前后两多余块和左右之厚块，且最后一次垂直切割这左右方向，令0,1,2z0,0,01zv0,1,

28、2zy,1,2;x1,2zyxv1,2y,1,2;0zx,2,3zyxv顶点集321vvvv， 共有 39个顶点。 问题转化为求赋权有向图g （v ，e ）中从顶点（ 0，0，0，0）到顶点（ 2，2，2，1）或（ 2，2，2，2）的所有最短路径。当 a0=10, 14.5, 19, a1=3, 2, 4, d1=6, 7, 9时，对于下述四种情况的最优加工方式：（1）. r=1,e=0; （2）. r=1.5,e=0; （3） . r=8,e=0; （4）. r=1.5;2e15 所得的结果如下表。r e 最优切割方式最少费用1 0 531624,536142 374 1.5 0 35146

29、2,315462 437.5 8 0 314526 540.5 1.5 2,2.5 315362,351462 437.5+3e 1.5 2.5 315462,351462,354162 445 1.5 (2.5,15) 354162 442.5 三、树3.1 基本概念连 通 的 无 圈 图 叫 做 树 ， 记 之 为 t 。 若 图g满 足)()(tvgv，)()(gete，则称 t 是g的生成树。图g连通的充分必要条件为g有生成树。一个连通图的生成树的个数很多，用)(g表示g的生成树的个数， 则有公式公式(caylay)2)(nnnk。公式)()()(egegg。其中eg表示从g上删除边

30、e，eg表示把 e的长度收缩为零得到的图。树有下面常用的五个充要条件。定理 1 （i）g是树当且仅当g中任二顶点之间有且仅有一条通路。（ii）g是树当且仅当g无圈，且1。（iii ）g是树当且仅当g连通，且1。（iv）g是树当且仅当g连通，且)(gee，eg不连通。（v）g是树当且仅当g无圈，)(gee，eg恰有一个圈。3.2 应用连线问题欲修筑连接 n 个城市的铁路，已知i城与j城之间的铁路造价为ijc ，设计一个线路图，使总造价最低。连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。下面介绍构造最小生成树的两种常用算法。3.2.1 prim 算法

31、构造最小生成树设置两个集合 p 和q,其中 p用于存放g的最小生成树中的顶点， 集合q存放g的最小生成树中的边。令集合p 的初值为1vp（假设构造最小生成树时，从顶点1v 出发） ，集合q的初值为q。prim 算法的思想是，从所有pp，pvv的边中，选取具有最小权值的边pv，将顶点 v加入集合 p 中，将边pv加入集合q中，如此不断重复，直到vp时，最小生成树构造完毕，这时集合q中包含了最小生成树的所有边。prim 算法如下：（i）1vp，q；（ii）while vp ,m i n (pvvppwpvpvvpp pvqqend 例 5 用 prim 算法求右图的最小生成树。我们用nresult

32、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; 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(t

33、emp); 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 3.2.2kruskal 算法构造最小生成树科茹斯克尔（ kruskal）算法是一个好算法。 kruskal 算法如下 : (i)选)(1gee，使得min)(1ew。(ii) 若ieee,21已选好，则从,)(21ieeege中选取1ie，使得,121iieeeeg中无圈，且min)(1iew。(iii) 直到选得1e为止。例 6 用 kruskal 算法构造例 3 的最小生成树。我们用

34、nindex2存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u 改记为此边的另一序号v，同时把后面边中所有序号为 u 的改记为 v。此方法的几何意义是： 将序号 u 的这个顶点收缩到 v顶点， u 顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。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,

35、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)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=; end result 四、匹配问题4.1 基本概念和性质定义若)(gem，meeji,，ie 与je 无公共端点（ji） ，则称 m为图g的一个对集； m 中的

36、一条边的两个端点叫做在对集m 中相配； m 中的端点称为被 m 许配；g中每个顶点皆被 m 许配时， m 称为完美对集；g中已无使| |mm的对集m，则 m 称为最大对集； 若g中有一轨， 其边交替地在对集 m 内外出现，则称此轨为m 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。若把可增广轨上在m 外的边纳入对集，把m 内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个。1957 年，贝尔热 (berge)得到最大对集的充要条件：定理 2 m 是图g中的最大对集当且仅当g中无 m 可增广轨。1935 年，霍尔 (hall) 得到下面的许配定理：定理 3 g为

37、二分图， x 与y 是顶点集的划分，g中存在把 x 中顶点皆许配的对集的充要条件是，xs，则|)(|ssn，其中)(sn是s中顶点的邻集。由上述定理可以得出：推论 1：若g是k（)0k正则 2 分图，则g有完美对集。所谓k正则图，即每顶点皆k度的图。由此推论得出下面的婚配定理：定理 4 每个姑娘都结识)1(kk位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。人员分派问题等实际问题可以化成对集来解决。人员分派问题： 工作人员nxxx,21去做 n件工作nyyy,21，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果

38、不能，最多几人可以有适合的工作？这个问题的数学模型是：g是二分图，顶点集划分为yxgv)(，,11nxxx，,11nyyy， 当且仅当ix 适合做工作iy 时，)(geyxii，求g中的最大对集。解决这个问题可以利用1965 年埃德门兹 (edmonds)提出的匈牙利算法。匈牙利算法：（i）从g中任意取定一个初始对集m 。（ii）若 m 把 x 中的顶点皆许配，停止，m 即完美对集；否则取x 中未被 m 许配的一顶点 u ，记us， t。（iii ）若tsn)(，停止，无完美对集；否则取tsny)(。（iv） 若y是被 m 许配的，设myz， zss， ytt， 转 （iii ） ；否则，取可

39、增广轨),(yup，令)()(mpepemm，转（ ii） 。把以上算法稍加修改就能够用来求二分图的最大对集。最优分派问题： 在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。这个问题的数学模型是：在人员分派问题的模型中，图g的每边加了权0)(jiyxw，表示ix 干jy 工作的效益，求加权图g上的权最大的完美对集。解决这个问题可以用库恩曼克莱斯（kuhn-munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。定义若映射rgvl)(:，满足yyxx,，),()()(yxwylxl，则称l是二分图g的可行顶点标号。令)()()

40、(),(|xywylxlgexyxyel，称以le 为边集的g的生成子图为相等子图，记作lg 。可行顶点标号是存在的。例如;),(max)(xxxywxlyyyyyl,0)(。定理 5 lg 的完美对集即为g的权最大的完美对集。kuhn-munkres 算法（i）选定初始可行顶点标号l，确定lg ，在lg 中选取一个对集 m 。（ii）若 x 中顶点皆被 m 许配，停止， m 即g的权最大的完美对集；否则，取lg 中未被 m 许配的顶点 u ，令us， t。(iii) 若tsnlg)(，转（ iv） ；若tsnlg)(，取)()()(min,xywylxltysxl，其它),(,)(,)()(

41、vltvvlsvvlvlll，ll，llgg。（iv ）选tsnlg)(中一顶点y，若y已被 m 许配，且myx，则zss， ytt，转（iii ） ；否则，取lg 中一个 m 可增广轨),(yup，令)()(mpepemm，转（ii） 。其中)(snlg是lg 中s的相邻顶点集。4.2 应用案例：锁具装箱问题某厂生产一种弹子锁具， 每个锁具的钥匙有5 个槽，每个槽的高度从 1，2，3，4，5，66 个数（单位从略）中任取一数。由于工艺及其它原因，制造锁具时对 5 个槽的高度有两个要求：一是至少有3 个不同的数；二是相邻两槽的高度之差不能为5。满足上述两个条件制造出来的所有互不相同的锁具称为一

42、批。销售部门在一批锁具中随意地抽取，每60 个装一箱出售。从顾客的利益出发，希望在每批锁具中不能互开（“一把钥匙开一把锁” ） 。在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下实验结果：若二者相对应的5 个槽的高度中有 4 个相同，另一个槽的高度差为1，则可能互开；在其它情况下，不可能互开。团体顾客往往购买几箱到几十箱，他们会抱怨购得的锁具中出现互开的情形。如何装箱，如何给箱子以标志，出售时如何利用这些标志，使团体顾客减少抱怨。一、 问题分析与建立模型用一个 5 元数组来表示一个锁具：key=（h1，h2，h3，h4，h5）其中 hi表示第 i 个槽的高度， i=1，2，3，4，5

43、。此 5 元数组表示一把锁，应满足下述条件：条件 1：对于任意一种槽高排列h1，h2，h3，h4，h5，至少有 3 种不同的槽高。条件 2：对于任意一种槽高排列h1，h2，h3，h4，h5，有51iihh，i = 2，3，4，5。而两个锁可以互开的条件为：两个锁的钥匙有四个槽高相同，其中一个槽高相差为 1。1一批锁具个数的计算记一批锁具的集合为：k= （h1，h2，h3，h4，h5）| hi1，2，3，4，5，6，i = 1，2，3，4，5，且（h1，h2，h3，h4，h5）为一锁具 ，则每批锁具的个数为x，且21xxx,其中 x1为满足条件 2，相邻构两槽高度之差不为5 的锁具数； x2为相

44、邻两槽之差不为 5 且槽高仅有 1 个或 2 个的锁具数，即满足条件2 但不满足条件 1的锁具数。造一个六点图，每个顶点分别代表1，2，3，4，5，6，除 1 与 6 外，任何两点之间有边相连，每点有一条自己到自己的环，则每个无1,6 相连的五位数与该图上长度为4 的一条链一一对应。构造这个图的邻接矩阵111110111111111111111111111111011111a则矩阵ka中所有元素的和，即为这个图中长度为k的链的个数，因为14116516516516514016519419419419416516519419419419416516519419419419416516519419

45、41941941651401651651651651414a所有无 1,6 相连的五位数的个数为这36个元素的和，即63061x。令612iiyx， 其中iy 表示满足条件 2 但不满足条件 1 且首位为 i 的锁具数。显然有61yy，2543yyyy。计算1y 时，可分别考虑槽高只有1，12，13，14，15 的情形。若只有 1，这样的锁具数年只有1 个；若只有 1 和i（5,4, 3,2i） ，这样的锁具数为： g 中以 1 和i为顶点，长度为 3 的道路数。取矩阵a 的第 1 行和第i行、第 1 列和第i列的元素所组成的矩阵11111ia，由于444431ia，所以614) 14444(

46、11y。同理，计算2y 时，考虑槽高只有2，21，22，23，24，25，26 的情形，类似计算可得765)144444(12y。426476261612iiyx，5880426630621xxx。所以每批锁具有 5880 个，共装 98 箱. 2互开图及其性质以一批锁具的全体为顶点集v，即v=54321hhhhh| 6, 5, 4, 3, 2, 1ih，51iihh，且 h1，h2，h3，h4，h5中至少三个不相同 当且仅当两个顶点所对应的锁具能够互开，它们之间连一条边，边集ejivv|jivvvji,，1jivv，51iiihv 称图 g（v，e）为互开图。对于互开图g，它是一个二部图，其

47、划分为（x ，y ） ，其中x 54321hhhhh|51iih为奇数 ，y54321hhhhh|51iih为偶数 ，可以证明，在x与 y 之间可以建立一一对应关系。则| x| | y| 。用匈牙利算法，可以求得g的最大匹配 m ，得知 m的边数 | m| | x| ，因此 m为理想匹配。对图 g（v，e） ，vn，若 n 的任意两个顶点都不相邻，则称n 为独立集；若 n 为独立集，任意增加一个顶点都不是独立集，则称n 为极大独立集；g 中顶点数最多的独立集， 称为最大独立集。最大独立集n 与最小覆盖 k 有关系： | n|+| k| | v| ，其中 | v| 是图 g的顶点数。若 n是图

48、g的最大独立集，则 | n| | x| 2940。对于同一批锁具， 将槽高之和为奇数、 偶数的分别装箱， 并做“奇” 、 “偶”标记，只要购买不超过 2940/60=49 箱，可保证不会出现互开现象，若购买超过 49 箱，则必定有互开的锁具。3抱怨程度的刻划从一批 5880 个锁具中，随机取60 个装一箱， 120 个装一箱， , ，抱怨程度可用所购的一箱或二箱，, ，锁具中平均有多少对互开来衡量。由于互开图 g（v，e）的边数| e| 22778，而 k5880的边数为从 5880任取2 个的组合数25880c，故一箱锁具中，任意二锁能够互开的概率为25880/22778 c，所以一箱锁具的

49、平均互开对数为e133.2/2277826025880cc两箱锁具的平均互开对数为：e240. 9/22778212025880cc一般地， k 箱锁具的平均互开对数为：ek26025880/22778kcc说明：直接用平均互开总对数来刻划抱怨程度有一定的不合理性。因为这样来刻划，购买的箱数越多，抱怨程度就越大，而实际上，购买的越多，自然互开的可能性就越大，这是顾客意料之中的，不应有太多的抱怨，顾客所不能容忍的是在购买少量的锁具而出现互开现象。因此应把购买箱数作为一个因素考虑到抱怨函数中。理想的抱怨函数应该是，开始随购买量的增加而增加，到一定量后下降，这才合理。五、euler 图和 hamil

50、ton 图5.1 基本概念定义经过g的每条边的迹叫做g的 euler 迹；闭的 euler 迹叫做 euler回路或 e回路；含 euler 回路的图叫做 euler 图。直观地讲， euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理 7 （i）g是 euler 图的充分必要条件是g连通且每顶点皆偶次。（ii）g是 euler 图的充分必要条件是g连通且diicg1，ic 是圈，)()()(jiceceji。（iii ）g中有 euler 迹的充要条件是g连通且至多有两个奇次点。定义包含g的每个顶点的轨叫做hamilton(哈密顿 )轨；

51、闭的 hamilton轨叫做 hamilton 圈或 h 圈；含 hamilton 圈的图叫做 hamilton 图。直观地讲， hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。5.2 euler 回路的 fleury 算法1921年，fleury 给出下面的求 euler 回路的算法。fleury 算法：1o. )(0gvv，令00vw。2o. 假设迹iiivevevw110已经选定，那么按下述方法从,1ieee中选取边1ie：（i）1ie和iv 相关联；（ii） 除非没有别的边可选择， 否则1ie不是,1iieegg的割边 (

52、cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。3o. 当第 2步不能再执行时，算法停止。5.3 应用案例1 邮递员问题一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。显然，若此连通赋权图是euler 图，则可用 fleury 算法求 euler 回路，此回路即为所求。对于非 euler 图，1973 年，edmonds和 johnson给出下面的解法：设g是连通赋权图。（i）求)2(mod1)(),(|0

53、vdgvvvv。（ii） 对每对顶点0,vvu， 求),(vud（),(vud是 u 与v的距离，可用 floyd算法求得）。（iii ）构造完全赋权图|0vk，以0v 为顶点集，以),(vud为边 uv的权。（iv）求|0vk中权之和最小的完美对集m 。（v）求 m 中边的端点之间的在g中的最短轨。（vi） 在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。（vii ）在（ vi）中得的图g上求 euler 回路即为中国邮递员问题的解。多邮递员问题：邮局有)2(kk位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的

54、时间最早？我们把这一问题记成 kpp。kpp 的数学模型如下：),(evg是连通图，)(0gvv，求g的回路kcc,1，使得（i）)(0icvv，ki,2 ,1，（ii）min)(max)(1iceekiew，（iii ）kiigece1)()(2 旅行商（ tsp）问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的hamilton 圈。称这种圈为最优圈。 与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所

55、以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个hamilton 圈c， 然后适当修改c以得到具有较小权的另一个hamilton 圈。修改的方法叫做改良圈算法。设初始圈121vvvvcn。（i）对于nji11，构造新的 hamilton 圈: 12112121vvvvvvvvvvvcnjjijjjiij, 它 是由c中 删 去 边1iivv和1jjvv， 添加 边jivv和11jivv而 得到 的 。 若)()()()(1111jjiijijivvwvvwvvwvvw， 则以ijc 代替c，ijc 叫做c的改良圈。（ii）转（ i） ，直至无法改进，停止。用改良圈算法