图论教程（运筹学分支物理学、化学、控制论、信息论、科学管理、电子计算机）

图论图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。再例如，各种通信网络的合理架设，交通网络的的合理分布等问题，应用图论的方法求解，都很简便。

欧拉在1736年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。如下图（a）所示。

当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。

1736年欧拉将此问题归结为上图（b）所示图形的一笔画问题。即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。欧拉证明了这是不可能的，因为上图（b）中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。这是古典图论中一个著名问题。随着科学技术的发展以及电子计算机的出现与广泛应用，二十世纪五十年代，图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少，距离最短，费用最省等等。图论收到数学、工程技术以及经营管理等各个方面越来越广泛的重视。一、图的基本概念在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。

例1

图10-2时是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的联线代表这两个城市之间的铁路线。诸如此类的还有电话线分布图、煤气管道图、航空线路图等等。例2有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况，也可以用图表示出来。已知甲队和其它各队都比赛过一次，乙队和甲丙队比赛过，丙队和乙、丁队比赛过，丁队和丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点分别代表这五个队，某两个队之间比赛过，就在这两个队所对应的点之间联一条线，这条线不过其它的点，如图10-3所示。例3某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点分别代表这八种药品，若药品和药品是不能存放在同一个库房的，则在和之间联一条线。如图10-4所示。从这个图中可以看到，至少要有四个库房，因为必须存放在不同的库房里。事实上，四个库房就足够了。例如，各存放在一个库房里。（这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的）。从以上几个例子可见，可以用由点及点与点的联线所构成的图，去反映实际生活中，某些对象之间的某个特定的关系。通常用点代表研究的对象（如城市、球队、药品等等），用点与点的联线表示这两个对象之间有特定的关系（如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等）。因此，可以说图是反映对象之间关系的一种工具，在一般情况下，图中点的相对位置如何，点与点之间联线的长短曲直，对于反映对象之间的关系，并不是重要的。如例2，页可以用图10-5所示的图去反映这五个球队的比赛情况，这与图10-3没有本质的区别。所以，图论中的图与几何图、工程图等是不同的。前面几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙与甲也又这种关系。例如甲药品不能和乙药品放在一起，那么，乙药品当然也不能和甲药品放在一起。在实际生活中，有许多关系不具有这种对称性。比如人们之间的认识关系，甲认识乙不代表乙也认识甲。比赛中的胜负关系也是这样，甲胜乙和乙胜甲是不用的。反映这种非对称的关系，只用一条联线就不行了。如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图10-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的联线表示。例如球队胜了球队，可以从引一条带箭头的联线到。图10-6反映了五个球队比赛的胜负情况，可见三胜一负，打了三场球，全负等等。类似胜负这种非对称的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系、一项工程中各工序之间的先后关系等等。综上所述，一个图是由一些点及一些点之间的联线（不带箭头和带箭头）所组成的。为了区别起见，把两点之间的不带箭头的联线称为边，带箭头的联线称为弧。如果一个图G是由点及边所构成的，则称为无向图（也简称为图），记为G=（V，E），式中V，E分别是G的点集合和边集合。一条联结点的边记为（或）。如果一个图D是由点及弧所构成的，则称为有向图，记为D=（V，A），式中V，A分别表示D的点集合和弧集合。一条方向是从指向的弧记为图10-7是一个无向图。其中图10-8是一个有向图其中图G或D中的点数记为或，边（弧）数记为（）。在不会引起混淆的情况下，也分别简记为。下面介绍常用的一些名词和记号，先考虑无向图若边则称u,v是e的端点，也称u,v是相邻的。称e是点u（及点v）的关连边。若图G中，某个边e的两个端点相同，则称e是环（如图10-7中的），若两个点之间有多于一条的边，称这些边为多重边（如图10-7中的

）。一个无环，无多重边的图成为简单图，一个无环，但允许有多重边的图称为多重图。以点v为端点的边的个数成为v的次，记为或。如图10-7中，（环在计算时算作两次）。称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。定理1图中，所有点的次之和是边数的两倍，即这是显然的，因为在计算个点的次时，每条边被它的端点各用了一次。次为奇数的点，称为奇点，否则称为偶点。定理2任一个图中，奇点的个数为偶数。给定一个图，一个点、边的交错序列如果满足则称为一条联结和的链，记为，有时称点为链的中间点。

链中，若，则称之为一个圈，记为。若链中点都是不同的，则称之为初等链；若圈中，都是不同的，则称之为初等圈；若链（圈）中含的边均不相同，则称之为简单圈。以后说到链（圈），除非特别交代，均指初等链（圈）。例如图10-9中，是一条简单链，但不是初等链，是一条初等链。这个图中，不存在联结和的链。是一个初等圈，是简单圈，但不是初等圈。图G中，若任何两个点之间，至少有一条链，则称G为连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图（也简称分图）。如图10-9是一个不连通图，它有两个连通分图。给了一个图G=（V,E），如果图G’=（V’,E’），使

，则称G’是G的一个支撑子图。设，用G-v表示从图G中去掉点v及v的关联边后得到的一个图。例如若G如图10-10（a）所示，则如图10-10（b）所示。图10-10（c）是图G的一个支撑子图。现在讨论有向图的情形。设给了一个有向图，D=（V，A），从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G（D）。给D中的一条弧a=(u,v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。设是D中的一个点弧交错序列，如果这个序列在基础图G（D）中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链（圈）。如果是D中的一条链，并且对均有，称之为从到的一条路。若路的第一个点和最后一个点相同，则称之为回路。类似定义初等路（回路）。例如图10-8中，是一个回路，是从到的路，是一条链，但不是路。对无向图，链与路（圈与回路）这两个概念是一致的。类似于无向图，课定义简单有向图，多重有向图，图10-8是一个简单有向图。以后除特别交代外，说到图（有向图）均指简单图（简单有向图）。二、树1、树及其性质在各式各样的图中，有一类图是极其简单然而却是很有用的，这就是树。例1已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以相互通话（允许通过其它城市），并且电话线的根数最少。用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍然是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图10-11代表了满足要求的一个电话线网。定义1一个无圈的连通图称为树。例2某工厂的组织机构如下所示：如果用图表示，该工厂的组织机构就是一个树定理1设图G=（V，E）是一个树，，则G中至少有两个悬挂点。定理2图G=（V，E）是一个树的充分必要条件是G不含圈，且恰有p-1条边。定理3图G=（V，E）是一个树的充分必要条件是G是连通图，并且q(G)=p(G)-1。定理4图G是树的充分必要条件是任意两个顶点之间恰有一条链。

由这个定理，很容易推出如下结论：（1）从一个树中去掉任意一条边，则余下的图是不连通的。由此可知，在点集合相同的所有图中，树是含边数最少的连通图。这样例1中所要求的电话线网就是以这五个城市为点的一个树。（2）在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步的说，如果再从这个圈上任意去掉一条边，可以得到一个树。如图10-11中，添加，就得到一个圈，如果从这个圈中去掉一条边，就得到如图10-13所示的树。2、图的支撑树定义2设图T=（V，E’）是图G=（V，E）的支撑子图，如果图T=（V，E’）是一个树，则称T是G的一个支撑树。例如图10-14（b）是图10-14（a）的一个支撑树。若T=（V，E’）是图G=（V，E）的一个支撑树，则显然，树T中边的个数是p（G）-1，G中不属于树T的边数是q（G）-p（G）+1。定理5图G有支撑树的充分必要条件是图G是连通的。定理4中充分性的证明，提供了一个寻求连通图的支撑树的方法。这就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树，称这种方法为“破圈法”。例3在图10-15中，用破圈法求出图的一个支撑树。类似有“避圈法”。例4在图10-16中，用避圈法求出一个支撑树。3、最小支撑树问题定义3给图G=（V，E），对G中的每一条边，相应地有一个数，则称这样的图G为赋权图，称为边上的权。这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，例如表示距离、时间、费用等。赋权图在图的理论及其应用方面有着重要的地位。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛地应用于解决工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。设有一个连通图G=（V，E），每一边有一个非负权。定义4如果T=（V，E’）是G的一个支撑树，称E’中所有边的权之和为支撑树T的权。即如果支撑树的权是G的所有支撑树的权中最小者，则称是G的最小支撑树（简称最小树）。即式中对G的所有支撑树T取最小。最小支撑树问题就是要求G的最小支撑树。假设给定一些城市，已知每对城市间交通线的建造费用。要求建造一个联结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。避圈法开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条）。

破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，一直得到一个不含圈的图为止，这时的图便是最小树。例5分别用避圈法和破圈法求下图的最小支撑树。三、最短路问题已知如图10-18所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从出发，通过这个交通网到去，求使总费用最小的旅行路线。可见，从到的旅行路线是很多的，例如可以从出发，依次经过，然后到；也可以从出发，依次经过然后到等等。不同的路线，所需费用是不同的。比如，按前一个路线，总费用是6+1+6=13单位，而按后一个路线，总费用是3+2+10+2+4=21单位。不难看到，用图的语言来描述，从到的旅行线路与有向图中从到的路是一一对应的。一条旅行线路的总费用就是相应的从到的路中所有弧旁数字之和。当然，这里说到的路可以不是初等路。例如某人从到的旅行路线可以是从出发，依次经最后到达。这条路线相应的路是总费用是47单位。从这个例子，可以引出一般的最短路问题，给定一个赋权有向图，即给了一个有向图D=(V,A)，对每一个弧，相应地有权，又给定D中的两个顶点。设P是D中从的一条路，定义路P的权是P中所有弧的权之和，记为。最短路问题就是要在所有从的路中，求一条权最小的路，即求一条从的路，使式中对D中所有从的路P取最小，称是从的最短路。路的权称为从的距离，记为。显然，与不一定相等。最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它的优化问题。这里介绍一个赋权有向图中寻求最短路的方法，这些方法实际上求出了从给定一个点到任一个点的最短路。如下事实是经常要利用的，如果P是D中从的最短路，是P中的一个点，那么，从沿P到的路是从的最短路。事实上，如果这个结论不成立，设Q是从的最短路，令是从沿Q到达，在从沿P到达的路，那么，的权就比P的权小，这与P是从的最短路矛盾。四、偶图、匹配定义1若图G=(V,E)的点集能划分为两个互不相交的非空子集和，的端点分别属于，则称G为偶图，记作。若为偶图，且的每个点均与的每个点相邻，则称G为完全偶图，记作。例如，图10.7中（a），（b），（c）均为偶图，其中（c）为完全偶图。定理1一个图为偶图当且仅当它不含长度为奇的圈。定理2若无公共端点，则称M为G的一个匹配；M中一条边的两个端点叫做在M中相配；M中边的端点称为被M许配；若G中每个顶点皆被M许配时，M称为完全许配，M称为完备匹配；含边数最多的匹配称为最大匹配。由定义知完备匹配必为最大匹配，而最大匹配不一定是完备匹配。一个图的最大匹配必存在，但完备匹配未必存在。显然，G存在完备匹配的一个必要条件是G的点数为偶数。我们感兴趣的是求最大匹配。那么如何判断一个匹配是最大匹配呢？下面给出一个充要条件，先引入两个概念。定义2若M是G的匹配，又G中有一条路，其边交替地在E-M中与M中出现，称这条路为M的交错路。若M的交错路的起点和终点皆未被M许配，称此为M的可增广路。

例如，图10.8中取，则路是一条M的可增广路。将中不在匹配中的边放入该匹配中，而把原来属于匹配中的边删去，得到新的匹配显然，，即M不是该图的最大匹配。定理3G的匹配M是最大匹配当且仅当G不含M的可增广路。下面介绍一下偶图存在某类匹配的条件。取图G的一个顶点子集S，