计算机数学17PPT课件

1、基本要求、重点难点17.1 图的基本概念 17.2 无向图的连通性 17.4 无向图的矩阵表示 17.5 有向图的矩阵表示 17.3 有向图的连通性 17.6 欧拉图与哈密顿图 17.7 树 第1页/共58页基本要求 掌握图的基本概念； 掌握图的连通性； 掌握树的定义与应用。第2页/共58页重点难点重点：图的基本概念； 图的连通性； 树的定义与应用。 第3页/共58页17.1 图的基本概念 图是指一个离散集与其某些两元素子集的集合构作的一种数学结构，它的数学形象是，在纸上画几个(顶)点，再把其中一些点对用曲线段或直线段连接起来，如此形成的一维网络，其中点的位置与连线的曲直长短可以任意。图显示的

2、是点与点之间的二元关系。 哥尼斯堡七桥问题拉姆齐(Ramsey)问题第4页/共58页哥尼斯堡(Konigsberg)七桥问题 继续第5页/共58页著名数学家欧拉仔细研究了这个问题，他将上述四块陆地与七座桥的关系用一个抽象图形来描述(如图17.1.2)，其中四块陆地分别由四个点表示，而陆地之间有桥相联者则用连接两个点的弧边表示。 于是问题就变成：从图中任一点出发，通过每条边一次而返回原点的回路是否存在? 在此基础上，欧拉找到了存在这样一条回路的充要条件。由此推得哥尼斯堡七桥问题无解。欧拉的研究奠定了图论的基础。目前，他被公认为图论之父。 返回第6页/共58页拉姆齐(Ramsey)问题 可以用图形

3、来描述。用6个小圆点a，b，c，d，e，f 来表示任意六个人，若某两个人彼此认识，则相应的两点用实线连接，若两人彼此不认识，则在相应两点之间画一条虚线。因此，任两点之间若不存在实线，就必存在虚线，反之亦然。于是，在图论中此命题则为：六个点的图形中一定存在一个实三角形，或一定存在一个虚三角形。 继续第7页/共58页任取一点，比如a，显然在其余五点之中，存在三点与a用实线连接，或者，存在三点与a用虚线连接，并且，只存在一种可能。若a与三点用实线相联，比如b，c，d三点，如下图(a)所示。考察b，c，d 三点，若有两点用实线连接，比如b与c，则a，b，c构成一实线三角形。若b，c，d三点之间均用虚线

4、连接，则b，c，d已构成一虚线三角形。即b，c，d之间的任何一种情况都将导致出现实线三角形或虚线三角形。上图反之，若a对b，c，d均由虚线连接，如下图(b)所示，可用同样方法证明必然存在实线三角形或者虚线三角形。因此，原命题得证。 由以上例子可以看出，通过用图形来描述，问题就显得简洁多了。同时，所得结论更深刻，其应用更广泛.在这里，我们感兴趣的是图形中有哪些点以及点与点之间是否有线连接，而并不关心这些点具体代表什么，它们之间的连接方式如何。这种由点集和边集组成的整体称为一个图。返回第8页/共58页 17.1.2 图的基本概念 .定义17.1 图G是由非空结点集合V=v1，v2，vn以及边集合E

5、=l1，l2，lm两部分所组成，其中每条边可用一个结点对表示，即Li=(vi1，vi2)(i=1，2，m). 这样一个图G记为G=V，E。 图可以用图形来表示。结点也称顶点，或简称点，在图形中用一圆点表示。而边在图形中用线段或曲线段表示，所以也可称为弧。有时我们为了叙述方便，不区分图与其图形两个概念。具有n个结点，m个边所组成的图称为(n，m)图。第9页/共58页例17.1.3 有四个城市v1，v2，v3，v4。其中v1与v2间、v1与v4间、v2与v3间开办了民航客运业务。此事实用图的方法表示，则为G=V，E，其中V=v1，v2，v3，v4，E=(v1，v2)，(v1，v4)，(v2，v3)

6、。如下图(a)所示。 例17.1.4 有四个程序p1，p2，p3，p4。它们之间有一些调用关系：p1能调用p2；p2能调用p3；p2能调用p4；p3能调用p2。此事实用图的方法表示，则为D=V，E。其中V=p1，p2，p3，p4，E=(p1，p2)，(p2，p3)，(p2，p4)，(p3，p2)。如图17.1.4(b)所示。第10页/共58页 以上两例中，对于结点对的概念，可有两种不同的理解。例17.1.3中，两城市间的航空业务是双向的，也就是说(v1，v2)与(v2，v1)具有相同的含义，亦即结点对(v1，v2)与次序无关。这种结点对叫做无序结点对，它所对应的边称为无向边。但在例17.1.4

7、中，程序的调用关系则是单向的，比如p1能调用p2不能保证p2也一定能调用p1.此时(p1，p2)与(p2，p1)具有不同的含义，即结点对与次序有关。这种结点对叫做有序结点对，它所对应的边称为有向边。有向边可在边上加箭头用来表示边的方向，而无向边则边上不须加箭头。 利用图中边的有向与无向性可将图分成两种类型.即 有向图：图中的所有边均为有向边。 无向图：图中的所有边均为无向边。 例17.1.3、例17.1.4所给出的图分别为无向图与有向图。 在有向边lk=(vi，vj)中，vi称为lk的起点，vj称为lk的终点。而不管lk为有向边还是无向边，我们均称边lk与结点vi，vj相关联，称vi与vj为邻

8、接的。若干条边关联于同一个结点，则这些边称为邻接的。例如，在图17.1.4中，p1与p2分别为边(p1，p2)的起点与终点，结点p1，p2与有向边(p1，p2)相关联，结点v1，v2与边(v1，v2)相关联，结点v1与v2是邻接的，边(v1，v2)与边(v2，v3)是邻接的。第11页/共58页例17.1.5 一个图中某点不与任何边关联，称此点为孤立点。 图17.1.5 一个图可以没有边，所有点均为孤立点，这种图称为零图。图17.1.5(a)所示的图为4个结点的零图。 只有一个点也构成图，称为平凡图。它是点数最小的零图。 各点之间都有边相联的无向图是一种特殊图，叫做完全图。有n个点的完全图用Kn

9、表示。如图17.1.5(b)所示的图为K5。 容易证明，完全图Kn具有（1/2）n(n-1)条边。各点之间都有两条相向的边连接的有向图，也叫做完全图。它为有向完全图。图17.1.5(c)所示的图为3个结点的有向完全图。第12页/共58页定义17.2 图G=V，E与G=V，E间如果有V V及E E，则称G是G的子图。若G是G的子图，并且V=V，则称G为G的生成子图。若G=V，E是G的非空子图，并且边集E为二端点均在V中的边的全体所组成的集合，则称G为G的导出子图。 例17.1.6 图17.1.6中，图G与G均为G的子图，G为G的生成子图，G为G的导出子图。 图17.1.6 第13页/共58页定义

10、17.3 设G=V，E与G=V，E是两个图。若在V和V之间存在双射，使得(vi，vj)E当且仅当(vi)，(vj)E，其中vi，vjV，则称G与G是同构的图。 例17.1.7 图17.1.7中，图G=V，E与图H=P，L是同构的。其中V=1，2，3，4，5，P=a，b，c，d，e。 图17.1.7 第14页/共58页 在点集V与点集P之间可建立双射如下：(1)=a，(2)=c，(3)=e，(4)=b，(5)=d. 则满足如下性质：对任意(vi，vj)E，当且仅当(vi),(vj)L。 两个同构的图，除了图中各点的名字或符号不同外，本质上是一样的。可以把它们用完全相同的图形表示出来，因此，今后我

11、们主要研究不同构的图。第15页/共58页 17.1.3 图中结点的度数 定义17.4 在有向图中，以结点v为起点的边的条数叫v的出度，记为 (v)。以v为终点的边的条数叫v的入度，记为 (v)。v的入度与出度之和称为v的度数，记为deg(v)。在无向图中，结点v的度数就是与v相关联的边的条数，它也用deg(v)表示。 零图中各点度数均为0。完全图Kn各点的度数均为n-1。 在图中，每条边必与两个结点相关联，这就导致图中所有结点的度数之和为偶数，且必为图中边数的两倍，故我们有下面的定理。 定理17.1 设图G=V，E为(n，m)图。则有 换句话说，有限图G的各点度数总和是边数的两倍。第16页/共

12、58页推论：一个图中度数为奇数的点的个数为偶数。 定理17.2 在有向图中，各结点出度之和等于各结点入度之和。 例17.1.8 图G=V，E为(n，m)图，、分别是 G 中点的最小度与最大度，即 第17页/共58页 17.1.4 多重图与带权图 在实际问题中，有时会遇到与图的定义不完全相同的特殊的图，在这里，我们作简单介绍。若一个边连接同一个点，我们将其称为圈，允许有圈的图称为带圈图。 在无向图中，若两个或两个以上的边连接同一对点，我们将其称为平行边。在有向图中，若两个或两个以上方向相同的有向边连接同一对点，我们亦将其称为平行边。允许有平行边的图称为多重图。例如，在哥尼斯堡七桥问题中的图就为多

13、重图。 既不包含圈，又不包含平行边的图，叫做简单图。在以后的讨论中，不特别指出的话，我们讨论的图均指简单图。 有时，在一个图中边的旁侧附加一些数字以刻画此边的某些数量特征，这些数字叫做边的权。根据实际问题的需加，可以赋予权不同的含义，它可以表示距离、费用、时间等。而具有有权边的图叫做带权图。第18页/共58页研究图的性质，最重要一点，就是其连通性。 17.2 无向图的连通性 定义17.5 在无向图G=V，E中，设li是关联于结点vi-1和vi的边，交替序列v0l1vil2lnvn称为连接v0到vn点的一条通道。通道可简记为(vn，v1，vn)。通道中边的个数称为通道的长。若v0=vn，称之为闭

14、通道。 直观地说，通道就是通过相连的若干条边从一点到达另一点的路线。通道上的点、边均可以重复出现。定义17.6 无重复边的通道称为迹。无重复边的闭通道则称为闭迹。 第19页/共58页定义17.7 无重复点的通道称为路。若一条长为n的闭通道上n个点各不相同，且n3，则称之为一条回路。 如果长为n的通道上n+1个点各不相同，则相应的n条边也必然各不相同，因此，路一定是迹。相反地，长为n的通道上n条边各不相同时，却仍可能有重复点出现，因此迹不一定是路。同样，闭迹不一定是回路，而回路则一定是闭迹。例 17.2.1 图17.2.1中，(1，2，3，4，5，1，2)为一条长为6的通道，但不是迹，当然也不是

15、路；(1，2，4，1，2，4，1)为一条长为6的闭通道，但不是闭迹，当然也不是回路；(1，2，3，4，2)为一条长为4的迹，但不是路；这样一通道(1，5，4，3，2，4，1)为一条长为6的闭迹，但不是回路；(1，2，3，4)为长为3的路；(1，2，3，4，1)为长为4的回路。 (1，2，1)为长为2的闭通道，尽管两点不同，两条边却相同，它不构成回路，也不是闭迹。 图17.2.1 第20页/共58页例17.2.2 证明：一条通道不是路，当且仅当此通道中有一子序列构成一条闭通道。 证 “必要性” 若(vi1，vin)不是路，则在vij(j=1，n)中必存在某两点相同，设为vik，vim。(vi1，

16、vin)的子序列(vik，vim)，由于vik=vim，可得此子序列为一条闭通道。 “充分性” 若(vi1，vin)中有一子序列构成闭通道，设其为(vik，vim)，其中vik=vim。 所以，(vi1，vin)中有重复的点，因此不是路。原命题得证。证毕。 第21页/共58页定理17.3 在一个具有n个结点的图中，任一条路的长度均不大于n-1，任一回路的长度均不大于n. 第22页/共58页17.2.2 连通性 定义17.8 G=V，E是一无向图。u，vV，uv，若G中存在从u至v的通道，则称u与v是可达的。否则，称u，v不可达。并定义图中任一点与其自身是可达的。 定义17.9 G=V，E是一无

17、向图，u，vV，若u，v是可达的，称u与v连通。若图中任两点连通，则G称为连通图。否则G称为非连通图。 第23页/共58页 如果我们将结点的连通视为图中点集上的一个关系，由定义显然可以得到此关系满足自反性、对称性和传递性，即连通关系是等价关系。此等价关系必然惟一地将v划分成k(k1)个等价类，记为V1，V2，V3，Vk。由它们导出的导出子图(V1，E1)，(V2，E2)，(Vk，Ek)称为G的连通分图。连通分图是连通图。一个连通分图中的任一点与其他连通分图中的点不连通。连通图的连通分图只有一个，就是它本身。 例17.2.4 图17.2.2(a)所示，G为连通图。 图17.2.2(b)所示，G为

18、非连通图。G有两个连通分图，它们分别是由V1=10，9，1，2，6，5和V2=4，3，7，8，11导出的子图。 第24页/共58页定义17.10 在连通无向图G中： (1) 如果去掉一个结点v及与v关联的边，图将不连通，则称结点v为图的割点或关节点； (2) 如果去掉一条边，图将不连通，则称这条边为图的割边或桥； (3) 若S为图G中若干边的非空集合，图G去掉S 则不连通，而去掉S 的任一真子集仍连通，则称S为图G的一个割集。即割集S是G的最少边的集合，除去它将使G分割为两个连通子图。 例17.2.6 考虑七个城市的交通。由于种种原因，这七个城市有的可直达，有的不能直达。如图17.2.3所示，

19、点a，b，c，d，e，f，g代表城市，边代表两城市之间可直达。图17.2.3显然，此图为连通图，即任两点是可达的，也就是说，七个城市中任两城市均可通过交通联系。但此交通系统是不理想的，因为它的连通程度并不高，一旦某些环节出了问题，系统就会中断。比如，城市a，b任一城市交通堵塞或被破坏，或者，ab之间交通堵塞或被破坏，整个交通系统将会中断。可见，点a，b，边(a，b)对于图17.2.3的连通性具有特殊意义，我们称之为割点及桥。 第25页/共58页 在图17.2.3所示图中，有两个割点：a、b。一条边是桥：(a，b)。割集有(a，b)，(a，d)，(a，e)，(a，d)，(d，e)，(a，e)，(

20、e，d)，(b，c)，(b，f )，(b，g)，(b，c)，(c，g)，(b，f)，(f，g)，(c，g)，(b，g)，(f，g)。其他边集则不是割集，比如：(a，b)，(a，d)，(b，c)，(b，f )等。 第26页/共58页定义17.11 图G为一无向连通图： (1) 图G的点连通度(G)，是为了由G产生一个不连通图或平凡图，而需从G中去掉的最少的点数； (2) 图G的边连通度(G)，是为了由G产生一个不连通图或平凡图，而需从G中去掉的最少的边数。 定理17.4 无向图G中，(G)为点连通度，(G)为边连通度，(G)为最小度，则(G)(G)(G)。第27页/共58页17.3 有向图的连通

21、性 无向图中无长为2的回路，有向图中却可能有长为2的有向回路。这是因为，无向图中，两个不同点之间只能有一条边，而有向图中两不同点之间可以有一对相向的边。 定义17.12 有向图D中一个点、有向边交替的序列：v0，(v0，v1)，v1，(v1，v2)，vn称为一条长为n的有向通道，记为(v0，v1，vn)。有向闭通道、有向迹、有向闭迹和有向路可类似定义。有向回路是无重复出现的点的有向闭通道。 第28页/共58页 有向通道是有方向性的，所以在有向图中，u可达v时，不一定有v可达u。即使u可达v且v可达u，从u到v的有向通道与从v到u的有向通道也是不同的。对于有向图，由于其边有方向性，可达关系不一定

22、是对称的。因此有向图的连通性比无向图的连通性包含了更多的内容。 定义17.13 在有向图D中，若存在从点u到点v的有向通道，则称点u可达点v。 第29页/共58页 例 17.3.1 图17.3.1中有八个结点数为3的有向图。其中(a) 中是两个非连通图；(b) 中是两个弱连通图；(c) 中是两个单向连通图；(d) 中是两个强连通图。 定义17.14 一个有向图D=V，E，若忽略其边的方向后，得到的无向图是连通的，则称D是弱连通的。否则称D为非连通的。若D中任意两点u，v都有从u可达v、或从v可达u，则称D 是单向连通的；若D 中每一点u均可达其他任一点v，则称D是强连通的。 很显然，在有向图中

23、，强连通图是单向连通的，也是弱连通的。同样，一个单向连通图必是弱连通的。但反之则不然，弱连通图不一定是单向连通的或强连通的，单向连通图也不一定是强连通的。 第30页/共58页定义17.15 在有向图D中，具有极大强连通的子图，称为D的一个强分图；具有极大单向连通性的子图，称为D的一个单向分图；具有极大弱连通性的子图，称为D的一个弱分图。强分图的定义中，“极大”的含义是：对该子图再加入其他结点，它便不再具有强连通性。对单向分图、弱分图也类似。 例17.3.2 图17.3.2中，点集c，f，g，d，h的导出子图为强分图。a，b，e的导出子图仅为单向分图。弱分图只有一个就是图自身。 第31页/共58

24、页定理17.5 有向图D是强连通的，当且仅当D中存在一条包含D中所有点的有向闭通道。证 (1) “充分性”D中有一条包含了D中所有点的有向闭通道，则D中任一点u沿此通道前进，可达其他任一点v，因此D是强连通的。(2) “必要性”若D是强连通的，从D中任一点v1出发，可达其他点v2，再从v2可达v3，至最后一点vn，最后从vn可达v1，这就是一条包含了所有点的有向闭通道。故，定理得证。证毕.定理17.6 有向图D中，它的每个结点位于且只位于一个强连通分图中。 第32页/共58页17.4 无向图的矩阵表示 定义17.16 设无向图G=V，E的结点集V=v1，v2，vn.若n阶方阵A(G)=(aij

25、)n满足条件： 则称A(G)为图G的点邻接矩阵，简称邻接矩阵。 邻接矩阵可以完全描述一个图。给定一个邻接矩阵，就能够确定一个图。由于无向图中，点的邻接关系是对称的，邻接矩阵一定是对称阵。我们所研究的图为简单图，所以邻接矩阵主对角线上元素全为0。无向图的邻接矩阵中，行元素之和等于相应点的度。通过以下例题我们可以明显看出，邻接矩阵的这些特点。 第33页/共58页定理17.7 若A(G)是无向图G的邻接矩阵，Y=(A(G)k(kN)，则Y中元素yij表示从结点vi到结点vj的长为k的通道的数目。 定义：17.17 G=V，E为无向图，V=v1，v2，vn，E=l1，l2，ln。若nm的矩阵M(G)=

26、(bij)nm满足 则矩阵M(G)称为图G的点边关联矩阵，简称关联矩阵。 关联矩阵也可以完全描述一个图。关联矩阵中的每一行对应图中的一个点，每一列对应图中的一条边。每行元素之和为相应点的度，每列则恰有两个非0元素。第34页/共58页17. 5 有向图的矩阵表示 定义：17.18 D=V，E是有向图，V=v1，v2，vn，若n阶方阵A(D)=(aij) n满足 则称A(D)为D的邻接矩阵。 与无向图的邻接矩阵相同，有向图的邻接矩阵完全描述了一个有向图。由于有向图中边为有向边，故其邻接矩阵不一定是对称阵，只有两点间的边均成对出现，矩阵才是对称的。D的邻接矩阵A(D)中每一行元素之和，表示相应点的出

27、度，每一列元素的和表示相应点的入度。只有当第i行、i 列元素全为0时，所对应点vi不与任何边关联，即孤立点。第35页/共58页 例17.5.1 有向图D=V，E的关联矩阵为 则有向图的图形可见图17.5.1。 与无向图的邻接矩阵类似，我们也可通过有向图的邻接矩阵来研究有向图中两点之间通道的数量。第36页/共58页定理17.8 若A(D)是有向图D=V，E的邻接矩阵，Y=(A(D)k，(kN)，则Y中元素yij表示从点vi至点vj的长为k的有向通道的数目。 例 17.5.1 中的有向图D=V，E的邻接矩阵为A(D)， 由此可见，从v1至v3的长度为2的通道有一条，从v3至v1的长度为3的通道有2

28、条，通过v3点长度为4的闭通道有2条。 第37页/共58页定义：17.19 D=V，E是有向图，V=v1，v2，vn，E=l1，l2，lm。若nm矩阵M(D)=(bij)nm满足 则称M(D)为D的关联矩阵。 在有向图的关联矩阵中，非0元的值可以是1或-1。因为每列对应一条有向边，所以每列恰有两个非零元1和-1。每行对应一个点，所以每行元素的绝对值之和为对应点的度数，1的个数为出度，-1的个数为入度。矩阵的所有元素的代数和为0，1的个数等于-1的个数等于有向图的边数。这些特征均可在如下例题中看出。 第38页/共58页定义：17.20 若D=V，E为有向图，V=v1，v2，vn。若n阶方阵P(D

29、)=(cij)n满足 则称P(D)为D的可达性矩阵。 根据图的图形写出图的可达性矩阵并不是我们的目的，因为它仍然脱离不开对图形的依赖性。下面介绍一种求可达性矩阵的算法.我们先来定义一种特殊的运算：布尔运算。 若a，bN，则定义： 第39页/共58页 17.6 欧拉图与哈密顿图 17.6.1 欧拉图定义：17.21 在一个无向图中(也可以是无向多重图)，包含了所有边的一条迹称为欧拉迹，包含了所有边的闭迹称为欧拉闭迹.具有欧拉闭迹的图称为欧拉图。 定理：17.9 非平凡无向图G据有一条欧拉迹，当且仅当G是连通的，且有零个或两个奇度数结点。若有两个奇度数结点，它们是G中每条欧拉迹的端点。推论 非平凡

30、无向图为欧拉图，当且仅当G连通，且所有结点度数均为偶数。 这个定理给出了判别欧拉图的一个非常简单有效的方法。利用这个方法可以马上看出哥尼斯堡七桥问题是无解的。因为哥尼斯堡七桥所对应的图，其每个结点的度数均为奇数。欧拉迹问题是一个实用性很强的问题。第40页/共58页第41页/共58页 例17.6.3 判定图17.6.3中的四个图形是否可以一笔画。 解 图17.6.3(a)中，1，5 两点为奇度数点，其余点均为偶度数点.故以1 开始起存在一笔画路线至5结束。比如(1，2，4，5，6，3，1，5，2，3，5). 图17.6.3(b)中有欧拉迹。图17.6.3(c)(d)均为欧拉图。所以，均可以一笔画

31、。第42页/共58页定义：17.22 在一个有向图中，包含了所有有向边的一条有向迹称为此有向图的欧拉迹。包含了所有有向边的有向闭迹称为有向图的欧拉闭迹.具有欧拉闭迹的有向图为有向欧拉图。 定理：17.10 一个有向图D具有欧拉迹，当且仅当D是连通的，且除两个结点外，其余结点入度等于出度，这两个例外结点中，一个入度比出度大1，另一个入度比出度小1。 推论 一个有向图为欧拉图，当且仅当D是连通的，且所有结点入度等于出度。第43页/共58页 17.6.2 哈密顿(Hamilton)图 哈密顿问题，起源于一种游戏，它是由英国数学家哈密顿于1859年提出，这个曾风靡一时的游戏名叫周游世界游戏。这个游戏的

32、内容就是，用一个正十二面体的20个顶点代表世界上20个著名的大城市(如图17.6.5(a)。游玩的人沿正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。 如果我们以正十二面体顶点作为点，相应的棱作为边，就可以得到平面上的一个图(如图17.6.5(b)。可知游戏要寻找的是一条通过图中每个结点一次的回路。此回路有若干个，称为哈密顿回路。一般我们在无向图中研究哈密顿图问题。 第44页/共58页注意 欧拉图与哈密顿图研究目的不同，前者要遍历图的所有边，后者要遍历图的所有点。虽然都是遍历问题，两者的困难程度却大不相同。我们已较满意地解决了欧拉图问题，而哈密顿问题却是一个至今尚未解决的

33、难题。在大多数情况下，人们还是采用尝试的方法来解决。 定义：17.23 通过图G中每结点一次的通道定为路，此路称为哈密顿路。通过图G中每结点一次的闭通道为回路，此回路称为哈密顿回路。具有哈密顿回路的图叫哈密顿图。设G中有n个点，则G 的哈密顿路有n-1条边，G的哈密顿回路有n条边。 第45页/共58页 例17.6.5 有9个学生打算几天都在一个圆桌上共进晚餐，并且希望每次晚餐时，每个学生两边邻座的人都不相同，按照这样一种要求，他们在一起共进晚餐最多几天? 。 第46页/共58页解 以9个学生为结点，两人相邻而坐，就可看作两点之间有边相联。因此，相邻就座的所有可能合在一起，就是9个结点的完全图K

34、9，而K9任意一个哈密顿回路，就表示一次晚餐的就座方式。两个哈密顿回路只要没有公共边，就表示对应的两次晚餐的就座中，每个人相邻就座者都不相同。由于K9共有 条边，在K9中每条哈密顿回路的长度为9。则没有公共边的哈密顿回路数目至多有36/9=4条。9人的坐法，只由他们之间的相邻关系决定。排成圆形时，仅与排列顺序有关。因此对各种坐法，可认为一人的座位不变，我们可将其设作1号，并不妨放于圆心，其余8人可均匀地放在圆周上(如图17.6.6所示)。于是不同的哈密顿回路，可由圆周上不同编号的旋转而得到。 如果9个人标号为1，2，9，则四天中排列情况如下：1 2 3 9 4 8 5 7 6 1；1 3 4

35、2 5 9 6 8 7 1；1 4 5 3 6 2 7 9 8 1；1 5 6 4 7 3 8 2 9 1。 故他们在一起共进晚餐最多4天。第47页/共58页 例17.6.6 图17.6.7中，(a)图有哈密顿路，亦有哈密顿回路。比如：(a，b，c，d，e)为哈密顿路，(a，c，e，b，d，a)为哈密顿回路，此图为哈密顿图。 图(b)若有哈密顿回路，则此回路必通过与1，3，5，7点关联的边，而这些边已构成回路，但9，10点不在回路中，所以此图没有哈密顿回路。事实上，此图也无哈密顿路。图(c)有哈密顿路，没有哈密顿回路。这是因为若此图有哈密顿回路，则此回路必通过边(a，c)，(a，b)；(f，g

36、)，(c，g)；(d，e)，(e，c)。于是回路中，通过c点有三条边，这不可能，所以图(c)无哈密顿回路。第48页/共58页17.7 树 17.7.1 无向树 定义：17.24 不包含回路的连通无向图称为无向树，简称树。每个连通分图都是树的非连通图称为林。 例17.7.1 在图17.7.1中，(a)图是树，因为它连通又不包含回路。而(b)，(c)图均不是树。图(b)虽连通但有回路，图(c)虽无回路，但不连通。 在树中，度数为1的结点称为树叶，度数大于1的结点称为分支点。如图17.7.1(a)中，v1，v4，v5点为树叶，v2，v3点为分支点。 平凡图(n=1)为树，称为平凡树。 第49页/共5

37、8页定理：17.11 在(n，m)树中必有n=m+1。证 用数学归纳法对n进行归纳。n=1时，定理成立。设对所有i(in)定理成立，需求证n时有n=m+1。设有一(n，m)树G，因为G不包含任何回路，所以G中删去一边后就变成两个互不连通的子图，每个子图是连通的且无回路，所以每个子图均为树，设它们分别为(n1，m1)树及(n2，m2)树。由于n1n，n2n，由归纳假设可得：n1=m1+1，n2=m2+1。又因为n=n1+n2，m=m1+m2+1。故我们得到 n=m+1，原命题得证。证毕.第50页/共58页定理：17.11若无向图G为(n，m)图，则下述命题等价： (1) G是树； (2) G中任意两点间有惟一一条路； (3) G连通，且去掉一条边则不连通； (4) G连通，且n=m+1； (5) G中无回路，且n=m+1； (6) G中无回路，且若在任意两不相邻结点间增加一条边，则恰有一条回路； (7) G连通，且当n3时不是