1.1 图论模型的基本理论

对于前面的两个例子，我们可以这样来理解，所谓的图就是由平面上的一些点以及这些点之间的连线构成的结构.这里我们对点的位置，连线的曲折程度、长短不做区分，重点在于哪些点对是相连的，由几条线相连.图中的点在图论中称为顶点，两点之间的连线·2 ·称为边.和某一点有边连接的其他点都称为它的邻点.

在过河问题的解决方案中，从一点出发，通过一些边经过不同的点到达另一点的路径我们称之为路，所含边的数目称为路的长度.一般来说，图中连接两点的路不止一条，我们把这些路中所含边数最少的路所含的边数称为这两点之间的距离.

实际问题中所建立的图论模型往往比上述问题复杂，因此需要借助计算机并通过好的图论算法来解决.我们将在本章对一些基本算法逐一介绍，然后在以后的章节里通过模型加以应用.而运用计算机解决图上的问题，首先我们要让计算机学会读取图的信息.为了做到这一点，我们引进了关联矩阵和邻接矩阵.

• 关联矩阵：当图G中顶点集和边集分别为V={v1,v2,…,vn}和E={e1,e2,…,em}时，我们可以写出其对应的关联矩阵M（G）=（mij），其中，如果vi是边ej的一个端点则mij为1，否则为0.

• 邻接矩阵：当图G的顶点集为V={v1,v2,…,vn}时，我们可以定义它的邻接矩阵A（G）=（aij），其中aij为连接顶点vi与vi的边的数目.

例如，如图1.4所示，其关联矩阵和邻接矩阵分别为

很显然，图的邻接矩阵是对称的，因此为了节约计算机储存空间，我们往往只需要读取对角线及以上部分.

在实际问题中，我们遇到的绝大多数图中两点之间至多只有一条边连接，且没有自己到自己的边，这样的图称为简单图.如果根据实际问题需要，对图中的边赋予一定的权重，我们称这样的图为赋权图，记边（vi,vj）的权为w（vi,vj）.对于赋权图，两点间的距离的定义和一般图就不一样了，它是指连接两点之间的所有路中权重最小的路的权重.有时我们需要对图的每一条边都规定方向，加了定向的图我们称为有向图.当然，为了突出有向图的方向性，它的邻接和关联矩阵都和无向图有所区别，我们将在后面的章节中介绍.

最后，我们介绍几类后面章节中将要涉及的图类，如表1.1所示.

通常我们可以通过去边和去点的方法得到包含在一个大图中的小图，我们称之为子图，注意去点时也去掉该点相关联的边.包含所有顶点的子图叫作支撑子图，特别地，如果一个支撑子图是树时，我们称它为图的支撑树[见图1.5（b）].由两两无公共端点的边所组成的子图称为图的匹配，如果该匹配涵盖了图的所有顶点，则称其为图的完美匹配.图1.6所示就是一个二部图和它的一个完美匹配.

1.1.1 图的独立集

图的一个顶点子集如果满足其中任何两个顶点之间都没有边相连，那么我们称其为一个独立集.如果把图看成集合上的二元关系，独立集中的顶点相互没有关系，所以在信息科学研究中常称其为稳定集.所含顶点个数最多的独立集称为最大独立集，而这一最大值称为图的独立数.如何找点数多的独立集以及确定图的独立数是图论研究中一个极其重要的问题.我们可以通过取点然后删去它的邻点，再取点再删邻点的这种贪婪算法得到独立集，但并不能保证所得的独立集所含点数足够多.如果一个独立集不包含于任何其他独立集，我们称其为极大独立集.如何将一个图的顶点集划分成尽可能少的独立集的并即为图的着色问题.

图的覆盖是与图的独立集紧密相关的一个概念.图的一个顶点子集如果满足图中任意一条边都与其中某一点关联，则称该子集为图的一个覆盖.所含点数最小的覆盖称为最小覆盖.如果一个点覆盖不包含其他覆盖，我们称其为图的极小覆盖.如果以顶点集为全集，每个独立集的补集为图的一个覆盖，而任何一个覆盖的补集必为一个独立集.所以极大独立集与极小覆盖也为互补关系，因此寻找极大独立集和寻找极小覆盖为两个等价的问题.

如图1.7所示，{5,7,8}是一个极大独立集，{1,4,7,8}是一个最大独立集，{1,2,3,4,6}是一个极小覆盖，{2,3,5,6}是一个最小覆盖.

1.1.2 竞赛图

竞赛图是一种特殊的有向图，它的任何一对顶点之间都有一条唯一的有向边相连.换句话说，竞赛图实际上是由对完全图的每条边都赋上一个方向得到.之所以称之为竞赛图，是因为我们可以用它来记录一场小组内循环赛的比赛结果.因为对每一条边的方向只有两个选择，所以，我们只能记录必须分出胜负的比赛，不允许出现打平的情况，例如篮球比赛.我们可以用顶点来表示运动员或运动队，用有向边来记录两队的比赛结果.具体地，如果甲赢了乙，在甲和乙之间用一条由甲指向乙的边来连接.这样我们得到了一张竞赛图记录了所有的比赛.竞赛图当前主要应用于包括投票理论和社会选择理论在内的研究.

下面我们介绍两个竞赛图的基本性质.

性质1任何竞赛图都含有一个有向的哈密尔顿路.

我们定义一个无向图的哈密尔顿路，即从图某一点出发到达另一顶点且经过图中所有其他顶点恰好一次的路径.对于有向图，我们有类似的定义，所谓有向的哈密尔顿路是从一点出发到达另一顶点并经过所有顶点恰好一次的有向路径，这里有向路径是指路径中的边的方向都一致.

性质2任何竞赛图都有一个唯一的双连通分支的线性排序.

如果图中任意两个顶点之间都有两条方向相反的有向路连接，则称其是双连通或强连通的.对于不是双连通的图，都可以分解成若干个极大的双连通分支.上述性质指出对于竞赛图，存在极大的双连通分支的唯一的一个线性排列，即D1,D2,…,Dk，其中对于任何i＜j,Di和Dj之间的有向边的方向均为从Di的顶点指向Dj的点.

如图1.8所示是一个竞赛图，它不是双连通的，D→A→B→C→E为一条有向的哈密尔顿路，该图有3个双连通分支且唯一线性排序为D1={D},D2={A,B,C},D3={E}.

1.1.3 Dijkstra算法

Dijkstra算法（迪杰斯特拉算法，一般用其英文）是一个用来计算给定赋权图中一点到其他各点之间距离的算法，也称为最短路径算法.

输入：n个顶点的赋权图G，顶点u0.

（1）置l（u0）=0，对v≠u0,l（v）=∞,S0={u0}且i=0.

（2）对每个v∈Si，用min{l（v）,l（ui）+w（ui,v）}代替l（v）.计算，并且把达到这个最小值的一个顶点记为ui+1，置Si+1=Si∪{ui+1}.

（3）若i=n-1，则停止.若i＜n-1，则i+1代替i，并转入（2）.

输出：u0和图中任意点之间的距离.

注意：Dijkstra算法是一个多项式时间算法，事实上它能执行不超过n2次简单运算（n为图中顶点的个数），算出赋权图上任意两点之间的距离.

下面我们运用Dijkstra算法来计算图1.9中点u0到其他各点的距离.

1.1.4 Kruskal算法

要求一张赋权图的最小支撑树，我们可以采用如下的Kruskal算法（克鲁斯卡尔算法，一般用其英文），也称为最小支撑树算法.

输入：赋权图G（V,E,w），其中w为各条边权重的赋值函数.

（1）选择边e1，使得w（e1）尽可能小.

（2）若已经选定边e1,e2,…,ei，则从E＼{e1,e2,…,ei}中选取ei+1，使得

① 由e1,e2,…,ei，构成的子图G[{e1,e2,…,ei+1}]为无圈图；

② w（ei+1）是满足（1）的尽可能小的权.

（3）当第（2）步不能继续执行时则停止.

输出：最小支撑树T（G）.

下面我们运用Kruskal算法，求出图1.10中的最小支撑树（最后一张图加粗边为支撑树）.·6 ·

1.1.5 匹配算法

本节中我们将介绍与匹配相关的两个经典算法——匈牙利算法和Kuhn-Munkres算法（也称KM算法）。

为了便于理解算法，我们先介绍两个相关的概念.假设M是图G的一个匹配，v是G的一个顶点，如果v是M中某条边的端点，则称M饱和v，否者称v是M的非饱和点.

一条连接两个非饱和点x和y的由M外的边和M的边交错组成的路称为M的可扩（x,y）路.设S为G中一些顶点组成的集合，记N（S）为S中各点邻点的并集.

图1.11中的匹配M中就存在可扩路P，经过更新后得到一个边数更多的匹配M＾.

1.匈牙利算法

匈牙利算法主要用于求已知二部图的最大匹配，如果二部图两部分顶点一样多，该算法显然可以确定完美匹配是否存在.

（1）若M饱和X的每个顶点，则停止.否则，设u是X中的M非饱和点.置S={u}及T=∅.

（2）若N（S）=T，由于|T|=|S|-1，所以 |N（S）|＜|S|，因而停止，因为根据Hall定理（参考文献[1]），不存在饱和X的每个顶点的匹配.否则，设y∈N（S）＼ T.

（3）若y是M饱和的.设yz∈M，用S∪{z}代替S,T∪{y}代替T，并转到第（2）步.否则，设P是M可扩（u,y）路，用代替M，并转到第（1）步.其中E（P）为P的边集.符号Δ表示集合的对称差运算.通常，对于集合A,B，其对称差AΔB=（A-B）∪（B-A）=（A∪B）-（A∩B）.

2.Kuhn-Munkres算法

Kuhn-Munkres算法是对匈牙利算法的一个改进，可以用来找出赋权完全二部图的最优匹配.

假设l是顶点集X∪Y上的实函数，且满足对于所有的x∈X及y∈Y，均有

l（x）+l（y）≥w（x,y），

其中w（x,y）为边xy的权重，则称l为G的一个可行顶点标号.这样的标号一定是存在的，例如，我们可以对所有Y中的点都标零，而对于X中的点x标上与它关联的所有边的权重的最大值即可.记Gl为在标号l下，那些使得上式取等号的边组成的G的子图.Gl中与顶点集S关联的点的集合记为.

从任一可行顶点标号l开始，然后决定Gl，并且在Gl中选取任意一匹配M.

（1）若X是饱和的，则M是完美匹配，并且是最优的，算法终止；否则，令u是一个M非饱和点，置S={u},T=∅.

（2）若，则转入（3）；否则.计算

且由

给出可行顶点标号 以代替l，以代替Gl.

（3）在中选择一个顶点y.考察y是否M饱和.若y是M饱和的，并且yz∈M，则用S∪{z}代替S，用T∪{z}代替T，再转到（2）；否则，设P是Gl中M可扩（u,y）路，用代替M，并转到（1）.

图1.12所示为一个赋权完全二部图G=（G,w），以及在标号l和下的子图以及最优匹配.