第7章 图论 7.1 图的基本概念 7.6 树 7.2 路与圈 7.7 根树及其应用 7.3 图的矩阵表示 7.8 偶图与匹配

Presentation on theme: "第7章 图论 7.1 图的基本概念 7.6 树 7.2 路与圈 7.7 根树及其应用 7.3 图的矩阵表示 7.8 偶图与匹配"— Presentation transcript:

1 第7章 图论 7.1 图的基本概念 7.6 树 7.2 路与圈 7.7 根树及其应用 7.3 图的矩阵表示 7.8 偶图与匹配
第7章 图论 7.1 图的基本概念 7.2 路与圈 7.3 图的矩阵表示 7.4 有向图和可达性矩阵 7.5 欧拉图与哈密尔顿图 7.6 树 7.7 根树及其应用 7.8 偶图与匹配 7.9 平面图与欧拉公式 习 题 7

2 7.1 图的基本概念 图 例１ a， b， c， d 4个篮球队进行友谊比赛。 为了表示４个队之间比赛的情况， 我们作出图 7 ― 1的图形。 在图中４个小圆圈分别表示这４个篮球队， 称之为结点。 如果两队进行过比赛， 则在表示该队的两个结点之间用一条线连接起来， 称之为边。 这样利用一个图形使各队之间的比赛情况一目了然。

3 图 7 ― 1 例 1用图

4 如图 7 ― 1中的４个结点a， b， c， d分别表示４个人， 当某两个人互相认识时， 则将其对应点之间用边连接起来。 这时的图又反映了这４个人之间的认识关系。
  这种用图形来表示事物之间的某种关系的方法我们也曾经在第 4 章中使用过。 显然在这样的图形中， 我们感兴趣的是结点与结点之间是否有线（即边）连接， 至于点与点之间用什么样的线连接则无关紧要。 这类事例的数学模型就产生了图的概念。

5 定义 7.1 ― 1 一个图G是一个序偶（V， E）， 记为G＝（V， E）。 其中V是有限非空集合， 其元素称为结点（或顶点、 点）， V也称为结点集； E是另一个集合， 其元素称为边， E也称为边集， 对E中的每个元素， 有V中的结点对与之对应。 定义中的结点对可以是有序的， 也可以是无序的。 我们将结点 u、 v 的无序结点对记为（u， v）， 有序结点对记为〈u， v〉。

6 定义 7.1 ― 2 若图G中的边e与结点u、 v的无序结点对（u， v）相对应， 则称e为无向边， 记为e＝（u， v）。 这时称e与两个结点u和v互相关联， u、 v称为该边的两个端点。 这时也称u与v是邻接的， 否则称为不邻接的。 关联于同一结点的两条边称为邻接边。

7 定义 7.1 ― 3 图G中的边e与结点u 、 v 的有序结点对〈u， v〉相对应， 则称e为有向边， 记为e＝〈u， v〉。 有向边又称为弧， 这时称u 为弧尾（或始端）， 称v为弧头（或终端）。
图可用一个图形来表示。 在图的图形中用由u 指向v 的有向线段表示弧〈u， v〉， 无向线段表示边（u， v）。

8 如例１中的图， 结点集V＝｛a， b， c， d｝， 边集
E＝｛e1， e2， e3， e4， e5｝， 其中 e1＝（a， b）， e2＝（a， c）， e3＝（a， d）， e4＝（b， c）， e5＝（c， d）。 d与a、 d与c是邻接的， 但d与b不邻接， 边e3与e5是邻接的。

9 图 7 ― 2 例 2用图

10 定义 7.1 ― 4 每条边都是无向边的图称为无向图； 都是有向边的图称为有向图；既有无向边， 又有有向边的图称为混合图。
本书主要研究无向图和有向图。 对于有向图， 我们将在第7.4节中讨论。

11 例２ 设图G＝（V， E）如图7 ― 2所示。 这里V＝｛v1， v2， v3｝， E＝｛e1， e2， e3， e4， e5｝， 其中e1 ＝（v1， v2）， e2＝（v1， v3）， e3 ＝（v3， v3）， e4 ＝（v2， v3）， e5＝（v2， v3）。 在这个图中， e3是 两个端点相同的边， 我们称为自回路； 边e4和e5都与结点v2、 v3关联， 也就是说结点v2和v3之间有两条边相连， 这样的边称为多重边。

12 定义 7.1 ― 5 若图中两个结点有多条边相连， 则称这些边为多重边。 连接两结点的多重边的条数称为连接这两结点边的重数。 没有多重边和自回路的图称为简单图。

13 7.1.2 结点的度 我们常常需要关心图中有多少条边与某一结点关联， 这就引出了图的一个重要概念——结点的度。 定义 7.1 ― 6 图中结点v 所关联的边数（有自回路时计算两次）称为结点v 的度数， 记为deg（v）。 如图7 ― 2中的deg（v1）＝2， deg（v2）＝3， deg（v3）＝5。

14 定理 7.1 ― 1 图G＝（V， E）中结点度数的总和等于边数的两倍， 即
证明 因为每条边都与两个结点关联， 所以加上一 条边就使得各结点度数的和增加 2， 由此结论成立。 推论 图G中度数为奇数的结点必为偶数个。

15 证明 设V1和V2分别是G中奇数度数和偶数度数的结点集。
由定理7.1 ― 1知 由于  是偶数之和， 必为偶数， 而2|E|也 为偶数， 故 是偶数。 由此|V1|必为偶数。 定义 7.1 ― 7 在图中， 度数为０的结点称为孤立点， 度数为１的结点称为悬挂点。

16 7.1.3 几种常见的图 定义 7.1 ― 8 具有n个结点和m条边的图称为（n， m）图。 一个（n， 0）图称为零图（即该图只有n个孤立结点）。 只有一个结点的图， 即（1， 0）图称为平凡图。 定义 7.1 ― 9 任意两个不同的结点都是邻接的简单图称为完全图。 n 个结点的无向完全图记为Kn。 图7 ― 3给出了K3和K4。 从图中可以看出K3有３条边， K4有６条边。 容易证明Kn有 条边。

17 图 7 ― 3 K3与K4示意图 图 7 ― 4 G和 G 示意图

18 定义 7.1 ― 10 设G＝（V， E）是一个具有n个结点的简单图。 以V为结点集， 以从完全图Kn中删去G的所有边后得到的图称为G的补图（或称为G的补）， 记为G 。

19 定义 7.1 ― 11 给每条边赋以一个实数（称为该边的权）的图叫有权图。 边e的权常记为ＷG（e）。 有权图G＝（V， E）中所有边的权之和 称作图G的权， 记为ＷG（G）。

20 例３ （拉姆齐问题）试证在任何一个有６个人的组里， 存在３个人互相认识， 或者存在３个人互相不认识。
我们用６个结点来代表人， 并用邻接性来代表认识关系。 这样一来， 该例就是要证明： 任意一个有６个结点的图G中， 或者有３个互相邻接的点， 或者有３个互相不邻接的点。 即， 对任何一个有６个结点的图G， G或G 中含有一个三角形（即K3）。

21 证明 设G＝（V， E）， |V|＝6， v是G中一结点。 因为v 与G的其余５个结点或者在G中邻接， 或者在G中邻接。 故不失一般性可假定， 有３个结点v1， v2， v3在G中与v邻接。
如果这３个结点中有两个结点（如v1， v2）邻接， 则它们与v 就是G中一个三角形的３个顶点。 如果这3个结点中任意两个在G中均不邻接， 则v1， v2， v3就是G中一个三角形的３个顶点。

22 7.1.4 子图 在研究和描述图的性质时， 子图的概念占有重要地位。 定义 7.1 ― 12 设有图G＝（V， E）和图 G′＝（V′， E′）。 1) 若V′V， E′E， 则称G′是G的子图。 2) 若G′是G的子图， 且E′≠E， 则称G′是G的真子图。

23 3) 若V′＝V， E′E， 则称G′是G的生成子图。
图 7 ― 5给出了图G以及它的真子图G1和生成子图G2。 图 7 ― 5 图G以及其真子图G 1和生成子图G2

24 定义 7.1 ― 13 如果图G中的一个子图是通过删去图G的结点集V的一个子集V1的所有结点及与其关联的所有边得到的， 则将该子图记为G－V1。
定义 7.1 ― 14 如果图G中的一个子图是通过删去图G的边集E的一个子集E1的所有边， 而不删去它们的端点而得到的， 则将该子图记为G－E1。 如图7 ― 5中， G2＝G－｛(2， 4)｝。

25 7.1.5 图的同构 从图的定义可以看出， 图的最本质的内容是结点与结点的邻接关系。 例如例１也可以用图7 ― 6中几种不同形状的图形表示。 它们与图7 ― 1一样， 都同样表示例１中４个队之间的比赛情况。 从这个意义上讲， 我们说它们是同一个图， 并称图7 ― 1与图7 ― 6的(a)和(b)是同构的。

26 图 7 ― 6 同构的图 图 7― 7 例 4 用图

27 定义 7.1 ― 15 设有图 G＝（V， E） 和图 G′＝（V′， E′ ）。 如果存在双射ｇ： V→V′， 使得 e＝（u， v）∈E iff e′＝（ｇ(u)， ｇ(v)）∈E′， 且（u， v）与（ｇ(u)， ｇ(v)）有相同的重数， 则称G与G′同构。 记作G≌G′。 例４ 考察图7 ― 7中的两个图G＝（V， E）和G′＝（V′， E′）。

28 显然， 定义ｇ： V→V′， ｇ（vi）＝v′i， 可以验证ｇ是满足定义7.1 - 15的双射， 所以G≌G′。
对于同构， 形象地说， 若图的结点可以任意挪动位置， 而边是完全弹性的， 只要在不拉断的条件下， 这个图可以变形为另一个图， 那么这两个图是同构的。 故同构的两个图从外形上看可能不一样， 但它们的拓扑结构是一样的。

29 7.2 路 与 圈 7.2.1 路、 圈和连通性 定义 7.2 ― 1 给定图G＝（V， E）。 设v0， v1， …， vk∈V， e1， e2， …， ek∈E， 其中ei是关联于结点vi-1和vi的边， 称交替序列v0e1v1e2…ekvk为连接v0到vk的路， 路中边的数目k称作路的长度。

30 定义 7.2 ― 2 设μ＝v0e1v1e2…ekvk是图G中连接v0到vk的路。
2) 若e1， e2， …， ek都不相同， 则称路μ为迹； 3) 若v0， v1， …， vk都不相同， 则称路μ为通路； 4) 长度大于２的闭的通路（即除v0＝vk外， 其余结点均不相同的路）μ称作圈。

31 图 7 ― 8 例图

32 例如在图 7 ― 8中， 有连接v5到v3的路v5e8v4e5v2e6v5e7v3， 这也是一条迹； 路v1e1v2 e3v3是一条通路； 路v1e1v2e3v3e4v2e1v1是一条回路， 但不是圈； 路v1e1v2e3v3e2v1是一条回路， 也是圈。 在简单图中， 一条路v0e1v1e2…ekvk完全由它的结点序列v0v1…vk确定。 所以简单图 的路可由结点序列表示。 如图7 ― 1表示的简单图中， 路ae1be4ce5d可写成abcd。 下面我们利用通路的概念解决一个古老的著名问题。

33 例1 （渡河问题） 一个摆渡人， 要把一只狼、 一只羊和一捆干草运过河去， 河上有一只木船， 每次除了人以外， 只能带一样东西。 另外， 如果人不在旁时， 狼就要吃羊， 羊就要吃干草。 问这人怎样才能把它们运过河去？ 解 用Ｆ表示摆渡人， W表示狼， Ｓ表示羊， Ｈ表示干草。

34 解 用F表示摆渡人， W表示狼， S表示羊， H表示干草。
FWSH FWS FWH FSH WSH FW FS FH WS WH SH F W S H φ 这里φ表示左岸是空集， 即人、 狼、 羊、 干草都已运到右岸去了。

35 根据题意检查一下就可以知道， 这16种情况中有６种情况是不允许出现的。 它们是： WSH、 FW、 FH、 WS、 SH、 F。 如FH表示人和干草在左岸， 而狼和羊在右岸， 这当然是不行的。 因此， 允许出现的情况只有10种。

36 我们构造一个图， 它的结点就是这10种状态。 若一种状态可以转移到另一种状态， 就在表示它们的两结点间连一条边， 这样就画出图7 ― 9。 本题就转化为找结点FWSH 到结点φ的通路。 从图中得到两条这样的通路， 即有两种渡河方案。

37 图 7 ― 9 例 1 用图

38 定义 7.2 ― 3 在图G中， 若结点vi到vj有路连接（这时称vi和vj是连通的）， 则其中长度最短的路称为从vi到vj的短程。 短程的长度称为vi到vj的距离， 用符号d（vi， vj）表示。
例如在图7 ― 8中， ｄ（v1， v4）＝２。

39 定理 7.2 ― 1 设G是具有n个结点的图， 如果从结点vi到另一结点vj存在一条路， 则其短程是一条长度不大于n－1的通路。
证明 设从结点vi到结点vj存在一条路μ， 该路上的结点序列为vi…vk…vj。 我们用反证法证明， 当μ是短程时， μ一定是通路。

40 若μ不是通路， 则μ中至少有两个结点相同， 设为vs。 即必有结点序列vi…vs… vs…vj。 在μ中去掉路vs…vs的这些边， 仍得到从结点vi到结点vj的一条路， 但此路的长度要比μ的长度小， 这与μ是短程矛盾。 故μ必是一条通路。 若μ的长为l， 则其结点序列必有l＋1个点， 它们又互不相同， 所以l＋1≤ｎ， 即 ｌ≤ｎ－１。

41 图 7 ― 10 图G与G′

42 推论 设图G＝（V， E）， |V|＝n， 则G中任一圈长度不大于n。
定义 7.2 ― 4 如果一个图的任何两个结点之间都有一条路， 那么我们称这个图是连通的， 否则是不连通的。 定义 7.2 ― 5 图G的一个连通的子图（称为 连通子图）若不包含在G的任何更大的连通子图中， 它就被称作G的连通分支。 我们把图G的连通分支数记作W（G）。

43 在图7 ― 10中， G是不连通的， W（G）＝２， 而G′是连通的， W（G′）＝１。

44 7.2.2 有权图的最短路径问题 有权图经常出现在图论的应用中。 如在通讯图中， 权可以表示各种通讯线路的建造或维修费用； 在交通图中， 权可以表示两地的距离等等。 定义 7.2 ― 6 有权图G中， 连接两个结点vi和vj的路μ的权是μ中各边的权之和， 记为WG（μ）。

45 下面介绍有权的简单连通无向图G＝（V， E）中的最短路径问题。 该问题是： 在一个有权图G中找出仅当u0（称为源点）到G中其余各点（称为该路的终点）具有最小权的路（称为最短路径）。
为清楚起见， 我们把有权图中一条路的权称为它的长。 下面叙述的算法是迪克斯特拉（Dijkstra）在1959年提出的， 它给出了从源点u0到G的其它所有结点的最短路径。 在这里我们假设WG(e)＞0（e∈E）。 该算法的基本思想很简单。

46 首先容易用反证法证明边权为正的最短路径有这样的性质： 若u0u1…um-1um是从u0到um的最短路径， 则u0u1…um-1是从u0到um-1的最短路径。
这样， 假设S为图G中按长度递增的次序已求出的最短路径的终点的集合， 则下一条长度较长的最短路径的终点u可求之如下：

47 令S ＝V－S， 对于t∈S ， 考虑每个x -i∈S， 将从结点xi到结点t的边（若有这样的边）连接在从u0到xi的最短路径后面， 这样就构成了从u0到t的l条不同的路（若图中有边(u0， t)， 则u0t是其中的一条路）。 选出这l条路中的最短路， 并设该路长为D(t)， 令D(u)＝min{D(t)|t∈S }， 则由上面所述性质知， u即为所求结点。 由此可知， u0到所求结点u的最短路径或是路u0u， 或是以S中的点作为中间结点的路。

48 综上所述， 可得迪克斯特拉算法步骤如下： 1) 把V分成两个子集S和S ＝V－S， 初始时 S＝{u0}。 令D(i)（i∈S ）为 (u0, i)∈E=∞ (*) 否则 其中 WG（u0， i）是G中的边（u0， i）的权， 而∞表示某个足够大的数。

49 2) 找S 中的点u， 使D(u)＝min{D(t)|t∈S }， 则D(u)就是u0到u的最短路径长度。
3) 将点u从S 中删除并加入集合S中， 即置S为S∪{u}， 置S 为S －{u}。 4) 若S≠V， 则修改D(t)（t∈S ）的值， 其方法是： 若有（u， t）∈E（u 是步骤2)中选出的）， 则置D(t)为min{D(t)， D(u)＋WG(u， t)}。 转2)。 5) 若S＝V， 则算法结束。

50 因为该算法每执行一次（以执行算法步骤 2)～4) 为一次）， 选取一个有最短路径的结点u， 所以图中结点全部处理完要执行|V|－１次。
为清楚起见， 我们将本算法用框图表示， 见图7 ― 11。

51 图7 ― 11 迪克斯特拉算法框图

52 例２ 在图7 ― 12所示的有权图中， 用迪克斯特拉算法求结点v0到其余各点的最短路径。
解 初始状态为 S＝{v0}， S ＝{v1， v2， v3， v4， v5， v6}， D(v1)＝２， D(v2)＝３， D(v3)＝５， D(v4)＝∞， D(v5)＝∞， D(v6)＝５。

53 图7 ― 12 例2用图

54 算法共执行 6 次。 第 1 次 ① S中有最小D值的结点为v1， 选u＝v1。 ② 置S为S∪{u}＝{v0， v1}； 置S 为S －{u} ＝{v2， v3， v4， v5， v6}。

55 ③ 修改S 中诸元素的D值如下： D(v2)←min{D(v2)， D(v1)＋WG(v1， v2)} ＝min{３， ２＋∞}＝３ D(v3)←min{D(v3)， D(v1)＋WG(v1， v3)} ＝min{５， ２＋２}＝４ D(v4)←min{D(v4)， D(v1)＋WG(v1， v4)} ＝min{∞， ２＋∞}＝∞ 同理有D(v5)＝９， D(v6)＝５。

56 图7 ― 13 例2算法示意图

57 图7 ― 13 例2算法示意图

58 第 2 次 ① S 中有最小D值的结点为v2， 选u＝v2。 ② 置S为S∪{u}＝{v0， v1， v2}， 置S 为 S －{u}＝{v3， v4， v5， v6}。 ③ 修改S 中诸元素的D值， 求得 D(v3)＝４， D(v4)＝８， D(v5)＝９， D(v6)＝５。 第 3 次到第 6 次的过程请读者自己补出。

59 7.3 图的矩阵表示 上面我们介绍了图的一种表示方法， 即用图形表示图。 它的优点是形象直观， 但是这种表示在结点与边的数目很多时是不方便的。 下面我们提供另一种用矩阵表示图的方法。 利用这种方法， 我们能把图用矩阵存储在计算机中， 利用矩阵的运算还可以了解到它的一些有关性质。

60 定义 7.3 ― 1 设G＝（V， E）是有n个结点的图， 则n阶方阵Ａ＝（aij）称为G的邻接矩阵。 其中
否则 如图7 ― 14所示的图G， 其邻接矩阵A为

61 如图7 ― 14所示的图G， 其邻接矩阵A为 显然无向图的邻接矩阵必是对称的。 下面的定理说明， 在邻接矩阵A的幂A2， A3， …矩 阵中， 每个元素有特定的含义。

62 图7 ― 14 图G

63 定理 7.3 ― 1 设G是具有n个结点集｛v1， v2， …， vn｝ 的图， 其邻接矩阵为A， 则Al（l＝1， 2， …）的（i， j）项元素a(l)ij是从vi到vj的长度等于l的路的总数。
当l＝1时， A1＝A， 由A的定义， 定理显然成立。 若l＝k时定理成立， 则当l＝k＋1时， A k+1＝Ak ·A， 所以

64 由定理7.3 ― 1和定理7.2 ― 1可得出以下结论： 1) 如果对l＝1， 2， …， n-1， Al的（i， j）项元素（i≠j）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。 2) 结点vi 到vj （i≠j）间的距离d（vi， vj）是使Al（l＝1， 2， …， n-1 ）的（i， j）项元素不为零的最小整数l。 3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。

65 例１ 图G＝（V， E）的图形如图7 ― 15， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。
解

66 图 7 ― 15 例1用图

67 1) 由A中a(1)12＝1知， v1和v2是邻接的； 由A3中a(3)12＝2知， v1到v2长度为3的路有两条， 从图中可看出是v1v2v1v2和v1v2v3v2。
3) 由于A3的主对角线上元素全为零， 所以G中没有长度为３的回路。

68 4) 由于a（１）34＝a（２）34＝a（３）34＝a（４）34＝０， 所以结点v3和v4间无路， 它们属于不同的连通分支。
5) d（v1， v3）＝２。 对其他元素读者自己可以找出它的意义。

69 有向图和可达性矩阵 有向图 在动态状态中， 例如计算机的流程系统中， 有向图的概念常常比无向图更有用。 为此， 我们应了解有向图的一些概念和有关性质。

70 定义 7.4 ― 1 设G是一个有向图， 结点v的出度和入度分别是以v为弧尾和以v 为弧头的弧的条数， 分别记作deg＋(v)与deg－(v)。 结点v的出度和入度之和称作结点v的度， 记作deg(v)。

71 如在图7 ― 16所表示的有向图中， 有 deg＋(v1)＝１， deg－(v1)＝２， deg(v1)＝３ deg＋(v2)＝２， deg－(v2)＝２， deg(v2)＝４ deg＋(v3)＝２， deg－(v3)＝１， deg(v3)＝３ 无向图中的路、 迹、 通路和圈的概念都可照搬到有向图中， 只是弧的方向必须与路的方向相一致。 即有向图G中一条（有向）路是结点和弧的交替序列 ｗ＝v0e1v1e2v2…ekvk， 使得每条弧ei从vi-1开始vi处结束。

72 图 7 ― 16 有向图示例

73 定义 7.4 ― 2 在有向图中， 若有一条从结点vi到结点vj的路， 则称vi到vj是可达的。
定义 7.4 ― 3 设有有向图G， 1) 若略去弧的方向后， G成为连通的无向图， 则称G是弱连通的； 2) 若G中任意两个结点之间， 至少有一个结点到另一个结点是可达的， 则称G是单向连通的； 3) 若G中任意两个结点之间是相互可达的， 则称G是强连通的。

74 从定义可知： 若图G是单向连通的， 则必是弱连通的；若图G是强连通的， 则必是单向连通的， 且也是弱连通的。 但反之不真。
如图7 ― 17所示的３个有向图中， (a)是强连通的， (b)是单向连通的， (c)是弱连通的。

75 图 7 ― 17 有向图连通性的示例

76 定理 7.4 ― 1 一个有向图G是强连通的， 当且仅当G中有一个（有向）回路， 它至少包含每个结点一次。
证明 必要性： 如果有向图G是强连通的， 则任意两个结点都是相互可达的。 故必可作一回路经过图中所有各结点。 否则必有一回路不包含某一结点v。 这样， v与回路上各结点就不能相互可达， 这与G是强连通矛盾。 充分性： 如果G中有一个回路， 它至少包含每个结点一次， 则G中任意两个结点是相互可达的， 故G是强连通的。 例如， 图7 ― 17(a)中有一回路v1v2v3v1， 它包含图中所有结点。  

77 定义 7.4 ― 4 在有向图G＝（V， E）中， 设G′是G的子图。 若
2) G中没有包含G′的更大的子图是强连通的（单向连通的、 弱连通的）， 则称G′是G的强分图（单向分图、 弱分图）。 在图7 ― 18的有向图中， 因为结点v4与任何别的结点都不相互可达， 我们也称（｛v4｝， φ）是一个强分图。

78 图 7 ― 18 有向图示例

79 可以看出该有向图的强分图的集是： ｛（｛v1， v2， v3｝， ｛e1， e2， e3｝）， （｛v4｝， φ）， （｛v5｝， φ）， （｛v6｝， φ）｝ ； 单向分图的集是： ｛（｛v1， v2， v3， v4， v5｝， ｛e1， e2， e3， e4， e5｝）， （｛v5， v6｝， ｛e6｝）｝； 弱分图的集是： ｛（｛v1， v2， v3， v4， v5， v6｝， ｛e1， e2， e3， e4， e5， e6｝）｝。

80 若在结点集V上定义关系ρ为： viρvj当且仅当vi和vj在同一强（弱）分图中。 容易证明， ρ是一个等价关系。 这种等价关系把V中的结点分成若干个等价类， 等价类的集合是V上的一个划分。 每一个等价类的结点以及相应的边导出一个强（弱）分图。 由此有下面的定理。 定理 7.4 ― 5 在有向图G＝（V， E）中， G的每一个结点都在也只在一个强（弱）分图中。

81 *7.4.2 有向图的可达性 下面用矩阵来研究有向图的可达性。 与无向图一样， 有向图也能用相应的邻接矩阵 A＝（aij）表示， 其中 (否则) 但注意这里A不一定是对称的。

82 定义 7.4 ― 5 设G＝（V， E）是一个有n个结点的有向图， 则n阶方阵Ｐ＝（pij）称为图G的可达性矩阵。 其中
(vi到vj可达) (否则) 根据可达性矩阵， 可知图中任意两个结点之间是否 至少存在一条路以及是否存在回路。 由7.2节定理7.2 ― 1及其推论可知， 利用有向图的 邻接矩阵A， 分以下两步可得到可达性矩阵。

83 1) 令Bn＝A＋A2＋…＋An, 2) 将矩阵Ｂn中不为零的元素均改为１， 为零的元素不变， 所得的矩阵P就是可达性矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。

84 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。
因可达性矩阵是一个元素仅为１或０的矩阵（称为布尔矩阵）， 而在研究可达性问题时， 我们对于两个结点间具有路的数目并不感兴趣， 所关心的只是两结点间是否有路存在。 因此， 我们可将矩阵A， A2， …， An分别改为布尔矩阵A(1)， A(2)， …， A(n)。

85 定义 7.4 ― 6 集合｛0， 1｝中的二元运算∧和∨定义如下：
０∨０＝０ ０∨１＝１∨０＝１∨１＝１ １∧１＝１ １∧０＝０∧１＝０∧０＝０ 分别称∧、 ∨为布尔加和布尔乘运算。 定义 7.4 ― 7 两个布尔矩阵中， 若将矩阵运算中元素的相加和相乘均规定为布尔加和布尔乘， 则这种矩阵运算称为布尔矩阵运算， 相应的矩阵加法和乘法称为矩阵的布尔加∨和布尔乘∧。

86 由此有 A(2)＝A(1)∧A(1)＝A∧A A(3)＝A(2)∧A(1) …… A(n)＝A(n-1)∧A(1) P＝A(1)∨A(2)∨…∨A(n)

87 图7 ― 19 例1用图

88 例１ 求出图7 ― 19所示图的可达性矩阵。  解 该图的邻接矩阵为

89 故

90 定理 7.4 ― 3 有向图G是强连通的当且仅当其可达性矩阵P除主对角线外， 其它元素均为１。
下面介绍如何利用一个图的可达性矩阵， 求出这个图的强分图。 设P＝（pij）是图G的n阶可达性矩阵， P＇是P的转置矩阵， 定义矩阵运算PP′为

91

92 由定义， 如果从结点vi到vj是可达的， 则应有
pij＝１； 如果从结点vj到vi是可达的， 则应有pji＝１。 因此， 结点vi和vj是相互可达的， 当且仅当矩阵PP′的（i， j ）项元素（i≠j）pijpji＝１。 这样， 若矩阵PP′的第i行的非零元素在第j1， j2， …， jk列， 则结点vi， vj1， vj2， …， vjk为强连通子图的结点。 如对本节图7 ― 18的图可求出的可达性矩阵P为

93 由此也可求出该有向图的强分图点集是： ｛v1， v2， v3｝， ｛v4｝， ｛v5｝， ｛v6｝。

94 例２ 在操作系统中， 设在时刻t有多道程序P1， P2， …， Pm运行， 系统的资源r1， r2， …， rn被运行中的程序所占用。 若占用ri的程序Pk又对资源rj提出要求时， 则从结点ri出发引一条有向边与rj相连， 用n个结点r1， r2， …， rn分别表示n个资源， 这样得到有n个结点的有向图， 它是某一时刻机器内的资源分配状态图 。 例如有资源分配状态图如图7 ― 20所示， 对该图讨论“死锁”问题。

95 图7 ― 20 资源分配状态图

96 在该图中， P1占有 r1, 对r2， r3提出要求； P2占有r2, 对r3， r4提出要求； P3占有r3, 对r1， r4提出要求； P4占有r4, 对r1， r2提出要求。 这时资源r1， r2， r3， r4无法从被占有的状态中释放出来， 我们说此刻系统处于“死锁”状态。 可以看出， 当且仅当资源分配状态图G包含多于一个结点的强分图时， 系统才在t时刻发生“死锁”， 故可用前述的矩阵方法去识别是否包含多于一个结点的强分图， 从而检查出“死锁”状态。

97 7.5 欧拉图与哈密尔顿图 7.5.1 欧拉图 历史上的哥尼斯堡七桥问题是著名的图论问题。
7.5 欧拉图与哈密尔顿图 7.5.1 欧拉图 历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的： 18世纪的东普鲁士有个哥尼斯堡城， 在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥， 它们把河的两岸和两个岛连接起来（如图7 ― 21）。

98 每逢假日， 城中居民进行环城游玩， 人们对此提出了一个“遍游”问题， 即能否有这样一种走法， 使得从某地出发通过且只通过每座桥一次后又回到原地呢？
我们将图7 ― 21中的哥尼斯堡城的4块陆地部分分别标以A， B， Ｃ， D， 将陆地设想为图的结点， 而把桥画成相应的连接边， 这样图7 ― 21可简化成图7 ― 22。 于是七桥“遍游”问题等价于在图7 ― 22中， 从某一结点出发找到一条迹， 通过它的每条边一次且仅一次， 并回到原来的结点。

99 图 7 ― 21 哥尼斯堡七桥问题示图

100 图 7 ― 22 哥尼斯保七桥问题简化图

101 定义 7.5 ― 1 给定无孤立结点的图G， 若存在一条经过G中每边一次且仅一次的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。
例如， 给出如图7 ― 23所示的两个图， 容易看出， (a)是欧拉图， 而(b)不是欧拉图。

102 图 7 ― 23 图形示例

103 定理 7.5 ― 1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数（这样的结点称为偶度结点）。
证明 必要性： 设G是一欧拉图， α是G中的一条欧拉回路。 当α通过G的任一结点时， 必通过关联于该点的两条边。 又因为G中的每条边仅出现一次， 所以α所通过的每个结点必定是偶度结点。

104 图 7 ― 24 图G

105 充分性： 我们可以这样来作一个闭迹β， 假设它从某结点A开始， 沿着一条边到另一结点， 接着再从这个结点， 沿没有走过的边前进， 如此继续下去。 因为我们总是沿着先前没有走过的新边走， 又由于图G的边数有限， 所以这个过程一定会停止。 但是， 因为每一个结点都与偶数条边关联， 而当沿β前进到达结点v 时， 若v≠A， β走过了与v关联的奇数条边， 这样在v上总还有一条没有走过的边。 因此， β必定返回停止在A（见图7 ―24）。

106 如果β走遍了G的所有边， 那么我们就得到所希望的一条欧拉回路。 如果不是这样， 那么在β上将有某一结点B， 与它关联的一些边尚未被β走过（因G连通）。 但是， 实际上， 因为β走过了与B关联的偶数条边， 因此不属于β的与B关联的边也是偶数条。 对于其他有未走过边所关联的所有结点来说， 上面的讨论同样正确。 于是若设G1是G－β的包含点B的一个连通分支， 则G1的结点全是偶度结点。

107 运用上面的讨论， 我们在G1中得到一个从B点出发的一条闭迹β1。 这样我们就得到了一条更大的闭迹， 它是从A点出发沿β前进到达B， 然后沿闭迹β1回到B， 最后再沿β由B走到A。 如果我们仍然没有走遍整个图， 那么我们再次把闭迹扩大， 以此类推， 直到最后得到一个欧拉回路。 由于在七桥问题的图7 ― 22中， 有４个点是奇度结点， 故不存在欧拉回路， 七桥问题无解。

108 在图7 ― 23中， (a)图的每个结点的度数都为４， 所以它是欧拉图；(b)图不是欧拉图。 但我们继续考察(b)图可以发现， 该图中有一条路v2v3v4v5v2v1v5， 它经过(b)图中的每条边一次且仅一次， 我们把这样的路称为欧拉路。 定义7.5 ― 2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。 对于欧拉路有下面的判定方法。

109 定理7.5 ― 2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的奇度结点。
证明 将边(vi， vj)加于图G上， 令其所得的图为G′（可能是多重图）。 由定理7.5 ― 1知： G有连接结点vi和vj的欧拉路， iff G′有一条欧拉回路， iff G′的所有结点均为偶度结点， iff G的所有结点除vi和vj外均为偶度结点， iff vi和vj是G中仅有的奇度结点。

110 我国民间很早就流传一种“一笔画”游戏。 由定理7.5 ― 1和定理7.5 - 2知， 有两种情况可以一笔画。
1) 如果图中所有结点是偶度结点， 则可以任选一点作为始点一笔画完； 2) 如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点也可一笔画完。

111 例１ 图7 ― 25(a)是一幢房子的平面图形， 前门进入一个客厅， 由客厅通向4个房间。 如果要求每扇门只能进出一次， 现在你由前门进去， 能否通过所有的门走遍所有的房间和客厅， 然后从后门走出。

112 图 7 ― 25 例1用图

113 解 将4个房间和一个客厅及前门外和后门外作为结点， 若两结点有边相连就表示该两结点所表示的位置有一扇门相通。 由此得图7 ― 25(b)。 由于图中有4个结点是奇度结点， 故由定理7.5 ― 2知本题无解。 类似于无向图的结论， 对有向图有以下结果。

114 定理7.5 ― 3 一个连通有向图具有（有向）欧拉回路的 充要条件是图中每个结点的入度等于出度。 一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度， 但在这两个结点中， 一个结点的入度比出度大1， 另一个结点的入度比出度少1。 下面举一个有趣的例子是计算机鼓轮的设计。

115 例2 设一个旋转鼓的表面被分成２4个部分， 如图7 - 26所示。 其中每一部分分别由导体或绝缘体构成， 图中阴影部分表示导体， 空白部分表示绝缘体， 绝缘体部分给出信号0，导体部分给出信号1。 根据鼓轮转动后所处的位置， 4个触头a， b， c， d将获得一定的信息。 图中所示的信息为1101， 若将鼓轮沿顺时针方向旋转一格， 则4个触头a， b， c， d获得1010 。试问鼓轮上16个部分怎样安排导体及绝缘体， 才能使鼓轮每旋转一格后， 4 个触头得到的每组信息（共16组）均不相同？这个问题也即为： 把16个二进制数字排成一个环形， 使得4个依次相连的数字所组成的16个4位二进制数均不相同。

116 解 问题的答案是肯定的。 下面谈一下解决这个问题的思路。
设αi∈｛ 0， 1 ｝（i∈Ｎ16）。 每旋转一格， 信号从α1α2α3α4转到α2α3α4α5， 前者的右 3 位决定了后者的左 3 位。 于是， 我们的想法是将这16个二进制数字的环形α1α2…α16对应一个欧拉有向路， 使其边依次为α1α2α3α4， α2α3α4α5， α3α4α5α6， …（图7 ― 27）。 我们把α2α3α4对应一个结点， 它是弧α1α2α3α4的终点也是弧α2α3α4α5的始点。 这样我们的问题就转化为以３位二进制数为结点作一个有向图， 再在图中找出欧拉回路。

117 图 7 ― 26 例 2 用图

118 图 7 ― 27 欧拉有向路示图

119 构造一个有８个结点的有向图G（图7 ― 28）。 其结点分别记为３位二进制数000、 001、 010、 011、 100、 101、 110、 111。 从结点α1α2α3出发可引出两条有向边， 其终点分别是α2α3０和α2α3１， 记这两条有向边为α1α2α3０和α1α2α3１。 这样图G就有16条边。 由于G中每点的入度等于出度都等于２， 故在图中可找到一条欧拉回路。

120 例如（仅写出边的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。 根据邻接边的标号记法， 这16个二进制数可写成对应的二进制序列 ， 把这个序列排成环状， 与所求的鼓轮相对应， 如图7 ― 26所示。 该例可推广到鼓轮有n个触点的情况。

121 图 7 ― 28 具有 8 个结点的有向图G

122 7.5.2 哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。 它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏： 能否在图7 ― 29中找到一个回路， 使它含有图中所有结点一次且仅一次？ 若把每个结点看成一座城市， 连接两个结点的边看成是交通线， 那么这个问题就变成能否找到一条旅行路线， 使得沿着该旅行路线经过每座城市恰好一次， 再回到原来的出发地呢？为此， 这个问题也被称作周游世界问题。

123 图 7 ― 面体游戏示图

124 对图7 ― 29， 图中粗线给出了这样的回路。 定义 7.5 ― 3 给定图G， 若有一条路通过G中每个结点恰好一次， 则这样的路称为哈密尔顿路；若有一个圈， 通过G个每个结点恰好一次， 这样的圈称为哈密尔顿回路（或哈密尔顿圈）。 具有哈密尔顿回路的图称为哈密尔顿图。 尽管哈密尔顿回路与欧拉回路问题在形式上极为相似， 但是到目前为止还不知道一个图为哈密尔顿图的充要条件， 寻找该充要条件仍是图论中尚未解决的主要问题之一。 下面先给出一个简单而有用的必要条件。

125 定理7.5 ― 4 设图G＝（V， E）是哈密尔顿图， 则对于V的每个非空子集S， 均有
W（G－S）≤|S| 成立， 其中W（G－S）是图G－S的连通分支数。

126 证明 设α是G的哈密尔顿回路， S是V的任一非空子集。 在G－S中， α最多被分为|S|段， 所以
W（G－S）≤|S| 利用本定理可判别某些图不为哈密尔顿图。 如在图7 ― 30中， 若取S＝｛v1， v4｝， 则G－S有 3 个连通分支， 故该图不是哈密尔顿图。 判断哈密尔顿图的充分条件很多， 我们仅介绍其中一个。

127 图7 ― 30 图形示列

128 定理 7.5 ― 5 设G＝（V， E）是有n个结点的简单图，
1） 如果任两结点u， v∈V， 均有deg(u)＋deg(v)≥ n－1， 则在G中存在一条哈密尔顿路； 2） 如果对任两结点u， v∈V， 均有deg(u)＋deg(v)≥ n， 则G是哈密尔顿图。 证明 略。

129 例３ 某地有５个风景点。 若每个景点均有两条道路与其他景点相通， 问是否可经过每个景点恰好一次而游完这５处？
解 将景点作为结点， 道路作为边， 则得到一个有５个结点的无向图。 由题意， 对每个结点vi， 有deg(vi)＝2（i∈Ｎ5）。 则对任两点vi， vj（i， j∈Ｎ5）均有 deg(vi)＋deg(vj)＝2＋2＝4＝5－1 可知此图一定有一条哈密尔顿路， 本题有解。 我们再通过一个例子， 介绍一个判别哈密尔顿路不存在的标号法。

130 例４ 证明图7 ― 31所示的图没有哈密尔顿路。 证明 任取一结点如v1， 用A标记， 所有与它相邻的结点标B。 继续不断地用A标记所有邻接于B的结点， 用B标记所有邻接于A的结点， 直到图中所有结点全部标记完毕。 如果图中有一条哈密尔顿路， 则必交替通过结点A和B。 因此或者结点A和B数目一样， 或者两者相差１个。

131 图7 ― 31 例４用图

132 而本题有３个结点标记A， ５个结点标记B， 它们相差２个， 所以该图不存在哈密尔顿路。
作为哈密尔顿回路的自然推广是著名的货郎担问题。 问题是这样叙述的： 设有一个货郎， 从他所在的城镇出发去n－１个城镇。 要求经过每个城镇恰好一次， 然后返回原地， 问他的旅行路线怎样安排才最经济？从图论的观点来看， 该问题就是： 在一个有权完全图中找一条权最小的哈密尔顿回路。

133 研究这个问题是十分有趣且有实用价值的。 但很可惜， 至今没有找到一个很有效的算法。
当然我们可以用枚举法来解， 但是当完全图的结点较多时， 枚举法的运算量在计算机上也很难实现。 下面介绍的“最邻近方法”给出了问题的近似解。 最邻近方法的步骤如下： 1) 由任意选择的结点开始， 找与该点最靠近（即权最小）的点， 形成有一条边的初始路径。

134 图 7 ― 32 例 5 用图

135 2) 设ｘ表示最新加到这条路上的结点， 从不在路上的所有结点中选一个与ｘ最靠近的结点， 把连接ｘ与这一结点的边加到这条路上。 重复这一步， 直到G中所有结点包含在路上。
3) 将连接起始点与最后加入的结点之间的边加到这条路上， 就得到一个圈， 即为问题的近似解。

136 例５ 某流动售货员居住在ａ城， 为推销货物他要访问ｂ， ｃ， d城后返回ａ城。 若该４城间的距离如图7 ― 32所示， 试用最邻近方法找出完成该旅行的最短路线？
解 按最邻近方法一共有４步， 见图7 ― 33。 得到的总距离为46。

137 图 7 ― 33 例 5 题解用图

138 树 树是图论中的一个重要概念。 早在1847年克希霍夫就用树的理论来研究电网络， 1857年凯莱在计算有机化学中Ｃ2H2n+2的同分异构物数目时也用到了树的理论。 而树在计算机科学中应用更为广泛。 本节介绍树的基本知识， 其中谈到的图都假定是简单图。

139 7.6.1 树 定义 7.6 ― 1 一个连通无圈图称为树。 树中度数为1的结点称为树叶（或终端结点）， 度数大于１的结点称为分枝点（或内点， 或非终端结点）。 一个无圈图称为森林。   显然若图G是森林， 则G的每个连通分支是树。 如图 7 ― 34(a)图所示的是一棵树；(b)图所示的是森林。

140 图 7 ― 34 树和森林示意图

141 定理 7.6 ― 1 一个（n, m）图G是树的充分必要条件是G连通且m＝n－1。
证明 必要性： 设G是树， 则G自然连通。 只需证明m＝n－1。 对n用归纳法。 当n＝１时， 定理显然成立。 假设定理对n－1个结点的树已经证明。 则对n个结点的树G， 由树的定义知， G至少有一片树叶， 设为a。 令G′＝G－｛a｝， 则G′是一个有n－1 个结点的树。

142 根据归纳假设， G′的边数m′＝n－2， 而G′的边数比G的边数少１， 则G的边数
m＝m′＋1＝(n－2)＋1＝n－1 充分性： 与证明必要性类似， 也是对n用归纳法。 我们把此证明留给读者。

143 定理 7.6 ― 2 设Ｔ是一棵（n， m）树， 则T有如下性质：
1) T中去掉任意一条边后， 所得的图G是不连通的。 2) T中每一对结点间有且仅有一条通路相连。 3) 在T中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个圈。 4) 若树Ｔ的结点数n≥２， 则T至少有两片树叶。

144 证明 1) 如果G是连通的， 那么G仍是树。 由定理7.6 ― 1知， G有n－1条边， 即与T的边数相同， 矛盾。
2) 因为T连通， 由定理7.2 ― 1知， T的任一对结点u、 v之间有一条通路相连。 若u、 v间通路不唯一， 则T中必有圈， 与树的定义矛盾。 所以仅有一条通路连接u与v。   3) 设在T中添加新边（u， v）。 由于T连通， 故在T中u与v之间存在一条通路， 它与新边（u， v）一起构成一个圈Ｃ。 若添加新边（u， v）于T后有两个圈Ｃ1与Ｃ2， 则在T中有两条连接u到v的通路， 与2)矛盾。

145 4) 因为 T是一棵n≥２的（n， m）树， 所以由定理7.1 ― 1和定理7.6 ― 1， 有
(1) 若T中的树叶少于两片， 则T中至少有n－1个结点 的度数不少于2。所以 (2)

146 (1)， (2)矛盾。 故T至少有两片树叶。 由定理7.6 ― 2所刻画的树的特征可见： 在结点数给定的所有图中， 树是边数最少的连通图， 也是边数最多的无圈图。 由此可知， 在一个（n， m）图G中， 若m＜n－1， 则G是不连通的； 若m＞n－1， 则G必定有圈。

147 7.6.2 生成树与最小生成树 定义 7.6 ― 2 若连通图G的生成子图是一棵树， 则称该树是G的生成树， 记为TG。 生成树TG中的边称为树枝。 图中其他边称为TG的弦。 所有这些弦的集合称为TG的补。 如图7 ― 35中(b)、 (c)所示的树T1、 T2是(a)图的生成树， 而(d)所示的树T3不是(a)图的生成树。 一般的， 图的生成树不唯一。

148 图 7 ― 35 图和树示例

149 考虑生成树T1， 可知e1， e2， e3， e4是T1的树枝， e5， e6， e7是T1的弦， 集合｛e5， e6， e7｝是T1的补。 生成树有其一定的实际意义。
例１ 某地要兴建５个工厂， 拟修筑道路连接这５处。 经勘测其道路可依如图7 ― 35(a)图的无向边铺设。 为使这５处都有道路相通， 问至少要铺几条路？ 解 这实际上是求G的生成树的边数问题。 一般情况下， 设连通图G有n个结点， m条边。 由树的性质知， T有n个结点， n－1条树枝， m－n＋1条弦。 在图7 ― 35(a)中， n＝5， 则n－1＝5－1＝4， 所以至少要修４条路才行。

150 定义 7.6 ― 3 设G＝（V， E）是一连通的有权图， 则G中具有最小权的生成树TG称为G的最小生成树。 求最小生成树问题是有实际意义的。
如要建造一个连接若干城市的铁路网络， 已知城市vi和vj之间直达铁路的造价， 设计一个总造价为最小的铁路网络， 就是求最小生成树TG。 下面介绍求TG的克鲁斯克尔（Kruskal)算法。

151 此方法又称为“避圈法”。 其要点是， 在与已选取的边不成圈的边中选取最小者。 具体步骤如下：
1) 在G中选取最小权边， 置边数i＝1。 2) 当i＝n－1时， 结束。 否则， 转3)。   3) 设已选择边为 e1， e2， …， ei， 在G中选取不同于e1， e2， …， ei的边ei+1， 使｛e1， e2， …， ei， ei+1｝无圈且ei+1是满足此条件的最小权边。 4) 置i为i＋1， 转2)。

152 例２ 求图7 ― 36(0)中有权图的最小生成树。 解 因为 图中n＝8， 所以按算法要执行n－1＝7次， 其过程见图7 ― 36中(1)~(7)。

153 图 7 ― 36 例 2 题解示例

154 7.7 根树及其应用 7.7.1 根树、 有序树、 M叉树 定义 7.7 ― 1 一个有向图， 若不考虑边的方向， 它是一棵树， 则这个有向图称为有向树。 一棵有向树， 如果恰有一个结点的入度为０， 其余所有结点的入度都为１， 则称为根树， 其中入度为０的结点称为根， 出度为０的结点称为叶， 出度不为０的结点称为分枝点或内点。

155 如图7 ― 37(a)表示一棵根树， 其中v1为根， v1， v2， v3为分枝点， 其余结点为叶。 习惯上我们把根树的根画在上方， 叶画在下方。 这样就可以省去根树的箭头， 如图7 - 37(b)。 在根树中， 称从树根到结点v的距离为该点的层次。 这样对图7 ― 37中的根树， v1的层次为０， v2、 v3的层次为１， 其余结点的层次均为２。 我们用家族关系表示根树中各结点的关系。

156 图 7 ― 37 根树示例

157 定义 7.7 ― 2 在根树中， 若从vi到vj可达， 则称vi是vj的祖先， vj是vi的后代； 又若〈vi， vj〉是根树中的有向边， 则称vi是vj的父亲， vj是vi的儿子； 如果两个结点是同一结点的儿子， 则称这两个结点是兄弟。 定义 7.7 ― 3 在根树中， 任一结点v及其v的所有后代和从v 出发的所有有向路中的边构成的子图称为以v为根的子树。 根树中的结点u的子树是以u的儿子为根的子树。   在现实的家族关系中， 兄弟之间是有大小顺序的， 为此我们又引入有序树的概念。

158 定义 7.7 ― 4 如果在根树中规定了每一层次上结点的次序， 这样的根树称为有序树。 我们在有序树中规定同一层次结点的次序是从左至右。 在树的实际应用中， 我们经常研究完全ｍ叉树。
定义 7.7 ― 5 在根树中， 若每个结点的出度小于或等于ｍ， 则称这棵树为ｍ叉树。 如果每个结点的出度恰好等于０或ｍ， 则称这棵树为完全ｍ叉树。 二叉树的每个结点v 至多有两棵子树， 分别称为v的左子树和右子树。

159 图 7 ― 38 例 1 用图

160 例１ 甲、 乙两人进行球赛， 规定三局两胜。 图3 - 28 表示了比赛可能出现的各种情况（图中结点标甲者表示甲胜， 标乙者表示乙胜）， 这是一棵完全二叉树。

161 定理 7.7 ― 1 在完全m叉树中， 若树叶数为ｔ， 分枝数为ｉ， 则
证明 由假设知， 该树有ｉ＋ｔ个结点， 由定理7.6 ― 1知， 该树边数为ｉ＋ｔ－１。 因为所有结点出度之和等于边数所以根据完全m叉树的定义知， 有 mｉ＝ｉ＋ｔ－１ 即 （m－１）ｉ＝ｔ－１

162 例２ 假设有一台计算机， 它有一条加法指令， 可计算 3 个数之和。 如果要求 9 个数x1， x2， …， x9之和， 问至少要执行几次加法指令？
解 用 3 个结点表示 3 个数， 把 9 个数看成树叶， 将表示 3 数之和的结点作为它们的父亲结点。 这样本问题可理解为求一个完全三叉树的分枝点的个数问题。

163 由定理7.7 ― 1知， 有 （３－１）ｉ＝９－１ 得 ｉ＝４ 所以要执行 4 次加法指令。 图7 ― 39表示了两种可能的顺序。

164 图 7 ― 39 例 2 用图

165 例３ 8 枚硬币问题。 若有 8 枚硬币a， b， c， d， e， f， g， h， 其中 7 枚重量相等， 只有 1 枚稍轻。 现要求以天平为工具， 用最少的比较次数挑出轻币来。
  解 可用图7 ― 40所示的树表示判断过程。 从图中可知， 只需称 2 次即可挑出轻币。 这种用于描述判断过程的树叫判定树。

166 图 7 ― 40 例 3 用图

167 7.7.2 二叉树 m叉树中， 应用最广泛的是二叉树。 由于二叉树在计算 机中最易处理， 所以常常要把一棵有序树转换为二叉树。 其一般步骤为： (1) 从根开始， 保留每个父亲与其最左边儿子的连线， 撤消与别的儿子的连线； (2) 兄弟间用从左向右的有向边连接； (3) 用如下方法选定二叉树的左儿子和右儿子： 直接处于给定结点下面的结点作为左儿子； 对于同一水平线上与给定结点右邻的结点作为右儿子， 依次类推。

168 例４ 将图7 ― 41(a)所示的三叉树转换为一棵二叉树。
解 对(a)图进行步骤(1)、 (2)得(b)图， 再按步骤(3)得(c)图。 图 中的(c)即为所求的二叉树。 反过来， 我们也可将(c)图还原为(a)图。 一个森林也可转换为二叉树。 其步骤为： (1) 先把森林中的每一棵树表示成一棵二叉树； (2) 除第一棵二叉树外， 依次将每棵二叉树作为左边二叉树的根的右子树， 直到所有的二叉树都连成一棵二叉树为止。

169 图 7 ― 41 例 4 用图

170 例５ 将图7 ― 42(a)所示的森林转换为一棵二叉树。
解 如图 7 ― 42(b)的二叉树即为所求。 反过来， 我们也可将二叉树转换成森林。 对于二叉树， 一个十分重要的问题是要找到一些方法， 能系统地访问树的结点， 使得每个结点恰好被访问一次， 这就是二叉树的遍历问题。 反过来， 我们也可将二叉树转换成森林。

171 图 7 ― 42 例 5 用图

172 对于二叉树， 一个十分重要的问题是要找到一些方法， 能系统地访问树的结点， 使得每个结点恰好被访问一次， 这就是二叉树的遍历问题。
下面介绍二叉树的 3 种常用的遍历方法。 １. 先根次序遍历法， 分 3 步。 (1) 访问根； (2) 按先根次序遍历根的左子树； (3) 按先根次序遍历根的右子树。

173 ２. 中根次序遍历法， 分 3 步。 (1) 按中根次序遍历根的左子树； (2) 访问根； (3) 按中根次序遍历根的右子树。 ３. 后根次序遍历法， 分 3 步。 (1) 按后根次序遍历根的左子树； (2) 按后根次序遍历根的右子树； (3) 访问根。

174 例６ 对图7 ― 43 所示的二叉树， 写出 3 种遍历方法得到的结点次序。
解 先根次序遍历为v1v2v4v6v7v3v5v8v9v10v11v12； 中根次序遍历为v6v4v7v2v1v8v5v11v10v12v9v3； 后根次序遍历为v6v7v4v2v8v11v12v10v9v5v3v1。 对一棵树的遍历有两种方法， 即先根次序遍历和后根次序遍历。 我们以图7 ―41(a) 和相应的二叉树(c)为例讨论如下：

175 图7 ― 二叉树

176 (a)的先根次序遍历的结果为v1v2v5v6v3v4v7v9v10v11v8；
(c)的先根次序遍历的结果也为v1v2v5v6v3v4v7v9v10v11v8； (a)的后根次序遍历的结果为v5v6v2v3v9v10v11v7v8v4v1； (c)的中根次序遍历的结果也为v5v6v2v3v9v10v11v7v8v4v1。

177 比较以上结果可以看出： (1) 树的先根次序正是相应二叉树的先根次序； (2) 树的后根次序正是相应二叉树的中根次序。 该结果具有普遍的意义。

178 定义 7.7 ― 6 在根树中， 一个结点的通路长度， 就是从树根到此结点通路的边数。 我们把分枝点的通路长度称为内部通路长度； 树叶的通路长度称为外部通路长度。 树中最长通路长度称为树的高度。
内部通路长度和外部通路长度有如下的关系。

179 定理 7.7 ― 2 若完全二叉树有n个分枝点，且内部通路长度总和为Ｉ， 外部通路长度总和为E， 则
E＝Ｉ＋２n 本定理可通过对分枝点数目n进行归纳证明， 请读者自证。

180 7.7.3 二叉树在计算机中的应用 １. 表达式的波兰表示法和逆波兰表示法 利用二叉树可以表示算术表达式。 其方法是： 将表达式的运算符（在计算机中分别以“＋”、 “－”、 “*”、 “／”、 “↑”表示加、 减、 乘、 除、 乘方运算）作为分枝结点， 将运算量（常数和变量等）作为叶结点画出二叉树。

181 图 7 ― 44 例 7 用图

182 例７ 将下面的算术表达式用二叉树表示   解 原表达式可写成ａ*（ａ＋２*ｂ）／（６*ｂ－ｃ）。 对应的二叉树如图7 ― 44。 对本题二叉树的 3 种遍历， 结果如下： 先根次序遍历为／*ａ＋ａ*２ｂ－*６ｂｃ； 中根次序遍历为ａ*ａ＋２*ｂ／６*ｂ－ｃ； 后根次序遍历为ａａ２ｂ*＋*６ｂ*ｃ－／。

183 把这 3 种结果与原表达式对照， 可以发现， 中根次序遍历的结点序列没有括号， 因此这种表示会产生二义性。 而先根次序遍历的结点序列恰好是把表达式中的运算符写在两运算量前， 这种表示方法称为表达式的前缀表示法， 也称为波兰表示法。 同样地， 后根次序遍历的结点序列恰好是把表达式中的运算符写在两运算量后， 这种表示方法称为表达式的后缀表示法， 也称为逆波兰表示法。 这后两种表示法都能正确的计算表达式。

184 ２. 最优树 定义 7.7 ― 7 设有一棵二叉树， 有ｔ片树叶。 使其树叶分别带权w1， w2， …， wt的二叉树称为带权的二叉树。 定义 7.7 ― 8 设有一棵带权w1， w2， …， wt的二叉树。 若权为wi的树叶， 其通路长度为Ｌ（wi）。 1) 该带权二叉树的权W（T）定义为

185 2) 在所有带权w1， w2， …， wt的二叉树中， W（T）最小的树称为最优树。
最优树问题源于计算机科学、 生产管理等领域。 简单举一个例子。 用机器分辨一些币值为１分、 ２分、 ５分的硬币， 假设各种硬币出现的概率分别为0.5， 0.4， 0.1。 问如何设计一个分辨硬币的算法， 使所需时间最少（设每作一次判别所用的时间相同， 以此为一个单位时间）？这个问题就是构造一个有 3 片树叶的最优树问题。

186 1952年哈夫曼给出了求带权w1， w2， …， wt的最优树的方法。 先假设w1≤w2≤…≤wt。 哈夫曼算法的关键是： 从带权w1＋w2， w3…， wt的最优树T′中得到带权w1， w2， …， wt的最优树。 其依据是下面两个定理。

187 定理 7.7 ― 3 设T是带权w1， w2， …， wt的最优树， 则
*证明 设ｖ是T中内点的通路长度最长的结点， 不妨设ｖ的儿子分别带权wx和wy， 这时有 L（wx）≥ L（w1）， L（wy）≥L（w2）。

188 由于T是最优树， 必有L（wx）≤L（w1），
L（wy）≤L（w2）。 否则， 将wx和w1或w2对调， 将产生更小权的树， 与T是最优树矛盾。 所以 L（w1）＝L（w2）＝L（wx）＝L（wy） 此时， 将w1， w2和wx， wy对调， 得到带权w1， w2的树叶 ， 是兄弟的最优树， 且结点 ， 的通路长度等于树高。

189 定理 7.7 ― 4 设T′是带权w1＋w2， w3， …， wt（w1≤w2≤…≤wt）的二叉树， 则T′是最优树的充要条件是： 将T′中权为w1＋w2的叶子用子树
代替得到的新树T为带权w1 w2w1， w2， …， wt的最优树。

190 证明 略。 根据这个定理， 构造具有ｔ片叶子的最优树问题， 可以归结为构造具有ｔ－１片叶子的最优树问题； 而构造具有ｔ－１片叶子的最优树问题又可以归结为构造具有ｔ－２片叶子的最优树问题； 依次类推， 最后归结为构造具有２片叶子的最优树问题。 现在可以解决设计一个分辨硬币的算法问题。 实际上该问题归结为求带权 0.1， 0.4， 0.5的最优树问题。 答案的图示见图7 ― 45或图7 ― 46。 所需时间为 2×0.1＋2×0.4＋2×0.5＝1.5（单位时间）。

191 图 7 ― 45 分辨硬币的算法示意图(一)

192 图 7 ― 46 分辨硬币的算法示意图(二)

193 例８ 求带权7， 8， 9， 12， 16的最优树。 解 全部过程见图7 ― 47(a)～(d)。

194 图7 ― 47

195 ３. 前缀码 在通讯中， 常用０和１的字符串表示字符来传递信息。 用不等长的二进制数序列表示26个英文字母时， 其长度为１的二进制数序列最多有２个， 长度为２的二进制数序列最多有２2个， 依次类推。 由于２＋２2＋２3＋２4＝30＞26， 所以， 用长度不超过４的二进制数序列就可表达26个不同的英文字母。 为使代码总长尽可能短， 我们用较短的序列表示使用频繁的字母。 为避免二义性， 我们常常使用前缀码。

196 定义 7.7 ― 9 由０和１的字符串组成的集合叫前缀码， 其中集合的每个元素（字符串）都不是另一个元素的前缀（即左子串）。
例如， 集合｛00， 10， 11， 010， 011｝是一个前缀码， 而集合 ｛00， 01， 001｝不是前缀码， 因为00是001的前缀。 

197 给定一棵二叉树， 对每个分枝点引出的左侧的边标记０， 右侧的边标记１。 这样， 由树根到每一树叶的通路上， 有由各边的标号组成的序列， 它是仅含０和１的二进制数串。 显然， 任一树叶对应的二进制数串都不是其它树叶对应的二进制数串的前缀。 所以， 任一二叉树的树叶集合对应一个前缀码。 我们还可证明， 任何一个前缀码对应一棵二叉树。 下面以例说明。

198 例９ 给出与前缀码｛00， 10， 11， 010， 011｝对应的二叉树。
解 因为该前缀码中最长序列长为３， 我们如图7 ― 48(a) 作一个高度为３的二叉树。 对二叉树中对应前缀码中序列的结点用方框标记， 删去标记结点的所有后代和边得到所求的二叉树如图7 ― 48(b)所示。

199 图 7 ― 48 例 9 用图

200 对26个英文字母， 设各字母使用的频率分别为p1， p2， …， p26， 求出带权p1， p2， …， p26的最优树， 从而解决最佳编码问题。

201 7.8 偶 图 与 匹 配 7.8.1 偶图 定义 7.8 ― 1 若无向图G＝（V， E）的结点集V能划分为两个子集V1和V2， 使G中每条边具有形式（ｖi， ｖj）， 其中ｖi∈V1， ｖj∈V2， 则称G为二部图或偶图。

202 这时V1和V2称为偶图G的互补结点子集。 偶图也可记为G＝（V1， E， V2）。
由定义知， 偶图G＝（V1， E， V2）中， 没有两个端点全在V1或全在V2的边, 故偶图没有自回路。

203 定义 7.8 ― 2 在偶图G＝（V1， E， V2）中， 若V1的每个结点都与V2的每个结点邻接， 则称G为完全偶图或完全二部图， 记为Km,n， 其中m＝|ｖi|， n＝|V1|。
图7 ― 49给出了偶图G和完全偶图K2,3、 K3,3。 在G中V1＝｛ｖ1， ｖ2， ｖ3｝， V2＝｛ｖ4， ｖ5， ｖ6， ｖ7｝。

204 图 7 ― 49 偶图G以及完全偶图K 2,3 、 K 3,3

205 定理 7.8 ― 1 无向图G＝（V， E）为偶图的充要条件是G的所有回路的长均为偶数。
证明 必要性：　设G是偶图且G＝（V1， E， V2）。 令Ｃ＝ｖ0ｖ1…ｖkｖ0是G的一个回路， 其长为ｋ＋１。 不失一般性， 假定ｖ0∈V1， 则由偶图的定义知， ｖ1∈V2， ｖ2∈V1。

206 由此推出， ｖ2i∈V1且ｖ2i+1∈V2。 又因为ｖ0∈V1， 所以ｖk∈V2， 因而ｋ为奇数， 故Ｃ为偶数长。 充分性: 不妨设G是连通图， 并设G中每个回路长度均为偶数。 任选ｖ0∈V， 定义V的两个子集V1和V2为 V1＝｛ｖi|d（ｖi， ｖ0）为偶数｝ V2＝V－V1 现在证明V1中任两结点间无边存在。

207 假若存在一条边（ｖi， ｖj）∈E， 其中ｖi，
ｖj∈V1， 则由ｖ0到ｖi间的短程（偶数长）， 边（ｖi， ｖj）和ｖj到ｖ0间的短程（偶数长）所组成的回路的长为奇数， 与假设矛盾。 同理可证V2中任两结点间无边存在。 故G中的每条边必具有形式（ｖi， ｖj）， 其中ｖi∈V1， ｖj∈V2， 即G是具有互补结点子集V1和V2的一个偶图。

208 7.8.2 匹配 与偶图紧密相连的是匹配问题。 定义 7.8 ― 3 设无向图G＝（V， E）， G中有边集ME， 且在Ｍ中任意两条边都没有公共的端点， 称边集Ｍ为图G的一个匹配。 图G的所有匹配中， 边数最多的匹配称为最大匹配。

209 例１ 如图7 ― 50中， 图(b)和(c)中的粗线分别表示了图(a)的两个匹配M1和M2。
（ｖ5， ｖ6）｝ 由定义知，M2是图的最大匹配， 而M1不是图的最大匹配。 求最大匹配要用到交错路与可扩路的概念。

210 图 7 ― 50 例 1 用图

211 *定义 7.8 ― 4 设M是G＝（V， E）的匹配。 1) 其边在M和E－M中交错出现的路称为G的M交错路。 2) 其起点和终点都不与M中的边相关联的G的M交错路称为G的M可扩路。 在图7 ― 50(b)中， 对匹配M1而言， 路ｖ1ｖ2ｖ3是一个M1交错路， 而ｖ3ｖ4ｖ5ｖ6是一个M1可扩路。

212 因为在一个M可扩路中， 不在M中的边数比在M中的边数多１。 如果在这条路中把属于M中的边从匹配中去掉， 把不属于M中的边添入到匹配中， 则得到新的匹配M1的边集比M多１。 例如图7 ― 50(b)中匹配M1变成图7 ― 50(c)中匹配M2后|M1|＝２， |M2|＝２＋１＝３。 如果图中还存在可扩路， 再按上面的步骤做， 所得到的匹配的边数又多１， 一直到图G中不存在可扩路为止。 可以想像， 这样做下去将得到最大匹配。 这就是下面的定理。

213 定理 7.8 ― 2 图G的匹配M是最大匹配， 当且仅当图G中不存在关于M的可扩路。 证明 略。
求一般图的最大匹配过程比较复杂， 下面仅讨论如何在偶图中求最大匹配的问题。 设偶图G＝（V1， E， V2）， 在G中求最大匹配的关键是寻找可扩路。 通常是在有了一个匹配M以后， 我们先看看V1中有没有与M的边关联的点。 如果没有， 那么M肯定是最大匹配了；如果有， 我们就从这些点出发来找出它们中以某点为端点的M可扩路。 找M可扩路我们采用标记法， 其过程如下：

214 首先在G中作一个匹配M， 把V1中所有不是M的边的端点用（*）加以标记， 然后交替地进行以下步骤１）和２）。
１） 选一个V1的新标记过的结点， 比如ｘi， 用（ｘi）标记不通过在M中的边与ｘi邻接且未标记过的V2的所有结点。 对V1所有新标记过的结点重复这一过程。   ２） 选一个V2的新标记过的结点， 比如ｙj， 用（ｙj）标记通过M中的边与ｙj邻接且未标记过的V1的所有结点。 对V2所有新标记过的结点重复这一过程。

215 执行以上步骤， 直至标记到一个V2的不与M中任何边关联的结点， 从该结点倒向追踪到标记有（
执行以上步骤， 直至标记到一个V2的不与M中任何边关联的结点， 从该结点倒向追踪到标记有（*）的结点， 就出现一个M可扩路。 可按上述方法得到一个边数为|M|＋１的匹配， 再返回１）。 如果已不可能标记更多的结点， 而V2的所有标记的结点均与M的边关联， 则说明G中已不存在M可扩路， 这时M就是最大匹配。

216 图7 ― 51图

217 例２ 如图7 ― 51图(a)， 求其最大匹配。 解 取图7 ― 51图(a)的一个匹配M＝｛(ｘ3， ｙ1)， (ｘ5， ｙ2)｝。 对图(a)用标记法得到一条M可扩路ｘ2ｙ2ｘ5ｙ3， 由此得匹配M1＝｛(ｘ2， ｙ2)， (ｘ3， ｙ1)， (ｘ5， ｙ3)｝。 对匹配M1再用标记法（见图7 ― 51(b)）知， 图中已不存在M1可扩路， 所以M1就是最大匹配。

218 7.9 平面图与欧拉公式 7.9.1 平面图 先从一个简单的例子谈起。 一个工厂有 3 个车间和 3 个仓库。 为了工作需要， 车间与仓库之间将设专用的车道。 为避免发生车祸， 应尽量减少车道的交叉点， 最好是没有交叉点， 这是否可能？

219 如图7 ― 52(a)所示， A， B， Ｃ是 3 个车间，M， Ｎ， P是 3 座仓库。 经过努力表明， 要想建造不相交的道路是不可能的， 但可以使交叉点最少（如图7 ― 52(b)）。 这些实际问题涉及到平面图的研究。 近年来， 由于大规模集成电路的发展， 也促进了平面图的研究。

220 如图7 ― 52(a)所示， A， B， Ｃ是 3 个车间，M， N， P是 3 座仓库。 经过努力表明， 要想建造不相交的道路是不可能的， 但可以使交叉点最少（如图7 ― 52(b)）。
这些实际问题涉及到平面图的研究。 近年来， 由于大规模集成电路的发展， 也促进了平面图的研究。

221 图 7 ― 52 图形示例

222 定义 7.9 ― 1 设无向图G＝（V， E）， 如果能把G的所有结点和边画在平面上， 使得任何两条边除公共结点外没有其他的交点， 则称G是一个平面图。
应当注意， 有些图从表面上看， 它的某些边是相交的， 但是不能就此肯定它不是平面图。 如图7 ― 53(a)表面上看有几条边相交， 但是把它画成图7 ― 53(b)， 则可以看出它是一个平面图。

223 图 7 ― 53 平面图示例

224 显然， 当且仅当一个图的每个连通分支都是平面图时， 这个图是平面图。 所以， 在研究平面图性质时， 只要研究连通的平面图就可以了。 故我们约定在本节中所讨论的图均为连通图。

225 定义 7.9 ― 2 设G是一个连通平面图， 由图中的边所包围的区域， 其内部不包含图的交点， 也不包含图的边， 称为G的一个面， 包围该面的诸边所构成的回路称为这个面的边界。
面的概念也可以用下面形象的说法加以描述： 假设我们把一个平面图画在平面上， 然后用一把小刀， 沿着图的边切开， 那么平面就被切成许多块， 每一块就是图的一个面。 更确切地说， 平面图的一个面就是平面的一块， 它用边作边界线， 且不能再分成更小的块。

226 图 7 ― 54 有限面和无限面示例

227 如图7 ― 54的图有７个结点、 ８条边， 它把平面分成三个面： r1， r2， r3。 其中r2由回路ｖ1ｖ4ｖ7ｖ1 所围， 而r1由回路ｖ1ｖ2ｖ3ｖ4ｖ5ｖ6ｖ5ｖ4ｖ1所围。 另外还有一个面r3在图形之外， 称为无限面。 一般地说， 如果一个面的面积是有限的， 称该面为有限面； 否则， 称为无限面。 显然， 平面图恰有一个无限面。

228 图7 ― 54中， r1和r2是有限面， r3是无限面。 定义 7.9 ― 3 平面图的面r的边界的回路长度称为该面的次数， 记为deg(r)。 图7 ― 54中， deg(r1)＝８， deg(r2)＝３， deg(r3)＝５。

229 定理 7.9 ― 1 一个平面图， 面的次数之和等于其边数的两倍。
证明 因任何一条边， 或者是两个面的公共边， 或者是在一个面中作为边界被重复计算两次。 故面的次数之和等于其边数的两倍。 如在图7 ― 54中， ， 这正好是边数８的两倍。

230 7.9.2 欧拉公式 1750年欧拉发现， 任何一个凸多面体， 若有n个顶点、 m条棱和r个面， 则有n－m＋r＝２。 这个定理也可以推广到平面图上来。 定理 7.9 ― 2 设有连通平面图G， 它共有n个结点、 m条边和r个面， 则有欧拉公式 n－m＋r＝２ 证明 我们对G的边数m进行归纳。

231 若m＝０， 由于G是连通图， 故必有n＝１。 这时只有一个无限面， 即r＝１。
所以有 n－m＋r＝１－０＋１＝２。 若m＝１， 这时有两种情况： 1) 该边是自回路， 则有n＝１， r＝２。 所以 n－m＋r＝１－１＋２＝２。 2) 该边不是自回路， 则有n＝２， r＝１。 所以 n－m＋r＝２－１＋１＝２。 假设对小于m条边的所有图， 欧拉公式成立。 现考虑m条边的图G， 设它有n个结点。 

232 我们分两种情况讨论： 1) 若G是树， 那么m＝n－１， 这时r＝１。 所以 n－m＋r＝n－（n－１）＋１＝２ 2) 若G不是树， G中必有圈， 设ａ是某圈的一条边， 则图G－｛ａ｝仍是连通平面图， 它有n个结点、 m－１条边和r－１个面， 按归纳假设知 n－（m－１）＋（r－１）＝２ 整理得 n－m＋r＝２ 所以对m条边的连通平面图， 欧拉公式也成立。

233 定理 7.9 ― 3 设G是一个有n个结点m条边的简单连通平面图， 若n≥３， 则有
证明 设G有ｋ个面， 因为每个面至少由３条边围成， 所以G的各面次数之和 由定理7.9 ― 1知， ２m≥3ｋ， 即 ， 代入欧拉公式有

234 即 整理得

235 推论 K5是非平面图。 证明 K5如图7 ― 55， 这里n＝５， m＝10， 而 ３n－６＝３×５－６＝９≥10 所以K5不是平面图。

236 图 7 ― 55 图K5

237 定理 7.9 ― 4 若G是每个面由４条或４条以上的边围成的连通平面图， 则有
m≤２n－４ 其中m和n分别是G的边数和结点数。 证明 设G有k个面。 由题设知， 所以２m≥4k， 即 ， 代入欧拉公式有

238 整理得 m≤２n－４

239 推论 K 3,3不是平面图。 证明 K 3,3如图7 ― 49(c)所示。 因在K 3,3中任取３个结点， 至少有 2 个结点不邻接， 故每个面的次数不小于４。 而在K 3,3中， n＝６， m＝９， 于是 ２n－４＝２×６－４＝８＜９ 故K 3,3不是平面图。 我们称K 3,3和K5为库拉托夫斯基（Kuratowski）图。

240 定义 7.9 ― 3 如果两个图G1和G2是同构的， 或者通过反复插入或删去度数为２的结点后是同构的， 则称G1和G2在２度结点内同构（或称同胚）。
如图7 ― 56中(a)、 (b)中的两个图都是同胚的。 若G1是平面图， 而G2与G1同胚， 则G2也是一个平面图。 即一个图变成与它同胚的图不会影响图的平面性。

241 图 7 ― 56 同胚图

242 图 7 ― 57 示例图G

243 定理 7.9 ― 5 （库拉托夫斯基定理) 一个图是一个平面图的充要条件是它不包含与K3,3或K5同胚的子图。
证明 略。 例如图7 ― 57的图G不是平面图， 因为G包含与K3,3同胚的子图。 这个定理虽然给出了判断平面图的充要条件， 结果是漂亮的， 但实际上要用于判断比较复杂的图是否是平面图还是很困难。

244 习 题 7 １. 试找出附图的一个真子图、 生成子图， 并找出它们的补图。
习 题 7 １. 试找出附图的一个真子图、 生成子图， 并找出它们的补图。 ２. 对于（n， n＋１）图G， 证明G至少有一个结点的度数大于等于３。 ３. 证明附图中两个图同构。

245 第 1 题 附图 第 ３ 题 附图

246 *４. 证明任意的９个人中一定有３个人互相认识或者有 ４个人互相不认识。
５. 给定图G（见附图）， 求 1) 从A到F的所有通路。 2) 从A到F的所有迹。 3) A和F之间的距离。 4) 指出图G中所有的圈。

247 第 ５ 题 附图

248 ６. 设G是有n个结点的简单图。 如果G中每一对结点度数之和大于或等于n－１， 那么G是连通图。
７. 对于任何简单图G， 证明或者G是连通的， 或者G的补G 是连通的。 *８. n个城市由k条公路网连接（一条公路定义为两个城市间的一条道路， 并且它们之间不能通过任何中间城市）。 证明： 如果有 则人们总能通过连接的公路， 在任何两个城市之间旅行。

249 *９. 用迪克斯特拉算法求附图中从点ａ到其它各结点的最短路径， 并用图示表示算法中每一次的执行情况。
第 ９ 题 附图

250 10. 已知图G的邻接矩阵如下 请画出G的图形。

251 11. 求出附图中有向图的邻接矩阵A， 找出从ｖ1到ｖ4长度为２和４的路， 用计算A2， A3， A4来验证这一结论。 并求出该图的可达性矩阵。
12. 求证： 在任意一个有向图中， 所有结点的入度之和等于它们的出度之和。 13. 试求出附图中所有的强分图、 弱分图和单向分图。

252 第 11 题 附图

253 第 13 题 附图

254 14. 判断附图中两图是否能一笔画。 15. 如附图所示， ４个村庄下面各有一个防空洞A， B， Ｃ， D， 相邻的两个防空洞之间有地道相通， 并且每个防空洞各有一条地道与地面相通。 能否安排一条路线， 使得每条地道恰好走过一次， 既无重复也无遗漏？

255 第 14 题 附图 第 15 题 附图( 表示地道)

256 16. 画一个图， 1) 使它有一条欧拉回路和一条哈密尔顿回路。 2) 使它有一条欧拉回路但没有哈密尔顿回路。 3) 使它没有欧拉回路但有哈密尔顿回路。 4) 使它既没有欧拉回路也没有哈密尔顿回路。 17. 附图中的图G是否是哈密尔顿图。

257 第 17 题 附图

258 18. 完全图Kn是否是欧拉图， 是否是哈密尔顿图。
19. 设G是一个具有n个结点的简单无向图（n≥３）， G的结点表示人， G的边表示他们间的友好关系， 若两个结点被一条边连接， 当且仅当对应的人是朋友。 1) 一个结点的度数可作何解释？ 2) 对G是连通图这一事实应作何解释？ 3) 对G是哈密尔顿图又可作何解释？

259 第 20 题 附图 第 21 题 附图

260 20. 用标号法指出附图中的图G中没有哈密尔顿路。
21. 对于附图中的图， 如何从ａ点开始， 根据最邻近方法求具有最小权的哈密尔顿回路。 22. 证明： 图G为森林的充要条件是 m＝n－W(G) 其中W(G)是G的连通分枝数， n为G中结点数目， m为边数。

261 23. 对定理7.6 ― 1的充分性部分进行证明。 24. 证明具有m条边的连通图最多具有m＋１个结点。 25. 用定理7.1 ― 1和定理7.6 ― 2的结论证明定理7.6 ― 1。 26. 一棵树有两个结点度数为２， １个结点度数为３， ３个结点度数为４， 其余结点度数均为１， 问该树有几个度数为１的结点？ 27. 对于附图， 利用克鲁斯克尔算法求一棵最小生成树。

262 第 27 题 附图

263 28. 两人进行乒乓球比赛。 如果一人连胜 2 盘或共胜 3 盘就获胜， 比赛结束。 用一棵二叉树表示比赛可能进行的各种情况。
29. 根据简单有向图的邻接矩阵， 如何确定它是否是根树？如果它是根树， 如何确定它的根和叶。 30. 将附图中给定的有序树画出相应的二叉树。 31. 证明在完全二叉树中， 边的总数等于２(n－１)， 这里n是叶子数。 32. 分别写出按先根次序遍历法、 中根次序遍历法和后根次序遍历法， 对附图中的二叉树的结点进行访问的顺序。

264 第 30 题 附图 第 32 题 附图

265 33. 设有一个代数表达式如下 1) 画出这个代数表达式相应的根树。 其中用“↑”表示乘方、 “*”表示乘、 “／”表示除、 “＋”表示加、 “－”表示减。 2) 分别用先根次序遍历法、 中根次序遍历法和后根次序遍历法重写这个代数表达式。 34. 对权１， ２， ３， ４， ５， ６， ７， ８， ９ 构造一棵最优二叉树。

266 35. 自动售货机使用４种颜色的筹码： 红、 黄、 蓝、 白。 假使这４种筹码投入的可能性（即概率）分别为0. 05、 0. 15、 0
35. 自动售货机使用４种颜色的筹码： 红、 黄、 蓝、 白。 假使这４种筹码投入的可能性（即概率）分别为0.05、 0.15、 0.50、 0.30。 假设每次只能有一个筹码进入机器， 机器内有一个判别机构， 判别筹码的方式有几种？ 现有一批筹码， 问用哪一种方式进行判别， 使得机器的判别总次数最少？ *36. 证明树是一个偶图。

267 *37. 如果在偶图G＝（V1， E， V2）中， |V1|＞|V2|， 并且V1的每个结点的度数不小于δ， 那么V2中必有一个结点的度数大于δ。
*38. 证明如果G是一个偶图， 它有n个结点， m条边， 则 。

268 39. 某单位按编制有７个工作p1， p2， …， p7空缺， 有10个申请者a1， a2， …， a10。 他们能胜任的工作集合依次是{p1， p5， p6｝， {p2， p6， p7}， {p3， p4}， {p1， p5}， {p6， p7}， {p3}， {p2， p3}， {p1， p3}， {p1}， {p5}。 问如何安排他们工作能使无工作的人最少？ 40. 写出下面平面图的面、 边界以及每面的次数。 41. 证明少于30条边的简单平面图至少有一个结点， 它的度数小于等于４。

269 第 43 题附图 第 40 题附图

270 42. 证明具有６个结点和12条边的简单平面图， 它的每一个面都是由３条边围成的。
43. 证明附图不是平面图。 44. 如果图G的结点数n≥11， 证明G与G的补 G 中至少有一个不是平面图。 45. 在一个连通平面图中， 若它有n个结点， m条边， 且每个面由k条边围成。 试证