第5章图论
图的应用非常广泛。现实世界中许多现象都能用某种图形表示，这种图形由一些点和一些连接两点间的连线组成。本章介绍图的基本知识和应用。


5.1图的基本概念


在集合论部分已给出有序对及笛卡儿积的概念，这里给出无序对及无序积的概念。
任意两个元素a和b构成的无序对，记作(a,b)，这里总有(a,b)=(b,a)。
设A和B为任意两个集合，无序对的集合{(a,b)a∈A∧b∈B}称为集合A与B的无序积，记作A&B。无序积与有序积的不同在于A&B=B&A。
例如，设A=a,b，B=1,2,3，则
A&B={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}=B&A
当集合中允许元素重复出现时称之为多重集。
5.1.1图的定义及相关概念
定义5.1图G是一个二元组(V，E)，即G=（V，E）。其中V={v1,v2,…,vn}是一个非空集合，称V中的元素vi（i=1，2，…,n）为图的结点或顶点，称V为G的顶点集，E={（vi，vj）|vi，vj∈V}，E中的元素e=（vi,vj）为图的边或弧，称E为G的边集。称|V|和|E|为图G的顶点数（阶）和边数。若图G的顶点数和边数都是有限集，则称G为有限图； 否则为无限图。V=的图称为空图。有n个顶点的图称为n阶图。E=的图称为零图。仅有一个顶点的图称为平凡图，否则为非平凡图。
如果没有特殊说明，集合V和E都假设是有限的并且假设V是非空的。
定义5.2在图G=（V，E）中，若边e=（vi,vj）是无序对，即（vi,vj）=(vj，vi),则称G为无向图，其中V是一个非空的结点（或顶点）集； E是无序积V&V的多重子集，其元素称为无向边。
在一个图G=（V，E）中，为了表示V和E分别是图G的结点集和边集，常将V记作V(G)，而将E记作E(G)。
例5.1在无向图G=(V,E)中,V=v1,v2,v3,v4,v5,
E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3),(v3,v4)},G的图形如图5.1所示。
定义5.3在图G=（V，E）中，若边e=（vi,vj）是有序对，即（vi,vj）≠(vj，vi),则称G为有向图。其中V是一个非空的结点（或顶点）集； E是笛卡儿积V×V的多重子集，其元素称为有向边，记作< vi,vj >。
例5.2在有向图G=(V,E)中，其中V=v1,v2,v3,v4，
E={<v1,v1>,<v1,v2>,<v2,v3>,<v3,v2>,<v2,v4>,<v3,v4>},G的图形如图5.2所示。


图5.1无向图



图5.2有向图







为了表示方便，常常将边用ei来表示。如图5.1中，用e1表示边（v1,v2）,e5表示边 （v1,v3）等。
有向图和无向图统称为图。由于有向图的边也称为弧，由弧构成的集合记为E。因此，为了区分有向图和无向图，有向图也记为D=（V，E），而无向图记为G=（V，E）。为方便起见，在后面的论述中，有时也用G（V，E）表示有向图。
定义5.4在无向图G=（V，E）中，
（1） 当e=(u,v)时,称u和v是e的端点，并称e与u和v是关联的。
（2） 若u≠v，则称e与u（或v）关联的次数是1; 若u=v，称e与u关联的次数为2； 若u不是e的端点，则称e与u的关联次数为0。
没有边关联的顶点称为孤立点。
在图5.1中，e1=(v1,v2)，v1、v2是e1的端点，e1与v1、v2的关联次数均为1； v5是孤立点； e2是环，e2与v2关联的次数为2。
定义5.5在有向图G=（V，E）中，
（1） 当e=<u,v>时,e是一条有向边，则称u是e的始点，v是e的终点，也称u、v为e的端点，并称e与u和v是关联的。
（2） 若u≠v，则称e与u（或v）关联的次数是1;若u=v，称e与u关联的次数为2； 若u不是e的端点，则称e与u的关联次数为0。
一条有向边的始点与终点重合，则称此条边为环。
在图5.2中，e1=<v1,v2>，v1是e1的始点，v2是e1的终点； e2=<v1,v1>，e2称为环。
定义5.6在无向图G=（V，E）中，若存在一条边e=(u,v)，则称端点u、v是相邻的。若两条边e1、e2至少有一个公共端点，则称边e1、e2是相邻的。在有向图G=(V，E)中，若存在一条边e=<u,v>，则称始点u邻接到终点v。若边e1的终点与边e2的始点重合，则称边e1、e2是相邻的。
在图5.1中，e1=(v1,v2)，端点v1、v2是相邻的； 边e1、e2是相邻的。
在图5.2中，e1=<v1,v2>,始点v1邻接到终点v2； 边e1、e2是相邻的。
5.1.2结点的度
定义5.7
（1） 设G=（V，E）为一无向图，v∈V,v关联边的次数之和称为v的度数，简称度，记作d(v)。
在图5.1中，d(v1)=3，d(v2)=4，d(v3)=4，d(v4)=1，d(v5)=0。
（2） 设G=（V，E）为一有向图，v∈V,v作为边的始点的次数之和，称为v的出度，记作d+(v)； v作为边的终点的次数之和称为v的入度，记作d－(v)； v作为边的端点的次数之和称为v的度数，简称度，记作d(v)，显然d(v)=d+(v)+d－(v)。
在图5.2中，d+(v1)=2，d－(v1)=1，d+(v2)=d－(v2)=2； d+(v3)=2,d－(v3)=1,d+(v4)=0,d－(v4)=2。
（3） 称度为1的结点为悬挂点，与悬挂点关联的边称为悬挂边。如图5.1中，v4是悬挂点，e6是悬挂边。
（4） 无向图G=(V,E)中，
最大度Δ(G)=maxd(v)v∈V(G)，最小度δ(G)=mind(v)v∈V(G)。
（5） 若G=(V,E)是有向图，定义
最大度Δ(G)=maxd(v)v∈V(G)，
最小度δ(G)=mind(v)v∈V(G),
最大出度Δ+(G)=maxd+(v)v∈V,
最大入度Δ－(G)=maxd－(v)v∈V,
最小出度δ+(G)=mind+(v)v∈V,
最小入度δ－(G)=mind－(v)v∈V。
图5.2中,Δ(G)=4，δ(G)=2，Δ+(G)=2,δ+(G)=0,Δ－(G)=2，δ－(G)=1。
例5.3在图5.1中，
∑v∈Vd(v)=d(v1)+d(v2)+d(v3)+d(v4)+d(v5)=3+4+4+1+0=12,而该图有6条边，即结点的度之和是边数的２倍。事实上这是图的一个重要性质。
定理5.1设任一图G=（V，E），其中V={v1,v2,…,vn}，边数|E|=m,则 
∑ni=1d(vi)=2m
这就是图论中著名的握手定理。
证明因为每条边有2个端点，所有顶点的度之和就等于所有以顶点作为端点的次数之和。因此，所有顶点的度之和等于边数的2倍。
若d(v)为奇数，则称v为奇点； 若d(v)为偶数，则称v为偶点。
推论任一图中，奇点个数为偶数。
证明设V1={vv为奇点}，V2={vv为偶点}，则∑v∈V1d(v)+∑v∈V2d(v)=∑v∈Vd(v)=2m,因为∑v∈V2d(v)是偶数，所以∑v∈V1d(v)也是偶数，而V1中每个点v的度d(v)均为奇数，因此V1为偶数。
对有向图，还有下面的定理。
定理5.2设有向图G=(V,E)，V={v1,v2,…,vn}，E=m，则
∑ni=1d+(vi)=∑ni=1d－(vi)=m
证明因为在有向图中，每条边有2个端点，即一个始点和一个终点。所以，同握手定理，所有顶点的入度之和等于出度之和等于边数。
如图5.2中，|E|=6,
∑v∈Vd+(v)=d+(v1)+d+(v2)+d+(v3)+d+(v4)=2+2+2+0=6
∑v∈Vd－(v)=d－(v1)+d－(v2)+d－(v3)+d－(v4)=1+2+1+2=6
设V={v1,v2,…,vn}是图G的顶点集，称d(v1),d(v2),…,d(vn)为G的度序列。如图5.1的度序列为3,4,4,1,0，图5.2的度序列是3,4,3,2。
例5.4
（1） 图G的度序列为2,2,3,3,4，则边数m是多少？
（2） 3,3,2,3；  5,2,3,1,4能成为图的度序列吗？为什么？
（3）  图G有12条边，度为3的结点有6个，其余结点的度均小于３，图G中至少有几个结点？
解
（1）  由握手定理2m=∑v∈Vd(v)=2+2+3+3+4=14，所以m=7。
（2）  由于这两个序列中有奇数个是奇点，由握手定理的推论知，它们都不能称为图的度序列。
（3）  由握手定理∑d(v)=2m=24，度为３的结点有６个占去18度，还有６度由其余结点占有，其余结点的度可为0,1,2，当均为２时所用结点数最少，所以应由３个结点占有这６度，即图G中至少有９个结点。
5.1.3完全图和补图
定义5.8在无向图中，如果有多于1条的无向边关联同一对顶点，则称这些边为平行边，平行边的条数称为重数。在有向图中，如果有多于1条的有向边的始点和终点相同，则称这些边为有向平行边，简称平行边。
定义5.9
（1） 简单图： 既不含平行边也不含环的图。含有平行边的图称为多重图。
（2） 设G=(V,E)是无向简单图，若每一对结点之间都有边相连，则称G为(无向)完全图，具有n个结点的完全图记作Kn。
（3） 设G=(V,E)为有向简单图，若每对结点间均有一对方向相反的边相连，则称G为(有向)完全图，具有n个结点的有向完全图记作Dn。
例5.5在图5.1中,e4、e5是平行边，在图5.2中，e3、e4不是平行边。这两个图都有环，图5.1中还有平行边，所以都不是简单图。
例5.6图5.3给出几个完全图的例子。
由完全图的定义可知，无向完全图Kn的边数为E(Kn)=12n(n－1),而有向完全图的边数为E(Dn)=n(n－1)。


图5.3完全图的例子


图5.3（a）中各图都是无向完全图，图5.3（b）中各图都是有向完全图，但它们都是简单图。
定义5.10设G为n阶(无向)简单图，从 n阶完全图Kn中删去G的所有边后构成的图称为G的补图，记作。类似地,可定义有向图的补图。
例5.7图5.4中是G的补图。
由补图的定义，显然有如下的结论： 
（1）  G与互为补图，即G==G； 
（2）  若G为n阶图，则E(G)∪E()=E(Kn)，且E(G)∩E()=。
定义5.11各结点的度均为k的无向简单图称为k正则图。
图5.5所示的图称为彼得森图，是3正则图。


图5.4补图



图5.5彼得森图


5.1.4子图与图的同构
定义5.12 
（1） 设G=(V,E)，G′=(V′,E′)是两个图。若V′V且E′E，则称G′是G的子图。G是G′的母图，记作G′G。
（2） 若V′V或E′E，则称是G的真子图。
（3） 若V=V′且E′E，则称G′是G的生成子图。
（4） 若V1V且V1≠，以V1为顶点集，以图G中两个端点均在V1中的边为边集的子图，称为由V1导出的导出子图，记作G［V1］。
（5） 设E1E且E1≠，以E1为边集，以E1中的边关联的结点为结点集的图G的子图，称为由E1导出的导出子图，记作G［E1］。
例5.8在图5.6中，G1、G2、G3均是G的真子图，其中G1是G的生成子图，G2是由V2={a,b,c,f}导出的导出子图G［V2］，G3是由E3={e2,e3,e4}导出的边导出子图G［E3］。


图5.6真子图、生成子图与导出子图

由于在画图时，结点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是同一个图。为了判断不同图形是否表示同一个图，在此我们给出图的同构的概念。
定义5.13设有两个图G=(V,E)，G1=(V1,E1)，如果存在双射h: V→V1，使得(u,v)∈E当且仅当(f(u),f(v))∈E1（或者<u,v>∈E当且仅当<f(u),f(v)>∈E1），且它们的重数相同，则称图G与G1同构，记作GG1。
定义说明，两个图的结点之间，如果存在双射，而且这种映射保持了结点间的邻接关系和边的重数（在有向图时还保持方向），则两个图是同构的。
例5.9图5.7中，G1G2，其中f:V1→V2，f(vi)=ui(i=1,2,…,6)； G3G4,其中
h:V3→V4，h(v1)=u3，h(v2)=u4,h(v3)=u1,h(v4)=u2。


图5.7同构图

容易看出，两个图同构的必要条件是： 
（1） 结点数相同； 
（2） 边数相同； 
（3） 度序列相同。

但这不是充分的条件，例如图5.8中图H1和H2虽然满足以上3个条件，但不同构。图H1中的4个3度结点与H2中的4个3度结点的相互间的邻接关系显然不相同。


图5.8不同构图


5.2图的连通性

哥尼斯堡（Konigsberg）七桥问题
18世纪东普鲁士的哥尼斯堡城有一条横贯全城的普雷格尔（Pregel）河，河中有两个小岛，分别为A和B，并有7座桥把两个岛和岸边连接起来，如图5.9(a)所示。当时当地的居民有个有趣的问题： 是否存在这样一种走法，从A、B、C、D四个地点的任意点开始，通过每座桥且恰好都经过一次，再回到起点。这个问题就是著名的哥尼斯堡七桥问题。
1736年，瑞士数学家欧拉（Leonhard Euler）把这个难题化成了这样的问题来看： 把两岸和小岛缩成点，桥化为边，于是“七桥问题”就等价于图5.9(b)中所画图形的一笔画问题了，如果能够一笔画成这个图，对应的“七桥问题”也就解决了。


图5.9哥尼斯堡七桥问题

经过研究，欧拉发现了一笔画的规律。他认为，能一笔画成的图形必须是连通图。连通图就是指一个图形各部分总是有边相连的，这道题中的图就是连通图。
但是，不是所有的连通图都可以一笔画成的。能否一笔画成是由图的奇、偶点的数目来决定的。那么，什么叫奇、偶点呢？
前面介绍，与奇数（单数）条边相连的点叫作奇点； 与偶数（双数）条边相连的点叫作偶点。如图5.10中的①和④为奇点，②和③为偶点。由此，有下面的结论。

（1） 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点作为起点，最后一定能以这个点为终点画完此图。例如图5.11中都是偶点，画的线路可以是： ①→③→⑤→⑦→②→④→⑥→⑦→①。



图5.10奇点与偶点




图5.11由偶点组成的连通图


（2）  凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点作为起点，另一个奇点作为终点。例如图5.10中，画的线路是： ①→②→③→①→④。
（3）  其他情况的图都不能一笔画出。
5.2.1通路和回路
定义5.14
（1） 设G=(V,E)是图,从图中结点v0到vn的一条通路（路径，Path）是图的一个点、边的交错序列v0e1v1e2v2…vn－1envn，称v0和vn是此通路的起点和终点。此通路中边的数目称为此通路的长度。
（2） 当起点和终点重合时，则称此通路为回路。
（3） 若通路中的所有边互不相同，则称此通路为简单通路； 此通路中的始点与终点相同时，称此简单通路为简单回路。
（4） 若通路中的所有结点互不相同，从而所有边互不相同，则称此通路为基本通路或初级通路（路径）； 若通路中的始点与终点相同时，称此初级通路为基本回路或初级回路（圈）。
（5） 有边重复出现的通路称为复杂通路，有边重复出现的回路称为复杂回路。
说明： 
（1） 回路是通路的特殊情况； 
（2） 基本通路（基本回路）一定是简单通路（简单回路），但反之不然，因为没有重复的结点一定没有重复的边，但没有重复的边不一定没有重复的结点； 
（3） 有时通路(v0e1v1e2v2…vn－1envn)也可以用边的序列e1e2…en来表示。
例5.10图5.12（a）所示图中的通路：

Γ1=v1e1v2e5v5e7v6

Γ2=v1e1v2e2v3e3v4e4v2e5v5e7v6

Γ3=v1e1v2e5v5e6v4e4v2e5v5e7v6


是否为简单通路、基本通路和复杂通路？
图5.12（b）所示图中的回路：

Γ1=v2e4v4e3v3e2v2

Γ2=v2e5v5e6v4e3v3e2v2

Γ3=v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2


是否为简单回路、基本回路和复杂回路？并求其长度。


图5.12例5.10题图

解根据定义5.14得通路Γ1是基本通路，长度是3； 通路Γ2是简单通路，长度是6； 通路Γ3是复杂通路，长度是6； 回路Γ1是基本回路，长度是3； 回路Γ2是基本回路，长度是4； 回路Γ3是复杂回路，长度是7。
图中的通路和回路有下面的重要性质。
定理5.3在一个n阶图G=(V,E)中，如果从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度不大于n－1的通路。
证明设v0e1v1e2v2…vl－1elvl是从vi=v0到vj=vl的一个通路，如果l>n－1，因为n阶图中有n个顶点，所以在v0,v1,…,vl中一定有2个顶点相同。假设顶点vm=vn,m<n，那么vmemvm+1em+1…vnen是一条回路，删去这条回路，得到v0e1v1…vmen+1…vl－1elvl仍然是从vi=v0到vj=vl的一个通路，其长度减少n-m。如果它的长度仍大于n－1,重复上述过程，直到长度不超过n－1的通路为止。
推论在一个n阶图G=(V,E)中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度不大于n－1的路径。
证明由定理5.3可知，从vi到vj存在长度不大于n－1的通路。若这个通路已经是路径，则推论成立，否则必存在若干顶点在这条通路上的回路，删除这些回路，就得到vi到vj存在长度不大于n－1的路径。
定理5.4在一个n阶图G=(V,E)中，若存在顶点vi到自身的回路，则存在vi到自身长度小于或等于n的回路。
证明方法类似于定理5.3。
推论在一个n阶图G=(V,E)中，若存在顶点vi到自身的简单回路，则一定存在vi到自身长度小于或等于n的基本回路（圈）。
证明方法类似于定理5.3的推论。
定义5.15在图G=(V,E)中，从结点vi到vj的最短通路（一定是路）称为vi与vj间的短程线，短程线的长度称vi到vj的距离，记作d(vi,vj)。若从vi到vj不存在通路，则记d(vi,vj)=∞。
注意： 在有向图中，d(vi,vj)不一定等于d(vj,vi)，但一般有如下性质： 
（1）  d(vi,vj)≥0； 
（2）  d(vi,vi)=0； 
（3）  d(vi,vj)+d(vj,vk)≥d(vi,vk)（通常称为三角不等式）。
5.2.2图的连通性
定义5.16在一个无向图G中，若存在从结点vi到vj的通路（当然也存在从vj到vi的通路），则称vi与vj是连通的。规定vi到自身是连通的。
在一个有向图G中，若存在从结点vi到vj的通路，则称从vi到vj是可达的。规定vi到自身是可达的。
定义5.17若无向图G中任意两结点都是连通的，则称图G是连通图，否则称G是非连通图或分离图。
显然，无向完全图Kn(n≥1)都是连通图，而顶点数大于或等于2的零图均为非连通图。
定义5.18在无向图G中，结点之间的连通关系是等价关系。设G为一无向图，R是V(G)中结点之间的连通关系，由R可将V(G)划分成k(k≥1)个等价类，记作V1,V2,…,Vk，由它们导出的导出子图G［V1］,G［V2］,…,G［Vk］称为G的连通分支，其个数应为ω(G)。
例5.11如图5.13所示的图G1是连通图，ω(G1)=1； 图G2是一个非连通图，ω(G2)=3。


图5.13连通图和非连通图

定义5.19
（1） 设G是一有向图，若略去G中各有向边的方向后所得无向图是连通的，则称G是弱连通的。
（2） 如果G中任意两点vi和vj之间，vi到vj或vj到vi至少有一个可达，则称图G是单向连通的。
（3） 如果G中任意两结点都互相可达，则称G是强连通的。
例5.12在图5.14中，G1是弱连通的，G2是单向连通的，G3是强连通的。


图5.14单向连通、弱连通和强连通

注意： 强连通一定是单向连通图，单向连通一定是弱连通图，但反之不真。

5.2.3无向图的连通度
为了精确地体现连通图的连通程度，引入顶点连通度和边连通度的概念，在给出这两个概念之前，先给出点割集和边割集的概念。
定义5.20设无向图G=(V,E)，若存在V′V且V′≠，使得ω(G－V′)>ω(G)，且对于任意的V″V′，均有ω(G－V″)=ω(G)，则称V′是G的点割集。特别地，若点割集中只有一个顶点，即V′={v}，则称v为割点。
例5.13在图5.15中，{v2,v7},{v3},{v4}为点割集，其中v3、v4均为割点。


图5.15割点

定义5.21设无向图G=(V,E)，若存在E′E且E′≠，使得ω(G－E′)>ω(G)，且对于任意的E″E′，均有ω(G－E″)=ω(G)，则称E′是G的边割集，简称割集。特别地，若边割集中只有一条边e，即E′={e}，则称e为割边或桥。
例5.14在图5.15中，{e1,e2},{e1,e3,e4},{e6},{e7,e8},{e2,e3,e4}等都是割集，其中e6是桥。
定义5.22设G=(V,E)是一个无向图，要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少顶点数称为G的顶点连通度，简称连通度,记为χ=χ(G)。
说明： 对于特殊的图，顶点连通度是已知的。
（1） K1平凡图χ(K1)=0；  有割点的图χ(G)=1。
（2） 不连通的图χ(G)=0；  完全图Kp(p≥2)χ(Kp)=p－1。
（3） 若G连通，则χ(G)≥1； 若χ(G)≥1，则G连通或是非平凡图。
不难看出在图5.15中，图的顶点连通度χ=1，该图是1连通图。
定义5.23设G=(V,E)是一个无向图，要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少边数称为G的边连通度，简称连通度，记为λ=λ(G)。
说明： 
（1） 对于连通图，边连通度就是割集中最小的那个； 
（2） 对于一个图，割集可以有多个，但边连通度只有一个； 
（3） 对于非平凡图，割集永远也不能为零（空集），但边连通度在图不连通时是零。
不难看出在图5.15中，图的边连通度λ=1，该图是1连通图。
顶点连通度χ(G)、边连通度λ(G)、最小度δ(G)之间有以下的关系。
定理5.5（Whitney定理）对任一图G，均有下面的不等式成立。
χ(G)≤λ(G)≤δ(G)
证明先证λ(G)≤δ(G)，若δ(G)=0，则G不连通，从而λ(G)=0。所以，这时λ(G)≤δ(G)； 若δ(G)>0，不妨设degv=δ(G)，从G中去掉与v关联的δ(G)条边后，得到图中v是孤立顶点。所以，这时λ(G)≤δ(G)。因此，对任何图G有λ(G)≤δ(G)。
其次，证明对任何图G有χ(G)≤λ(G)。若G是不连通的或平凡图，则显然有χ(G)≤λ(G)=0； 
现设G是连通的且非平凡的。若G有桥x，则去掉x的某个端点就得到一个不连通图或平凡图，从而χ(G)=1=λ(G)。所以，这时有χ(G)≤λ(G)； 若G没有桥，则λ(G)≥2。于是，从G中去掉某些λ(G)边得到一个不连通图。这时从G中去掉λ(G)条边的每一条的某个端点后，至少去掉了λ(G)条边。于是，产生了一个不连通图或平凡图，从而χ(G)≤λ(G)。 因此，对任何G，均有χ(G)≤λ(G)。

5.3图的矩阵表示

由图的数学定义可知，一个图可以用集合来描述； 从前面的例子可以看出，图也可以用点线图表示，图的这种图形表示直观明了，在较简单的情况下有其优越性。但对于较为复杂的图，这种表示法显示了它的局限性。所以对于结点较多的图常用矩阵来表示，这样便于用代数知识来研究图的性质，同时也便于计算机处理。
5.3.1无向图的关联矩阵
定义5.24设无向图G=(V,E)，V={v1,v2,…,vn}，E={e1,e2,…,em}，
令
mij=0,vi与ej不关联

1,vi与ej的关联次数为1

2,vi与ej的关联次数为2
则称(mij)n×m为G的关联矩阵，记作M(G)。


图5.16例5.15题图

例5.15图5.16中图G的关联矩阵是

M(G)=111100
110000
001021
000101
000000

不难看出M（G）有下列性质： 
（1）  ∑ni=1mij=2(j=1,2,…,m)，即M(G)每列元素的和为2，因为每边恰有两个端点； 
（2） ∑mj=1mij=d(vi)（第i行元素之和为vi的度）； 
（3） ∑mj=1mij=0，当且仅当vi为孤立点； 
（4）  若第j列与第k列相同，则说明ej与ek为平行边。
5.3.2有向图的关联矩阵
定义5.25设G=(V,E)是无环有向图，V={v1,v2,…,vn}，E={e1,e2,…,em},
令
mij=1,vi为ej的起点
0,vi与ej不关联
－1,vi为ej的终点
则称(mij)n×m为G的关联矩阵，记作M(G)。


图5.17 例5.16题图

例5.16图5.17中图G的关联矩阵是
M(G)=－11000
101－10
0－1－111
0000－1


由此可看出M(G)有如下性质： 
（1）  ∑ni=1mij=0,j=1,2,…,m； 
（2）  每行中1的个数是该点的出度，-1的个数是该点的入度。
5.3.3有向图的邻接矩阵
定义5.26设G=(V,E)是有向图，V={v1,v2,…,vn}，令
a(1)ij=k,从vi邻接到vj的边有k条
0,没有vi到vj的边


图5.18例5.17题图

则称(a(1)ij)n×n为G的邻接矩阵，记作A(G)，简记A。

例5.17图5.18中图G的邻接矩阵是

A=1010
0010
0101
0010

有向图的邻接矩阵具有下列性质： 
（1） ∑nj=1a(l)ij=d+(vi),i=1,2,…，n，因而∑ni=1∑nj=1a(l)ij=∑ni=1d+(vi)=m； 
（2） ∑ni=1a(l)ij=d-(vj),j=1,2,…，n，因而∑nj=1∑ni=1a(l)ij=∑nj=1d－(vj)=m； 
（3） 由（1）和（2） 不难看出，A(G)中所有元素之和是G中长度为l的通路（含回路）数，而∑ni=1a(l)ii为G中长度为l的回路总数。
如何利用有向图的邻接矩阵计算出有向图中长度为l≥2的通路数和回路数？有下面的定理及推论。
定理5.6设A为有向图G的邻接矩阵，V={v1,v2,…,vn}，则Al(l≥1)中元素a(l)ij为vi到vj长度为l的通路数，∑ni=1∑nj=1a(l)ij为G中长度为l的通路（含回路）总数，其中∑ni=1a(l)ii为G中长度为l的回路数。
如在图5.18中，计算长度为2、3、4的通路数和回路数，计算A2、A3、A4得
A2=1111
0101
0020
0101A3=1131
0020
0202
0020A4=1333
0202
0040
0202

观察各矩阵发现，a(2)13=1,a(3)13=3,a(4)13=3,即G中v1到v3长度为2、3、4的通路分别为1条、3条、3条。而a(2)11=a(3)11=a(4)11=1，则G中以v1为起点（终点）的长度为2、3、4的回路各有一条。由于∑ni=1∑nj=1a(2)ij=10，所以G中长度为2的通路总数为10，其中长度为2的回路总数为5。
推论设Br=A+A2+…+Ar(r≥1)，则Br中元素b(r)ij为图G中vi到vj长度小于或等于r的通路数，∑ni=1∑nj=1b(r)ij为图G中长度小于或等于r的通路（含回路）总数，其中∑ni=1b(r)ii为图G中长度小于或等于r的回路总数。
例如，与图5.18对应的矩阵为
B4=4585
0333
0363
0333
对于无向图可类似地定义邻接矩阵，对有向图的邻接矩阵得到的结论，可并行地用到无向图上。
5.3.4有向图的可达矩阵
定义5.27设G=(V,E)是有向图，V={v1,v2,…,vn}，令
pij=1,vi可达vj（i≠j,pii=1）

0,否则i=1,2,…,n，j=1,2,…,n


图5.19例5.18题图


则称(pij)n×n为G的可达矩阵，记作P(G)，简记P。

例5.18图5.19所示有向图G的可达矩阵为
P=11111
11111
11111
11111
11111

由于任何顶点到自身都是可达的，故可达矩阵对角线上的元素恒为1。vi可达vj，即vi到vj有通路，当且仅当b(n－1)ij≠0(i≠j)。因此，p(D)中非对角线元素确定如下： 当b(n－1)ij≠0时，
pij=1，否则pij=0,i≠j,i,j=1,2,…,n。所以，可由有向图的邻接矩阵求可达矩阵。
类似地，可以定义无向图的邻接矩阵和可达矩阵。

5.4最短路径与关键路径

在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，如在企业管理中，如何制订管理计划和设备购置计划，使收益最大或费用最小； 在组织生产中，如何使各工序衔接好，才能使生产任务完成得既快又好； 在现有交通网络中，如何使调运的物资数量多且费用最小； 等等。这类问题均可借助于图论中最短路径及关键路径知识得以解决。
5.4.1问题的提出
网络图中某两点的最短路径问题广泛应用于各个领域。例如，求交通距离最短，完成各道工序所花时间最少，或费用最省等，都可用求网络最短路径算法得到解决。
例5.19图5.20是一个石油流向的管网示意图，v1代表石油开采地，v7代表石油汇集站，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？ 


图5.20石油流向的管网示意图


也可以用点代表城市，以连接两点的连线表示城市间的道路，这样便可用图形描述城市间的交通网络。如果连线旁标注城市间道路的距离或单位运价，就可进一步研究从一个城市到另一个城市的路径最短或运费最省的运输方案。
在动态规划中，最短路径问题可由贝尔曼最优化原理及其递推方程求解，在阶段明确情况下，用逆向逐段优化嵌套推进，这是一种反向搜索法； 在阶段不明确情况下，可用函数迭代法逐步正向搜索，直到指标函数衰减稳定得解。这些算法都是依据同一个原理建立的。即在网络图中，如果v1…vn是从v1到vn的最短路径，则v1…vn-1也必然是从v1到vn-1的最短路径。
那么,如何用图论来分析及求解网络最短路径问题呢？
5.4.2最短路径
定义5.28图G是一个三重组(V，E，W)，其中V是结点集合，E是边的集合，W={w(e)|e∈E}，w(e)是附加在边e上的实数，称为边e上的权，图G称为带权图。
图5.20给出一个带权图。

E={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}

V={v1,v2,v3，v4,v5,v6，v7}
={<v1,v2>,<v1,v3>,<v2,v5>,<v2,v4>,<v3,v4>,

<v3,v6>,<v4,v5>,<v4,v6>,<v5,v7>,<v6,v7>}
w(e1)=20,w(e2)=15，w(e3)=24,w(e4)=8,w(e5)=10,

w(e6)=6，w(e7)=10,w(e8)=8，w(e9)=11,w(e10)=20

定义5.29设带权图G=(V，E，W)中，边的权也称为边的长度，一条通路的长度指的就是这条通路上各边的长度之和。从结点u到v的所有通路中长度最小的通路，称为u到v的最短路径。u到v的最短路径的长度称为u到v的距离。
下面介绍求解两个结点之间最短路径问题的一种简便、有效的算法——Dijkstra算法。
1959年狄克斯特拉（E．W．Dijkstra）提出了求网络最短路径的标号法，用给结点记标号来逐步形成起点到各点的最短路径及其距离值，这种方法被称为Dijkstra算法，被公认为目前较好的一种算法。
算法的基本思想是： 先给带权图G的每一个结点一个临时标号(Temporary Label，T标号）或固定标号(Permanent Label，P标号）。T标号表示从始点到这一点的最短路长的上界； P标号则是从始点到这一点的最短路长。每一步将某个结点的T标号改变为P标号，则最多经过n-1步算法停止（n为G的结点数）。
最短路径的Dijkstra算法： 
（1）  给始点v1标上P标号p(v1)=0，令P0={v1}，T0=V-{v1}，给T0中各结点标上T标号t0(vj)=w1j(j=2,3,…,n),令r=0，转步骤（2）。
（2）  若minvj∈Tr{tr(vj)}=tr(vk)，则令Pr+1=Pr∪{vk}，Tr+1=Tr－{vk}。若Tr+1=，则结束，否则转步骤（3）。
（3）  修改Tr+1中各结点vj的T标号： Tr+1(vj)=min{tr(vj)，tr(vk)+wkj},转步骤（2）。
例5.20求图5.21（a）中结点v1到v7的最短路径。


图5.21 例5.20题图

解根据Dijkstra算法，在图5.21(a)中用方框表示P标号，用圆框表示T标号，凡图5.21中无标号的点即该点的标号为+∞（下同）。
（1）  p(v1)=0,P0={v1},T0={v2,v3,v4,v5,v6,v7},T0中各元素的T标号为t0(v2)=2,…，如图5.21(b)所示。
（2） minvj∈T0{t0(vj)}=t0(v4)，将v4的标号T改为P标号，且P1=P0∪{v4}={v1,v4}。
T1={v2,v3,v5,v6,v7},修改T1各结点的T标号为： 
t1(v2)=min{t0(v2),t0(v4)+w42}=min{2,1+∞}=2
t1(v3)=min{t0(v3),t0(v4)+w43}=min{8,1+7}=8
t1(v6)=min{t0(v6),t0(v4)+w46}=min{+∞,1+9}=10
t1（v7）=t1(v5)=min{+∞,1+∞}=+∞

如图5.21(c),依此类推可得各结点的P标号，标号过程如图5.21(a)~(h)所示,由图5.21(h)可知，v1到v7的距离为6，v1到v7的最短路径为v1v2v5v7。


例5.21以图5.20给出的石油流向的管网示意图为例，v1代表石油开采地，v7代表石油汇集站，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？
解（1） 给起点v1标号（0，λ），从v1到v1的距离p(v1)＝0，v1为起点。
（2） 标号的点的集合P0＝｛v1｝，没有标号的点的集合T0={v2,v3,v4,v5,v6,v7}，边集为
A={(vi,vj)vi∈P0,vj∈T0}={(v1,v2),(v1,v3)}
T12=p(v1)+ω12=0+20=20
T13=p(v1)+ω13=0+15=15

min{T12,T13}=T13=15

给边(v1,v3)的终点v3以双标号（15，1）。
（3） 标号的点的集合P1={v1,v3}，没有标号的点的集合T1={v2,v4,v5,v6,v7}，边集为
A={(vi,vj)vi∈P1,vj∈T1}={(v1,v2),(v3,v4),(v3,v6)}
T34=25，T36=21

min{T34,T36,T12}=T12=20
给边(v1,v2)的终点v2以双标号（20，1）。
（4） 标号的点的集合P2={v1,v2,v3}，没有标号的点的集合T2={v4,v5,v6,v7}，边集为
A={(vi,vj)vi∈I,vj∈J}={(v2,v4),(v2,v5),(v3,v4),(v3,v6)}
T24=p(v2)+ω24=20+8=28
T25=p(v2)+ω25=20+24=44

min{T24,T25,T34,T36}=T36=21
给边(v3,v6)的终点v6以双标号（21，3）。
（5） 标号的点的集合P3={v1,v2,v3,v6}，没有标号的点的集合T3={v4,v5,v7}，边集为
A={(vi,vj)vi∈P3,vj∈T3}={(v2,v4),(v2,v5),(v3,v4),(v6,v7)}
T67=p(v6)+ω67=21+20=41

min{T24,T25,T34,T67}=T34=25
给边(v3,v4)的终点v4以双标号（25，3）。
（6） 标号的点的集合P4={v1,v2,v3,v4,v6}，没有标号的点的集合T4={v5,v7}，边集为
A={(vi,vj)vi∈I,vj∈J}={(v2,v5),(v4,v5),(v6,v7)}
T45=p(v4)+ω45=25+10=35

min{T25,T45,T67}=T45=35
给弧(v4,v5)的终点v5以双标号（35，4）。
（7） 标号的点的集合P5={v1,v2,v3,v4,v5,v6}，没有标号的点的集合T5={v7}，边集为
A={(vi,vj)vi∈I,vj∈J}={(v5,v7),(v6,v7)}
T57=p(v5)+ω57=35+11=46

min{T57,T67}=T67=41
给边(v6,v7)的终点v7以双标号（41，6）。
至此，全部顶点都已得到标号，计算结束。得到石油开采地v1到汇集点v7的最短路径，即v1→v3→v6→v7，由v7的第一个标号可知路程长41。
对于无向图的Dijkstra算法求解： 无向图中的任一条边(vi,vj)均可用方向相反的两条边(vi,vj)和(vj,vi)来代替。把原来的无向图变为有向图后，即可用上述的Dijkstra算法求解。
当然，也可以直接在原来的无向图上用Dijkstra算法求解。在无向图上求解与在有向图上求解的区别在于寻找邻点时不同： 在无向图上，只要两结点之间有连线，就是邻点。因此，在无向图上的求解和在相应的有向图上求解相比，计算过程中的邻点个数可能增多，边集合中的边数也就随着增多。计算结束时，一定是所有结点都得到了标号，且其最优结果不会劣于相应有向图的最优结果。
5.4.3关键路径
在实施一个工程计划时，若将整个工程分成若干工序，有些工序可以同时实施，有些工序必须在完成另一些工序后才能实施，工序之间的次序关系可以用有向图来表示，这种有向图称为计划评审技术（Project Evaluation and Review Technique）图，简称PERT图。
定义5.30设有向图
G=<V,E>，v∈V
v的后继元集Γ +(v)={x|x∈V∧<v,x>∈E}
v的先驱元集Γ -(v)={x|x∈V∧<x,v>∈E}

定义5.31设G=（V,E,w）是一个n阶有向带权图,满足以下条件：
(1) G是简单图；
(2) G中无回路；
(3) 有一个入度为0的顶点称作始点; 有一个出度为0的顶点称作终点；
(4)  通常边<vi,vj>的权表示时间，始点记作v1，终点记作vn。

则称G为PERT图。
定义5.32关键路径: PERT图中从始点到终点的最长路径。通过求各顶点的最早完成时间来求关键路径。
vi的最早完成时间TE(vi): 从始点v1沿最长路径到vi所需的时间。
TE(v1)=0
TE(vi)=max{TE(vj)+wji|vj∈Γ -(vi)}，i=2,3,…,n

vi的最晚完成时间TL(vi): 在保证终点vn的最早完成时间不增加的条件下，从始点v1最迟到达vi的时间。
TL(vn)=TE(vn)
TL(vi)=min{TL(vj)-wij|vj∈Γ +(vi)}，i=n-1,n-2,…,1
vi的缓冲时间TS(vi)=TL(vi)-TE(vi)，i=1,2,…,n
vi在关键路径上TS(vi)=0
因为在关键路径上，任何工序如果耽误了时间t，整个工序就耽误了时间t，因而在关键路径上各顶点的缓冲时间均为0。
例5.22求图5.22所示的PERT图中各顶点的最早、最晚和缓冲时间以及关键路径。


图5.22例5.22题图

解各点最早完成时间： 
TE(v1)=0
TE(v2)=max{0+1}=1
TE(v3)=max{0+2,1+0}=2
TE(v4)=max{0+3,2+2}=4
TE(v5)=max{1+3,4+4}=8
TE(v6)=max{2+4,8+1}=9
TE(v7)=max{1+4,2+4}=6
TE(v8)=max{9+1,6+6}=12
各点最晚完成时间： 
TL(v8)=12
TL(v7)=min{12-6}=6
TL(v6)=min{12-1}=11
TL(v5)=min{11-1}=10
TL(v4)=min{10-4}=6
TL(v3)=min{6-2,11-4,6-4}=2
TL(v2)=min{2-0,10-3,6-4}=2
TL(v1)=min{2-1,2-2,6-3}=0
各点缓冲时间： 
TS(v1)=0-0=0
TS(v2)=2-1=1
TS(v3)=2-2=0
TS(v4)=6-4=2
TS(v5)=10-8=2
TS(v6)=11-9=2
TS(v7)=6-6=0
TS(v8)=12-12=0
关键路径: v1v3v7v8。
关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小的浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

5.5欧拉图与哈密顿图

本节介绍两种特殊的连通图，一种是具有经过所有边的简单生成回路的图； 另一种是具有生成圈的图。
5.5.1欧拉图
欧拉图产生的背景就是前面介绍的哥尼斯堡七桥问题图。在图中是否存在经过每条边一次且仅一次行遍所有顶点的回路？欧拉在他的论文中论证了这样的回路是不存在的。称具有这种特点的图为欧拉图。
定义5.33设有向图（无向图）G=(V，E )是连通的、无孤立点的图。
(1) 若存在这样的通路，经过图中每条边一次且仅一次就可以行遍所有顶点，称此通路为欧拉通路； 
(2) 若存在这样的回路，经过图中每条边一次且仅一次就可以行遍所有顶点，称此回路为欧拉回路； 具有欧拉回路的图称为欧拉图； 
(3) 具有欧拉通路但无欧拉回路的图称为半欧拉图。
规定： 平凡图为欧拉图。
例5.23判断图5.23所示各图中哪些是欧拉图？哪些是半欧拉图？


图5.23例5.23题图

解此例中，图5.23(a)、图5.23(b)是欧拉图； 图5.23(c)是半欧拉图； 图5.23(d)中不存在欧拉通路，更不存在欧拉回路。这是因为图5.23(a)中有欧拉回路(abcdeca)。对于图5.23(b)、图5.23(c)，读者可做类似的研究。
判断一个图是欧拉图，还是半欧拉图，按定义来判断很复杂，有时甚至是不可能的，因此可由下面的定理来判断。
定理5.7（欧拉定理）设G=(V，E )是无孤立点的无向图，G是欧拉图当且仅当G连通且无奇度顶点。
证明若G为平凡图，则定理显然成立。下面讨论非平凡图。
必要性设C是G中一条欧拉回路，则
（1） 图G是连通的。因为图G中无孤立点，所以图G中的每个结点都有一些边与之关联，而欧拉回路C包含了图G中的每一条边，回路C在通过各边的同时必通过图G中每个顶点。所以图G中每个结点都在回路C上。因此，图G中任何2个顶点，都可以通过回路C相互到达，故图G是连通的。
（2） 图G中无奇度顶点。vi∈V，vi在C上每出现1次获2度，所以vi为偶度顶点。由vi的任意性，结论为真。
充分性对边数m作归纳法。
（1） m=1时，G为一个环，则G为欧拉图。
（2） 设m≤k(k≥1)时结论为真，则m=k+1时证明如下： 
① 制造满足归纳假设的若干小欧拉图。由连通及无奇度顶点可知，δ(G)≥2，用扩大路径法可得G中长度≥3的圈C1。删除C1上所有的边（不破坏G中顶点度数的奇偶性）得G′，则G′无奇度顶点，设它有s(s≥1)个连通分支G′1,G′2,…,G′s，它们的边数均≤k，因而它们都是小欧拉图。设C′1,C′2,…,C′s是G′1,G′2,…,G′s的欧拉回路。
② 将C1上被删除的边还原，从C1上某一顶点出发走出G的一条欧拉回路C。
综上所述，定理充分性成立。
推论设G=(V,E)是无孤立点的无向图，G有欧拉通路当且仅当G连通且恰有2个奇度顶点。
证明必要性设G是m条边的n阶无向图，因为G中存在欧拉通路（但不存在欧拉回路），设Γ=vi0ej1vi1ej2…vim－1ejmvim为G中一条欧拉通路，vi0≠vim。v∈V(G)，若v不在Γ的端点出现，显然d(v)为偶数，若v在端点出现过，则d(v)为奇数，因为Γ只有两个端点且不同，因而G中只有两个奇度顶点。另外，G的连通性是显然的。
充分性（利用欧拉定理）
设u和v为G中的两个奇度顶点，令G′=G∪(u,v)，则G′连通且无奇度顶点，由欧拉定理知G′为欧拉图，因而存在欧拉回路C，令Γ=C－(u,v)，则Γ为G中的欧拉通路。


图5.24例5.24题图

例5.24图G如图5.24所示。图G是否是欧拉图？若是，求其欧拉回路。

由于图G中6个顶点的度都为偶数且图G连通，根据欧拉定理可知G为欧拉图。
在图G中任意找一简单回路C： （1,2,3,1）。还有7条边不在该回路中，边（3,4）不在C中且与回路中的顶点3相关联，由顶点3出发经过边（3,4）可得到一简单回路C′(3,4,5,3)，将C′并入C得到了一个新的更长的简单回路C： （1,2,3,4,5,3,1）。
此时仍有4条边不在回路C中，边（4,6）不在C中且与顶点4相关联，由顶点4出发经过边（4,6）又可得到一个简单回路C″： （4,6,5,2,4）。将C″并入C得到一个更长的简单回路C： （1,2,3,4,6,5,2,4,5,3,1）。可以看到，G中所有的边已全部在C中了，故得此回路为G中的一条欧拉回路。
定理5.8有向图G是欧拉图当且仅当G是弱连通的且每个顶点的入度等于出度。
本定理的证明类似于定理5.7。读者可以自己证明。
推论有向图G有欧拉通路当且仅当G是单向连通的且G中恰有2个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。
本推论的证明类似于定理5.7。
定理5.7和定理5.8提供了欧拉通路与欧拉回路的十分简便的判别准则。
根据定理5.7和定理5.8再判断例5.24中各个图，哪些图是欧拉图？哪些图是半欧拉图？
例5.25欧拉图的应用——一笔画问题。
所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复地画完该图。“一笔画问题”本质上就是一个无向图是否存在欧拉通路（回路）的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点； 如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点； 如果该图中不存在欧拉通路，则不能一笔画完该图。
例5.26图 5.25所示的三个图能否一笔画成？为什么？


图5.25例5.26题图


解因为图5.25（a）和图5.25（b）中分别有0个和2个奇数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画成，并且在图5.25（a）中笔能回到出发点，而图5.25（b）中笔不能回到出发点。图5.25（c）中有4个度为3的结点，所以不存在欧拉通路，因此不能一笔画成。
例5.27计算机磁鼓的设计如图5.26所示。


图5.26例5.27题图

计算机旋转磁鼓的表面被等分成2n个部分，与n个电刷相接触。绝缘体(空白部分)不通电表示信号0； 导体(阴影部分)通电表示信号1。从而n个电刷上就产生一n位二进制信号。
问： 鼓轮上的8个扇区应如何安排导体或绝缘体，使鼓轮旋转一周，触点输出一组不同的二进制信号？

每转一个扇区，信号a1a2a3变成a2a3a4，前者右两位决定了后者左两位。因此，把所有两位二进制数作为结点，从每一个结点a1a2到a2a3引一条有向边表示a1a2a3这三位二进制数，作出表示所有可能数码变换的有向图，如图5.26(b)。于是问题转化为在这个有向图上求一条欧拉回路，这个有向图的4个结点的度都是出度、入度各为2，图5.26(b)中有欧拉回路存在，例如(e0e1e2e5e3e7e6e4)是一欧拉回路，对应于这一回路的德布鲁因序列是00010111，因此材料应按此序列分布。
用类似的论证，可以证明存在一个2n个二进制的循环序列，其中2n个由n位二进制数组成的子序列都互不相同。例如16个二进制数的布鲁因序列是0000101001101111。
此序列称为德布鲁因（De Bruijn）序列。这一应用是由Good(1946)提出的。
欧拉图的应用——中国邮递员问题。
1962年我国的管梅谷首先提出并研究了如下的问题： 邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，邮递员希望找出一条行走距离最短的路线。这个问题被外国人称为中国邮递员问题（Chinese Postman Problem）。
把邮递员的投递区域看作一个连通的带权无向图G，其中G的顶点被看作街道的交叉口和端点，街道被看作边，权被看作街道的长度。解决中国邮递员问题，就是在连通带权无向图中，寻找经过每边至少一次且权和最小的回路。
如果对应的图G是欧拉图，那么从对应于邮局的顶点出发的任何一条欧拉回路都是符合上述要求的邮递员的最优投递路线。
如果图G只有两个奇点x和y，则存在一条以x和y为端点的欧拉链，因此由这条欧拉链加x到y的最短路即是所求的最优投递路线。
如果连通图G不是欧拉图也不是半欧拉图，由于图G有偶数个奇点，对于任两个奇点x和y，在G中必有一条路连接它们。将这条路上的每条边改为二重边得到新图H1，则x和y就变为H1的偶点，在这条路上的其他顶点的度均增加2，即奇偶数不变，于是H1的奇点个数比G的奇点个数少2。对H1重复上述过程得H2，再对H2重复上述过程得H3，……，经若干次后，可将G中所有顶点变成偶点，从而得到多重欧拉图G′（在G′中，若某两点u和v之间连接的边数多于2，则可去掉其中的偶数条多重边，最后剩下连接u与v的边仅有1条或2条，这样得到的图G′仍是欧拉图）。这个欧拉图G′的一条欧拉回路就相当于中国邮递员问题的一个可行解，且欧拉回路的长度等于G的所有边的长度加上由G到G′所添加的边的长度之和。但怎样才能使这样的欧拉回路的长度最短呢？如此得到的图G′中最短的欧拉回路称为图G的最优环游。
5.5.2哈密顿图
哈密顿图是由威廉·哈密顿(Willian Hamilton)爵士于1856年在解决关于正十二面体的一个数学游戏时首次提出的。
1856年哈密顿爵士发明了一种数学游戏： 一个人在(实心的)正十二面体的任意5个相继的顶点(正十二面体由12个相同的正五边形组成，有20个顶点和30条棱)上插上5个大头针，形成一条路，要求另一个人


图5.27环球航行问题

扩展这条路，以形成一条过每个顶点一次且仅一次的圈。

哈密顿爵士在1859年将他的正十二面体数学游戏重新叙述为： 能否在全球选定的20个都会城市(据说有中国三个城市——北京、上海、西安)中，从任一城市出发，进行环球航行，经过这20个城市一次且仅一次(不能去其他城市)，然后回到出发点。这就是著名的环球航行问题或周游世界问题。哈密顿给出了这个问题的肯定的答案，如图5.27所示。按照图5.27中所给城市的编号行遍，可得所要求的回路，对于一般的连通图G也可以提出这样的问题，即能否找到一条含图中所有顶点的基本通路或回路。

定义5.34设有图G=(V，E)：
(1) 哈密顿通路——经过图中所有顶点一次且仅一次的通路。
(2) 哈密顿回路——经过图中所有顶点一次且仅一次的回路。
(3) 哈密顿图——具有哈密顿回路的图。
(4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图。
说明： 
（1） 平凡图是哈密顿图。
（2） 哈密顿通路是基本通路，哈密顿回路是基本回路。
（3） 环与平行边不影响哈密顿性。
（4） 哈密顿图的实质是能将图中的所有顶点排在同一个圈上。
例5.28判断图5.28中哪些图是哈密顿图？哪些是半哈密顿图？


图5.28例5.28题图

解图5.28(a)、图5.28(b)是哈密顿图； 图5.28(c)是半哈密顿图； 图5.28(d)既不是哈密顿图，也不是半哈密顿图。
到目前为止，还没有简明的条件作为判断一个图是否为哈密顿图的充要条件，因此研究哈密顿图要比研究欧拉图难些。下面给出一些哈密顿通路、回路存在的必要条件或充分条件。
定理5.9设无向图G=（V，E）是哈密顿图，对于任意V1V且V1≠，均有
p(G-V1) ≤ |V1|
其中p(G-V1)是从G中删除V1后所得到的连通分支数。
证明设C为G中任意一条哈密顿回路，当V1中顶点在C中均不相邻时，p(G-V1)=|V1|最大，其余情况下均有p(G-V1)< |V1|，所以有p(G-V1) ≤ |V1|。而C是G的生成子图，所以，p(G-V1) ≤ p(C-V1) ≤|V1|。
推论设无向图G=（V,E）是半哈密顿图，对于任意的V1V且V1≠均有
p(G-V1) ≤ |V1|+1
证明令Γ(uv)为G中哈密顿通路，令G′=G∪(u,v)，则G′为哈密顿图。于是

p(G-V1)=p(G′-V1-(u,v)) ≤ |V1|+1

本定理的条件是哈密顿图的必要条件，但不是充分条件。可以利用本定理的必要条件来判定某些图不是哈密顿图。
例5.29利用定理5.9判定图5.29中的图不是哈密顿图。


图5.29例5.29题图

解图5.29(a)不是哈密顿图。
图5.29(a)中共有9个结点，如果取结点子集V1={3个白点}，删除V1。而这时图5.29(a)的连通分支为ω(G－S)=4，如图5.29(b)所示。根据定理5.9的逆否命题得图5.29(a)不是哈密顿图。但要注意，若一个图满足定理5.9的条件也不能保证这个图一定是哈密顿图。可以验证彼得森图［如图5.29（c）所示］满足定理的条件，但它不是哈密顿图。若一个图不满足定理中的条件，则它一定不是哈密顿图。
在彼得森图中存在哈密顿通路不存在哈密顿回路，所以彼得森图是半哈密顿图。
下面给出一些图具有哈密顿回路或通路的一些充分条件。
定理5.10设G是n阶无向简单图，若对于任意不相邻的顶点vi和vj，均有
d(vi)+d(vj) ≥ n-1

则G中存在哈密顿通路。
证明
（1） 首先证明G是连通的。假设G不连通，G至少有两个连通分支，设G1和G2是顶点数分别为n1和n2(n1≥1,n2≥1)的连通分支，设v1∈V(G1),v2∈V(G2)，由于G是简单图，所以，dG(v1)+dG(v2)=dG1(v1)+dG2(v2)≤n1－1+n2－1≤n－2。
这与定理中条件d(vi)+d(vj)≥n－1矛盾，所以G是连通的。
再证明G中存在哈密顿通路。
（2） 设Γ=v1v2…vl为G中极大路径，l≤n，若l=n，则Γ为G中经过所有顶点的路径，即为哈密顿通路。
若l<n，说明G中还有在Γ外的顶点，但此时可以证明存在经过Γ上所有顶点的回路。
① 若在Γ上v1与vl相邻，则v1v2…vlv1为过Γ上所有顶点的回路。
② 若在Γ上v1与vl不相邻，假设v1在Γ上与vi1=v2,vi2,vi3,…,vik相邻（k必大于或等于2，否则d(v1)+d(vl)≤1+l－2<n－1），此时vl必与vi2,vi3,…,vik相邻的顶点vi2－1,vi3－1,…,vik－1至少之一相邻（否则d(v1)+d(vl)≤k+l－2－(k－1)=l－1<n－1）。设vl与vir－1(2≤r≤k)相邻，如图5.30（a）所示，删除边(vir－1,vir)，得到回路C=v1vt1…vtr－1vtvt－1…vik…vtrv1。
③ 证明存在比Γ更长的路径。
由连通性，可得比Γ 更长的路径［如图5.30（b）所示］，对它再扩大路径，重复(2)，最后得哈密顿通路。


图5.30哈密顿通路存在的充分条件


推论1设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻的顶点vi和vj，均有 d(vi)+d(vj) ≥ n，则G中存在哈密顿回路，从而G为哈密顿图。
证明由定理5.10得Γ=v1v2…vn为G中哈密顿通路。
若(v1,vn)∈E(G)，得证。否则利用推论条件d(vi)+d(vj)≥ n证明存在过v1，v2,…，vn的哈密顿回路。
推论2设G为n(n≥3) 阶无向简单图，若对任意的v∈V(G)，均有d(v)≥n2，则G为哈密顿图。
利用推论1可证推论2。
定理5.11设u和v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)≥n，则G为哈密顿图当且仅当G∪(u,v)为哈密顿图。 
本定理的证明留给读者。
以上定理及推论都是针对无向图的条件，下面讨论有向图中的哈密顿通路。
讨论一类一定含有哈密顿通路（回路）的有向图——竞赛图。
定义5.35（竞赛图）无向完全图的定向图称为竞赛图。
注： 竞赛图中任何两个结点间都有且仅有一条有向边。
例5.30图5.31给出了三个具有4个结点的竞赛图。


图5.31竞赛图


定理5.12若G为n（n≥2）阶竞赛图，则G中具有哈密顿通路。
证明略。
哈密顿图应用
(1) 环球航行问题(如图5.27所示)。
易知 a b c d e f g h i j k l m n o p q r s t a 为图5.27中的一条哈密顿回路。
注意: 此图不满足定理5.10推论1条件。
(2) 在四分之一国际象棋盘（由4×4方格组成）上跳马无解(如图5.32所示)。


图5.32国际象棋盘跳马

令V1={a，b，c，d}，则 p(G-V1)=6 >4，由定理5.9可知图5.32中无哈密顿回路。
(3) 旅行商问题（Traveling Salesman Problem,TSP）是在加权完全无向图中，求经过每个顶点恰好一次的（边）权和最小的哈密尔顿圈，又称之为最优哈密尔顿圈。如果将加权图中的结点看作城市，加权边看作距离，旅行商问题就成为找出一条最短路线，使得旅行商从某个城市出发，遍历每个城市一次，最后再回到出发的城市。
若选定出发点，对n个城市进行排列，因第2个顶点有n-1种选择，第3个顶点有n-2种选择，依此类推，共有(n-1)!条哈密尔顿圈。考虑一个哈密尔顿圈可以用相反两个方向来遍历，因而只需检查12(n－1)!个哈密尔顿圈，从中找出权和最小的一个。我们知道12(n－1)!随着n的增加而增长得极快，例如有20个顶点，需考虑12×19!（约为6.08×1016）条不同的哈密尔顿圈。要检查每条哈密尔顿圈用最快的计算机也需大约一年的时间，才能求出该图中长度最短的一条哈密尔顿圈。
因为旅行商问题同时具有理论和实践的重要性，所以已经投入了巨大的努力来设计解决它的有效算法。目前还没有找到一个有效算法。因此，解决旅行商问题的实际方法是使用近似算法。大家可以通过查阅资料进行学习。

5.6平面图

在一些实际问题中，常常需要考虑一些图在平面上的画法，希望图的边与边不相交或尽量少相交。如印制电路板上的布线、线路或交通道路的设计以及地下管道的敷设等。 
例如，一个工厂有3个车间和3个仓库，因工作需要，车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能呢？
如图5.33(a)所示，A、B、C是3个车间； M、N、P是3座仓库。经过研究表明，要想建造不相交的道路是不可能的，但可以使交叉点最少，如图5.33(b)所示。此类实际问题涉及平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。


图5.33车间和仓库之间的通道


5.6.1平面图的定义
定义5.36设G=(V,E)是一无向图。如果能把G的所有结点和边画在平面上，使得任何两条边除公共端点外没有其他的交点，则称G是一个平面图或称该图能嵌入平面； 否则，称G是一个非平面图。
直观上讲，平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。 
例如，图5.34(a)是无向完全图K3，它是平面图。图5.34(b)是无向完全图K4，它表面上看有相交边，但是把它画成图5.34(c)，则可以看出它是一个平面图。图5.34(d)是平面图。图5.34(e)经改画后得到图5.34(f)，图5.34(g)经改画后得到图5.34(h)，由定义知它们都是平面图。而图5.34(i)和图5.34(j)是无向完全图K5，K5和图5.33中的两个图，无论怎样调整边的位置，都不能使任何两边除公共端点外没有其他的交点，所以它们不是平面图，它们是两个最基本、最重要的非平面图，在平面图理论的研究中有非常重要的作用。
设G是平面图，G的以无交边的方式画在平面上的图，称为平面图G的平面嵌入。如图5.34中的(c)、(f)、(h)分别为图(b)、(e)、(g)的平面嵌入。


图5.34平面图和非平面图示例

关于平面图，以下两个结论是显然的。
定理5.13若G是平面图，则G的任何子图都是平面图。
定理5.14若G是非平面图，则G的任何母图都是非平面图。
推论无向完全图Kn(n≥5)是非平面图。
定义5.37设G=(V,E)是平面图。将G嵌入平面后，由G的边将G所在的平面划分为若干区域，每个区域称为G的一个面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界长度称为该面的次数，面R的次数记为deg(R)。
例5.31图5.34(a)共有两个面，每个面的次数均为3。图5.34(c)共有4个面，每个面的次数均为3。图5.34(f)共有3个面，每个面的次数均为4。图5.34(h)共有6个面，每个面的次数均为3。图5.35所示平面图G有4个面，deg(R1)=3，deg(R2)=3，R3的边界为e10e7e8e9e10，deg(R3)=5，R0的边界为e1e6e7e9e8e6e5e4e2，deg(R0)=9。


图5.35例5.31题图

关于面的次数，有下述定理。 
定理5.15在一个有限平面图G中，所有面的次数之和等于边数的2倍，即
∑ri=1deg(Ri)=2m
其中，r为G的面数，m为边数。 
证明注意到等式的左端表示G的各个面次数的总和，在计数过程中，G的每条边或者是两个面的公共边界，为每一个面的次数增加1； 或者在一个面中作为边界重复计算两次，为该面的次数增加2。因此在计算面的次数总和时，每条边都恰好计算了两次，故等式成立。 
推论在任何平面图中，次数为奇数的面的个数是偶数。 
G的不同平面嵌入的面的次数数列可能是不同的。图5.36中的G1和G2是同一个图的平面嵌入，但它们的面的次数数列分别是3,3,5,5和3,3,4,6。 


图5.36同一个图的平面嵌入

5.6.2欧拉公式
在1750年数学家欧拉发现，任何一个凸多面体的顶点数n，棱数m和面数r之间满足关系式：  
n－m+r=2
这就是著名的欧拉公式。 更一般地，对任意平面图，欧拉公式依然成立。这就是下面的定理和推论。 
定理5.16设G为一个连通平面图，它有n个结点、m条边和r个面，则有n－m+r=2。 
证明对G的边数m进行归纳证明。
当m=0时，由于G是连通的，因此G只能是平凡图。这时，n=1，m=0，r=1，n－m+r=2成立。
设m=k(k≥1)时，结论成立，下面证明当m=k+1时，结论也成立。
易见，一个具有k+1条边的连通平面图可以由k条边的连通平面图添加一条边后构成。因为一个含有k条边的连通平面图上添加一条边后仍为连通图，则有以下三种情况。
（1） 所增边为悬挂边［如图5.37(a)所示］，此时G的面数不变，结点数增1，边数增1，欧拉公式成立。
（2） 所增边为一个环，此时G的面数增1［如图5.37(b)所示］，此时边数增1，但结点数不变，欧拉公式成立。


图5.37定理5.16证明

（3） 在图的任意两个不相邻结点间增加一条边［如图5.37(c)所示］，此时G的面数增1，边数增1，但结点数不变，欧拉公式成立。

定理5.17设G是连通的(n,m)平面图，且每个面的次数至少为l(l≥3)，则
m≤ll－2(n－2)
证明由定理5.15知
2m=∑ri=1deg(Ri)≥l·r(r为G的面数)
再由欧拉公式
n－m+r=2
得
r=2+m－n≤2ml
故
m≤ll－2(n－2)
推论1平面图G的平面嵌入的面数与G的嵌入方法无关。 
于是G的一个平面嵌入的面数，可直接称为平面图G的面数。 
推论2设G是有n个结点(n≥3)和m条边的简单平面图，则m≤3n－6。 
证明不妨设G是连通的，否则可在G的连通分支间加边而得到连通图G′，G′的结点数仍为n，边数m′≥m，所以若定理对G′成立，则对G也成立。 
由于G是有n个结点(n≥3)的简单连通平面图，所以G的每一个面至少由3条边围成。如果G中有r个面，则面的总次数
2m≥3r
即有
r≤2m3
代入欧拉公式，可得
n－m+2m3≥2
从而得到
m≤3n－6
推论2也可直接由定理5.17推出，只需令l=3即可。
推论3若有n个结点(n≥3)的简单连通平面图G不以K3为子图，则m≤2n－4。
证明由于G是有n个结点(n≥3)的简单连通平面图，且G中不含K3，所以G的每个面至少由4条边围成，即l≥4，代入定理5.16，立即得
m≤2n－4
推论4若G是一个简单平面图，则G至少有一个结点的度小于或等于5。 
证明当G的结点数小于或等于6时，结论显然成立。当G的结点数大于或等于7时，设G的最小度结点的度为δ，若δ>5，即δ≥6，由握手定理知
2m=∑v∈Vdeg(v)≥6n
故
m≥3n
与推论2矛盾，所以图G中至少有一个结点的度小于或等于5。 
例5.32证明K5不是平面图。 
证明K5的结点数n=5，边数m=10，若它是平面图，则由推论2得m≤3n－6，即10≤3×5－6，这是一个矛盾不等式，故K5不是平面图。 
上面给出的定理5.16和推论2、推论3、推论4都是一个图是平面图的必要条件，它们可用来判断某个图不是平面图。我们希望找出一个图是平面图的充分必要条件。经过几十年的努力，波兰数学家库拉托夫斯基（Kuratowski）于1930年给出了平面图的一个非常简洁的充分必要条件。下面就来介绍库拉托夫斯基定理。为此先引入同胚的概念。
定义5.38设G为一个无向图，e=(u,v)是G的一条边，在G中删去边e，增加新的结点w，使u、v均与w相邻接，则称在G中插入一个2度结点；  设w为G的一个2度结点，w与u、v相邻接，在G中删去结点w及与w相连接的边(w,u)和(w,v)，同时增加新边(u,v)，则称在G中消去一个2度结点w，如图5.38所示。 


图5.38插入和消去2度结点

定义5.39如果两个无向图G1与G2同构或通过反复插入或消去2度结点后是同构的，则称G1与G2是同胚的。 
例如，图5.39所示的4个图是同胚的。


图5.39同胚图

定理5.18(库拉托夫斯基定理)一个无向图是平面图当且仅当它不含有与K5或K3,3同胚的子图。 
库拉托夫斯基定理的必要性容易看出，因为K5不是平面图，因此与K5同胚的图也不是平面图。一个无向图若是平面图，则它自然不会含有非平面图作为它的子图。 
库拉托夫斯基定理的充分性证明较复杂，这里不再引述。有兴趣的读者可参阅邦迪(J.A.Bondy)和默蒂(U.S.R.Murty)的《图论及其应用》。 
例5.33证明图5.40(a)所示的彼得森图是非平面图。 



图5.40例5.33题图

证明在图5.40(a)所示的彼得森图中同胚于图5.40(b)、图5.40(c)，由库拉托夫斯基定理知，彼得森图不是平面图。

5.6.3平面图着色
平面图的着色问题最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1852年，英国青年盖思瑞（Guthrie）提出了用4种颜色可以对地图着色的猜想（简称四色猜想）。1879年肯普（Kempe）给出了这个猜想的第一个证明，但到1890年希伍德（Hewood）发现肯普的证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用4种颜色就够了，但却可以证明用5种颜色就够了，即五色定理成立。此后四色猜想一直成为图论中的难题。许多人试图证明猜想都没有成功。直到1976年美国数学家阿佩尔（K.Appel）和哈肯(W.Haken)利用计算机分析了近2000种图形和100万种情况，花费了1200个机时，进行了100多亿个逻辑判断，证明了四色猜想。从此四色猜想便被称为四色定理。但是，不依靠计算机而直接给出四色定理的证明，仍然是数学界一个令人困惑的问题。
为了叙述图形着色的有关定理，下面先给出对偶图的概念。
定义5.40给定平面图G=(V，E)，其面的集合F(G)={f1,f2,…,fn}。若有图G*=(V*,E*)满足下列条件： 


图5.41对偶图

（1） 对于任意一个面fi∈F(G)，其内部有且仅有一个结点v*i∈V*； 
（2） 对于G中的面fi和fj的公共边ek，有且仅有一条边e*k∈E*，使得e*k=(v*i,v*j)，且e*k与ek相交； 
（3） 当且仅当ek只是一个面fi的边界时，v*i存在一个环e*k且e*k与ek相交。

则称图G*是图G的对偶图。
例如，在图5.41中，G的边和结点分别用实线和“”表示，而它的对偶图G*的
边和结点分别用虚线和“·”表示。

从对偶图的定义可以看出，若G*=(V*,E*)是平面图G=<V,E>的对偶图，则G也是G*的对偶图。
定理5.19一个连通平面图G的对偶图G*也是平面图，而且有m*=m，n*=r，r*=n，degG*v*i=degGfi，fi∈F(G),v*i∈V*，其中n、m、r和n*、m*、r*分别是G和G*的结点数、边数和面数。
证明由定义5.39对偶图的构造过程可知，G*也是连通的平面图，且n*=r，m*=m和degG*v*i=degGfi显然成立，下证r*=n。因为G和G*均是连通的平面图，由欧拉公式有
n－m+r=2， n*－m*+r*=2
由n*=r，m*=m可得r*=n。

定义5.41若图G的对偶图G*同构于G，则称G是自对偶图。


图5.42自对偶图

例如，图5.42给出了一个自对偶图。

定理5.20若平面图G=(V，E)是自对偶图，且有n个结点和m条边，则m=2n－1。
证明由欧拉公式知
n－m+r=2
由于图G=(V，E)是自对偶图，则有n=r，从而有
2n－m=2
即

m=2n－1
从对偶图的定义易知，对于地图的着色问题，可以化为一种等价的对于平面图的结点的着色问题。因此，四色问题可归结为证明： 对任意平面图一定可以用4种颜色对其结点进行着色，使得相邻结点都有不同颜色。
定义5.42平面图G的正常着色，简称着色，是指对G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。若可用n种颜色对图G着色，则称G是n可着色的。对图G着色时，需要的最少颜色数称为G的着色数，记为χG。
于是，四色定理可简单地叙述如下。
定理5.21（四色定理）任何简单平面图都是4可着色的。
证明一个简单平面图是5可着色的很容易。
定理5.22（五色定理）对于任何简单平面图G=(V，E)，均有χG≤5。
证明只需考虑连通简单平面图G的情形。对V进行归纳证明。
当V≤5时，显然，χG≤5。
假设对所有的平面图G=(V，E)，当V≤k时有χG≤5。现在考虑图G1=(V1,E1)，V1=k+1的情形。由定理5.17的推论4可知，存在v0∈V1，使得degv0≤5。在图G1中删去v0，得图G1－v0。由归纳假设知，G1－v0是5可着色的，即χG1－v0≤5。因此只需证明在G1中，结点v0可用5种颜色中的一种着色并与其邻接点的着色都不相同即可。


图5.43用5种颜色着色

若degv0<5，则与v0邻接结点数不超过4，故可用与v0的邻接点不同的颜色对v0着色，得到一个最多是五色的图G1。

若degv0=5，但与v0邻接的结点的着色数不超过4，这时仍然可用与v0的邻接点不同的颜色对v0着色，得到一个最多是五色的图G1。
若degv0=5，且与v0邻接的5个结点依顺时针排列为v1,v2,v3,v4和v5，它们分别着不同的颜色红、白、黄、黑和蓝，如图5.43所示。

考虑由结点集合V13=vv∈VG1－v0∧v着红色或黄色所诱导的G1－v0的子图G13。若v1,v3属于G13的不同连通分支，如图5.44所示。则将v1所在的连通分支中的红色与黄色对调，这样并不影响G1－v0的正常着色，然后将v0涂上红色即可得到G1的一种五着色。
若v1和v3属于G13的同一个连通分支，则由结点集V13∪v0所诱导的G1的子图<V13∪v0,E′13>中含有一个圈C，而v2和v4不能同时在该圈的内部或外部，即v2与v4不是邻接点，如图5.45所示。于是，考虑由结点V24=vv∈VG1－v0∧v着白色或黑色所诱导子图G24，由于圈C的存在，G24至少有两个连通分支，一个在C的内部，一个在C的外部（否则图G1中将有边相交，与图G1是平面图的假设矛盾），则v2和v4必属于G24的不同连通分支，作与上面类似的调整，又可得到G1的一种五着色。故χG≤5。由归纳原理，定理得证。


图5.44v1、v3属于G13的不同连通分支




图5.45v1、v3属于G13的一个连通分支



习题5

1.  写出图5.46中各图的度数列，对有向图还要写出出度列和入度列。


图5.46习题1图

2. 下列各组数中，哪些能构成无向图的度序列？哪些能构成无向简单图的度序列？ 
（1） 1,1,1,2,3; （2）  2,2,2,2,2; （3） 3,3,3,3; （4） 1,2,3,4,5; （5） 1,3,3,3。
3. 设无向图中有6条边，3度与5度顶点各1个，其余的都是2度顶点。问： 该图有几个顶点？
4. 设图G中有9个结点，每个结点的度不是5就是6。试证明： G中至少有5个6度结点或至少有6个5度结点。
5. 写出如图5.47所示相对于完全图的补图。

6. 在图5.48中，G1与G2同构吗？为什么？



图5.47习题5图
 


图5.48习题6图


7. 在图5.49所示的4个图中，哪几个是强连通图？哪几个是单向连通图？哪几个是连通图（弱连通图）？


图5.49习题7图

8. 如图5.50所示，G中长度为4的路有几条？其中有几条回路？写出G的可达矩阵。
9. 在图5.51所示的图中，指出割点和割边。


图5.50习题8图



图5.51习题9图


10. 有向图G如图5.52所示。
（1）   写出图G的邻接矩阵A。
（2）   G中长度为3的通路有多少条？其中有几条为回路？
（3）  利用图G的邻接矩阵A的布尔运算求该图的可达矩阵P，并根据P来判断该图是否为强连通图和单向连通图。
11. 设无向图G=<V,E>，V={v1，v2，v3，v4},邻接矩阵
A=0101
1011
0100
1100
（1） deg（v1）和deg（v2）分别是多少？
（2）  图G是否为完全图？
（3）  从v1到v2长为3的路有多少条？
（4）  借助图解表示法写出从v1到v2长为3的每一条路。
12. 证明图5.53所示的图不是哈密顿图。


图5.52习题10图



图5.53习题12图


13. 设有a，b，c，d，e，f，g 7个人，他们分别会讲的语言如下: a会讲英语； b会讲汉语和英语； c会讲英语、西班牙语和俄语； d会讲日语和汉语； e会讲德语和西班牙语； f会讲法语、日语和俄语； g会讲法语和德语。能否将这7个人的座位安排在圆桌旁，使得每个人均能与他身边的人交谈？
14. 求图5.54中v1到其余各点的最短路径。


图5.54习题14图

15. 问： 图5.55中的两个图，各需要几笔画出（笔不离纸，每条边均不能重复画）？


图5.55习题15图

16. 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同。问： 这11个人共进午餐最多能有多少天？
17.   写出图5.56的关联矩阵和邻接矩阵。
18. 图5.57是有向图。
（1）  求出它的邻接矩阵A和可达矩阵P。
（2）  求出A2、A3、A4。



图5.56习题17图



图5.57习题18图


19． 求图5.58的带权图中最优投递路线，邮局在D点。


图5.58习题19图


20.  某次会议有20个人参加，其中每人至少有10个朋友，这20人围成一圆桌吃饭，要想使每人的
相邻两位都是他的朋友是否可能？
21. 图5.59(a)和图5.59(b)所示的平面图各有几个面？写出它们各面的边界及次数。


习题答案




图5.59习题21图


22. 一只蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，爬过每一个顶点一次且仅一次，最后回到原出发点？利用图作解释。
23. 分别画出满足下列条件的无向图。
（1） 既是欧拉图又是哈密顿图；
（2） 是欧拉图，不是哈密顿图；
（3） 不是欧拉图，是哈密顿图；
（4） 既不是欧拉图又不是哈密顿图。