离散数学第7章

第四篇 图论

图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。例：用定理解决哥尼斯堡桥的问题

第四篇 图论

图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。WWW电力网因特网复杂网络的事例——技术网络复杂网络的事例——社会网络朋友关系网演员网科学家合著网科学引文网复杂网络的事例——交通运输网络城市公共交通网道路交通网航空网复杂网络的事例——生物网络神经网络生态网络蛋白质相互作用网络基因网络新陈代谢网络SantaFe研究所的科学家合作网复杂网络的事例——科学家合作网经济物理学科学家合作网复杂网络的事例——科学家合作网复杂网络的事例——中药方剂网示意图点（药材），边（药材之间相互作用），局域世界（方剂）§1图的基本概念定义:

图（graph）G由一个三元组<V(G),E(G),G>表示，其中：非空集合V(G)={v1,v2,…,vr}

称为图G的结点集，其成员vi(i=1,2,…,r)称为结点或顶点（nodes

orvertices）；集合E(G)={e1,e2,…,es}

称为图G的边集，其成员ej(j=1,2,…s)称为边(edges)。函数G

：E(G)→(V(G),V(G))

，称为边与顶点的关联映射（associatvemapping）§1图的基本概念例：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)abcde1e2e3e4e5e6§1图的基本概念

讨论定义：

(1)V(G)={V1，V2，…，Vn}为有限非空集合,Vi称为结点,简称V是点集。

(2)E(G)={e1，…，em}为有限的边集合,ei称边，每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。§1图的基本概念(3)若Ｇ中每一条边e与有序偶对<vi,vj>或无序偶对(vi,vj)相关联，则可说边e连接结点vi和vj(4)可用e＝<vi,vj>或e＝(vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝<Ｖ，Ｅ>。例：有图如下，试写成定义表达式Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝{v1,v2,v3,v4,v5}Ｅ＝{x1,x2,x3,x4,x5,x6}§1图的基本概念例：对有向图可表示为：Ｇ＝〈Ｖ、Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝§1图的基本概念下面定义一些专门名词：(1)有向边：若边ej与结点序偶<vj,vk>关联，那么称该边为有向边。(2)无向边：若边ej与结点无序偶(vj,vk)关联，那么称该边为无向边。§1图的基本概念(3)邻接结点：由一条边（有向或无向）连接起来的结点偶对。(4)（ｎ，ｅ）图：具有ｎ个结点（顶点），ｅ条边的图。§1图的基本概念(5)有向图：在Ｇ中每一条边均为有向边。(6)无向图：每条边均为无向边的图。(7)混合图：有些边是无向边，有些边是有向边的图称为混合图。§1图的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环§1图的基本概念(8)点和边的关联：如ei=(u，v)或ei=<u，v>称u，v与ei关联。(9)点与点的相邻：关联于同一条边的结点称为邻接点。(10)边与边的邻接：关联于同一结点的边称为邻接边。§1图的基本概念(11)孤立结点：不与任何结点相邻接的结点称为孤立结点。(12)零图：仅有孤立结点的图。(13)平凡图：仅有一个孤立结点的图。(14)自回路(环)：关联于同一结点的边称为自回路，或称为环。§1图的基本概念(15)

平行边：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。

定义：在图G=<V，E>，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。图G最大度记为(G)=max{deg(v)|vV(G)}，最小度数记为(G)=min{deg(v)|vV(G)}§1图的基本概念

定义：在有向图中，vV，以v为始点的边数称为该结点的出度，记作deg+(v);以v为终点的边数称为该结点的入度，记作deg-(v)。显然有

deg(v)=deg+(v)+deg-(v)如：G1是无向图，deg(v1)=3，deg(v2)=1G2是有向图，deg+(v1)=2，deg-(v1)=3，deg(v1)=5，v1v2G1v1v3v4v2G2定理：每个图中，结点度数总和等于边数的两倍。即deg(v)=2|E|vV

定理：在任何图中,度数为奇数的结点必定是偶数个。定理：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。定义：含有平行边的图称为多重图。简单图：不含平行边和环的图称为简单图。定义：简单图G=<V，E>中，若每一对结点间均有边相连，则称该图为完全图。有n个结点的无向完全图记为Kn。定理：在任何图中,n个结点的无向完全图Kn的边数为n(n-1)/2。无向完全图：每一条边都是无向边不含有平行边和环每一对结点间都有边相连证明：n个结点中任取两个结点的组合数为

Cn2

=

n(n-1)/2故的边数为

|E|=n(n-1)/2定义：给定一个简单图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图，记为G。即G=<V，E1>，G=<V，E2>，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图G’定义：设图G=<V，E>，如果有图G’=<V’，E’>，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。相对于图G的补图定义：设G’=<V’，E’>是G=<V，E>的子图，若给定另一个图G”=<V”，E”>使得E”=E-E’，且V”中仅包含E”的边所关联的结点，则称G”是子图G’相对于图G的补图。定义：设图G=<V，E>及图G’=<V’，E’>，如果存在一一对应的映射g：vivi’且e=(vi，vj)(或<vi，vj>)是G的一条边，当且仅当e’=(g(vi)，g(vj))(或<g(vi)，g(vj)>)是G’的一条边，则称G与G’同构，记作G≌G’。两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。§2路与回路

定义:

给定图G=<V,E>,设v0,v1,…,vnV，e1,…,enE,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路（拟路径Pseudopath）

。

v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路（闭路径closedwalk）。

例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3v5e8v4e5v2e6v5e7v3e4v2v4e8v5e6v2e1v1e2v3v2e1v1e2v3e7v5e6v2§2路与回路

若一条路中所有的边e1,…,en均不相同称作迹（路径walk）。若一条路中所有的结点v0,v1,…,vn均不相同,称作通路（Path）。闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit）。

§2路与回路

定理：

在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。§2路与回路

推论：在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。§2路与回路

定义：

在无向图G中，如果从结点u和结点v之间若存在一条路，则称结点u和结点v是连通的（connected）。§2路与回路

结点之间的连通性是结点集V上的等价关系。把子图G(V1),G(V2),…,G(Vm)称为图G的连通分支（connectedcomponents）,图G的连通分支数记为W(G)

。§2路与回路

定义：若图G只有一个连通分支，则称G是连通图。显然在连通图中，任意两个结点之间必是连通的。§2路与回路

对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。

删除结点：所谓在图中删除结点v，即是把v以及与v关联的边都删除。删除边：所谓在图中删除某条边，即是把该边删除。

§2路与回路v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e

定义：设无向图G=<V,E>是连通图,若有结点集V1V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-set

ofnodes)。若某一个点构成一个点割集，则称该点为割点。sabcdabcdba§2路与回路

点连通度：为了产生一个不连通图需要删去的点的最少数目，也称为连通度,记为k(G)。即k(G)=min{|V1||是G的点割集}称为图G的点连通度(node-connectivity)。§2路与回路(1)若G是平凡图则k(G)=0(2)k(Kn)=n-1(3)若图存在割点，则k(G)=1(4)规定非连通图的连通度k(G)=0§2路与回路v5v1v2v3v4v5v1v3v4点割集V1={v2}§2路与回路

定义：设无向图G=<V,E>是连通图,若有边集E1E，使图

G中删除了E1的所有边后，所得到的子图是不连通图，而删除了E1的任何真子集后，所得到的子图仍是连通图，则称E1是G的一个边割集(cut-setof

edges)。若某一条边就构成一个边割集，则称该边为割边或桥。割边e使图G满足W(G-e)>W(G)

。§2路与回路

边连通度(edge-connectivity)

(G)定义：非平凡图的边连通度为

(G)=min{|E1||E1是G的边割集}

边连通度

(G)是为了产生一个不连通图需要删去的边的最少数目。§2路与回路(1)若G是平凡图则(G)=0(2)若G存在割边，则(G)=1，(3)规定非连通图的边连通度为(G)=0§2路与回路

定理：

对于任何一个图G,有k(G)≤(G)≤δ(G)

。δ(G)=min(deg(v)，vV)§2路与回路

若G不连通，则k(G)=(G)=0，故上式成立。若G连通，可分两步证明上式也成立：

1)先证明(G)≤(G)：如果G是平凡图，则(G)=0≤(G)，若G是非平凡图，则因每一结点的所有关联边必含一个边割集，(因(G)=min{deg(v)|vV}，设uV使的deg(u)=δ(G)，与u相关联的条边必包含一个边割集，至少这条边删除使图不连通。)故(G)≤(G)。§2路与回路

2)再证k(G)≤(G)：(a)设(G)=1，即G有一割边，显然这时k(G)=l，上式成立。§2路与回路

(b)设(G)≥2，则必可删去某(G)条边，使G不连通，而删去其中(G)-1条边，它仍是连通的，且有一条桥e=(u，v)。对(G)-1条边中的每一条边都选取一个不同于u，v的端点，把这些端点删去则必至少删去(G)-1条边。若这样产生的图是不连通的，则k(G)≤(G)-1<(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v就必产生一个不连通图，故k(G)≤(G)。由1)和2)得k(G)≤(G)≤(G)。§2路与回路

定理：一个连通无向图G的结点v是割点的充分必要条件是存在两个结点u和w,使得结点u和w的每一条路都通过v

。§2路与回路

1)先证:v是割点存在结点u和w的每条路都通过v

若v是连通图G=<V,E>割点，设删去v得到的子图G’,则G’至少包含两个连通分支G1=<V1,E1>和G2=<V2,E2>

。任取uV1，wV2，因为G是连通的，故在G中必有一条连结u和w的路C，但u和w在G’中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v

。

§2路与回路

2)再证:存在结点u和w的每条路都通过v

v是割点若连通图G中的某两个结点的每一条路都通过v，则删去v得到子图G’

，在G’中这两个结点必然不连通，故v是图G的割点。§2路与回路

在无向图G中，从结点u到v若存在一条路，则称结点u到结点v是可达的。§2路与回路

对于任何一个有向图G=<V,E>,从结点u和到结点v有一条路,称为从u可达v。可达性(accesible),是结点集上的二元关系，它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。§2路与回路

如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为u和v之间的距离（或短程线），记作d<u,v>，它满足下列性质：

d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>§2路与回路如果从u到v是不可达的，则通常写成d<u,v>=∞注意：当u可达v，且v也可达u时，d<u,v>不一定等于d<v,u>§2路与回路有关距离的概念对无向图也适用，把

D=maxd<u,v>,u,v∈V称作图的直径。§2路与回路

定义:

在简单有向图G中，任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是单侧连通的。§2路与回路

如果对于图G中的任何一对结点两者之间是相互可达的，则称这个图是强连通的。如果在图G中略去边的方向，将它看成无向图后，图是连通的，则称该图为弱连通的。显然，强连通图→单侧连通图→弱连通图。而逆推均不成立。§2路与回路v2v3v4v1(a)强连通v2v3v4v1(b)单侧连通v2v3v4v1(c)弱连通§2路与回路

定理：一个有向图是强连通的充分必要条件是G有一个回路，它至少包含每个结点一次。§2路与回路

证明：充分性：如G中有一条有向回路，经过每一点至少一次，则G中任意两点u，v∈V，u可以沿着该有向回路的一部分的而到达v，则G是强连通图。§2路与回路

必要性：任取u，v∈V，图G是强连通图，则u→v有有向路，v→u也有有向路，则u→v→u构成了一个有向回路，如果该有向回路没有包含w，而u→w，w→u均有有向路，则u→v→u→w→u又是一个有向回路，一直下去可以将图中所有的点均包含进去。§2路与回路

定义：在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。§2路与回路v4v2v3v1(a)v5v4v2v3v1(b)§2路与回路

定理:在有向图G=<V,E>中，它的每一个结点位于且只位于一个强分图中。§3图的矩阵表示

图的邻接矩阵表示方法

定义：设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，其中V={v1,v2,…vn}定义一个nxn的矩阵A，并把其中各元素aij表示成：

则称矩阵A为图G的邻接矩阵。§3图的矩阵表示例：设图Ｇ＝＜Ｖ，Ｅ＞如下图所示讨论定义：（1）图G的邻接矩阵中的元素为0和1，∴又称为布尔矩阵；（2）图G的邻接矩阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。§3图的矩阵表示∴若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中，①行中1的个数就是行中相应结点的引出次数②列中1的个数就是列中相应结点的引入次数§3图的矩阵表示２．矩阵的计算：§3图的矩阵表示主对角线上的数表示结点i（或j）的引出次数。

主对角线上的数表示结点i（或j）的引入次数。§3图的矩阵表示表示i和j之间具有长度为2的路径数，表示i和j之间具有长度为3的路径数，表示i和j之间具有长度为4的路径数，§3图的矩阵表示bij表示从结点vi到vj有长度分别为1，2，3，4的不同路径总数。此时，bij0，表示从vi到vj是可达的。§3图的矩阵表示定义：设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，其中|V|=ｎ（），定义一个矩阵P，它的元素为：则P称为图G的可达性矩阵。

由可计算出可达性矩阵，其方法是：若中（i,j）是非“0”元素，则对应，否则。§3图的矩阵表示定义：设无向图Ｇ＝＜Ｖ，Ｅ＞，

其中，则称B为无向图G的完全关联矩阵。

令可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有回路。从图G的邻接矩阵A可以得到可达矩阵P，即令Bn=A+A2+A3+…+An，再从Bn中非零元素改为1而零元素不变，这种变换后的矩阵即是可达矩阵P。§3图的矩阵表示例：讨论定义：（1）完全关联矩阵为布尔矩阵；（2）对应B中行均为0的结点为孤立结点，只有一个“1”的行的结点一定为悬挂的边，且一定不在任一循环中全部为1的行的结点必定联结图中所有的结点。3)每一条边关联两个结点,故每一列中只有两个1。

4)每一行中元素之和等于该行对应的结点的度数。

5)两个平行边其对应的两列相同。

6)同一个图当结点或边的编号不同时，其对应的矩阵只有行序列序的差别。有向图的关联矩阵

定义：给定简单有向图G=<V,E>,设v1,v2,…,vpV,e1,…,eqE,称p×q阶矩阵M(G)=(mij)p×q

为图G的完全关联矩阵(incidencematrix)。其中:1

若vi是

ej的起点。

-1

若vi是

ej的终点。

0若vi不关联

ej。mij=

有向图的关联矩阵的特点：

(1)每一列中有一个1和一个-1，对应一边一个始点、一个终点，元素和为零。

(2)每一行元素的绝对值之和为对应点的度数。-1的个数等于入度，1的个数等于出度。

有向图G的两行相加定义为：第i行第j列的对应元素算术相加；相当于删除结点vi与结点vj之间的关联边，合并结点vi和vj

。合并后得到的新结点记为vi,j。无向图G的两行相加定义为：第i行第j列的对应元素模2相加；相当于删除结点vi与结点vj之间的关联边，合并结点vi和vj

。合并后得到的新结点记为vi,j。

3、关联矩阵的秩

定理：

如果一个连通图G=<V,E>,有r个结点,则其完全关联矩阵M(G)的秩为r-1,即rankM(G)=r-1

。推论：如果一个连通图G=<V,E>,有r个结点,w个最大连通子图,则图G的完全关联矩阵M(G)的秩为r-w,即rankM(G)=r-w

。

例：写出如图7-3.11所示的图G的完全关联矩阵，并验证其秩如定理7-3.2所述。e1e2e3e4e5e6e7e8e9A100001010B011000100C000110010D110000001E000011100F001100001完全关联矩阵为:此图为连通图，由定理其秩为5。§4欧拉图和汉密尔顿图2.定理7-4.1

无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。1.定义7-4.1

如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路径（Eulerwalk）。如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图（Eulergraph）。

由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故欧拉回路必不存在。3.定理7-4.1的推论

无向图G具有一条欧拉路，当且仅当G连通且所有结点度数皆为偶数。例：用定理解决哥尼斯堡桥的问题一笔画问题要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。定义7-4.2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。可以将欧拉路和欧拉回路的概念推广到有向图中。

定理7-4.2

有向图G为具有一条单向欧拉回路，当且仅当G连通，并且每个结点的入度等于出度。有向图G有单向欧拉路，当且仅当G连通，并且恰有两个结点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。

例1有向欧拉图应用示例：计算机鼓轮的设计。鼓轮表面分成24=16等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息4个触点a,b,c,d读出1101(状态图中的边e13),转一角度后将读出1010(边e10)。问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。01111111100000001110abcd

设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数{000，001，……，111}，设ai{0,1}，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。

设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数{000，001，……，111}，设ai{0,1}，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。

所求的欧拉回路为：

e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)

（从图示位置开始）

e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6(e13)

所求的二进制序列为：

0000100110101111(0)

1101011110000100(1)（从图示位置开始）

上述结论可推广到鼓轮具有n个触点的情况。构造2n-1

个结点的有向图，每个结点标记为n-1位二进制数,从结点a1a2a3...an-1出发,有一条终点为a2a3...an-10的边,该边记为a1a2a3...an-10；还有一条终点标记为a2a3...an-11的边,该边记为a1a2a3...an-11

。邻接边的标记规则为：“第一条边后n-1位与第二条边前n-1位二进制数相同”。二、汉密尔顿图

与欧拉回路类似的是汉密尔顿回路。它是1859年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在图7-4.6中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。定义7-4.3：给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图定理7-4.3若图G＝<V，E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的连通分支数。证明设C是G的一条汉密尔顿回路，对于V的任何一个非空子集S，在C中删去S中任一结点a1，则C-a1是连通的非回路，W(C-a1)=1，|S|≥1，这时W(C-S)≤|S|。若再删去S中另一结点a2，则W(C-a1-a2)≤2，而|S|≥2，这时W(C-S)≤|S|。由归纳法可得：W(C-S)≤|S|。同时C-S是G-S的一个生成子图，因而W(G-S)≤W(C-S)，所以W(G-S)≤|S|。

此定理是必要条件，可以用来证明一个图不是汉密尔顿图。

如右图，取S={v1,v4}，则G-S有3个连通分支，不满足W(G-S)≤|S|，故该图不是汉密尔顿图。

所以用此定理来证明某一特定图是非汉密尔顿图并不是总是有效的。例如，著名的彼得森(Petersen)图，在图中删去任一个结点或任意两个结点，不能使它不连通；删去3个结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或5个以上的结点，余下子图的结点数都不大于6，故必不能有5个以上的连通分支数。所以该图满足W(G-S)≤|S|，但是可以证明它是非汉密尔顿图。说明：此定理是必要条件而不是充分条件。有的图满足此必要条件，但也是非汉密尔顿图。下面的定理给出一个无向图具有汉密尔顿路的充分条件

定理7-4.4

设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。证明思路：1)先证G连通:

若G有两个或多个互不连通的分支,设一个分图有n1个结点,任取一个结点v1,另一分图有n2个结点,任取一个结点v2,因为deg(v1)≤n1-1,deg(v2)≤n2-1,deg(v1)+deg(v2)≤n1+n2-2<n-1,与假设矛盾,G是连通的。2)先证(构造)要求的汉密尔顿路存在:

设G中有p-1条边的路,p<n,它的结点序列为v1,v2,…,vp。如果有v1或vp邻接于不在这条路上的一个结点,立刻扩展该路,使它包含这个结点,从而得到p条边的路。否则v1和vp都只邻接于这条路上的结点,我们证明在这种情况下,存在一条回路包含结点v1,v2,…,vp。

若v1邻接于vp,则v1,v2,…,vp即为所求。若v1邻接于结点集{vl,vm,…,…,vj,…,vt}中之一,这里2≤l,m,...,j,...,t≤p-1,如果vp是邻接于vl-1,vm-1,…,…,vj-1,…,vt-1中之一,譬如是vj-1,则v1v2…vj-1vpvp-1...vjv1是所求回路（如图7-4.9(a)所示）。如果vp不邻接于vl-1,vm-1,…,…,vj-1,…,vt-1中任一个,则vp最多邻接于p-k-1个结点,deg(vp)≤p-k-1,deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1与vp度数之和最多为n-2，得到矛盾。至此，已经构造出一条包含结点v1,v2,…,vp的回路,因为G是连通的,所以在G中必有一个不属于该回路的结点vx与回路中某一结点vk邻接,如图7-4.9(b)所示,

于是就得到一条包含p条边的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…,vj,v1,v2,…,vk-1),如图7-4.9(c)所示,重复前述构造方法，直到得到n-1条边的路。例某地有5个风景点，若每个景点均有两条道路与其他景点相通，问是否可经过每个景点一次而游完这5处。解将景点作为结点，道路作为边，则得到一个有5个结点的无向图。由题意，对每个结点vi(i=1,2,3,4,5)有

deg(vi)=2。则对任两点和均有

deg(vi)+deg(vj)=2+2=4=5–1

所以此图有一条汉密尔顿回路。即经过每个景点一次而游完这5个景点。例：在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。证明：设G为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课程的一个适当的安排。4.定理7-4.5

设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则G中存在一条汉密尔顿回路。证明思路：由定理7-4.4知,必有一条汉密尔顿路,设为v1,v2,…,vn,若v1与vn邻接,则定理得证。若v1与vn不邻接,假设v1邻接于{vi1,vi2,…,vik},2≤ij≤n-1,vn必邻接于vi1-1,vi2-1,…,vik-1中之一。若vn不邻接于vi1-1,vi2-1,…,vik-1中之一,则vn至多邻接于n-k-1个结点,因而,

deg(vn)≤n-k-1,而

deg(v1)=k,

deg(v1)+deg(vn)≤n-k-1+k=n-1,与假设矛盾,所以必有一条汉密尔顿路v1v2…vj-1vnvn-1…vjv1,如图7-4.11所示。