1、2022年年3月月27日日 裘国永裘国永离散数学离散数学第十章 图陕西师范大学计算机科学学院 本章内容及教学要点本章内容及教学要点10.1 图的基本概念教学内容：结点（顶点），边，无向边， 有向边（弧），环（自回路）， 孤立结点，有向图，无向图， 度数，出（入）度， 欧拉握手定理陕西师范大学计算机科学学院 10.2 路、回路与连通性教学内容：路（通路），回路（圈）， 简单（回）路，基本（回）路， 连通图，连通分支，点（边）割集， 割（边），强（单向，弱）连通图， 强（单向，弱）分图陕西师范大学计算机科学学院 10.4 欧拉图与哈密顿图 教学内容：欧拉（回）路，欧拉图， 哈密顿（回）路，哈密顿图
2、陕西师范大学计算机科学学院10.6 平面图教学内容：平面图，面，边界，欧拉公式陕西师范大学计算机科学学院10.7 树及其应用教学内容：树，树叶，分支点，生成树， 最小生成树，Kruskal算法， Prim算法，根树，有序树， 二叉树，树的遍历， 最优二叉树， Haffman算法陕西师范大学计算机科学学院10.9 最短路径教学内容：最短路径，Dijkstra算法陕西师范大学计算机科学学院 图论是以图为研究对象的一个数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。陕西师范大学计算机
3、科学学院 在自然界和人类社会中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。陕西师范大学计算机科学学院 另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系（芯片设计）等等。陕西师范大学计算机科学学院 任何一个包含某种二元关系的系统都可以用图形来表示。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学
4、抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。图是计算机中数据表示、存储和运算的基础。陕西师范大学计算机科学学院 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家欧拉于1736年解决的哥尼斯堡七桥问题。陕西师范大学计算机科学学院 东普鲁士的哥尼斯堡城（今俄罗斯的加里宁格勒）位于普雷格尔（Pregel）河的两岸，河中有一个岛，于是城市被这条河、它的分支和岛分成了四个部分，各部分通过7座桥彼此相通。该城的居民喜欢在周日绕城散步。于是就产生了这
5、样一个问题：能不能设计一条散步的路线，使得一个人从家里（或从四部分陆地任一块）出发，经过每座桥恰好一次再回到家里？这就是有名的哥尼斯堡七桥问题。陕西师范大学计算机科学学院 哥尼斯堡七桥问题看起来并不复杂，因此立刻吸引许多人的注意，但是实际上很难解决。 瑞士数学家欧拉注意到了这个问题，并在1736年写的有关“哥尼斯堡七桥问题”的论文中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，欧拉也因此被誉为图论之父。陕西师范大学计算机科学学院陕西师范大学计算机科学学院 欧拉是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线。则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点
6、出发，通过每边一次且仅一次返回原出发点的路线（回路）是否存在？欧拉证明这样的回路是不存在的。 陕西师范大学计算机科学学院 第二阶段是从19世纪中叶到1936年。一开始，图论的理论价值似乎不大，因为图论主要研究一些娱乐性的游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。但是随着一些图论中的著名问题如四色问题（1852年）和哈密顿环游世界问题（1856年）的出现，出现了以图为工具去解决其它领域中一些问题的成果。 陕西师范大学计算机科学学院 1847年德国的克希霍夫将树的概念和理论应用于电网络研究。1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物分子结构即CnH2n+2的同分异构
7、物数目的研究中。 1936年匈牙利的数学家哥尼格写出了第一本图论专著有限图与无限图的理论，标志着图论成为一门独立学科。 陕西师范大学计算机科学学院 第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是计算机的大量应用，使大规模问题的求解成为可能。陕西师范大学计算机科学学院 电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。10.1
8、 图的基本概念陕西师范大学计算机科学学院 这一节的主要内容：这一节的主要内容： 无（有）向边、环、孤立结点、无（有）向图、混合图、基图、简单图、多重图、平凡平凡图、图、零图、完全图、加权图、度数、出度、入度、欧拉握手定理。陕西师范大学计算机科学学院定义10.1.1 一个图G定义为一个有序对，记为G=。其中V为非空有限集，其元素称为结点或顶点（Vertex, Node），E也是有限集，其元素称为边（Edge）。对E中的每条边都有V中的两个结点与之对应，其结点对可以有序也可无序。陕西师范大学计算机科学学院 若边e与无序结点对u, v对应，称e为无向边（Undirected edge），简称边，记为
9、e=u, v，u、v称为边e的端点，也称u和v为邻接点，边e关联u与v。关联同一结点的两条边称为邻接边。连接一结点与它自身的边称为环或自回路（Loop）。两条端点对应相同的边称为平行边。陕西师范大学计算机科学学院 若边e与有序结点对对应，称e为有向边或弧（Directed edge），记为e=，u和v分别称为弧e的始点（Initial vertex）和终点（Terminal vertex），也称u邻接到v，v邻接于u。若e和e 有相同始点，称e和e 相邻。始点和终点都对应相同的弧称为平行弧。陕西师范大学计算机科学学院 在图中不是任何边的端点的结点称为孤立结点（Isolated vertex）。
10、 每条边都是无向边的图称为无向图（Graph）。每条边都是有向边的图称为有向图（Digraph）。既有有向边又有无向边的图称为混合图。将有向图各有向边去掉方向后 得 到 的 无 向 图 称 为 原 图 的 基 图 （Underlying graph）。陕西师范大学计算机科学学院例10.1.1 图10-1的两个图分别为无向图和有向图。在（a）中，e7是环，e1、e2与e3是邻接边。在（b）中，v2v1与v2v3是邻接边，但v2v3和v3v2不是邻接边，v5为孤立结点。陕西师范大学计算机科学学院定义10.1.2（1）含有平行边（或弧）的图称为多重图（Multigraph）。不含平行边（或弧）和环的
11、图称为简单图（Simple Graph）。（2）具有n个结点和m条边的图称为(n, m)图，也称n阶图。一个(n, 0)图称为零图，(1, 0)图称为平凡图。陕西师范大学计算机科学学院（3）任两结点之间都有边（或弧）的简单图称为完全图（Complete graph）。 n个结点的无向完全图记为Kn。陕西师范大学计算机科学学院例10.1.2 在图10-2中，（a）是简单图且为完全图，但（b）是多重图，因为e4和e5是平行弧。陕西师范大学计算机科学学院定理10.1.1 完全图Kn的边数为C(n, 2)。陕西师范大学计算机科学学院证明： 因为在完全图Kn中任意两结点之间都有边相连，且n个结点中任取两
12、点的组合数为C(n, 2)，故完全图Kn的边数为C(n, 2)。陕西师范大学计算机科学学院定义10.1.3 给每条边（或弧）都赋予权的图G=称为带权图或加权图（Weighted graph），记为G=，W为各边（或弧）权的集合。陕西师范大学计算机科学学院定义10.1.4 设G=、G =是两个图。（1）若VV且EE，则称G 为G的子图（S u b g r a p h ） ， G 为 G 的 母 图 （Supergraph）。陕西师范大学计算机科学学院（2）若G 是G的子图，且VV或EE，则称G 为G的真子图（Proper subgraph）。（3）若V =V且EE，则称G 为G的生成子图或支撑子
13、图（Spanning graph）。陕西师范大学计算机科学学院定义10.1.5 G=，V1 V且V1，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称为V1的诱导子图；E1 E且E1，以E1为边集，以E1中边关联的结点的全体为结点集的G的子图，称为E1的诱导子图。陕西师范大学计算机科学学院定义10.1.6 若G=是一个n阶无向简单图，从Kn中删去G的所有边而得到的图称为G的补图或G的相对于完全图的补图，记为 。陕西师范大学计算机科学学院例10.1.3 在图10-3中，（b）、（c）、（d）都是（a）的子图，也是真子图。（b）和（c）是（a）的生成子图。（d）既是结点集v2, v3
14、, v4的诱导子图，也是边集v2, v3，v2, v4，v3, v4的诱导子图。（b）和（c）互为补图。陕西师范大学计算机科学学院定义10.1.7 在有向图G=中，对于结点vV，以v为始点的弧的条数称为v的出度（Outdegree），记为d+(v)；以v为终点的弧的条数称为v的入度（Indegree），记为d-(v)；v的出度和入度之和称为v的度数（Degree），记为d(v)。陕西师范大学计算机科学学院 在无向图G=中，结点v的度数等于它关联的边数，记为d(v)。若v有环，规定该结点度数因环而增加2。陕西师范大学计算机科学学院例10.1.4 在图10-1（a）中，d(v1)=3，d(v2)=
15、5，在图10-1（b）中，d+(v2)=2，d-(v2)=1。陕西师范大学计算机科学学院定理10.1.2（握手定理） 在图G=中，结点度数的总和等于边数的两倍，即 2|E|= 。Vvdv)(陕西师范大学计算机科学学院证明： 因为图G中的每条边（包括环）都有两个端点，所以加上一条边就使各结点度数总和增加2，因此图G中结点度数的总和等于边数的两倍，即 =2|E|。Vvdv)(陕西师范大学计算机科学学院推论 图中度数为奇数的结点必为偶数个。陕西师范大学计算机科学学院定理10.1.3 在任何有向图中，所有结点的入度之和等于所有结点的出度之和。陕西师范大学计算机科学学院证明： 因为每一条有向边必对应一个
16、入度和一个出度，若某个结点具有一个入度或出度，则必关联一条有向边，所以有向图中各结点入度之和等于边数，各结点出度之和等于边数，故结论成立。陕西师范大学计算机科学学院定义10.1.8 无向图中度数为1的结点称为悬挂结点，它对应的边称为悬挂边。各结点度数均相同的图称为正则图。各结点度数均为k的图称为k度正则图。陕西师范大学计算机科学学院定理10.1.4 设G为任意n阶无向简单图，则每个结点的度数都不超过n-1。陕西师范大学计算机科学学院证明： 因G无平行边也无环，所以G中任意结点v至多与其余n-1个结点相邻，于是d(v)n-1。陕西师范大学计算机科学学院定义10.1.9 对无向图（或有向图）G1=
17、和G2=，若有双射f：V1V2，使得对任意u、vV1，有u, vE1 f(u), f(v)E2(或E1 E2)，且其重数相同，则称G1同构于G2，记为G1 G2。若G与其补图同构，称G为自补图。陕西师范大学计算机科学学院例10.1.5 在图10-5中，(a)和(b)是同构的。因为可作映射g，使得g(1)=v3，g(2)=v1，g(3)=v4，g(4)=v2。在映射g下，边，和分别映射到，和。陕西师范大学计算机科学学院 若两个图同构，则它们的结点数相同，边数相同，度数相同的结点数相同等等。但这并不是图同构的充分条件，如在图106中，(a)和(b)虽然满足以上3条件但不同构。(a)中的x应与(b)
18、中的y对应，因为度数都是3。但(a)中的x与两个度数为1的结点u、v邻接，而(b)中的y仅与一个度数为1的结点w邻接。陕西师范大学计算机科学学院例10.1.6 （1）画出4阶3条边的所有非同构无向简单图；（2）画出3阶2条边的所有非同构有向简单图。 陕西师范大学计算机科学学院解：（1）由握手定理可知，所画的无向简单图各结点度数之和为23=6，最大度数小于或等于3。于是所求无向简单图的度数列应满足的条件是：将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数个数为偶数。将这样的整数列排列出来只有下列三种情况： 3，1，1，1 2，2，1，1 2，2，2，0 陕西师范大学计算机科学
19、学院所要求的全部非同构的图，如图10-7所示。 陕西师范大学计算机科学学院（2）由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。 故度数列与入度列、出度列分别为： 度数列：1，2，1： 入度列为0，1，1；0，2，0或1，0，1； 出度列为1，1，0；1，0，1或0，2，0。 陕西师范大学计算机科学学院 度数列：2，2，0 入度列为1、1、0； 出度列为1、1、0； 四个所求有向简单图如图10-8所示。10.2 路、回路和连通性陕西师范大学计算机科学学院 这一节的主要内容：这一节的主要内容： 路、回路、简单路、基本路、简单回路、基本回路、结点之间的可达性
20、、连通图、连通分支、点割集、割点、边割集、割边、强连通、单向连通、弱连通。陕西师范大学计算机科学学院定义10.2.1 给定图G=，设v0，vmV，边（或弧）e1，e2，emE，其中vi-1、vi是ei的端点（始点和终点），交替序列v0e1v1e2emvm称为连接v0到vm的路或通路（Path），通常简记为v0v1vm。路上边的数目称为该路的长度。当v0=vm时，称其为回路（Cycle，Circuit）。陕西师范大学计算机科学学院定义10.2.2 在一条路中，若出现的所有边（或弧）互不相同，称其为简单路或迹；若出现的结点互不相同，称其为基本路或初级通路（Simple path）。陕西师范大学计算
21、机科学学院定义10.2.3 在一条回路中，若出现的每条边（或弧）恰好一次，称其为简单回路；若出现的每个结点恰好一次，称其为基本回路或初级回路或圈（Simple cycle）。陕西师范大学计算机科学学院定理10.2.1 在一个图中，若从结点u到v存在一条路，则必有一条从u到v的基本路。陕西师范大学计算机科学学院证明：（构造性证明方法） 若u到v的路已是基本路，结论成立。否则，在u到v的路中至少有一个结点比如w重复出现，于是经过w有一个回路C，删去回路C上的所有边（或弧）。若得到的u到v的路上仍有结点重复出现，则续行此法，直到u到v的路上没有重复的结点为止，此时所得即是基本路。 陕西师范大学计算机
22、科学学院例10.2.1 在图10-9中，v1v2v3v2v4是一条简单路但不是基本路，v1v2v3v4是一条基本路；v1v2v3v2v4v1是一简单回路但不是基本回路，v1v2v3v4v1是一基本回路。陕西师范大学计算机科学学院定理10.2.2 在n阶图中，任何基本路的长度均不大于n-1，任何基本回路的长度均不大于n。陕西师范大学计算机科学学院证明： 在n阶图中，因为任何基本路和基本回路中都最多有n个结点，所以任何基本路的长度均不大于n-1，任何基本回路的长度均不大于n。陕西师范大学计算机科学学院定义10.2.4 在一个图中，若从u到v存在路，或u=v，则称从u到v是可达（Accessible
23、）。 陕西师范大学计算机科学学院定义10.2.5 若无向图G中任意两个结点之间都是可达的，则称G为连通图（Connected graph），否则称G为非连通图（Disconnected graph）。一个图G的连通分支数记为 (G)。 连通分支就是图中具有连通性的最大子图。 陕西师范大学计算机科学学院定理10.2.3 若G是n阶m条边的连通无向图，则mn-1。 该定理的逆否命题可用来判定一个图不连通。陕西师范大学计算机科学学院例10.2.2 在图10-10中，（a）是连通的，而（b）是不连通的，其连通分支数为3。 陕西师范大学计算机科学学院定义10.2.6 设G=是无向无向连通图，若S V，使
24、G删除S（将S中结点及其关联的边都一起删除）后所得子图G-S不连通，但删去S的任一个真子集所得子图仍是连通的，则称S是G的一个点割集。若G的点割集S=v，称v是G的割点（Cut vertex）。陕西师范大学计算机科学学院 若T E，使G删除T（将T中的边从G中全删除）后所得子图G-T不连通，但删去T的任一个真子集所得子图仍是连通的，则称T是G的一个边割集。若G的边割集T=e，称e是G的割边或桥（Cut edge，Bridge）。陕西师范大学计算机科学学院例10.2.3 在图10-11中，v3是割点；v1, v3, v2, v3是边割集，但没有割边。陕西师范大学计算机科学学院定理10.2.4 一
25、个连通无向图G中的结点v是割点 存在结点u和w，使得连接u和w的每条路都经过v。陕西师范大学计算机科学学院证明： 充分性。若连通图G存在结点u和w，使得连接u和w的每条路都经过v，则在子图G-v中u和w必不可达，故v是G的割点。陕西师范大学计算机科学学院 必要性。若v是G的割点，则G-v至少有两个连通分支G1=和G2=。现取uV1，wV2。因为G连通，故在G中必有连接u和w的路。对任一条连接u和w的路 ，由于u、w在G-v中不可达，因此 必通过v。故u和w之间的任意路必经过v。陕西师范大学计算机科学学院定理10.2.5 一个连通无向图G中的边e是割边 存在结点u和w，使得连接u和w的每条路都经
26、过e。 陕西师范大学计算机科学学院定理10.2.6 无向图G的边e是割边 e不包含在图的任何基本回路中。陕西师范大学计算机科学学院证明： e=x, y是连通图G的割边当且仅当x、y在G-e的不同连通分支中，而后者等价于在G-e中不存在x到y的路，从而等价于e不包含在图的任何基本回路中。于是定理得证。陕西师范大学计算机科学学院定义10.2.7 在简单有向图G中，若任何两个结点之间是相互可达的，则称G是强连通的（Strongly connected）；若任何两个结点之间，至少从一个结点到另一个结点是可达的，则称G是单向连通的或单侧连通的（Unilaterally connected）；若有向图G的
27、基图是连通的，则称G是弱连通的（Weakly connected）。陕西师范大学计算机科学学院 由定义可知，强连通图一定是单向连通的，单向连通图一定是弱连通的，但反之不然。陕西师范大学计算机科学学院例10.2.4 在图10-12中，（a）是强连通的，（b）是单向连通非强连通的，（c）是弱连通非单向连通的。陕西师范大学计算机科学学院定理10.2.7 有向图G是强连通的 G中有一回路，它至少通过每个结点一次。陕西师范大学计算机科学学院证明：充分性。如G中有一回路，它至少通过每个结点一次，则G中任意两个结点相互可达，故G是强连通的。 必要性。如有向图G是强连通的，则任意两个结点相互可达。设V=v1,
28、 v2, , vn， i为vi到vi+1的路， n为vn到v1的路，则 1、 2、 n-1、 n所围成的回路至少通过每个结点一次。 陕西师范大学计算机科学学院定义10.2.8 在图G中，结点u到结点v的最短路的长度称为u到v的距离，记作d。如u到v没有路，则d=+。它具有下列性质： d0（非负性） d=0 d+dd（三角不等式） 注 u与v相互可达，d未必等于d。 10.4 欧拉图和哈密顿图陕西师范大学计算机科学学院 这一节的主要内容：这一节的主要内容： 欧拉回路、欧拉路、欧拉图、哈密顿回路、哈密顿路、哈密顿图。陕西师范大学计算机科学学院定义10.4.1 通过G的每条边恰好一次的路称为欧拉路（
29、Euler path）。通过图G的每条边恰好一次的回路称为欧拉回路（Euler cycle）。具有欧拉回路的图称为欧拉图（Euler graph）。 约定平凡图为欧拉图。 陕西师范大学计算机科学学院例10.4.1 在图10-18中，（a）有欧拉路但无欧拉回路，（b）有欧拉回路，（c）既无欧拉路也无欧拉回路。陕西师范大学计算机科学学院定理10.4.1 连通无向图G有欧拉回路 G中每个结点都是偶数度结点。陕西师范大学计算机科学学院证明： 必要性。若连通无向图G有欧拉回路，设C是G的一条欧拉回路，则C通过G的任一结点时必通过关联该点的两条边，而G中每条边仅出现一次，所以C所通过的每个结点必为偶数度结
30、点。陕西师范大学计算机科学学院充分性。若G中每个结点都是偶数度结点，因G连通，所以G中至少含有一个基本回路C1，从G中删除C1上的各边得到子图G1。若G1中仍然有边，由G1每个结点仍为偶数度结点，则可得基本回路C2，且C1与C2有一个公共结点。 续行此法，直到删去G中的所有边。于是得到一系列基本回路C1，C2，Cm，且 Ck与Cj有一个公共结点，则可由C1，C2，Cm构成一个欧拉回路。 11 jk陕西师范大学计算机科学学院定理10.4.1不仅给出了欧拉图的判定方法，而且也给出了构造欧拉回路的方法。陕西师范大学计算机科学学院例10.4.2 图G=如图10-19所示，构造其欧拉回路。 v5v4v3
31、v2v1图10-19陕西师范大学计算机科学学院解：在G中取基本回路C1：v1v2v3v4v5v1，对于图G-C1，又可取基本回路C2：v1v3v5v2v4v1，C1与C2的公共结点为v1，因为图G-C1-C2已没有边，所以得到的欧拉回路为：v1v2v3v4v5v1v3v5v2v4v1。 v5v4v3v2v1图10-19陕西师范大学计算机科学学院定理10.4.2 连通无向图G=，u、vV且uv，u与v之间存在欧拉路 G中仅有u和v为奇数度结点。 陕西师范大学计算机科学学院证明： 对G加上一条边u, v得到新图G1，G中u和v之间存在欧拉路 G1中有欧拉回路 G1中每个结点为偶数度结点 G除u、v
32、外其余结点均为偶数度结点 G仅有u和v为奇数度结点。 陕西师范大学计算机科学学院定理10.4.3 强连通有向图G有欧拉回路 G中的每个结点的入度等于出度。陕西师范大学计算机科学学院定理10.4.4 单向连通有向图G=，u、vV且uv，u与v存在欧拉路 G中唯有u和v的入度不等于出度，且u的出度比其入度大1，v的出度比其入度小1。陕西师范大学计算机科学学院与欧拉回路类似的是哈密顿回路问题。它是1859年哈密顿首先提出的一个关于12面体的数字游戏：能否在12面体中找出一条回路，使它通过图中所有结点一次且仅一次？ 将12面体画作与其同构的平面图，如图10-20所示。陕西师范大学计算机科学学院陕西师范
33、大学计算机科学学院定义10.4.2 经过图中每个结点恰好一次的路称为哈密顿路（Hamiltonian path）。经过图中每个结点恰好一次的回路称为哈密顿回路（Hamiltonian cycle）。具有哈密顿回路的图称为哈密顿图（Hamiltonian graph）。陕西师范大学计算机科学学院例10.4.3 在图10-21中，（a）有哈密顿路但无哈密顿回路，（b）既有哈密顿路又有哈密顿回路，（c）既无哈密顿路也无哈密顿回路。陕西师范大学计算机科学学院定理10.4.5 若连通图G=是哈密顿图，S是V的任意真子集，则 (G-S)|S|。陕西师范大学计算机科学学院证明： 若连通图G=是哈密顿图，设C
34、是G的哈密顿回路，则C-S是G-S的生成子图，所以 (G-S) (C-S)。易知当S中的结点互不邻接时，C-S的连通分支数达到最大值|S|，所以有 (C-S)|S|。故 (G-S)|S|。陕西师范大学计算机科学学院推论 若连通图G=存在哈密顿路，S是V的任意真子集，则 (G-S)|S|+1。 定理10.4.5给出了图是哈密顿图的必要条件，因此该定理的逆否命题可用来判断一个图不是哈密顿图，这是它的价值所在。陕西师范大学计算机科学学院例10.4.4 说明图10-22所示的图不是哈密顿图。陕西师范大学计算机科学学院解： 取S=v2, v6，则G-S有3个连通分图， (G-S)|S|，由定理10.4.
35、5知，图10-22所示的图不是哈密顿图。陕西师范大学计算机科学学院定理10.4.6 G=是n阶简单图，n3，则：（1）如任两不相邻结点u、vV，均有d(u) +d(v)n-1，则在G中存在一条哈密顿路。（2）如任两不相邻结点u、vV，均有d(u)+d(v)n，则G是哈密顿图。陕西师范大学计算机科学学院定理10.4.6只是一个充分条件，但反过来未必成立。例如，六边形的图是哈密顿图，但不满足定理的条件。陕西师范大学计算机科学学院例10.4.5 某地有5个风景点，若每个风景点均有两条道路与其他景点相通，问是否可经过每个风景点恰好一次而游玩这5处？陕西师范大学计算机科学学院解： 将风景点作为结点，连接
36、风景点的路作为边，则得到一个无向图G。由题意可知，对G中每个结点均有d(v)=2。于是对任意u、vG，有d(u)+d(v)=2+2=4=5-1，所以该图有一哈密顿路，故本题有解。10.6 平面图陕西师范大学计算机科学学院 这一节的主要内容：这一节的主要内容： 平面图、面、边界、欧拉公式。陕西师范大学计算机科学学院定义10.6.1 如把无向图G画在平面上，任意两条边除端点外均不相交，称G为平面图（Planar graph）。陕西师范大学计算机科学学院例10.6.1 K2、K3、K4都是平面图，完全二部图K1,n（n1）、K2,n（n2）也是平面图。 在研究平面图理论中有两个十分重要的图，就是被称
37、为库拉图斯基图的完全二部图K3,3和完全图K5，它们都不是平面图。其中，K3,3是边数最少的非平面图，K5是结点数最少的非平面图。陕西师范大学计算机科学学院由定义我们不难得出：平面图的任何子图都是平面图；非平面图的任何母图都是非平面图；图中的平行边和环并不影响图的平面性。 因为当且仅当一个图的每个连通分支都是平面图时，这个图才是平面图。所以，在研究平面图的性质时，只讨论连通平面图。陕西师范大学计算机科学学院定义10.6.2 设G为连通平面图，G的边将G所在的平面划分成若干区域，每个区域称为G的一个面（Face），记为f。包围这个区域的各条边构成的回路称为面f的边界（Boundary），其回路的
38、长度称为面f的次数或度数（Degree），记为d(f)。区域有限的面称为有限面，区域无限的面称为无限面。陕西师范大学计算机科学学院显然，任何连通平面图只有一个无限面。陕西师范大学计算机科学学院例10.6.2 在图10-27中，共有3个面f1、f2、f3。其中，面f1由回路v1v2v3v4v5v6v5v4v1所围，面f2由回路v1v4v7v1所围，面f3由回路v1v2v3v4v7v1所围，所以d(f1)=8，d(f2) =3，d(f3)=5。陕西师范大学计算机科学学院定理10.6.1 设G=是连通平面图，F是G的面的集合，则 =2|E|。 Ff)f (d陕西师范大学计算机科学学院证明： 因为G中
39、每条边无论作为两个面的公共边界，还是作为一个面的边界，在计算总的次数时都计算2次，所以结论成立。陕西师范大学计算机科学学院定理10.6.2 设G是n（n3）阶简单连通平面图，则G的每个面的次数大于等于3。陕西师范大学计算机科学学院证明： 因为G的任意一个面上至少有3个结点，所以G的每个面的次数都大于等于3。陕西师范大学计算机科学学院定理10.6.3（欧拉公式）若G为连通平面图，则n-m+r=2，其中，n、m、r分别为G的结点数、边数和面数。 欧拉公式是平面图的基本而重要的公式，它反映了平面图的结点数、边数和面数之间的关系。陕西师范大学计算机科学学院证明： 对G的边数m作归纳。 当m=0时，由于
40、G是连通图，所以G为平凡图，此时n=1，r=1，结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。陕西师范大学计算机科学学院设e是G的一条边，从G中删去e后得到的图记为G ，并设其结点数、边数和面数分别为n 、m 和r 。对e分下列情况来讨论：陕西师范大学计算机科学学院若e为割边，则G 有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1+n2=n =n，m1+m2=m =m -1，r1+r2=r +1=r+1。由归纳假设有n1-m1+r1=2，n2-m2+r2=2，从而(n1+n2)-(m1+m2)+(r1+r2)=4，
41、n-(m-1)+(r+1)= 4，即n-m+r=2。陕西师范大学计算机科学学院若e不为割边，则n =n，m =m-1，r =r-1，由归纳假设有n -m +r =2，从而n-(m-1)+r-1=2，即n-m+r=2。 由数学归纳法知，结论成立。陕西师范大学计算机科学学院定理10.6.4 若G是连通的平面图，且G的每个面的次数至少为l（l3），则G的边数m与结点数n有如下关系： 。)n(ll22m 陕西师范大学计算机科学学院证明： 设G有r个面，则2m= lr。由欧拉公式得，n-m+r=2。 于是， 。)n(ll22m )f(drii 1陕西师范大学计算机科学学院定理10.6.5 设G是n（n3
42、）阶m条边的简单连通平面图，则m3n-6。陕西师范大学计算机科学学院证明： 因为G是一个简单连通平面图，所以G任意面的次数d(f)3。由定理10.6.4可得m3n-6。陕西师范大学计算机科学学院上述定理是判别平面图的必要条件，而不是充分条件。也就是说，即使一个图满足上述不等式，也未必是平面图，但使用上述定理的逆否命题可以判别一个图不是平面图。陕西师范大学计算机科学学院例10.6.3 证明K5不是平面图。陕西师范大学计算机科学学院证明： 若K5是一个平面图，由于K5有5个结点10条边，则35-6=910，与定理10.6.5矛盾。所以，K5不是平面图。陕西师范大学计算机科学学院例10.6.4 证明
43、K3,3不是平面图。陕西师范大学计算机科学学院证明： 若K3,3是平面图，因为在K3,3中任取三个结点，其中必有两个结点不相邻，故每个面的次数大于等于4，于是4/(4-2)(6-2)= 89，与定理10.6.4矛盾。所以，K3,3不是平面图。陕西师范大学计算机科学学院判断一个图是否为平面图是一件困难的事。通常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的基本回路；然后将图中那些相交于非结点的边，适当放置在已选定的基本回路内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。 例如，K5不是平面图，因为无论如何画都不能使其所有边不相交。另外，也可以采用下
44、面的方法来判断。陕西师范大学计算机科学学院定义10.6.3 若G2可由在G1中的一些边上适当插入或涂抹度为2的有限个结点后而得到，则称G1与G2同胚或在2度结点内同构（Homeomporphism）。陕西师范大学计算机科学学院例10.6.5 图10-29所示的两个图形是同胚的。 陕西师范大学计算机科学学院定理10.6.6（库拉图斯基图定理）一个图G是平面图 G中不含同胚于K3,3或K5的子图。10.7 树及其应用陕西师范大学计算机科学学院 这一节的主要内容：这一节的主要内容： 树、生成树、弦、生成树的权、最小生成树、Kruskal算法、Prim算法、根树、有序树、二叉树、Huffman算法、前
45、缀码。陕西师范大学计算机科学学院定义10.7.1 连通无回路的无向图称为无向树（Tree），简称树，常用T表示。注 这里的回路指的是简单回路。陕西师范大学计算机科学学院 在树中，悬挂结点称为树叶，度数大于1的结点称为分支点或内结点（Branching vertex），悬挂边称为叶边。连通分支数大于1，且每个连通分支都是树的无向图称为森林。陕西师范大学计算机科学学院例10.7.1 在图10-31中，（a）和（b）是树，（c）是森林。图10-31陕西师范大学计算机科学学院 由定义不难得出，树一定是连通的简单平面图。陕西师范大学计算机科学学院定理10.7.1 设T=是n阶m条边的无向图，则下面命题等
46、价：（1）T是树。（2）T无回路且m=n-1。（3）T连通且m=n-1。（4）T连通且T的每条边都是割边。（5）T无回路，但任意增加一条边产生惟一一条回路。（6）T中每对结点间恰有一条基本路。陕西师范大学计算机科学学院证明： （1）（2）。只需证m=n-1。因为T是树，所以T是连通平面图，且T只有一个无限面，由欧拉公式得n-m+1=2，即m=n-1。 陕西师范大学计算机科学学院（2）（3）。只需证T连通。对n用数学归纳法证明。 若n=2，则命题显然成立。 假设当n=k时命题成立。则当n=k+1时，由于G无回路且m=n-1，所以一定存在度为1的结点（否则G中除了孤立结点之外，其他结点的度数都至少
47、是2。从而G一定存在基本回路，得出矛盾）。陕西师范大学计算机科学学院 不妨设v是G的度为1的结点，删去v及以v为端点的边得到图G1。图G1有k个结点且k-1条边，从而由归纳假设可知，图G1连通。从而G也连通。陕西师范大学计算机科学学院（3）（4）。只需证T的每条边都是割边。任取T的边e，则T-e的边数为m-1，结点数为n，于是m-1=n-2n-1，所以T-e是不连通的，因而e是割边。故T的每条边都是割边。陕西师范大学计算机科学学院（4）（5）。由于T的每条边都是割边，因而T中无回路。在T中添加新边u, v，由T是连通的，则存在u到v的一条路，于是+u, v构成一回路。若得到的回路不惟一，不妨记
48、为1和2，则1-u, v与2-u, v构成一回路，其经过的边都不是割边，矛盾。故在T中任意增加一条边产生惟一一条回路。陕西师范大学计算机科学学院（5）（6）。若T中存在两个结点u和v，它们之间不存在路，则添加边u, v不产生回路，矛盾。所以T中任意两个结点之间存在基本路。若u和v之间存在两条不同的基本路1和2，则由1和2可以得到一条基本回路，矛盾。所以T中每对结点间恰有一条基本路。陕西师范大学计算机科学学院（6）（1）。因为T中每对结点间恰有一条基本路，所以T是连通的。若T有回路，则回路经过的任意两个结点之间存在两条路，矛盾，所以T没有回路。因此，T是树。陕西师范大学计算机科学学院 由于树少一
49、边就不连通，多一边就有回路，所以树是以“最经济”的方式把各结点连接起来的图。因此，它可以用作典型的数据结构，各类网络的主干网也通常都是树结构。陕西师范大学计算机科学学院定理10.7.2 若T=是树，且|V|2，则T中至少存在两片树叶。陕西师范大学计算机科学学院证明： 由T是树得，|E|=|V|-1。设T有k片树叶，应用握手定理可得2|E|=2(|V|-1)= k+2(|V|-k)，于是k2。 Vv)v(d陕西师范大学计算机科学学院定义10.7.2 若T是连通无向图G的生成子图且是树，则称T是G的生成树（支撑树，Spanning tree）。G在T中的边称为T的树枝，G不在T中的边称为T的弦。陕
50、西师范大学计算机科学学院例10.7.2 在图10-32中，（b）是（a）的生成树，而（c） 不是。 陕西师范大学计算机科学学院定理10.7.3 无向图G=有生成树当且仅当G是连通的。陕西师范大学计算机科学学院证明： 必要性。设T=是G的生成树，则有VT=V。由于T是连通的，所以G是连通的。陕西师范大学计算机科学学院 充分性。若G中无回路，则G本身就是一棵生成树。若G中有回路，删去回路上的一条边得到图G1，G1仍是连通的且与G有相同的结点集。若G1还有回路，就再删去此回路上的一条边得到图G2，G2是连通的且与G有相同的结点集。续行此法，直到得到连通图T，它无回路且与G有相同的结点集，T就是G的生
