离散数学及其应用 课件 第4章图论

《离散数学及其应用》第4章图论目录4.1图的基本概念4.2通路与回路4.3图的连通性4.4图的矩阵表示4.5欧拉图和哈密尔顿图4.6树图论是以图为研究对象的数学分支。图论中的图指的是一些结点以及连接这些点的线的总体。通常用结点代表事物，连接两结点的线代表事物间的关系。图论研究的是事物对象在上述表示法中具有的特征与性质，即研究图的基本概念和性质、图的理论及其应用。在自然界和人类社会的实际生活中，用图来描述和表示某些事物之间的关系既方便又直观。例如，国家用顶点表示，有外交关系的国家用线连接，于是世界各国之间的外交关系就用一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通信系统中各通信站之间信息传递关系，用开关电路图来描述集成电路（integratedcircuit，IC）中各元件电路导线连接关系，等等。最早关于图论的论文可以追溯到1736年，当时瑞士数学家莱昂哈德·欧拉（LeonhardEuler）发表了一篇论文，给出了图论中的一个一般性的理论，其中包括现在被称为哥尼斯堡七桥问题的解。其背景是一个非常有趣的问题：18世纪，东普鲁士的哥尼斯堡城中的一个公园里，有7座桥将普雷格尔（Pregel）河中两个岛及岛与河岸连接起来，该城的居民喜欢在星期日绕城散步，如何从河岸或岛上的某一个位置出发，7座桥正好各经过一次，最后回到出发地。这就是有名的哥尼斯堡七桥问题（见图4.0.1）。哥尼斯堡七桥问题看起来不复杂，因此，立刻吸引了众多人的注意。有人尝试了很多次，然而始终没有成功。欧拉1707年4月15日生于瑞士巴塞尔，1783年9月18日卒于俄国圣彼得堡。他生于牧师家庭。15岁在巴塞尔大学获学士学位，翌年得硕士学位。1727年，欧拉应圣彼得堡科学院的邀请到俄国。1731年接替丹尼尔·伯努利成为物理教授。他以旺盛的精力投入研究，在俄国的14年中，他在分析学、数论和力学方面作了大量出色的工作。1741年受普鲁士腓特烈大帝的邀请到柏林科学院工作，达25年之久。在柏林期间他的研究内容更加广泛，涉及行星运动、刚体运动、热力学、弹道学、人口学，这些工作和他的数学研究相互推动。欧拉这个时期在微分方程、曲面微分几何以及其他数学领域的研究都是开创性的。1766年他又回到了圣彼得堡。欧拉小时候他就特别喜欢数学，不满10岁就开始自学《代数学》。这本书连他的几位老师都没读过。可小欧拉却读得津津有味，遇到不懂的地方，就用笔作个记号，事后再向别人请教。1720年，13岁的欧拉靠自己的努力考入了巴塞尔大学，得到当时最有名的数学家约翰·伯努利（JohannBernoulli，1667-1748年）的精心指导。这在当时是个奇迹，曾轰动了数学界。小欧拉是这所大学，也是整个瑞士大学校园里年龄最小的学生。欧拉在论文中给出了该问题的数学模型，用4个点代表4个被河隔开的陆地（两岸和岛屿），把桥表示为连接两个陆地之间的边，则得到图4.0.1所示的图，从而问题变为如何从图中的某个点出发，经过所有的边正好一次，最后回到这个点。在研究这个图的基础上，欧拉在论文中证明了该七桥问题无解，并且给出了一些规律性的理论。把实际问题抽象成点和边构成的图进行研究，标志着图论研究的开始。点边哥尼斯堡七桥问题与欧拉图:哥尼斯堡七桥问题就是要求在这个图中走一条欧拉回路，由于4个顶点都是奇度顶点，所以该问题无解。4.1图的基本概念4.1图的基本概念

4.1图的基本概念

图4.1.1无向图G说明

元素可以重复出现的集合称作多重集合。某元素重复出现的次数称作该元素的重复度。例如，在多重集合{a，a，b，b，b，b，c，c，c，d，e，e，e，e，e，e}中，a、b、c、d、e的重复度分别为2、4、3、1、6。从多重集合的角度考虑，无元素重复出现的集合是各元素重复度均为1的多重集。4.1图的基本概念

图4.1.2有向图D4.1图的基本概念与无向图和有向图的定义相关的概念和规定：（1）图（graph）：无向图和有向图统称作图，但有时也常把无向图简称作图。通常用G表示无向图，用D表示有向图，有时也用G泛指图（无向的和有向的）。用V(G)和E(G)分别表示无向图G的顶点集和边集，则|V(G)|和|E(G)|分别是G的顶点数和边数。用V(D)和E(D)分别表示有向图D的顶点集和边集，则|V(D)|和|E(D)|分别是有向图D的顶点数和边数。图4.1.1中|V(G)|=5和|E(G)|=7，图4.1.2中|V(D)|=4和|E(D)|=7。（2）阶（order）：图的顶点数称作图的阶。图4.1.1中图G的阶数为5，图4.1.2中图D的阶数为4。（3）n阶图（order-ngraph）：n个顶点的图称作n阶图。图4.1.1为5阶图，图4.1.2为4阶图。（4）(n，m)图：n个顶点，m条边的图，有时也称为(n，m)图。图4.1.1为(5，7)图，图4.1.2为(4，7)图。图4.1.1无向图G图4.1.2有向图D4.1图的基本概念图4.1.310阶零图N10图4.1.4零图应用举例（目标检测）（5）零图（nullgraph）：一条边也没有的图称作零图。n阶零图记作Nn。图4.1.3为10阶零图。图4.1.4为含有三种不同稀疏程度的点簇图，图中黑色像素点可以看做一系列顶点集，顶点与顶点之间没有边的连接，也可视为一种零图。（6）平凡图（trivialgraph）：1阶零图N1称作平凡图。平凡图只有一个顶点，没有边。(1，0)图是平凡图。（7）空图（emptygraph）：在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。4.1图的基本概念（8）标定图（labeledgraph）和非标定图（unlabeledgraph）：当用图形表示图时，如果给每一个顶点和每一条边指定一个符号（字母或数字，字母还可以带下标），称这样的图为标定图，否则称作非标定图。图4.1.5为标定图，图4.1.6为非标定图。图4.1.5标定图图4.1.6非标定图4.1图的基本概念（9）基图（basegraph）：将有向图的各条有向边改成无向边后得到的无向图，称作这个有向图的基图。图4.1.7所示有向图D的基图如图4.1.8所示。图4.1.7有向图D图4.1.8有向图D的基图

图4.1.5标定图基图环4.1图的基本概念

图4.1.7有向图D图4.1.5标定图孤立点孤立边4.1图的基本概念

图4.1.9赋权图（总权值数27）2权值4.1图的基本概念

图4.1.10无向图G4.1图的基本概念定义4.1.3

在无向图中，如果关联一对顶点的无向边多于1条，则称这些边为平行边（paralleledges），平行边的条数称作重数。在有向图中，如果关联一对顶点的有向边多于1条，并且这些边的始点与终点相同（也就是它们的方向相同），则称这些边为平行边。含平行边的图称作多重图（multigraph），既不含平行边也不含环的图称作简单图（simplegraph）。在图4.1.11中，e2和e3是平行边，e5和e8是平行边，e6和e1不是平行边。图4.1.11不是简单图，图4.1.10是简单图。图4.1.11有向图D（多重图）图4.1.10无向图G（简单图）平行边4.1图的基本概念

4.1图的基本概念图4.1.12中，d(v2)=4，d(v5)=6（环提供2度）。在图4.1.13中，d+(v2)=1，d-(v2)=2，d(v2)=1+2=3，v5为悬挂顶点，e2为悬挂边。图4.1.12无向图G图4.1.13有向图D

看成一个大顶点V1悬挂顶点悬挂边4.1图的基本概念定理4.1.1

握手定理（handshakingtheorem）

无向图G中，所有顶点的度数和等于边数的2倍。在图4.1.12中，共5个顶点、9条边，d(v1)=2，d(v2)=4，d(v3)=3，d(v4)=3，d(v5)=6，所有顶点的度数和等于18，正好是边数的2倍。定理4.1.2

有向图中，所有顶点的入度之和与所有顶点的出度之和都等于边数，且所有顶点的度数之和等于边数的2倍。在图4.1.13中，共5个顶点，8条边，所有顶点的出度之和与入度之和都等于8。推论

任何图（无向图或有向图）中，奇度顶点的个数是偶数。图4.1.12无向图G图4.1.13有向图D4.1图的基本概念

图4.1.12无向图G图4.1.13有向图D4.1图的基本概念

4.1图的基本概念图4.1.14分别示意了几种常见的无向完全图。图4.1.15为1阶、2阶、3阶有向完全图。图4.1.16为1阶、2阶、3阶、4阶竞赛图。图4.1.14无向完全图图4.1.15有向完全图图4.1.16竞赛图4.1图的基本概念

图4.1.175阶2-正则图图4.1.1810阶3-正则图4.1图的基本概念

图4.1.19二部图图4.1.20完全二部图K2,3图4.1.21完全二部图K3,34.1图的基本概念

在图4.1.22中，取V1={v1，v2，v3}，图(b)是图(a)的V1导出的子图。取E1={e1，e3}，图(c)是图(a)的E1导出的子图。图(e)和图(f)都为图(d)的子图，但图(f)是图(d)的导出的子图而图(e)不是，图(e)为图(d)的生成子图而图(f)不是。图4.1.22导出子图与生成子图(a)(b)(c)(d)(e)(f)4.1图的基本概念

(a)(b)(c)(d)图4.1.23

图及其补图4.1图的基本概念

4.1图的基本概念在图4.1.24中，设图(a)中图为G，则图(b)为G-e5，图(c)为G-{e1，e4}，图(d)为G-v5，图(e)为G-{v4，v5}，而图(f)为G\e5。图4.1.24删除边、删除顶点、边的收缩4.1图的基本概念图重点关注的是顶点与顶点的邻接关系，不在意顶点的位置和连线的形状。对于给定的图，图的表现形式可能不唯一。如果将图的顶点放置在不同的位置，边用不同形状的弧线或直线表示，则可以得到同一个图的不同形式的图形。因此，看起来完全不同的图形，可能表示着同一个图。为了描述看起来不同而其结构完全相同的图，引入同构的概念。如图4.1.25所示，虽然四个图形的形式各不相同，但它们表示同一个图。图4.1.25形式不同的图4.1图的基本概念

(a)(b)(c)图4.1.26图的同构（彼得松图）

4.2通路与回路4.2通路与回路

4.2通路与回路

4.2通路与回路如图4.2.1所示，在无向图G中，则有通路Γ(v1，v3)=(v1，e1，v1，e3，v4，e3，v1，e2，v2，e5，v4，e7，v3)，长度为6；回路Γ(v1，v1)=(v1，e1，v1，e3，v4，e3，v1，e2，v2，e4，v4，e3，v1)，长度为6；简单通路Γ(v1，v3)=(v1，e1，v1，e3，v4，e4，v2，e5，v4，e7，v3)，长度为5；简单回路Γ(v1，v1)=(v1，e1，v1，e3，v4，e4，v2，e2，v1)，长度为4；初级通路Γ(v1，v3)=(v1，e3，v4，e4，v2，e6，v3)，长度为3；初级回路Γ(v1，v1)=(v1，e3，v4，e7，v3，e6，v2，e2，v1)，长度为4，该回路是偶圈。然而，(v1，e4，v4，e6，v3，e2，v2，e3，v3)不是通路。图4.2.1无向图G4.2通路与回路如图4.2.2所示，在有向图D中，则有通路Γ(v1，v2)=(v1，e5，v3，e6，v4，e7，v1，e5，v3，e3，v2)，长度为5；回路Γ(v1，v1)=(v1，e5，v3，e6，v4，e7，v1，e5，v3，e4，v1)，长度为5；简单通路Γ(v1，v2)=(v1，e5，v3，e3，v2，e2，v2)，长度为3；简单回路Γ(v3，v3)=(v3，e3，v2，e2，v2，e1，v1，e5，v3)，长度为4；初级通路Γ(v1，v2)=(v1，e5，v3，e3，v2)，长度为2；初级回路Γ(v1，v1)=(v1，e5，v3，e3，v2，e1，v1)，长度为3，该回路是奇圈。图4.2.2有向图D4.2通路与回路

4.2通路与回路例4.2.1无向完全图K3（见图4.2.3）的顶点依次标定为v1、v2和v3。在定义意义下，K3中有多少个不同的圈（初级回路）？图4.2.3无向完全图解

同构意义下，K3中只有一个长度为3的圈（初级回路）。但在定义意义下，不同起点（或不同终点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同的长度都为3的圈：v1v2v3v1，v1v3v2v1，v2v1v3v2，v2v3v1v2，v3v1v2v3，v3v2v1v3。如果仅仅考虑起点（或终点）的差异，不考虑顺时针和逆时针的差异，有3种不同的圈，长度都是3：v1v2v3v1，v2v3v1v2，v3v1v2v3。4.3图的连通性4.3图的连通性

4.3图的连通性图4.3.1为连通图，图4.3.2为非连通图。图4.3.1连通图图4.3.2非连通图

4.3图的连通性图中两个顶点之间的通路可能不止一条，但是，总是存在长度最短的一条，即最短通路（最短路径）。

4.3图的连通性例4.3.1

（摆渡问题）一个人带着一条狗、一只羊和一筐蔬菜来到河的南岸。河边的小船一次只能载着人和他带的一样东西（狗、羊或菜）。而在人不在场的情况下，狗和羊，羊和菜不能放在一块，因为狗要咬羊，羊会吃菜。这个人怎样才能把他的三样东西安全地运到河对岸（北岸）？至少需要来回几次？解

用顶点表示可能的状况。例如，（人狗羊菜南，空北）表示人狗羊菜都在南岸，北岸什么也没有；（人羊南，狗菜北）表示人羊在南岸，狗菜在北岸。两个顶点之间有一条边当且仅当一次摆渡使表示的一种状态变成另一种状态，如图4.3.3所示。于是，从（人狗羊菜南，空北）到（空南，人狗羊菜北）的一条通路给出人把他的三样东西安全运到河对岸的一种方法，而这两点之间的距离是至少需要来回的次数。如图4.3.3所示，（人狗羊菜南，空北）（狗菜南，人羊北）（人狗菜南，羊北）（菜南，人狗羊北）（人羊菜南，狗北）（羊南，人狗菜北）（人羊南，狗菜）（空南，人狗羊菜北）是一条短程线（实线路径），距离为7。因此人至少要摆渡7次，7次摆渡过程如下：（1）带羊到北岸；（2）空手回到南岸；（3）带狗到北岸；（4）带羊回到南岸；（5）带菜到北岸；（6）空手回到南岸；（7）带羊到北岸。图4.3.3摆渡路径4.3图的连通性另一条短程线（含虚线路径）是（人狗菜羊南，空北）（狗菜南，人羊北）（人狗菜南，羊北）（狗南，人羊菜北）（人狗羊南，菜北）（羊南，人狗菜北）（人羊南，狗菜北）（空南，人狗羊菜北），摆渡方案与前面的不同，距离也是7次。（1）人带着羊到北岸；（2）人空手回到南岸；（3）人带着菜到北岸；（4）人带着羊回到南岸；（5）人带着狗到北岸；（6）人空手回到南岸；（7）人带羊到北岸。图4.3.3摆渡路径4.3图的连通性下面讨论无向图的连通程度。删除图中的顶点和边常常会影响图的连通性。例如，将连通图图4.3.4中的边e5删除，得到非连通图，如图4.3.5所示。图4.3.4连通图图4.3.5非连通图4.3图的连通性

图4.3.6无向图G图4.3.7无向图G删除{v1，v3}图4.3.8无向图G删除{v2}4.3图的连通性

图4.3.9无向图4.3图的连通性例4.3.2

在图4.3.10(a)中，顶点5、6、10是割点，顶点子集{1，4}是点割集，而顶点子集{1，9}、{7，8}、{4，5}、{1，3，4}不是点割集。边{5，6}是桥，边子集{(1，2)，(2，4)}、{(6，9)，(6，10)}、{(1，2)，(1，3)，(1，5)}是割集，而边子集{(3，4)，(4，5)}，{(1，3)，(1，5)，(4，5)}，{(6，10)，(9，10)，(10，11)}不是边割集。在图4.3.10(b)中，顶点3、4是割点，顶点子集{2，8}、{5，7}是点割集，而顶点子集{1，9}、{4，5}、{1，2，8}不是点割集。边{3，4}是桥，边子集{(2，3)，(3，8)}、{(4，5)，(4，7)}、{(1，2)，(2，9)，(2，8)，(3，8)}是边割集，而边子集{(3，4)，(4，5)}、{(2，3)，(2，8)，(3，8)}、{(1，2)，(2，8)，(1，8)}不是边割集。(a)(b)图4.3.10无向图的点割集、边割集、割点和割边4.3图的连通性

图4.3.9无向图4.3图的连通性

图4.3.9无向图4.3图的连通性

4.3图的连通性

4.3图的连通性

图4.3.11强连通图、单向连通图和弱连通图4.3图的连通性定理4.3.2

一个n阶简单有向图D=<V，E>是强连通图，当且仅当D中包含一条经过每个顶点有向回路。定理4.3.3

一个n阶简单有向图D=<V，E>是单向连通图，当且仅当D中包含一条经过每个顶点至少一次的通路。4.4图的矩阵表示4.4图的矩阵表示事物之间的联系可用图来表示，用图进行表示的优点是直观且形象。然而，当顶点和边比较多时，用图进行表示反而会显得混乱。此外，图不但可以用集合来定义，还可以用矩阵来表示。用矩阵表示图便于用代数方法研究图的性质，构造算法，也便于用计算机存储和处理图。为了用矩阵表示图，必须指定顶点或边的顺序，使其成为标定图，以确定矩阵元素和大小。本节主要讨论图的三种矩阵：关联矩阵、邻接矩阵和可达矩阵。关联矩阵描述的是点与边的邻接情况。邻接矩阵描述的是顶点与顶点之间的关系。可达矩阵描述的是图的连通情况。4.4图的矩阵表示

图4.4.1无向图G

v1v2v3v4v5e1e2e3e4e5e64.4图的矩阵表示

4.4图的矩阵表示

有向图D的关联矩阵M(D)有以下几个性质：（1）每列恰好有一个1和一个-1，说明每条有向边有一个起点和一个终点；（2）矩阵的所有元素和为0，即-1的个数等于1的个数，都等于边数m；（3）第i行中，1的个数等于顶点vi的出度d+(vi)，-1的个数等于顶点vi的入度d-(vi)；（4）平行边所对应的列相同。

图4.4.2所示的有向图D的关联矩阵为图4.4.2有向图D4.4图的矩阵表示

4.4图的矩阵表示图4.4.3所示的有向图D的邻接矩阵为：

图4.4.3有向图D4.4图的矩阵表示

图4.4.3有向图D4.4图的矩阵表示

图4.4.4无向图G

4.4图的矩阵表示

4.4图的矩阵表示

4.5欧拉图和哈密尔顿图4.5.1欧拉图欧拉图是一类非常重要的图，之所以如此，不仅是因为欧拉是图论的创始人，更重要的是欧拉图具有对边的“遍历性”。定义4.5.1

给定无孤立顶点的图G，通过图（无向图或有向图）中所有边一次且仅一次的通路称作欧拉通路（eulerpath）。通过图中所有边一次且仅一次的回路称作欧拉回路（eulercircuit）。具有欧拉回路的图称作欧拉图（eulergraph）。具有欧拉通路而无欧拉回路的图称作半欧拉图（semi

eulergraph）。显然，每个欧拉图必然是连通图。规定平凡图是欧拉图。欧拉通路是经过图中所有边的长度最短的通路，欧拉回路是经过图中所有边长度最短的回路。4.5.1欧拉图图4.5.1(a)为欧拉图，v1e1v2e2v3e3v4e4v1e5v1为图中的一条欧拉回路。图4.5.1(b)不是欧拉图，也不是半欧拉图，图中既没有欧拉回路，也没有欧拉通路。图4.5.1(c)为半欧拉图，v1e1v4e2v3e3v2e4v1e5为图中的一条欧拉通路，但图中不存在欧拉回路。图4.5.1欧拉图和半欧拉图图4.5.2(a)为欧拉图，v1v2v3v4v5v6v7v8v9v6v10v4v11v2v12v11v10v9v12v8v1为图中的一条欧拉回路。图4.5.2(b)为半欧拉图，v3v4v2v1v3v5v4为图中的一条欧拉通路，但图中不存在欧拉回路。图4.5.2欧拉图和半欧拉图（a）（b）（c）（a）（b）4.5.1欧拉图定理4.5.1

无向图G是欧拉图，当且仅当G是连通图且没有奇度顶点。根据定理4.5.1，图4.5.1中的3个无向图中，只有图(a)中无奇度顶点，因而图(a)是欧拉图，而图(b)、(c)都有奇度顶点，因而它们都不是欧拉图。第4章开头提到的哥尼斯堡七桥问题其实就是要求在图4.5.3(b)中走一条欧拉回路。1736年瑞士数学家欧拉在所发表的论文中证明了定理4.5.1，由于哥尼斯堡七桥问题所对应图中的4个顶点都是奇度顶点，故该问题无解。欧拉这篇论文被公认为是第一篇关于图论的论文。这也是欧拉回路和欧拉图名字的来源。图4.5.3哥尼斯堡七桥问题(a)(b)4.5.1欧拉图定理4.5.2无向图G是半欧拉图，当且仅当G是连通的且恰有两个奇度顶点，而且这两个奇点即是欧拉通路的起点和终点。根据定理4.5.2，图4.5.1(c)所示的是半欧拉图，但图4.5.1(b)所示的不是半欧拉图。例4.5.1

图4.5.4是一套平房的平面图，从前门进入客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在请你从前门进去，能否通过所有的门走遍所有的房间和客厅，最后从后门走出？(a)(b)解

将4个房间、一个客厅、前门外和后门外各对应成顶点，若两个顶点有边相连，就表示该两顶点所表示的位置有一扇门相通，如图4.5.4所示。由于图4.5.4(b)有4个顶点是奇度顶点，因此本题无解。图4.5.4房子平面图4.5.1欧拉图定理4.5.3

有向图D是欧拉图，当且仅当D是强连通的且每个顶点的入度等于出度。定理4.5.4

有向图D是半欧拉图，当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大，另一个顶点的出度比入度大1，而其余顶点的入度等于出度。定理4.5.5

G是非平凡的欧拉图，当且仅当G是连通的且是若干个边不重的圈的并集。图4.5.5(a)所示的为欧拉图，该图可以看成圈v7v8v6v7，v8v1v2v8，v2v3v4v2，v4v5v6v4的并集（见图4.5.5(b)），也可以看成圈v7v8v1v2v3v4v5v6v7和圈v8v2v4v6的并集（见图4.5.5(c)）。(a)(b)(c)图4.5.5欧拉图4.5.1欧拉图

4.6.1欧拉图例4.5.2

用Fleury算法从图4.5.6中找出一条欧拉通路。图4.5.6无向图解

图中奇度顶点是v1和v4，根据Fleury算法找出的一条欧拉通路如下：L=v1e1v1e2v1e4v3e5v4e8v2e3v5e6v4e7v5e10v1e9v44.6.2哈密尔顿图图论中还有一个看上去与欧拉图问题相似的问题，即哈密尔顿问题。欧拉图问题考虑边的遍历性，哈密尔顿图问题考虑点的遍历性。1859年，英国数学家哈密尔顿（Hamilton）提出一个问题，他用一个正十二面体的20个顶点代表世界上20个著名的大城市，要求沿着棱，从一个城市出发，经过每个城市仅一次，最后又回到出发点。这就是当时风靡一时的“周游世界”游戏，解决这个问题就是在如图4.5.7所示的图中寻找一条经过图中每个顶点恰好一次的回路。图4.5.7哈密尔顿图问题4.6.2哈密尔顿图定义4.6.2通过图（无向图或有向图）中所有顶点一次且仅一次的通路称作哈密尔顿通路。通过图中所有顶点一次且仅一次的回路称作哈密尔顿回路。具有哈密尔顿回路的图称作哈密尔顿图。具有哈密尔顿通路而无哈密尔顿回路的图称作半哈密尔顿图。规定平凡图是哈密尔顿图。哈密尔顿通路是经过图中所有顶点的长度最短的通路，哈密尔顿回路是经过图中所有顶点的通路中长度最短的回路。根据定义4.5.2，可直接得出下面结论：（1）每个哈密尔顿图都连通且每个顶点的度数均大于或等于2；（2）若一个图有哈密尔顿回路，则任何顶点所关联的边一定有两条在该哈密尔顿回路上；（3）若一个图有哈密尔顿回路，则该哈密尔顿回路上的部分边不可能组成一个未经过所有顶点的基本回路。判断一个图是否是哈密尔顿图，可以借助定义以及上面给出的3个结论，但这对顶点数较多的图来说不可行，因此有必要寻找其他方法，但可惜的是，尽管哈密尔顿图问题看起来与欧拉图问题类似，但它确实是一个至今尚未解决的难题。现在人们只是给出了一些充分条件和一些必要条件，有些结论的证明还比较复杂，至今还没有得到一个充分必要条件。4.5.3最短路问题、中国邮递员问题与货郎担问题

4.5.3最短路问题、中国邮递员问题与货郎担问题

4.6树4.6.1无向树及其性质定义4.6.1

连通无回路的无向图称作无向树，或简称树。每个连通分支都是树的无向图称作森林。平凡图称作平凡树。在无向树中，悬挂顶点称作树叶，度数大于或等于2的顶点称作分支点。说明

定义中的回路是指初级回路或简单回路。图4.6.1(a)~(d)都是树，其中图(c)是平凡树，它的顶点度数为0，而在任何非平凡树中，都无度数为0的顶点。图(e)所示的为森林。(a)(b)(c)(d)(e)图4.6.1无向树4.6.1无向树及其性质

4.6.1无向树及其性质

图4.6.2无向树

4.6.1无向树及其性质例4.6.2

饱和碳氢化合物的同分异构体。饱和碳氢化合物CnH2n+2由n个碳原子和2n+2个氢原子组成，碳原子是4价键，氢原子是1价键。当n=1，2，3，4时，各有多少种可能的饱和碳氢化合物。解

用4度顶点代表碳原子，1度顶点代表氢原子，表示CnH2n+2的图的度数列由n个4和2n+2个1组成。它有3n+2个顶点，度数之和等于4n+(2n+2)=2(3n+1)，因此是一颗树。当n=1，2，3时，都只有一棵非同构的树；当n=4时，有两棵不同构的树，如图4.6.3所示。这说明含有1个、2个和3个碳原子的饱和碳氢化合物都只有一种，而含有4个碳原子的饱和碳氢化合物可能有两种。事实上，分别含有1个、2个和3个碳原子的饱和碳氢化合物分别是甲烷、乙烷和丙烷，而含有4个碳原子的饱和碳氢化合物有两种同分异构体，分别是丁烷和异丁烷。图4.6.3饱和碳氢化合物4.6.1无向树及其性质例4.6.3

设T是一颗无向树，它有两个2度顶点，1个3度顶点，4个4度顶点，求T的叶数。解

设树T有x片树叶，则T的顶点数n=2+1+3+x=6+x，T的边数m=n-1=5+x。

根据握手定理有2m=2(5+x)=2×2+3×1+4×3+x

解得x=9，即树T有9片树叶。例4.6.4

设T是一颗无向树，它有7片树叶，3个3度顶点，剩下的都是4度顶点，则T有几个4度顶点？解

设树T有x个4度顶点，则根据握手定理有7×1+3×3+4x=2×(7+3+x-1)解得x=1，即树T有1个4度顶点。

4.6.2生成树

4.6.2生成树定理4.6.4

设T是图G的生成树，则（1）G的任何回路都至少包含T的一条弦；（2）若e为T的弦，则G中存在一条且只存在一条只含弦e，其余都是枝的初级回路，该回路称为弦e的初级回路。定理4.6.5

设T是图G的生成树，则（1）G的任一割集都至少含有T的一条枝；（2）若e为T的枝，则G中恰好存在一个只含枝e的割集，其余都是弦的割集，该割集称为枝e的基本割集。4.6.2生成树例4.6.5

图4.6.4(b)是图4.6.4(a)的一个生成树。（1）求此生成树的所有弦以及相应的基本回路。（2）求此生成树的枝(2，3)相应的基本割集。解

（1）图4.6.4(b)生成树的所有弦为(2，8)，(8，9)，(9，5)，(4，5)，(5，6)，(8，5)，(8，7)。它们对应的基本回路分别是：(1，2，8，1)，(8，9，3，2，1，8)，(9，5，7，1，2，3，9)，(4，5，7，1，2，3，9，4)，(5，6，1，7，5)，(8，5，7，1，8)，(1，8，7，1)。（2）去掉图4.6.4(b)生成树枝(2，3)，则该生成树就变成两个不连通的部分，其顶点集合分别为{3，9，4}和{1，2，8，7，5，6}。基本割集就是原图中连接这两组顶点的所有边的集合，即{(2，3)，(8，9)，(9，5)，(4，5)}(a)(b)图4.6.4连通图和它的生成树4.6.3根树定义4.6.3若有向图的基图是无向树，则称这个有向图为有向树。一个顶点的入度为0，其余顶点的入度为1的有向树称作根树。入度为0的顶点称作树根，入度为1、出度为0的顶点称作树叶，入度为1、出度不为0的顶点称作内点，内点和树根统称作分支点。从树根到任意顶点v的路径的长度（即路径中的边数）称作v的层数，所有顶点的最大层数称作树高。一颗根树，用图形表示，有树根在下（图4.6.5(a)）或树根在上（图4.6.5(b)）两种画法。然而，通常将树根画最上方，有向边的方向向下或斜下方，并省去各边上的箭头，如图4.6.5(c)所示。在图4.6.5(c)所示的根树中，有6片树叶、4个内点、5个分支点，树高为4，在树叶v5和v6处达到。图4.6.5根树(a)(b)(c)4.6.3根树

图4.6.5根树(a)(b)(c)4.6.3根树

4.6.3根树

图4.6.6中的T4是最优二叉树，Huffman（霍夫曼）算法是一种常用的求最优二叉树的算法。图4.6.6二叉树4.6.3根树

4.6.3根树例4.6.6

利用Huffma