离散数学 图论

第六章 图论基础

图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念

我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。 任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有(a,b)?(b,a)。 设A,B为两个集合，无序对的集合{(a,b)a?A?b?B}称为集合A与B的无序积（Unordered Product），记作A&B。无序积与有序积的不同在于A&B?B&A。

例如，设A??a,b?，B??0,1,2?，则A&B?{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)} ?B&A,A&A?{(a,a),(a,b),(b,b)}。 为了引出图的定义，我们先介绍如下的例子。

B start s=0,i =1 i=1 S i=11? Y N s=s+1 print s i=i+1 图6.1-2

end M 图6.1-1

H

例6.1-1 (1) 北京、上海、香港、澳门是中国的几个著名的城市，分别用字母表示为

B,S,H,M,城市的集合为V??B,S,H,M?，这些城市间现有的航空线的集合是

E??(B,S),(B,H),(B,M),(S,H),(S,M)?。我们也可以将这些城市间的航空线关系用图

6.1-1来表示。

⑵

10?i的程序框图如图6.1-2

i?1122

6.1.1 图的定义及相关概念

定义6.1-1 一个无向图(Undirected Graph)G是一个有序二元组?V,E?，记作

；E是无序G??V,E?，其中V是一个非空集合，V中的元素称为结点或顶点（Vertex）

积V&V的多重子集（元素可重复出现的集合），称E为G的边集(Edge Set)，E中的元素

称为无向边或简称边(Edge)。

在一个图G??V,E?中，为了表示V和E分别是图G的结点集和边集，常将V记成

V(G)，而将E记成E(G)。

以上给出的是一个无向图的数学定义。它们可以用图形来表示，而这种图形有助于我们理解图的性质。在这种表示法中，每个结点用点来表示，每条边用线来表示，这样的线连接着代表该边端点的两个结点。例如G??V,E?,V??v1,v2,v3,v4,v5?,E?{(v1,v2),

(v2,v2),(v2,v3),(v1,v3),(v1,v3),(v3,v4)},G的图形如图6.1-3所示。

v1 e1 e2 v2 e3 v5 e5 e4 v2

e6 v3 v4

v1

v3

图6.1-4

v4

图6.1-3

定义6.1-2 一个有向图(Directed Graph)G是一个有序二元组?V,E?，记作G??V,E?，其中V是一个非空的结点（或顶点）集；E是笛卡尔积V×V的多重子集，其元素称为有向边(Directed Edge)，也简称边或弧 (Arc)。

对于一个有向图G，一般也可画出图形来表示。例如G??V,E?，其中

V??v1,v2,v3,v4,v5?,E?{?v1,v1?,?v1,v2?,?v2,v3?,?v3,v2?,?v2,v4?,?v3,v4?},G的图形为图6.1-4。

给图的结点标以名称，如图6.1-3中的v1,v2,v3,v4,v5,这样的图称为标定图(Labled graph)。同时也可对边进行标定，图6.1-3中e1?(v1,v2), e2?(v2,v2), e3?(v2,v3),

e4?(v1,v3), e5?(v1,v3), e6?(v3,v4).

当e?(u,v)时,称u和v是e的端点（或顶点）(End Point)，并称e与u和v是关联的(Incidence)，而称结点u与v是邻接的(Adjacent)。若两条边关联于同一个结点，则称两边是

邻接的(Adjacent)。无边关联的结点称为孤立点(Isolated point)；若一条边关联的两个结点重合，则称此边为环(Ring)或自回路(Self circuit)。若u?v，则称e与u（或v）关联的次数是1;若u?v，称e与u关联的次数为2；若u不是e的端点，则称e与u的关联次数为0（或

123

称e与u不关联）。在图6.1-3中，e1?(v1,v2), v1,v2是e1的端点，e1与v1、v2的关联次数均为1，v5是孤立点，e2是环，e2与v2关联的次数为2。

当e??u,v?是有向边时，又称u是e的始点(Initial Point)，v是e的终点(Terminal Point)。

如果图的结点集V和边集E都是有限集，则称图为有限图(Finite graph)，本书讨论的图都是有限图。若图G??V,E?中V?n,E?m,为了方便起见，这样的图也称为?n,m?图，有时也简称n阶图。这时?n，0?图称为零图(Null Graph)，?1,0?图称为平凡图(Trivial Graph)。

关联于同一对顶点的两条边称为平行边(Parallel Edge)（若是有向边方向应相同），平行边的条数称为边的重数。不含平行边和环的图称简单图(Simple Graph)。在本书中除非特别声明，一般是指简单图。

6.1.2 结点的度

定义6.1-3 设G??V,E?为一无向图，v?V,v关联边的次数称为v的度数，简称度(Degree)，记作的d(v)。

设G??V,E?为一有向图，称为v的出度(Out Degree)，v?V,v作为边的始点的次数，记作d(v)；v作为边的终点的次数称为v的入度(In Degree)，记作d(v)；v作为边的端点的次数称为v的度数，简称度(Degree)，记作d(v)，显然d(v)?d(v)?d(v)。

在图6.1-3中，d(v1)?3，d(v2)?4，d(v4)?1，d(v5)?0； 在图6.1-4中，d(v1)?2，d(v1)?1，

??????d?(v4)?0,d?(v4)?0,d?(v2)?d?(v2)?2。

称度为1的结点为悬挂点(Hanging point)，与悬挂点关联的边称为悬挂边(Hanging edge)。如图6.1-3中，v4是悬挂点，e6是悬挂边。

记?(G)?maxd(v)v?V(G), ?(G)?mind(v)v?V(G),分别称为图G的最大度(Max Degree)和最小度(Min Degree)。若G??V,E?是有向图，除了?(G),?(G)，还有如下的定义

?????d最大入度?(G)?max?d最小出度?(G)?min?d最小入度?(G)?min?????最大出度?(G)?maxd(v)v?V

?????(v)v?V? (v)v?V? (v)v?V?

图6.1-4中,?(G)?4, ?(G)?2,

??(G)?2,??(G)?0,??(G)?2, ??(G)?1.

例6.1-2 在图6.1-3中

?d(v)?d(v)?d(v)?d(v)?d(v)?d(v)?3?4?4?1?0?12,而该图有６条

12345v?V边，即结点度数和是边数的２倍。事实上这是图的一般性质。

124

定理6.1-1 设图G为具有结点集{v1,v2,...,vn}的?n,m?图，则 若d(v)为奇数，则称v为奇点，若d(v)为偶数，则称v为偶点。 推论 任一图中，奇点个数为偶数。

证明 设V1?{vv为奇点}，V2?{vv为偶点}， 则

?d(v)?2m。

ii?1nv?V1所以?d(v)也是偶数，而V?d(v)??d(v)??d(v)?2m ,因为?d(v)是偶数，

v?V2v?Vv?V2v?V11中每个点v的度d(v)均为奇数，因此V1为偶数。

对有向图，还有下面的定理。

定理6.1-2 设有向图G??V,E?，v?{v1,v2,...,vn}， E?m 则

?di?1n?(vi)??d?(vi)?m.

i?1n以上两个定理及推论都很重要，要牢记并灵活运用。

设v?{v1,v2,...,vn}是图G的结点集，称d(v1),d(v2),...,d(vn)为G的度序列。如图6.1-3的度序列为3,4,4,1,0，图6.1-4的度序列是3,4,3,2。

例6.1-3 ⑴图G的度序列为2,2,3,3,4，则边数m是多少？ ⑵ 3,3,2,3； 5,2,3,1,4能成为图的度序列吗？为什么？

⑶ 图G有12条边，度数为３的结点有６个，其余结点度均小于３，问图G中至少有几个结点？

解 ⑴ 由握手定理 2m??d(v)?2?2?3?3?4?14，所以

v?Vm?7

⑵ 由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的

度序列。

⑶ 由握手定理

?d(v)?2m?24，度数为３的结点有６个占去18度，还有６度由

其余结点占有，其余结点的度数可为0,1,2，当均为２时所用结点数最少，所以应由３个结点占有这６度，即图G中至少有９个结点。

例6.1-4 证明在n(n?2)个人的集体中，总有两个人在此团体中恰有相同个数的朋友。 解 以结点代表人，二人如果是朋友，则在代表他们的结点间连上一条边，这样可得无向简单图G，每个人的朋友数即是图中代表他的结点的度数，于是问题转化为：n阶无向简单图G必有两个结点的度数相同。

125

用反证法，设G中每个结点的度数均不相同，则度序列为0,1,2,?,n?1，说明图中有孤立点，而图G是简单图，这与图中有n?1度结点相矛盾。所以必有两个结点的度数相同。

6.1.3 完全图和补图

定义6.1-4 设G??V,E?是无向简单图，若每一对结点之间都有边相连，则称G为完全图(Complete Graph)，具有n个结点完全图记作Kn。

设G??V,E?为有向简单图，若每对结点间均有一对方向相反的边相连，则称G为(有向)完全图，具有n个结点的有向完全图记作Dn。

例6.1-5 图6.1-5给出几个完全图的例子。

由完全图的定义可知，无向完全图Kn的边数为E(Kn)?边数为E(Dn)?n(n?1).

1n(n?1),而有向完全图的2K1

K2

K3

K4

K5

D1

D2

图6.1-5

D3

D4

定义6.1-5 设G为n阶(无向)简单图，从 n阶完全图Kn中删去G的所有边后构成的图称为G的补图(Complement of graph)，记作G。类似地,可定义有向图的补图。

例6.1-6 图6.1-6中G是G的补图。 由补图的定义，显然有如下的结论： ⑴ G与G互为补图，即G?G；

⑵ 若G为n阶图，则E(G)?E(G)?E(Kn)，且E(G)?E(G)??。 定义6.1-6 各结点的度数均为k的无向简单图称为k-正则图(Regular graph)。 图6.1-7所示的图称为彼得森（Petersen）图，是3?正则图。

126

v1 v2 v3 v5

v4

G

图6.1-6

G

图6.1-7

6.1.4 子图与图的同构

定义6.1-7 设G??V,E?，G??V,E?是两个图。若V?V，且E?E，则称G?是G的子图(Subgraph)。G是G?的母图(Contained graph)，记作G??G。

若V?V或E??E，则称G?是G的真子图(Proper subgraph)。

''若V?V且E?E，则称G?是G的生成子图(Spanning subgraph)。

若V1?V且V1??，以V1为结点集，以图G中两个端点均在V1中的边为边集的子图，称为由V1导出的导出子图(Induced subgraph)，记作G[V1]。

设E1?E，且E1??，以E1为边集，以E1中的边关联的结点为结点集的图G的子图，称为E1导出的边导出子图，记作G[E1]。

a a ''''''b e1 e5 e6 e4 f b e1 e2 c e5 e4 f e2 e7 G a e3 d e8

c d G1

e1 b e5 e4 f a

e4

e 2 e3 G3

d

f

e6 e2 c G2

图6.1-8

c

127

例6.1-7 在图6.1-8中，G1,G2,G3均是G的真子图，其中G1是G的生成子图，G2是由V2?{a,b,c,f}导出的导出子图G[V2]，G3是由E3?{e2,e3,e4}导出的边导出子图

G[E3]。

由于在画图的图形时，结点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是同一个图。为了判断不同图形是否表示同一个图形，在此我们给出图的同构的概念。

设有两个图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同构(Isomorphism)，记作G?G1。

定义6.1-8说明，两个图的结点之间，如果存在双射，而且这种映射保持了结点间的邻接关系和边的重数（在有向图时还保持方向），则两个图是同构的。

v1 v6 u1 v5u3 u6

v2

v3 G1

v4 v4u2

u3

v3

u4 G2

u5

u4v2

v1G3图6.1-9

u2u1G4例6.1-8 图6.1-9中，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。

容易看出，两个图同构的必要条件是：

⑴ 结点数相同；⑵ 边数相同；⑶ 度序列相同。但这不是充分的条件，例如图6.1-10中图H1,H2虽然满足以上3个条件，但不同构。图H1中的4个3度结点与H2中的4个3度结点的相互间的邻接关系显然不相同。

128

H1

图6.1-10

H2

习题6.1

6.1-1 画出下列各图的图形并求出各结点的度(出度、入度)： ⑴G??V,E?其中V?{a,b,c,d,e},

E?{(a,b),(a,c),(a,d),(b,a),(b,c),(d,d),(d,e)}。

⑵H??V,E?其中V?{a,b,c,d,e},E?{?a,b?,?a,c?, ?a,e?,?b,c?,?d,a?,?d,d,?,?d,e?}。

6.1-2 下列各组数中，哪些能构成无向图的度序列？哪些能构成无向简单图的度序列？ ⑴1,1,1,2,3; ⑵2,2,2,2,2; ⑶3,3,3,3; ⑷1,2,3,4,5; ⑸1,3,3,3.

g

1 2 f

e d c a b h 6

7 9 8 3

10 i j 5 4 G1

图6.1-11

G2

6.1-3 设图G??V,E?,V?8,若G有三个3度结点，两个2度结点，三个1度结点，试问：G有多少条边？

6.1-4 图G有12条边，三个度为4的结点，其余结点的度均为3，问图G有多少个结点？

6.1-5 图6.1-11中G1与G2同构吗？若两图同构，写出结点之间的对应关系；若不同构，则说明理由。

6.1-6 图6.1-12中，G1与G2，同构吗？为什么？

129

a

1 e

5

4 b

c d 2 3

G1

G2

图6.1-12

6.2图的连通性

计算机网络中常见的一个问题是，网络中任何两台计算机是否可以通过计算机间的信息传递而使其资源共享？我们可以用图论的方法对这个问题进行研究，其中用结点表示计算机，用边表示通讯连线，因此，计算机的信息资源共享问题就变为，图中任何两个结点之间是否都有连接通路存在?

6.2.1 通路

在图论的研究中，经常要考虑这样的问题，如何从一个图中的给定结点出发，沿着一些边移动到另一个结点。这种由结点和边形成的序列就引出了路的概念。

定义6.2-1 设G??V,E?是图,从图中结点v0到vn的一条通路或路径 (walk)是图的一个点、边的交错序列(v0e1v1e2v2...vn?1envn),其中ei?(vi?1,vi)(或者ei??vi?1,vi?)

(i?1,2,?,n), v0,vn分别称为通路的起点(Initial Point)和终点(Terminal Point),而称v1,v2,?,vn?1为内点(Interior point),通路中包含的边数n称为通路的长度(Length).当起点和

终点重合时则称其为回路（Circuit）;

若通路的边e1,e2,...,en互不相同,则称其为链(Chain)； 如果一条链满足v0?vn,则称其为闭链。

如果一条通路中结点v0,v1,v2,...,vn互不相同，则称其为道路，简称路（Path）。 如果一条回路的起点和内部结点互不相同，则称其为圈（Cycle）。一般地称长度为k的圈为k圈，并称长度为奇数的圈为奇圈，长度为偶数的圈为偶圈。

例6.2-1 在图6.2-1中，

⑴ p1?v1e4v5e5v4e6v1e1v2是一条通路，也是一条链。 ⑵ p2?v4e7v2e2v2e3v3e8v4是一回路，也是一闭链。 ⑶p3?v4e6v1e1v2e3v3是一条路。 ⑷p4?v4e6v1e1v2e3v3e8v4是一圈。

在不引起混淆的情况下，通路有时也可用边的序列或结

v1

e1 e6 e2 v2 e7 e3

v3

e4

e8 e5

v 点的序列来表示，如上例中的p3、p4可记为(v4v1v2v3)，5v4

和(v4v1v2v3v4)。特别地，单独一个结点也是一个通路，其

图6.2-1

长度为0。另外，由平行边e1和e2构成的通路ue1ve2u及由一个环构成的通路ueu均是回路。

定理6.2-1 在一个n阶图G??V,E?中，如果从结点vi到vj(vi?vj)存在一条通路，则从vi到vj存在一条长度不大于n?1的路。

证 假定从vi到vj存在一条通路(vi,...,vk,...,vj)，如果其中有相同的结点ve，例如(vi,...,vk,...,ve,...,ve,...,vj)，删去ve到ve的那些边，它仍是从vi到vj的通路，如此反复的进行直到(vi,...,vk,...,vj)中没有重复结点为止。此时所得就是一条从vi到vj的路。路的长度比所经结点数少1，图中共n个结点，故路的长度不超过n?1。

定理6.2-2 在一个n阶图G??V,E?中，如果存在一经过v1的回路，则存在一经过

130

v1的长度不超过n的圈。

定义6.2-2 在图G??V,E?中， 从结点vi到vj的最短通路（一定是路）称为vi与vj间的短程线(Geodesic)，短程线的长度称vi到vj的距离(Distance)，记作d(vi,vj)。若从vi到vj不存在通路，则记d(vi,vj)??。

注意，在有向图中，d(vi,vj)不一定等于d(vj,vi)，但一般地有如下性质： ⑴ d(vi,vj)?0； ⑵ d(vi,vi)?0；

⑶ d(vi,vj)?d(vj,vk)?d(vi,vk)。（通常称为三角不等式）。

6.2.2 图的连通性

图的连通性分为无向图的连通性和有向图的连通性。而且有向图的连通性要比无向图的连通性复杂些。

定义6.2-3 在一个无向图G中，若存在从结点vi到vj的通路（当然也存在从vj到vi的通路），则称vi与vj是连通的(Connected)。规定vi到自身是连通的。

在一个有向图D中，若存在从结点vi到vj的通路，则称从vi到vj是可达的(Accessible)。规定vi到自身是可达的。

定义6.2-4 若无向图G中任意两结点都是连通的，则称图G是连通的(Connected)。规定平凡图是是连通的。

易知，无向图G中，结点之间的连通关系是等价关系。设G为一无向图，R是V(G)中结点之间的连通关系，由R可将V(G)划分成k(k?1)个等价类，记作V1,V2,...,Vk，由它们导出的导出子图G[V1],G[V2],...,G[Vk]称为G的连通分支(Connected Component)，其个数应为?(G)。

例如图6.2-2所示的图G1是连通图，?(G1)?1，图G2是一个非连通图，?(G2)?3。

G1

图6.2-2

G2

定义6.2-5 设D是一有向图，若略去D中各有向边的方向后所得无向图G是连通的，则称D是连通的(Connected)，或称D是弱连通的(Weakly Connected Graph)。

如果D中任意两点vi,vj之间，vi到vj或vj到vi至少有一个可达，则称图D是单向连通的(Unilaterally Connected Graph)。

如果D中任意两结点都互相可达，则称D是强连通的(Strongly Connected Graph)， 例如在图6.2-3中，G1是弱连通的，G2是单向连通的，G3是强连通的。 注意，强连通一定是单向连通图，单向连通一定是弱连通图。但反之不真。

131

6.3.5 有向图的可达矩阵

定义6.3-5 设G??V,E?是有向图，V?{v1,v2,?,vn}，令 ?1,vi可达vj,pij??(i?j),pii?1,i?1,2,?,n

0,否则,?则称(pij)n?n为G的可达矩阵(Accessibility Matrix)，记作P(G)，简记P。

图6.3-5所示有向图G的可达矩阵为

?1?0P???0??0111?111??

111??111?2n?1因为B?E?A?A???A?(bij)n?n

则可达矩阵P中的元素可按如下的方式得到：

?1,bij?0pij??

0,否则?即可由邻接矩阵求可达矩阵。

习题6.3

6.3-1．设无向图G=, V ={v1, v2, v3, v4},邻接矩阵

?0?1A???0??1101?011??

100??100?⑴试问⑴ deg（v1）=？ deg（v2）= ？ ⑵ 图G是否为完全图？

⑶ 从v1到v2长为3的路有多少条？

⑷ 借助图解表示法写出从v1到v2长为3的每一条路。 6.3-2．画出邻接矩阵为A的无向图G的图形，其中

137

?0?1?A??0??1??11011?1101??1011?

?0101?1111??v4

v5 v3

v1

v2

6.3-3．有向图G如图6.3-5所示。 图6.3-5

⑴ 写出图G的邻接矩阵A。

⑵ G中长度为3的通路有多少条？其中有几条为回路？

⑶ 利用图G的邻接矩阵A的布尔运算求该图的可达性矩阵P，并根据P来判断该图是否为强连通图，单向连通图。

e1 e2

v3 e5 v4

v1 e1

v2

图 6.3-7

v4

e2

e3

e4

v3

e5 v1 e3 e4 v2 图6.3-6

6.3-4.求图6.3-6、图6.3-7的关联矩阵。 6.3-5.求图6.3-6、图6.3-7的邻接矩阵。

6.4 欧拉图与Hamilton哈密尔顿图

6.4.1 Euler图

18世纪，普鲁士的哥尼斯堡（K?nigsberg）城中有一条普雷格尔(Pregel)河，河上架设的7座桥连接着两岸及河中的两个小岛。（如图6.4-1(a)）

C C A B A B

D D (a)

图6.4-1

(b)

城里的人们喜欢散步，更期望能通过每个桥一次且仅一次再回到出发地，但谁都没能成功。于是哥尼斯堡的人们将这个问题写信告诉了瑞士著名的数学家欧拉（L.Euler）。欧拉

138

在1736年证明了这样的散步是不可能的。他用点代表岛和两岸的陆地，用线表示桥，得到该问题的数学模型如图6.4-1(b)，使“七桥问题”转化为图论问题。因此，后来的图论工作者将上述“七桥问题”作为图论的起点，并将欧拉作为图论的创始人。

定义6.4-1 设无向图G??V,E?是多重图，经过图G的所有边的闭链称为欧拉回路(Euler Circuit)，存在欧拉回路的图称为欧拉图(Euler Graph)。若图G有一条经过图G的每条边的链，称其为欧拉链(Eulerian trail)，并称该图的半欧拉图。

显然，欧拉图除孤立点外是连通的。这里不妨设欧拉图是连通图。 例6.4-1 图6.4-2中各图哪些是欧拉图？哪些是半欧拉图？

a b a c (a)

d e b e d (b)

图6.4-2

(c)

a b d d c a b (d) c c

此例中，图(a)，(b)是欧拉图，(c)是半欧拉图，(d)中不存在欧拉链，更不存在欧拉链。这是因为，图(a)中有欧拉回路(abcdeca )。对于图(b)、(c)读者可作类似的研究。

从上面的例子，我们发现，凡是结点的度均是偶数的图，都是欧拉图，这是否是一般规律呢？回答是肯定的。

定理6.4-1 无向连通图G??V,E?是欧拉图，当且仅当图G中无奇点。

证明 若G是平凡图，则定理显然成立。因此我们下面讨论的都是非平凡图。 必要性。设图G有欧拉回路C?(v0,v1,?,vk?1,v0)，v0是回路的起点和终点。图G的所有边都出现在C中，且每条边都只出现一次，但是结点vi却可能不止一次出现在C中。研究图G中的结点vi。

若vi?v0，则vi出现在C中既不是起点，也不是终点，则vi在C中出现一次，它就关联两条边，因此d(vi)等于结点vi在C中出现的次数的2倍。

若vi?v0，且v0在除起点和终点外的C的中间出现k(k?0)次，则d(vi)?2k?2。因此，对G中任何结点vi，d(vi)均为偶数。

充分性。因为图G是连通的，且每个结点均是偶数，则可按下列步骤构造一条Euler回路。

⑴ 从任一结点v0开始，取一关联v0的边e1到v1。因为所有结点为偶点，所以可继续取关联v1的边e2到v2，…，关联vi-1的边ei到vi，?，每条边均为前面没取过的，如此继续直到回到起点v0，得一回路C1:v0e1v1e2v2?eiviei?1?ekv0。若C1包含G中所有的边，则C1就是G中的欧拉回路，即G为欧拉图，否则转⑵；

⑵ 若G?C1?G1的边集非空，G1中的每个结点均是偶点，又G连通，G1与C1必有

?u1e2??vi。若一结点vi重合，在G1中从vi出发重复步骤⑴，又可得一回路C2:vie1?u1e2??viei?1vi?1 C1?C2?G，则G是欧拉图；欧拉回路为C1?C2?v0e1v1e2v2?eivie1?ekv0，否则转⑶；

139

⑶ 重复步骤⑵，直到构造一条包含G的所有边的回路为止，此回路即为欧拉回路，因此，G是欧拉图。

由此定理容易得到如下的推论。

推论 连通图G具有一条vi到vj的Euler链，当且仅当vi和vj是G中仅有的两个奇点。

定义6.4-2 设G是有向连通图，若G中具有包含所有边的闭链，则称该闭链为欧拉有向回路，并称G为欧拉有向图。

若连通有向图G具有一包含所有边的有向链，则称其为欧拉有向链，并称G为半欧拉有向图。由欧拉有向图的定义，连通的有向欧拉图一定是强连通的。

定理6.4-2 一个连通的有向图G是Euler图（具有Euler回路），当且仅当G的所有结点的入度等于出度。

推论 连通有向图G有一条vi到vj的Euler链，当且仅当

??⑴存在vi,vj?V(G)使得 d(vi)?d(vi)?1，d(vj)?1?d(vj)；

??⑵ 而在V(G)?{vi,vj}中的所有结点的入度等于其出度。

(1) (2) 图6.4-3

(3)

例6.4-2 欧拉图和Euler欧拉链的一个典型的应用是一笔画的判定，即用笔连续移动（笔不离纸，也不重复）将一个图描绘出来，这实质上就是判断图形是否存在欧拉链或Euler欧拉回路的问题，如图6.4-3，图⑴、⑵都可一笔画，因为欧拉图，而⑶不能一笔画。图6.4-4中(a)、(b)都可一笔画，因为图(a)是欧拉图，而图(b)是半欧拉图，而图(c)不能一笔画。

(a) (b) 图6. 4-4

(c)

例 6.4-3 图6.4-5表示的是一个展览馆的平面图。馆里各相邻房间之间都有门（共16扇）。一个参观者来到展览馆门外，他想在参观过程中，把馆里所有的门都不重复地穿行一遍后出来，这个想法能否实现？

首先建立该问题的图论模型。将展览馆的5个房间和馆外场地用6个结点表示，两个端点之间的边表示它们所在位置之间有一扇门，则得到如图6.4-5所示的图(b)。

于是，判断能否不重复地穿过展览馆的每扇门一次的问题就转化为图(b)是否是欧拉图

140

的问题。由图6.4-5中的图(b)可以看出，图中有4个奇点A,B,D,F，由定理6.4-1，图(b)不是欧拉图，即参观者的想法不能实现。

D A F C D (a)

B

E

A (b)

B C F E 图6. 4.5

4.5

例6.4-4 计算机鼓轮设计—布鲁英（De Bruijn）序列，旋转鼓轮的表面分成8个扇面，如图6.4-6所示。

c b a e0=000

00 e1=001 e=100

e2=010 4

01 10

e5=101 e3=011 e6=110

11

e7=111

图6.4-6 图6.4-7

图6.4-6中阴影部区表示用导体材料制成。空白区用绝缘材料制成，触点a,b和c与扇面接触时接触导体输出1，接触绝缘体输出0。鼓轮按逆时针旋转，触点每转一个扇区就输

出一个二进制信号。问鼓轮上的8个扇区应如何安排导体或绝缘体，使鼓轮旋转一周，触点输出一组不同的二进制信号？

每转一个扇区，信号a1a2a3变成a2a3a4，前者右两位决定了后者左两位。因此，我们把所有两位二进制数作结点，从每一个结点a1a2到a2a3引一条有向边表示a1a2a3这三位二进制数，作出表示所有可能数码变换的有向图（如图6.4-7）。于是问题转化为在这个有向图上求一条欧拉回路，这个有向图的4个结点的度数都是出度、入度各为2，根据定义6.4-2，图6.4-7中有欧拉回路存在，例如(e0e1e2e5e3e7e6e4)是一Euler回路，对应于这一回路的布鲁英序列是00010111，因此材料应按此序列分布。

用类似的论证，我们可以证明，存在一个2个二进制的循环序列，其中2个由n位二进制数组成的子序列都互不相同。例如16个二进制数的布鲁英序列是

。00001010101111

nn 141

中都是连通：

⑴若u,v分属不同结点子集,不妨设u?V1,v?V2，由假设在G中显然结点u,v是不连通的，所以，在G中u,v有边连接，即在G中u,v连通。

⑵若u,v属于同一结点子集，不妨设u,v?V1，取w?V2(因V2非空)，则在G中有路

uwv，即在G中u,v连通。

由此可知，无论是⑴或⑵都有G的补图G是连通的，所以，对于任意不连通的图G，其补图都是连通的。

例6.6-4如果一个简单图G与它的补图G同构，则称G是自补图(Self-complementary graph)。 证明：若n阶无向简单图是自补图，则n?0,1(mod4),即n?4k或n?4k?1（k为正整数）。

证明 若n阶无向简单图是自补图，则因G?G，而G与G的边数相同，设它们的边数为m。又因为G与G的边数之和为Kn的边数因此n?4k或n?4k?1（k为正整数）。

例6.6-5设G为有n个结点的简单图，且E?(n?1)(n?2)/2，则G是连通图。 证明 假设G??V,E?不连通，不妨设G可分为两个连通分支G1,G2，设G1,G2分别有n1,n2个结点，所以有n1?n2?n。由于ni?1,i?1,2，则有ni?n?1,i?1,2，从而

n(n?1)n(n?1)，所以即n(n?1)?4m， ?2m，22E?n1(n1?1)n2(n2?1)(n?1)(n1?n2?2)(n?1)(n?2) ???2222这与假设矛盾。所以G是连通图。

例6.6-6 对于如图6.6-1所示的有向图D??V,E?中，请计算下列问题： ⑴D中v1到v4长度为1的通路有几条？ ⑵长度为2的通路有几条？

⑶长度为3的通路有几条？ ⑷长度为4的通路有几条？

解 图的邻接矩阵为

v2 图6.6-1

152

v1 v4

v3

?0?1A???0??0111?010??，由a(1)=1，可知v到v长度为1

1414001??000?011?112??，由a(2)=1，可知v到v长度为2的通

1414000??000??1?02的通路为1条。计算A2得：A???0??0?0?13路为1条。计算A3得：A???0??02条。

112?011??，由a(3)=1，可知v到v长度为3的通路为

1414000??000??1?044计算A得：A???0??0011?112??，由a(4)=1，可知v到v长度为4的通路为1条。

1414000??000?例6.6-7问图6.6-2中的两个图，各需要几笔画出（笔不离纸，每条边均不能重复画）？ 解 在（a）中有8个奇数度结点，则（a）中存在4条边不重合的简单通路，它们含有图中的全部边。因此，（a）可4笔画出，如aei，kgc，badcbfjilkj，dhefghl四条链包含了（a）图中的全部边。（b）中有4个奇数度结点，因此，（b）图中存在两条边不重合的链，它们含有（b）图中的全部边。如eabiadhg，fgcjdcbfeh两条边不重合的链包含（b）图中全部边，因此（b）图可以2笔画出。

a e i d h l k g c j g c j f b d h e a i 10 f b 1 2 3

9 8 7 0 5 6 图6.6-3

4

(a)

图6.6-2

(b)

例6.6-8 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生

153

两旁所坐的人都不相同，问这11个人共进午餐最多能有多少天？

解 将这11个学生分别用结点表示，由于任意两个学生都可能是邻座，因此每两个结点之间都连一条边，得到无向完全图K11，每次午餐时，学生都按一条Hamilton圈沿桌而坐，若两个圈有公共边，则公共边端点上的两个学生是相邻的，从而上述问题转化为求K11有多少条无公共边的Hamilton圈问题，而K11共有55条边，又每个Hamilton圈恰有11条边，因此，11个人共进午餐最多能有5天。实事上，先将11个结点分别编号为0, 1,2, …,10，并作图如图6.6-3，在图中先取一条Hamilton圈为0,1,2,10,3,9,4,8,5,7, 6,0, 然后将圆周上的结点按逆时针方向转动一个位置，就可由图取得另一条Hamilton 圈为0,2,3,1,4,10,5,9,6,8,7,0,，显然这两条Hamilton 圈是没有公共边的。这样继续下去K11中共产生5条无公共边的Hamilton圈，故这11个人共进午餐最多能有5天。

复习题六

1. 设无向图G有12条边，已知G中度数为3的结点有6个，其余结点的度数均小于3，问G中至少有多少个结点？为什么？

2．一个n(n≥2)阶无向简单图G中，n为奇数，已知G中有r个奇度数结点，问G的补图G中有几个奇度结点？

3．证明，任何6个人中，要么有3人彼此相识，要么有3人彼此不认识。

4. 画出K4的所有非同构的子图，其中有几个是生成子图？生成子图中有几个是连通图？

5. 如下图所示之图1是否同构于图2？

u1 u2 u4 u5 u6

图1

u3

v1v6v5 e v1 v2 v2

v3图2

v3

v4v4 图3

v5

6. 试给出所有不同构的无向5阶自补图。 7. 在图3中找出其所有的路和圈。

8. 设G是具有n个结点的简单无向图，如果G中每一对结点的度数之和均大于等于n-1，那么G是连通图。

9. 寻找3个4阶有向简单图D1,D2,D3,使得D1为强连通图；D2为单向连通图但不是强连通图；而D3是弱连通图但不是单向连通图，当然更不是强连通图。

10. ⑴ 写出图4的关联矩阵和邻接矩阵；

⑵ 说明如何从关联矩阵中判断一个结点为割点，一条边为割边。

154

v1v1

v3

v2v4

v2

图4

v4

v3图5

11. 图5是有向图。

⑴ 求出它的邻接矩阵A。 ⑵ 求出AT(2),A(3),A(4)

TT说明从v1到v4长度为1,2,3,4的路径各有几条？

TT⑶ 求出A,AA,AA，说明AA,AA中第（2，3）个元素和第（2，2）个元素 的意义。

⑷ 求出A,A,A及可达性矩阵。

⑸ 求出图5的一个强连通子图。

12. 若无向图G是欧拉图，问G中是否有割边？为什么？

a b c l H k j i h 图6

g f 图7 G F d e A

B

C

D 234E

13.试从图6中找出一条欧拉回路。 14.试从图7中找出一条欧拉路。

15. 在图8中，那些是哈密尔顿图？那些是半哈密尔顿图？是哈密尔顿图的，请各在图中画出一条哈密尔顿回路；是半哈密尔顿图的，请画出一条哈密尔顿通路。

16. 给出满足下列条件之一的图的实例。 ⑴图中同时存在欧拉回路和哈密顿回路； ⑵图中存在欧拉回路，但不存在哈密顿回路； ⑶图中不存在欧拉回路，但存在哈密顿回路；

⑷图中不存在欧拉回路，也不存在哈密顿回路。

155

b d h b c j c a a g e f k i h g j f d e i ⑴

d ⑵

d h g j c f b a e h g j c f b a e i i ⑶

⑷

图8

17. 图9中的各个图是否能够一笔画出？如果能够，给出具体的画法。

v2 1 2 8 9 15 16 10 4

17 11 5 20 14 19 18 12 13 v1v7 v8 v9 v3 v10

3

7

v6 v12 v11 v4

6

(a)

v5 (b) 图9 判定一笔画

(c)

156

人称为中国邮递员问题（Chinese Postman Problem）。

我们把邮递员的投递区域看作一个连通的带权无向图G，其中G的顶点看作街道的交叉口和端点，街道看作边，权看作街道的长度，解决中国邮递员问题，就是在连通带权无向图中，寻找经过每边至少一次且权和最小的回路。

如果对应的图G是欧拉图，那么从对应于邮局的顶点出发的任何一条欧拉回路都是符合上述要求的邮递员的最优投递路线。

如果图G只有两个奇点x和y，则存在一条以x和y为端点的欧拉链，因此，由这条欧拉Euler链加x到y最短路即是所求的最优投递路线。

如果连通图G不是欧拉图也不是半欧拉Euler图，由于图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?中最短的欧拉Euler回路称为图G的最优环游。

定理1 设P是加权连通图G中一条包含G的所有边至少一次的闭链，则P最优（即具有最小长度）的充要条件是：

⑴ P中没有二重以上的边；

⑵ 在G的每个圈C中，重复边集E的长度之和不超过这个圈的长度的一半，即

w(E)?1w(C)。 2根据上面的讨论及定理1，我们可以设计出求非欧拉带权非欧拉连通图G的最优环游的算法。此算法称为最优环游的奇偶点图上作业法。

⑴ 把G中所有奇点配成对，将每对奇点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中没有奇点，即G1为多重欧拉图。

⑵ 若G1中每一对顶点之间有多于2条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接，得到图G2。

⑶ 检查G2的每一个圈C，若某一个圈C上重复边的权和超过此圈权和的一半，则将C中的重复边改为不重复，而将单边改为重复边。重复这一过程，直到对G2的所有圈，其重复边的权和不超此圈权和的一半，得到图G3。

⑷求G3的Euler回路。

例6.5-2求图6.5-2所示图G的最优环游。

解 图G中有6个奇点v2，v4，v5，v7，v9，v10，把它们配成三对：v2与v5，v4与v7，v9

与v10。在图G中，取一条连接v2与v5的路v2v3v4v5，把边(v2 , v3) , (v3 , v4), (v4 , v5)作为重复边加入图中；再取v4与v7之间一条路v4v5 v6v7，把边(v4 , v5), (v5 , v6)，( v6 ，v7)作为重复边加入图中，在v9和v10之间加一条重复边(v9，v10)，如图6.5-3所示，这个图没有奇点，是一

147

个欧拉图。

v1

5

2 3 6 9 4

v10 4 v9 5 v 8v1 5 2 3 6 9 9 2 v10

4 4 v9 5 v8

4 v2 v11

6 4

4 3 v12

6 8 4

v7

7

v2 5 5 v11 4 3 3 4 v12 6 7 8 6 v7

7 5

4 v3 v4

2 3 6 9 9 v5 v6 v8

4 v3 v4 3 v5 8 图6.5-3

v10 4 v9 5 3 v6 v8

4 v1 5 v10 4 v9 4 图6.5-2

5 v1 5 v2 5 5 v11 6 4 4 v12 4 3 v3 v4 v5 6 7 8 v7

7 v2 5 6 6 4 v11 4 v12 6 4 4 4 6 4 6 v7

7 8 v6 v3 9 v4 3 v5 8 v6

图6.5-5

图6.5-4

v1 5 2 3 6 6 9 4 v10 4 v9 5 4 4 3 6 v8

4 7 v1

5 2 v10 4 v9 5 v8

4 v2 5 v11 4 v12 6 v7

4 6 8 2 5 3 6 9 4 v2 5 v11 4 3 6 4 v12 8 5 4 6 v7

7 v3 v4 3 v5 图6.5-6

v6

v3 v4 3 v5 图6.5-7

v6

在图6.5-3中，顶点v4 与v5之间有三条重边，去掉其中两条，得图6.5-4所示的图，该图仍是一个欧拉图。

如图6.5-4中，圈v2v3v4v11v2的总权为24，而圈上重复边的权和为14，大于该圈总权的一半，于是去掉边(v2 ,v3)和(v3 ,v4)上的重复边，而在边(v2 ,v11)和(v4 ,v11)上加入重复边，此时重复边的权和为10，小于该圈总权的一半。同理，圈v5 v6v7v12v5的总权为25，而重复边权和为15，于是去掉边(v5, v6)和(v6 ,v7)上的重复边，在边(v5,v12)和(v7 ,v12)上加重复边，如图6.5-5所示。

图6.5-5中，圈v4v5 v12v11v4的总权为15，而重复边的权和为8，从而调整为图6.5-6所示。

图6.5-6中，圈v1v2v11v12v7 v8v9v10v1的总权为36，而重复边的总权为20，继续调整为图6.5-7所示。

检查图6.5-7，可知定理1的⑴和⑵均满足，故为最优方案，接着给出出图6.5-7所示图的Euler回路，即为图G的最优环游

148

由上例可知，对于比较大的图，要考察每个圈上重复边权和不大于该圈总权和的一半，确定每个圈的时间复杂性太大。1973年Edmonds和Johnson给出了一个更有效算法。

6.5-3旅行售货员问题

旅行售货员问题（Traveling Salesman Problem）是在加权完全无向图中，求经过每个顶点恰好一次的（边）权和最小的哈密尔顿圈，又称之为最优哈密尔顿圈(Optimum Hamilton cycle)。如果我们将加权图中的结点看作城市，加权边看作距离，旅行售货员问题就成为找出一条最短路线，使得旅行售货员从某个城市出发，遍历每个城市一次，最后再回到出发的城市。

若选定出发点，对n个城市进行排列，因第二个顶点有n-1种选择，第三个顶点有n-2种选择，依次类推，共有(n-1)!条哈密尔顿圈。考虑到一个哈密尔顿圈可以用相反两个方向来遍历，因而只需检查

1(n?1)!个哈密尔顿圈，从中找出权和最小的一个。我们知道21116比如有20个顶点，需考虑?19!（约为6.08?10）(n?1)!随着n的增加而增长得极快，

22条不同的哈密尔顿圈。要检查每条哈密尔顿圈用最快的计算机也需大约1年的时间才能求

出该图中长度最短的一条哈密尔顿圈。

因为旅行售货员问题同时具有理论和实践的重要性，所以已经投入了巨大的努力来设计解决它的有效算法。目前还没有找到一个有效算法！

当有许多需要访问的顶点时，解决旅行售货员问题的实际方法是使用近似算法（Approximation algorithm）。

下面介绍简便的“最邻近方法”给出旅行售货员问题的近似解。 最邻近方法的步骤如下：

⑴ 由任意选择的结点开始，指出与该结点最靠近（即权最小）的点，形成有一条边的初始路。

⑵ 设x表示最新加到这条路上的结点，从不在路上的所有结点中选一个与x最靠近的结点，把连接x与这个结点的边加到这条路上。重复这一步，直到图中所有结点包含在路上。

⑶ 将连接起点与最后加入的结点之间的边加到这条路上，就得到一个哈密尔顿圈，即得问题的近似解。

例6.5-3 用“最邻近方法”找出图6.5-8所示加权完全图中具有充分小权的哈密尔顿圈。 解 ADCBEFA 的权和为55，BCADEFB的权和为53，CBADEFC的权和为42，DABCFED的权和为42，EADCBFE的权和为51，FCBADEF的权和为42。

由上例可知，所选取的哈密尔顿圈不同，其近似解也不同，而“最邻近插入法”对上述方法可以进行改进，从而产生一个较好的结果。

该方法在每次迭代中都构成一个闭的旅行路线。它是由多个阶段而形成的一个个旅程，逐步建立起来的，每一次比上一次多一个顶点，即是说，下一个旅程比上一个旅程多一个顶点，求解时，在已建立旅程以外的顶点中，寻找最邻近于旅程中某个顶点的顶点，然后

149

将其插入该旅程中，并使增加的距离尽可能小，当全部顶点收入这个旅程后，就找到了我们所求的最短哈密尔顿圈的近似解。

A 16 F 13 18 9 15 3 12 2 E 18 13 D 图6.5-8

C

11 9 5 7 6 B

最邻近插入法的步骤如下（图中有n个结点）： ⑴任取图中一点v1，作闭回路v1v1，置k?1； ⑵若k?n，则输出闭回路，结束；否则转⑶；

⑶在已有闭回路Ck?v1v2?vkv1之外的结点V?{v1,v2,?,vk}中，选取与闭回路Ck最邻近的点u；

⑷将u插入闭回路Ck的不同位置可得k条不同的闭回路，从这k条闭回路选取一条长度最小的作为新的闭回路。k?k?1，转⑵。

例6.5-4 用“最邻近插入法”找出图6.5-8所示加权完全图中具有充分小权的哈密尔顿圈。

解 ①开始于顶点A，组成闭旅程AA。

②最邻近A的顶点为D，建立闭旅程ADA。 ③顶点B最邻近顶点A，建立闭旅程ADBA。

④由于C最邻近B，将C插入，分别得到三个闭旅程ACDBA、ADCBA、ADBCA，其长度依次为33、20、23，选取长度最短的旅程ADCBA。

⑤距旅程ADCBA中顶点最邻近顶点为F，将F插入，分别得到四个闭旅程AFDCBA、ADFCBA、ADCFBA、ADCBFA，其长度依次为52、34、37、45，选取长度最短的旅程ADFCBA。

⑥把顶点E插入旅程ADFCBA中，得到五个闭旅程AEDFCBA、ADEFCBA、ADFECBA、ADFCEBA、ADFCBEA、，其长度依次为54、42、60、61、49。显然，长度最短的旅程ADEFCBA即为我们要求的最短哈密尔顿圈的近似解。

习题6.5

6.5-1.求图6.5-9中从v1到v8的各条道路中，哪一条总长度（各弧长度之和）最短？

150

6.5-2.求图6.5-10的带权图中最优投递路线，邮局在D点。

v2 8 v1 11 v4 图6.5-9

2 4 v3 9 1 5 1 12 4 v7 v6 8 2 v5 2 v8

a B 50 19 A 30 C 40 6 35 D 12 23 10 图6.5-10

E 8 20 F G 14 b 7

5 14 10 c 图6.5-11

d 6 5 8 e 6

6.5-3 分别用最邻近算法和最邻近插入法求表示图6.5-11中的最短哈密尔顿回路。

6.6 习 题 解 析

例6.6-1设图G中有9个结点，每个结点的度不是5就是6。试证明：G中至少有5个6度结点或至少有6个5度结点。

证明 由握手定理的推论可知，G中5度结点只能是0，2，4，6，8五种情况（此时6度结点分别为9，7，5，3，1个）。以上五种情况都满足至少5个6度结点或至少有6个5度结点。

例6.6-2若有n个人，每个人恰有3个朋友，则n必为偶数。

证明 用n个结点v1,v2,?vn代表n个人，两个朋友对应的结点之间连边，则得到一个3正则图G，该题可以转化为3正则图必有偶数个结点。由于所有结点度数和为

?deg(v)?3n，而?deg(v)为偶数，所以3n为偶数，则n为偶数。

ii例6.6-3证明：若无向图G是不连通的，则G的补图G是连通的。

证明 因为，无向图G不连通，则可设G??V,E?至少有两个连通分支，并设其中一个连通分支为G1??V1,E1?，且V1,V2(?V?V1)都非空。现在证明任一两点u,v?V在G

151

本文来源：https://www.bwwdw.com/article/3abd.html