第5章〓图的基本概念
图论中所说的图与一般所说的几何图形或代数函数的图形是完全不同的。图论中的图是指一些点的集合和若干点对的集合所组成的系统。现实世界中许多现象都能用这种系统来表示。例如，一个企业的各管理部门和生产车间，可以用点来表示，如果两部门之间有直属的领导关系，就用线将表示这两个部门的点连接起来，这就形成了一个图。对于这种图，点的位置以及线的曲直是无关紧要的，只关心点的多少和这些线连接了哪些点。对它们进行数学抽象就得到了作为数学概念的图。

本章主要介绍无向图的一些基本概念，包括无向图、路、圈、子图、同构、偶图、补图、连通图、欧拉图、哈密顿图、图的矩阵表示、带权图等。

5.1图的基本定义

历史上一些著名问题的解决都归结为由点和线组成的图的某种问题。这种由点和线组成的图被广泛地使用着。然而，图论的研究对象——图，也没有统一的定义，但这并不妨碍对它的研究和应用。这里采用下面的定义。

定义5.1设V是一个非空有限集，集合E 2(V)={{u,v}|u,v∈V,u≠v}，二元组(V,E)称为一个无向图。V中的元素称为顶点(或结点)，V为顶点集； E中的元素称为边，E为边集。

无向图(V,E)常用字母G代替，即G=(V,E)。如果|V|=n、|E|=m，则称G为一个具有n个顶点m条边的图，记为(n,m)图。

如果x={u,v}是无向图G的一条边，则x是连接顶点u和v的边，u和v是边x的端点，且记为x=uv或x=vu，此时，称顶点u与v邻接，顶点u(同样地，顶点v)与边x互相关联。

如果无向图G中的两条边x和y仅有一个公共端点，则称边x与y邻接。

例5.1无向图G=(V,E)是一个(4,5)图，其中顶点集V={v1,v2,v3,v4}，边集E={{v1,v2},{v1,v4},{v2,v3},{v2,v4},{v3,v4}}，顶点v1与v2、v4邻接，顶点v1与v3不邻接，顶点v1与边{v1,v2}、{v1,v4}关联，顶点v1与边{v3,v4}不关联，边{v1,v2}与{v1,v4}邻接，边{v1,v2}与{v3,v4}不邻接。

当把无向图G的边集E看作顶点集V上的二元关系时，首先，由于每条边的两个端点必须互不相同，所以E是反自反的； 其次，由于每条边的两个端点构成的二元子集中的元素是没有次序的，所以E是对称的。因此，一个无向图G就是非空有限集V上以及V上的一个反自反且对称的二元关系E组成的有限关系系统。研究无向图，就是研究这个有限关系系统。

有限关系可以用图示方法表示，正是有了这种图示方法，使得图有直观的外形，富于启发性，而被广泛采用。一般地，无向图G的每个顶点在平面上用一个点或一个圆圈表示，在旁边写上顶点的名称，如果x={u,v}是G的一条边，则在代表顶点u和v的两点间连一条线，这样得到的图形就是G的图解。以后，图和它的图解不作区分，图解也说成图。

例5.2无向图G=(V,E)的顶点集V={v1,v2,v3,v4}，边集E={{v1,v2},{v1,v4},{v2,v3},{v2,v4},{v3,v4}}，则G可用图5.1(a)或图5.1(b)表示，由此可见图的图解表示不唯一。



图5.1







在无向图中，不与任何顶点相邻接的顶点称为孤立顶点。

仅由孤立顶点构成的图称为零图，仅由一个孤立顶点构成的图称为平凡图。

在无向图中，如果连接两顶点的边不止一条，则称这几条边为平行边，平行边的数目称为平行边的重数，有平行边的图称为多重图。

在无向图中，仅与一个顶点相关联的边称为环，有环的图称为带环图。

例5.3图5.2(a)所示的图为带环图，图5.2(b)所示的图为多重图。



图5.2


允许有平行边和环存在的图称为伪图，不含有平行边和环的图称为简单图。例5.1和例5.2中的图均为简单图。

定义5.1所定义的图就是简单图。图论的许多重要结果是针对简单图而证明的，它作了易于抽象的数学处理。但在许多应用中有时出现伪图或多重图。研究了简单图后，其结论在大多数情况下很容易推广到伪图或多重图，并不妨碍应用。今后如果不加说明只讨论简单图。

定义5.2设V是一个非空有限集，AV×V＼{(u,u)|u∈V}，二元组D=(V,A)称为一个有向图。

V中的元素称为顶点(或结点)，A中的元素(u,v)称为从u到v的弧或有向边。

如果x=(u,v)和y=(v,u)均为A的弧，则称x和y为一对对称弧。

不含对称弧的有向图称为定向图。

例5.4图5.3(a)所示的图为有向图，图5.3(b)所示的图为定向图。



图5.3


类似于无向图，可以定义有向图的环、多重弧、带环有向图、多重有向图、简单有向图。

本书第7章将专门研究有向图，所以，如无特殊说明，第5章、第6章的图均指无向图。

定义5.3设图G=(V,E)，vi∈V，与顶点vi相关联的边的数目称为顶点vi的度数，简称为度，记为deg(vi)。

显然，对(n,m)图G的每个顶点v，有0≤deg(v)≤n-1。引入记号

δ(G)=minv∈V{deg(v)}，Δ(G)=maxv∈V{deg(v)}

度数为1的顶点称为悬挂点，与悬挂点相关联的边为悬挂边。

定理5.1设G是一个(n,m)图，则G中顶点度数之和等于边数的2倍，即

∑ni=1deg(vi)=2m

证因为G中每条边必关联两个顶点，一条边为顶点度数之和的贡献是2，所以，m条边为顶点度数之和的贡献是2m，因此，在G中，顶点度数的和等于边数的2倍，∑ni=1deg(vi)=2m。证毕。

此定理是图论中的基本定理，常称为“握手定理”，它有一个重要的推论。

推论5.1在任何图中，奇度数顶点的个数为偶数。

证设G=(V,E)是一个(n,m)图，由握手定理可知，奇度数顶点的度数之和＋偶度数顶点的度数之和=全图顶点度数之总和=2m。

因为全图顶点度数之和为偶数，偶度数顶点的度数之和也为偶数，所以，奇度数顶点的度数之和必为偶数，因此，奇度数顶点的个数必为偶数。证毕。

定义5.4如果图G中每个顶点的度数均为d，则称G为d度正则图。

一个具有n个顶点的n-1度正则图称为n个顶点的完全图，记为Kn。

显然，在Kn中每个顶点与其余顶点均邻接，因此，Kn中共有12n(n-1)条边。

例5.5图5.4(a)所示为K4，图5.4(b)所示为K5。



图5.4


例5.6证明： 在n(n≥2)个人的团体里，至少有两个人，他们在此团体中有相同数目的朋友。

证如果用顶点表示人，两个人是朋友就在相应的两个顶点间连接一条边，这样就得到了具有n个顶点的图G，每个人的朋友数就是相应顶点的度，于是，问题就变成了证明在n(n≥2)个顶点的图G中，至少有两个顶点度数相同。

假设G中n个顶点的度数皆不相同。因为一个顶点的最大度数为n-1，最小度数为0，所以，G中各顶点的度只能为 0，1，…，n-1。

又因为0度顶点不与其他任何顶点相邻，而n-1度顶点与其他任何顶点都相邻，出现了矛盾，因此，在G中至少有两个顶点度数相同。证毕。

定义5.5设G=(V,E)和G′=(V′,E′)是两个图，如果存在从V到V′的双射f，使得对vi、vj∈V，{vi,vj}∈E，当且仅当{f(vi),f(vj)}∈E′，则称G′同构于G，称f为同构映射。

上述定义说明，在两个图的各顶点之间，如果存在着一一对应关系，而且这种对应关系又保持了顶点间的邻接关系，那么这两个图就是同构的。

例5.7在图5.5中，(a)和(b)两图是同构的，其映射为f(i)=vi(i=1,2,…,6)。

两图同构的必要条件是： 顶点数相等、边数相等、度数相同的顶点数相等。但是，上述3个条件并不是两图同构的充分条件。

例5.8在图5.6中，(a)和(b)两图虽然满足上述3个条件，但它们不同构。因为图5.6(a)中的4个度为3的顶点v2、v3、v7、v6是顺次相邻的，而图5.6(b)中的4个度为3的顶点v2、v6、v8、v4却不是顺次相邻的。



图5.5




图5.6


到目前为止，还没有一种简单有效的方法来判断图的同构，故同构图的判定是图论中一个重要而未解决的问题。

习题

1. 画出包含4个顶点的所有不同构的简单无向图。

2. 具有n个顶点的d度正则图有多少条边？

3. 设G是(n,m)图，v是G中度为d的顶点，e为G中一条边。

(1) 在G中去掉v后，还有多少顶点和多少条边？

(2) 在G中去掉e后，还有多少顶点和多少条边？

4. 在某次宴会上，许多人互相握手，证明： 握过奇数次手的人数为偶数。

5. 证明： 图5.7中两个图同构，它们是彼德森(Petersen)图。



图5.7


5.2子图和补图

在解决一些实际问题时，有时从一个图的子图或补图着手能够更有效地解决问题。在进一步研究图的性质和图的局部结构时，子图和补图都是相当重要的概念。

定义5.6设G=(V,E)和G′=(V′,E′)是两个图。

(1) 如果V′V且E′E，则称G′是G的子图。 

(2) 如果V′V或E′E，则称G′是G的真子图。 

(3) 如果V′=V且E′E，则称G′是G的生成子图。 

(4) 如果E′E，则以E′为边集、以E′中边的所有端点为顶点集，构成的子图称为由E′导出的G的子图，记为G(E′)。 

(5) 如果V′V，则以V′为顶点集，以端点均在V′中的G的所有边为边集，构成的子图称为由V′导出的G的子图，记为G(V′)。

例5.9在图5.8中，(b)～(d)均是(a)的子图，且都为真子图，(b)是(a)的生成子图，(c)是顶点子集{v1,v2,v4}导出的(a)的子图，(d)是边子集{{v1,v2},{v2,v3}}导出的(a)的子图。



图5.8


显然，每个图都是自身的生成子图，仅由图的所有顶点构成的图也是图的生成子图，这两种子图都称为平凡子图。

给定一个图，除可以得到它的子图外，还可以定义它的补图。

定义5.7设G=(V,E)是一个图，则=(V, 2(V)＼E)称为G的补图，也记为Gc。如果G与同构，则称G为自补图。

显然，是由G的所有顶点和为了使G成为完全图所需要添加的那些边所组成的图。两个顶点u与v在中邻接当且仅当u与v在G中不邻接。

例5.10在图5.9中，(a)是(b)的补图，(b)也是(a)的补图。

显然，如果是G的补图，那么G也是的补图。因此，G与互为补图。

例5.11图5.10(a)是4个顶点的自补图，(b)和(c)是5个顶点的自补图。



图5.9




图5.10



实际上，如果n个顶点的图G是自补图，因为G的边数与的边数相同，所以，Kn的边数为偶数。显然不存在3个或6个顶点的自补图。

例5.12证明： 一个自补图一定有4k或4k+1个顶点(k为正整数)。

证设G=(V,E)是自补图，且G=(n,m)，根据自补图的定义，G与同构，所以=(n,m)。

由于Kn有n(n-1)2条边，根据补图的定义，得2m=n(n-1)2，所以4m=n(n-1)。

若n为偶数，则n-1为奇数，欲使4m=n(n-1)，必有n=4k(k为正整数)。

若n为奇数，则n-1为偶数，欲使4m=n(n-1)，必有n-1=4k(k为正整数)，得n=4k+1(k为正整数)。

因此，一个自补图一定有4k或4k+1个顶点(k为正整数)。证毕。

定义5.8设图G′=(V′,E′)是图G=(V,E)的子图，若图G″=(V″,E″)满足： 

(1) E″=E-E′； 

(2) V″包含E″中的边所关联的顶点。

则称G″是G′相对于G的补图。

例5.13在图5.11中，(c)是(b)相对于(a)的补图，但(b)不是(c)相对(a)的补图。



图5.11


习题

1. 图5.12(a)和图5.12(b)所示为图G及其子图H。画出H的补图以及H相对于G的补图H′。



图5.12


2. 画出包含4个顶点的所有的简单无向图及其补图。

3. 画出图K4的所有不同构的生成子图。

5.3路、圈与连通图

路与圈是图论中两个重要而又基本的概念，而图的最基本性质是它是否连通。本节介绍路、圈和连通图的概念。

定义5.9设图G=(V,E)的一个点边交替序列P=v0e1v1e2v2…emvm，满足vi-1和vi是边ei的端点，则称P为v0-vm通道，简记为v0v1v2…vm。m为通道的长度。当v0=vm时，称P为闭通道。

由上述定义可知，在通道中，顶点和边均可重复出现。在计算通道的长度时，重复的边按重复的次数计算。

定义5.10如果图中一条通道上的各边互不相同，则称该通道为迹。如果一条闭通道上的各边互不相同，则称该闭通道为闭迹。

定义5.11如果图中一条通道上的各顶点互不相同，则称该通道为路。如果一条闭通道上的各顶点互不相同，则称该闭通道为圈或回路。

例5.14在图5.13中，P1=v1v2v3v5v2v4是一条通道，它是迹，但不是路； P2=v1v2v3v1既是闭迹又是圈。



图5.13


定理5.2设G=(V,E)是含有n个顶点的图，则：

(1) G中任何路的长度小于或等于n-1； 

(2) G中任何圈的长度小于或等于n。

证在任何路中，包含的所有顶点都是互不相同的。在长度为k的任何路中，不同顶点数为k+1。由于G中仅有n个不同顶点，所以k+1≤n，得k≤n-1，即任何路的长度小于或等于n-1。

而对长度为k的圈来说，不同的顶点数为k，所以k≤n，即任何圈的长度小于或等于n。证毕。

定义5.12设G是一个图，如果G中任意两个不同的顶点间至少有一条路，则称G是一个连通图。

直观上，在一个连通图的图解上，对任两顶点，从一个顶点沿着某些边走，一定能走到另一点。于是，一个不连通图的图解被分成若干互不相连的几个部分，每个部分是连通的，称为一个连通分支。

连通图只有一个连通分支，就是图本身。

例5.15图5.13是一个连通图。而图5.14是一个具有3个连通分支的不连通图。



图5.14


定理5.3设G=(V,E)是具有n个顶点的图，如果在G中任两个不邻接的顶点u和v，有deg(u)+deg(v)≥n-1，则G是连通的。

证反证法。假设G不连通，则G有两个或更多个连通分支。

设一个连通分支为G1=(V1,E1)，而其他所有连通分支构成的子图为G2=(V2,E2)。

设G1中有n1个顶点，其中一个顶点为u，G2中n-n1个顶点，其中一个顶点为v。

因为deg(u)≤n1-1，deg(v)≤n-n1-1，故deg(u)+deg(v)≤n-2＜n-1，这与给定的前提矛盾，因此G是连通的。证毕。

定理5.4设G=(V,E)是一个至少有一个顶点不是孤立顶点的图，如果v∈V，deg(v)是偶数，则G中有圈。

证考虑G中一条最长的路P=v1v2…vn，由于v∈V，deg(v)是偶数，所以deg(v1)≥2，故至少还有一个顶点u≠v2与v1邻接。

由于P是最长的路，所以，u必是v3,…,vn中的某个vi，于是，v1v2…viv1是G中的一个圈。证毕。

定理5.5如果图G中的两个不同顶点u与v之间有两条不同的路，则G中有圈。

证设P1和P2是G中两个不同顶点u与v之间的两条不同的路。由于P1≠P2，所以，必有一条边在P2上而不在P1上，不妨设该边为x=u′v′。

由P1和P2上的顶点和边构成的子图记为P1∪P2，于是，P1∪P2是G的一个连通子图，并且P1∪P2-x是G的一个连通子图，从而在P1∪P2-x中有u′和v′间的路，记为P=u′…v′，因此，P+x=u′…v′u′就是G中的一个圈。证毕。

习题

1. 设u和v是图G的两个不同顶点，如果u和v间有两条不同的通道(迹)，问G中是否有圈？

2. 证明： 一个连通的(n,m)图中m≥n-1。

3. 证明： 如果G是一个(n,m)图，且m＞12(n-1)(n-2)，则G是连通图。

4. 证明： 在一个连通图中，两条最长的路有一个公共顶点。

5. 证明： 如果图G不是连通图，则是连通图。

6. 证明： 一个图G是连通的，当且仅当将V划分成两个非空子集V1和V2时，G总有一条连接V1的一个顶点与V2的一个顶点的边。

5.4偶图

下面研究偶图的性质，偶图也称为二分图、二部图、双图等。

定义5.13如果图G=(V,E)的顶点集V有一个二划分{V1,V2}，使得G中任何一条边的两个顶点，一个属于V1，另一个属于V2，则称G为偶图，并记为G=(V1,V2,E)。

定义5.14在偶图G=(V1,V2,E)中，如果V1的每个顶点都与V2的每个顶点邻接，则称G为完全偶图。如果|V1|=n，|V2|=m，则完全偶图G可记为Kn,m。

显然，Kn,m有n·m条边。

例5.16在图5.15中，给出了K2,3和K3,3的图示。



图5.15


K3,3是重要的偶图，它与K5一起在平面图的判定中起着重要的作用。

定理5.6图G是偶图，当且仅当G中所有圈的长度均为偶数。

证设G=(V,E)是偶图，则V有一个二划分{V1,V2}，使得对任一{u,v}∈E，有u∈V1、v∈V2。

设C=v0v1v2…vkv0是G的一个长为k+1的圈，不妨设v0∈V1，则v0、v2、v4、…∈V1、v1、v3、v5、…∈V2。因为{vk,v0}∈E且v0∈V1，所以，必有vk∈V2，故k必为奇数，所以，C的长度为偶数。

设G=(V,E)中所有圈的长度均为偶数。不妨设G是连通图； 否则考虑G的每个连通分支。定义V的一个二划分{V1,V2}为： V1={vi|vi与固定顶点v0间的最短路的长度为偶数}，V2=V-V1。

假设存在一条边{vi,vj}∈E且vi、vj∈V1，因为G是连通的，由V1的定义知，vi与v0间的最短路的长度为偶数，vj与v0间的最短路的长度也为偶数，于是，由v0到vi，边{vi,vj}及vj到v0构成的圈长度为奇数，这与给定的前提矛盾，所以，vi、vj不能同时属于V1。类似地可证明边{vi,vj}的两端点vi、vj不能同时属于V2。因此，边{vi,vj}的两端点必有一个属于V1，另一个属于V2，因此G是一个偶图。证毕。

定义5.15图G=(V,E)的边子集ME，若M中任两边皆不相邻，则称M为G的一个匹配。若不存在匹配M′，可使MM′，则称M为极大匹配。边数最多的匹配称为G的最大匹配。

定义5.16在偶图G=(V1,V2,E)中，若V1的每一点都是匹配M中的边的端点，则称M为从V1到V2的一个完全匹配。

显然，完全匹配必是最大匹配，反之却不一定为真。存在从V1到V2的完全匹配的必要条件为V1≤V2。

例5.17在图5.16中给出了一个偶图，它具有互补结点子集V1和V2，以及从V1到V2的完全匹配(用粗线表示)。



图5.16


下面给出一个说明存在完全匹配的充分必要条件定理。

定理5.7设G=(V1,V2,E)是一个偶图，则G中存在从V1到V2的完全匹配，当且仅当对V1中每k个结点(k=1,2,…,V1) 至少和V2中k个结点相邻(这个条件称为相异性条件)。

证必要性。设偶图G满足相异性条件，下面对V1用数学归纳法进行证明。

V1=1时，因为G满足相异性条件，显然，存在从V1到V2的完全匹配。

假设V1≤n-1时，存在从V1到V2的完全匹配。

V1=n时，设SV1，τ(S)表示与S中结点相邻接的V2中的结点集合。

若对V1的任何真子集S，都有S＜τ(S)，可按下述方法构造出从V1到V2的完全匹配。

任取一边(vi,vj)，使得vi∈V1、vj∈V2。从图G中删去结点vi、vj，得到图G′。显然，图G′是具有互补结点子集V1-{vi},V2-{vj}的偶图，并且满足相异性条件。根据归纳假设，存在从V1-{vi}到V2-{vj}的完全匹配M′。故M=M′∪{(vi,vj)}就是从V1到V2的完全匹配。

若存在一个V1的真子集S，使得S=τ(S)，可按下述方法构造出从V1到V2的完全匹配。

首先，由于S=τ(S)且图G满足相异性条件，因此，在具有互补结点子集S和τ(S)的偶图中，相异性条件满足。由归纳假设，存在从S到τ(S)的完全匹配M′。

其次，若假设具有互补结点子集V1-S和V2-τ(S)的偶图不满足相异性条件，也就是存在S′V1-S，使得S′＞τ(S′)。由于S=τ(S)，有S∪S′＞τ(S)∪τ(S′)，这与G满足相异性条件矛盾。故具有互补结点子集V1-S和V2-τ(S)的偶图满足相异性条件。由归纳假设，存在从V1-S到V2-τ(S)的完全匹配M″。

综上所述，M=M′∪M″必为从V1到V2的完全匹配。

充分性。若偶图G中存在从V1到V2的完全匹配M，那么对于V1中每k个结点，必在V2中有k个结点与其邻接，故相异性条件满足。证毕。

例5.18对图5.16所示的偶图，满足相异性条件，因此其中有完全匹配。对图5.17





图5.17


所示的偶图，不满足相异性条件，因此其中不存在完全匹配。

不难看出，当偶图中的结点较多时，利用相异性条件判断其中是否存在完全匹配，十分复杂。下面介绍一个判断偶图存在完全匹配的充分条件，这个条件对于任何偶图都不难确定。

定理5.8设G=(V1,V2,E)是一个偶图，如果存在某个正整数t＞0，使得：

(1) V1中的每个结点，至少有t条边与其相关联；

(2) V2中的每个结点，至多有t条边与其相关联。

则G中必存在从V1到V2的完全匹配(这两个条件称为t条件)。

证如果条件(1)成立，则与V1中的具有k个结点的任意子集相关联边的总数，最小应是kt。

如果条件(2)成立，这些边必定至少与V2中的tk个结点相关联。因此，V1中每k个结点至少和V2中k个结点相邻接，由定理5.7知，存在从V1到V2的完全匹配。证毕。

例5.19对图5.18所示的偶图，满足定理5.8的条件，其中t=3，因此存在从V1到V2的完全匹配。

定义5.17如果偶图G=(V,U,E)中的一条径由不属于匹配M的边和属于M的边交替组成，且此径的两个端点不是M中边的端点，则称此径为G中关于匹配M的交替链。

例5.20在图5.19所示的偶图中，粗线表示匹配，P=v2u1v3u4是交替链。



图5.18




图5.19



对于偶图来说，要利用交替链求出偶图的最大匹配。具体方法如下。 

① 首先，在偶图G中任意找一个匹配M。

② 其次，如果能找出一条关于匹配M的交替链P，则把P中属于M的边从M中删去，而把P中不属于M的边添到M中，得到G中另一匹配M′，由于M′比M多一条边，因此，反复进行这样的过程，直至找不出关于M′的交替链为止，就可确认M′为G中的最大匹配。

这种方法的证明是比较复杂的。在此不予以证明。

下面介绍一种求交替链的标记法。设偶图G=(V,U,E)的任一匹配M。

首先把V中所有不是M中边的端点用(*)加以标记，然后交替进行以下所述的步骤(1)和(2)。

(1) 选V的一个新加以标记的结点vi，用(vi)标记不通过M中的边与vi邻接且未加以标记的U的所有结点。对所有V的新加以标记的结点重复这一过程。

(2) 选U的一个新加以标记的结点uj，用(uj)标记通过M中的边与uj邻接且未加以标记的V的所有结点。对所有U的新加以标记的结点重复这一过程。

直至标记到U的一个不与M中任何边邻接的结点，或者已不可能标记更多结点时为止。出现前一种情况，可按标记次序的逆序返回到标记有(*)的结点，所经过的路就是所求的交替链。出现后一种情况，说明G中已不存在关于M的交替链。

例5.21在图5.19中，可按下述步骤求出交替链： 

① 把v2加以标记(*)； 

② 从v2出发，按步骤(1)，把u1和u3加以标记(v2)； 

③ 从u1出发，按步骤(2)，把v3标以(u1)； 从u3出发，按步骤(2)，把v4标以(u3)； 

④ 从v3出发，按步骤(1)，把u4标以(v3)，因为u4不是M中的点，按标记次序逆求出一条交替链P=v2u1v3u4。

例5.22求出图5.20所示偶图中的最大匹配。



图5.20


解假设找到了一个匹配M={(v1,u3),(v2,u1),(v3,u2),(v4,u4)}，如图5.20(a)中粗线所示。用标记法可以找到关于M的交替链P=v5u2v3u6，按求最大匹配的方法，修改M={(v1,u3),(v2,u1),(v3,u6),(v4,u4),(v5,u2)}。这时用标记法已找不到交替链，所以，此时的匹配M就是最大匹配，如图5.20(b)中粗线所示。

一般求最大匹配，可先令M=。

习题

1. 图5.21所示的两图是否是偶图？如果是，求出其顶点集的二划分。



图5.21


2. 证明： 对于(n,m)偶图，必有m≤n24。

3. 有4名学生： 张明、王丽、李炎、赵红。分配他们去辅导4门课程： 数学、外语、物理和化学。张明精通外语和物理； 王丽精通数学和化学； 李炎精通数学、外语和物理； 赵红精通物理。问应如何进行分配才不会使任何人去教他不懂的课程？

4. 某单位按编制有7个空缺岗位p1,p2,…,p7，有10名申请者a1,a2,…,a10，各申请者适合的工作岗位集合依次是{p1,p5,p6}、{p2,p6,p7}、{p3,p4}、{p1,p5}、{p6,p7}、{p3}、{p2,p5}、{p1,p3}、{p1}、{p5}，问如何安排他们的工作能使无工作人员最少？

5.5欧拉图和哈密顿图

1727年，数学家欧拉的朋友向欧拉提出一个问题： 位于立陶宛的哥尼斯堡城有一条横贯全城的普雷格尔河，河上有七座桥把河中的两座岛屿以及河岸连接起来，如图5.22(a)所示。当时那里的居民热衷于一个问题： 游人从四块陆地中的任何一块出发，经过每座桥一次且仅一次，最后回到出发地，这是否可能？1736年，欧拉用图论的方法解决了这个问题，写了第一篇图论的论文，成为图论的创始人。后来称此问题为哥尼斯堡七桥问题。如果用顶点代表陆地，用边代表桥，便得到图5.22(b)所示的图。不难看出，哥尼斯堡七桥问题等价于在图5.22(b)中能否找到一个经过所有顶点和所有边的闭迹。



图5.22


定义5.18包含图的所有顶点和所有边的迹称为欧拉迹； 包含图的所有顶点和所有边的闭迹称为欧拉闭迹。存在欧拉闭迹的图称为欧拉图。

定理5.9图G是欧拉图当且仅当G是连通的且每个顶点的度数都是偶数。

证如果G是欧拉图，则G中有包含所有顶点和所有边的闭迹，所以G是连通的。

当沿着这条闭迹行走时，每经过一个顶点，均涉及两条以前未走过的边，其一是沿着这条边进入这个顶点，而另一条边是顺着它离开这个顶点。由于这条迹是闭迹，所以，每个顶点的度数都是偶数。

如果图G连通且每个顶点的度数都是偶数，可按以下方法构造一条欧拉闭迹。

由定理5.4知G中有一个圈Z1。如果Z1包含了G中的所有边，从而也就包含了G中的所有顶点，因此Z1是欧拉闭迹，故G是欧拉图； 否则Z1不包含G中的所有边，这时从G上删去Z1的所有边，得到图G1，显然G1中所有顶点的度数仍为偶数。并且因为G是连通图，所以Z1与子图G1至少有一个公共点，故G1中至少有一个顶点的度不为0。

再由定理5.4知G1中有一个圈Z2。这时从G1上删去Z2的所有边，得到图G2，显然G2中所有顶点的度数仍为偶数。如果G2中还有边，则同样由定理5.4知G2中有一个圈Z3，如此等等。最后必得到一个图Gk，Gk中无边。于是得到了G中的k个圈Z1,Z2,…，Zk，它们是两两无共同边的。

因此，G中的每条边在且仅在一个圈上。于是，G的边集被划分为k个圈。由于G是连通的，所以，每个圈Zi至少与其他的某个圈有公共顶点，从而这些圈构成一个欧拉闭迹。

这可由数学归纳法得证： 当k=1，显然成立。假设当k=p≥1时成立，得证对k=p+1时也成立。

由归纳假设Z1,Z2,…，Zp能构成一个闭迹，而Zp+1必与其他的某个圈，如与Z1有公共顶点v，则从v开始先走Z1,Z2,…，Zp构成的闭迹后回到v，再从v走过Zp+1后回到v，即得到由Z1,Z2,…，Zp+1构成的闭迹。

这就证明了G是欧拉图。证毕。

由上述定理知，哥尼斯堡七桥问题的答案是否定的，因为从图5.22(b)可以看到，4个顶点的度数全为奇数，所以不存在欧拉闭迹。

推论5.2图G有欧拉迹当且仅当G连通且恰有两个奇数度顶点。

证设G有欧拉迹，则由定理5.9的证明可知，除了这条迹的起点和终点外的每个顶点的度数都是偶数。

假设G连通且至多有两个奇数度顶点。

如果G没有奇数度顶点，则由定理5.9得G有欧拉闭迹。

今设G恰有两个奇数度顶点u和v，则在G中u和v之间加一条边得到图G′(G′可能是多重图)，由定理5.9得G′有欧拉闭迹。从这个欧拉闭迹中去掉所加于u和v之间的边，便得到G的欧拉迹。证毕。

对于一个图是否能一笔画出的问题，欧拉给出了完全彻底的解决。完全彻底是指他给出了一个充分必要条件，因而一笔画和非一笔画的界限彻底划清了。一个连通图是否能一笔画成，实质上就是判断在给定的图形中是否存在欧拉迹和欧拉闭迹的问题。

例5.23在图5.23中，(a)和(b)两图均可一笔画成，因为它们都存在欧拉迹。

如果一个连通图的奇数度顶点的个数不是0或2，那么这个图就不能一笔画成。于是便产生了一个问题，即这时最少要多少笔才能画成呢？实际上，这个问题也与顶点度数的奇偶性有关。

与欧拉闭迹类似的问题是哈密顿圈的问题。1859年，爱尔兰数学家哈密顿在给朋友的一封信中，首先谈到在正十二面体中的一个数学游戏。这种游戏要求游戏者沿着顶点标有城市名称的正十二面体的棱行走，找一条经过每个顶点一次且仅一次的圈，如图5.24(a)所示。他把这个问题称为周游世界问题。从图5.24(b)中粗线可以看出这样一条圈是存在的。



图5.23




图5.24



定义5.19包含图的所有顶点的路称为哈密顿路； 包含图的所有顶点的圈称为哈密顿圈。存在哈密顿圈的图称为哈密顿图。

从上述定义可以看出，图5.24(b)是哈密顿图。

显然，具有哈密顿路的图是连通的，每个哈密顿图是连通的，并且每个顶点的度都大于或等于2。

例5.24对于完全图Kn(n≥3)，由于Kn中任意两个顶点之间均有边，所以，从Kn的某一个顶点开始，总可以遍历其余顶点后，再回到该顶点，因此Kn是哈密顿图。

确定哈密顿路存在问题是一个很有实用价值的问题。在运筹学里，一条哈密顿路的确定是解决许多安排问题的钥匙。然而，迄今为止并未找到确定哈密顿圈存在的简单充分必要条件，只找到了几个简单的必要条件和一些充分条件。实际上，哈密顿圈问题仍是图论中尚未解决的主要问题之一。

定理5.10如果G=(V,E)是一个哈密顿图，则对于顶点集V的每个非空真子集S，均有W(G-S)≤|S|，其中W(G-S)是G-S中连通分支的个数。

证设C是图G的一个哈密顿圈。用数学归纳法首先证明，对于顶点集V的每个非空真子集S，均有W(C-S)≤|S|。

当|S|=1时，从C中删去一顶点v，则C变为哈密顿路，但仍连通，故W(C-S)=|S|=1。

假设|S|=k时，W(C-S)≤|S|。

当|S|=k+1时，先从C中删去k个顶点v1,v2,…,vk，即令Sk={v1,v2,…,vk}。

由归纳假设W(C-Sk)≤|Sk|。再从C-Sk的任一连通分支中删去一个顶点vk+1，这时最多可使连通分支的个数增加1，故W(C-Sk+1)≤k+1=|Sk+1|。

由于C-S是G-S的生成子图，故W(G-S)≤W(C-S)≤|S|。 证毕。

上述定理给出的条件是哈密顿图的必要条件，不是充分条件。例如，在彼德森图中，满足这个条件，但它不是哈密顿图。利用该定理可以判别某些图不是哈密顿图。

例5.25图5.25(a)所示的图G，取S={v6}，G-S如图5.25(b)所示，由于W(G-S)=2＞|S|=1，所以G不是哈密顿图。



图5.25

定理5.11设G是具有n(n≥3)个顶点的图，如果G中每一对不邻接的顶点u和v，有deg(u)+deg(v)≥n，则G是哈密顿图。

证用反证法。假设定理不成立，则存在一个满足定理条件且边数最多的非哈密顿图G，即G是一个非哈密顿图，且对G的任何一对不邻接的顶点v1和v2有G+{v1,v2}是哈密顿图。因为n≥3，所以G不是完全图。

设u和v是G中两个不邻接的顶点，因此G+{u,v}是哈密顿图，在G中存在一条包含{u,v}的哈密顿圈，且存在一条包含G中所有顶点的u-v路v1v2…vn-1vn(v1=u,vn=v)。如果v1与vi(2≤i≤n)邻接，则vi-1与vn不邻接； 否则v1vivi+1…vnvi-1vi-2…v1是G的一个哈密顿圈。

因此，对{v2,v3,…,vn-1}中每个与v1邻接的顶点，存在一个{v1,v2,v3,…,vn-1}中与vn不邻接的顶点，故deg(u)+deg(v)≤deg(u)+(n-1-deg(u))=n-1，矛盾。证毕。

上述定理的条件是充分的但非必要。

例5.26图5.26所示的图G，显然任何一对不邻接的顶点的度数之和为4＜6-1=5，但G中有一条哈密顿路。



图5.26


定理5.12设G是具有n个顶点的图，如果G中每一对不邻接的顶点u和v，有deg(u)+deg(v)≥n-1，则G有哈密顿路。

证因为G中每一对不邻接的顶点u和v，有deg(u)+deg(v)≥n-1，所以G是连通图。下面只需证明G中最长路的长度为n-1即可。

假设G中的最长路为v1v2…vk，k＜n，证明v1,v2,…,vk必在G的同一个圈上。

假如v1与vk邻接，则v1v2…vkv1是G的一个圈。

假如v1与vk不邻接，则deg(v1)+deg(vk)≥n-1。设vi1,vi2,…,vir(2=i1＜i2＜…＜ir＜k)与v1邻接，则vk必与某个vis-1(2≤s≤r)邻接； 否则，vk至多与最长路上其余的顶点邻接，所以deg(v1)+deg(vk)≤r+((k-1)-r)=k-1≤(n-1)-1=n-2，这是不可能的。于是，v1v2…vis-1vkvk-1…visv1是G的一个圈。总之v1,v2,…,vk必在G的同一个圈C上。

由于G是连通的，k＜n，所以，G必有某个顶点v不在C上，但与C上某个顶点vi邻接。于是得到G的一个更长的路，这就出现了矛盾。证毕。

例5.27某工厂生产由6种不同颜色的纱织成的双色布，双色布中，每一种颜色至少可以和其他3种颜色搭配。证明： 可以挑出3种不同的双色布，它们含有所有6种颜色。

证用顶点表示纱，如果两种颜色的纱能够搭配织成双色布，则对应两个顶点之间有边，得到无向图G。

根据题意，图G中的顶点数n=6，任意顶点v，deg(v)≥3。

图G的任意一对不邻接顶点(u,w)，deg(u)+deg(w)≥3+3=6，即deg(u)+deg(w)≥n，所以图G是哈密顿图，因此图G中有哈密顿圈C。

记C=c1c2c3c4c5c6c1，即c1和c2、c3和c4、c5和c6之间有边。

在原问题中，c1和c2、c3和c4、c5和c6搭配织成双色布，所以这6种不同颜色的纱织成了3种不同的双色布。结论成立。证毕。

习题

1. 证明： 设G是连通图，G恰有2k(k≥1)个奇数度顶点，则G的全部边可以排成k条开迹，而且至少有k条开迹。

2. 判别图5.27所示的两图能否一笔画成，如果不能一笔画成，那么能几笔画成。



图5.27


3. (1) 画出一个图，使它既是哈密顿图又是欧拉图。

(2) 画出一个图，使它是哈密顿图但不是欧拉图。

(3) 画出一个图，使它不是哈密顿图但是欧拉图。

(4) 画出一个图，使它既不是哈密顿图又不是欧拉图。

4. 完全偶图Kn,m是哈密顿图的充分必要条件是什么？

5. 今有n个人，已知他们中的任何2个人合起来认识其余n-2个人。证明： 

(1) 当n≥3时，这n个人能排成一列，使中间每个人都认识两旁的人；

(2) 当n≥4时，这n个人能排成一个圆圈，使每个人都认识两旁的人。

5.6图的矩阵表示

在前面曾经讨论过图的几何图形表示法，这对于分析给定图的某些特征是十分有用的。图还可以用矩阵表示，图的矩阵表示使得图的相关信息能在计算机中储存起来并加以处理，因此，图的矩阵表示是研究图性质的最有效工具之一。

定义5.20设图G=(V,E)的顶点集V={v1,v2,…,vn}，并且假定已排好了从顶点v1到vn的次序，n×n矩阵A=(aij)称为G的邻接矩阵，其中： 

aij=1{vi,vj}∈E0{vi,vj}E

由邻接矩阵的定义可以看出，图G的邻接矩阵由V中各元素的次序所决定，对于V中各元素间不同的次序关系，得到G的邻接矩阵不唯一。但对于同一个图的这些不同的邻接矩阵来说，只要适当地交换行和列的次序就能从其中一个邻接矩阵得到另一个邻接矩阵，也就是说，这些邻接矩阵所确定的图必是同构的。因此，可以忽略V中各元素间的次序关系给图的邻接矩阵带来的不唯一性，并选取图的任何一个邻接矩阵作为该图的邻接矩阵。

图G的邻接矩阵A包含了G的全部信息：  G的顶点数n就是A的阶； G的边数m就是A中1的个数的一半； G的顶点vi的度deg(vi)等于A的第i行上1的个数； A是对称的且对角线上的元素均为0。

例5.28图5.28所示图G的邻接矩阵为 



图5.28



A=0101
1011
0101
1110



定理5.13设G是一个(n,m)图，A是G的邻接矩阵，则G中顶点vi与顶点vj间长度为l的通道的数目等于Al的元素a(l)ij的值。

证用数学归纳法，施归纳于l。

当l=1时，显然定理成立。

当l=2时，A2的元素为a(2)ij=∑nh=1aih·ahj，aih·ahj=1，当且仅当aih=1且ahj=1，这意味着在图中同时存在边{vi,vh}和{vh,vj}，就存在一条vi与vj间长度为2的通道。因此，vi与vj间长度为2的通道的数目等于a(2)ij的值。

假设当l=k＞2时，定理成立。现证l=k+1时，定理成立。

因为Ak+1=Ak·A，所以a(k+1)ij=∑nh=1a(k)ih·ahj。由归纳假设a(k)ih为vi与vh间长度为k的通道数目，当ahj=1时，{vh,vj}是G的边，所以，a(k)ih·ahj为vi与vj间并通过vh后一步就得到vj的长度为k+1的通道数目，而当ahj=0时，{vh,vj}不是G的边，所以，G中没有vi与vj间并通过vh后一步就到vj的长度为k+1的通道； 反之，G中任一vi与vj间长度为k+1的通道，在到达vj之前必通过某个顶点vh，因此，a(k+1)ij就是vi与vj间长度为k+1的通道数目。

由数学归纳法原理，定理的结论成立。证毕。 

特别地，当i=j时，元素a(k)ii的值就表示经过点vi的长度为k的圈的数目。而当i≠j时，在A～An-1的各个矩阵中，使元素a(x)ij非零的最小正整数值x，就是vi与vj的距离d(vi,vj)。

例5.29对图5.28所示的图G，能求得

A=0101101101011110A2=2121131221211213A3=2525545525255554

a(3)34=5说明v3与v4间长度为3的不同通道有5条； a(2)33=2说明经过顶点v3长度为2的圈有2条。a13=0，a(2)13=2说明v1到v3的距离d(v1,v3)=2。

定理5.14设G是一个有n个顶点的图，A是G的邻接矩阵，则G是连通的当且仅当(A+I)n-1＞0。

证设G是连通的，则对G的任两个不同的顶点vi与vj，vi与vj间至少有一条路。因此，对某l，1≤l≤p-1，a(l)ij＞0，所以∑n-1l=0a(l)ij＞0，因此

(A+I)n-1=I+C1n-1A+C2n-1A2+…+An-1≥∑n-1l=0Al＞0


设(A+I)n-1＞0，由于(A+I)n-1=I+C1n-1A+C2n-1A2+…+An-1＞0，所以，对任意i、j，1≤i、j≤n，如果i≠j，则存在一个l，1≤l≤p-1，使a(l)ij＞0，因此，vi与vj间有长度为l的通道，从而必有路，所以G是连通的。证毕。

例5.30对图5.28所示的图G，能求得(A+I)n-1＞0，所以G是连通图。

邻接矩阵虽然能够完全刻画图，但是当图的顶点较多而边相对较少时，其邻接矩阵中零元素较多，这不但浪费了存储空间，而且在处理边数与顶点数成比例的某些图论算法时，往往得不到效率高的好算法。因此，从算法设计的角度看，用邻接矩阵表示图未必是一种好方法。图的另一种可能的表示方法是用邻接表表示，该内容将在数据结构课程里学习。

习题



图5.29


1. 图5.29所示图G，求邻接矩阵A以及长度为4的v1～v4通
道的数目。

2. 偶图的邻接矩阵有什么特点？完全图的邻接矩阵有什么特点？

3. 怎样从G的邻接矩阵求的邻接矩阵？

5.7带权图与最短路问题


当用一个抽象的图模拟某个实际问题时，总希望将一些附加的信息赋予图的顶点或边，以供使用。例如，可以把城市的人口数赋予图中表示城市的顶点，还可以把两个城市之间公路的长度赋予图中表示公路的边等。抽象地，可以定义带权图。

定义5.21在图G=(V,E)中，如果对G中每个顶点v都定义了一个实数f(e)与之对应，则称G为顶点带权图，实数f(e)称为顶点v的权。如果对G中每条边e都定义了一个实数w(e)与之对应，则称G为边带权图，实数w(e)称为边e的权。

一个图G的顶点和边可以同时带权，这时称G为顶点边带权图。权在不同的问题中可以有不同的意义。在许多应用问题中，带权图频繁出现，下面讨论一个著名的应用问题，就是最短路问题。很多实际问题都可以转化成最短路问题加以解决。

设G=(V,E)是一个边带权图，每条边{vi,vj}的权记为w(vi,vj)； 如果顶点vi与vj之间无边时，令w(vi,vj)=+∞。

定义5.22设G=(V,E)是一个边带权图，路P中所有边对应的权之和称为路P的长度，记作w(P)。顶点vi与vj间长度最短的路称为vi与vj的最短路，该路的长度称为顶点vi与vj的距离，记作d(vi,vj)，即

d(vi,vj)=0vi=vj
min{w(P)|P为vi与vj间的路}vi与vj间有路
+∞vi与vj间没有路

所谓最短路问题就是在一个边带权图中，找一条从顶点a(称为源点)到另一个顶点b的最短路及其距离。

1959年，迪杰斯特拉(E.W.Dijkstra)提出了求边带权图的最短路算法，这个算法至今仍是求解这个问题的最好算法，它可以求出从给定顶点到其他每个顶点的最短路及其距离。算法步骤如下。 

(1) 设边带权图G=(V,E)有n个顶点。权w(vi,vj)≥0。设源点为a。

(2) 把V分成两个子集S和T。初始时，S={a}，T=V-S。设v是T中一个顶点，用D(v)表示从a到v但不包含T中其他顶点的最短路的长度。D(v)不一定是从a到v的距离，因为从a到v可能存在包含T中其他顶点的更短路。

(3) 对T中每一点v计算D(v)，根据D(v)值找出T中距a最短的节点x，写出a到x的最短路的长度D(x)。




图5.30

(4) 置S为S∪{x}，置T为T＼{x}，如果T=，则停止； 否则重复(3)。

可以证明，如果x是T中满足D(x)=minv∈T{D(v)}的顶点，则D(v)是从a到x的距离。

例5.31图5.30所示图G，求v1到其他顶点的最短路及其距离。

解初始置S={v1}，T={v2,v3,v4,v5,v6}，D(v1)=0，D(v2)=1，D(v3)=4，D(v4)=D(v5)=D(v6)=+∞。因为D(v2)=1是T中的最小D值，所以置S={v1,v2}，T={v3,v4,v5,v6}。然后计算： D(v3)=min{4,1+2}=3，D(v4)=min{+∞,1+7}=8，D(v5)=min{+∞,1+5}=6，D(v6)=min{+∞,+∞}=+∞。

重复上述过程，直到T=为止，整个过程概括于表5.1中，v1到各点的最短路在图5.30中用粗线画出。

表5.1



重复次数SvD(v)D(v2)D(v3)D(v4)D(v5)D(v6)

初始{v1}--14+∞+∞+∞
1{v1，v2}v21386+∞
2{v1，v2，v3}v3384+∞
3{v1，v2，v3，v5}v54710
4{v1，v2，v3，v4，v5}v479
5{v1，v2，v3，v4，v5，v6}v69


习题

1. 求图5.31所示两图中顶点s到顶点t的最短路及其距离。



图5.31


2. 一个图中最短圈的长度称为该图的围长，求图5.32所示两图的围长。



图5.32