离散数学电子教材7b(共35页).doc

《离散数学电子教材7b(共35页).doc》由会员分享，可在线阅读，更多相关《离散数学电子教材7b(共35页).doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上*7.5 二部图及匹配 7.5.1二部图在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它的一个重要应用匹配。定义7.5.1 若无向图的顶点集能分成两个子集和，满足（1），；（2），均有，。则称为二部图或偶图(Bipartite Graph或Bigraph)，和称为互补顶点子集，常记为。如果中每个顶点都与中所有顶点邻接，则称为完全二部图或完全偶图(Complete Bipartite Graph)，并记为，其中。由定义可知，二部图是无自回路的图。图7-55中，都是二部图，其中是完全二部图。图7-55二部图示例显然，在完全二部图中中，顶点数，

2、边数。一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图7-56中可改画成图，图可改画成图。可以看出，它们仍是二部图。图7-56二部图示例定理7.5.1 无向图为二部图的充分必要条件为中所有回路的长度均为偶数。证明 先证必要性。设是具有互补节点子集和的二部图。是中任一长度为的回路，不妨设，则，所以必为偶数，不然，不存在边。再证充分性。设是连通图，否则对的每个连通分支进行证明。设只含有长度为偶数的回路，定义互补节点子集和如下：任取一个顶点，令现在证明中任意两节点间无边存在。 假若存在一条边，且，则由到间

3、的最短路（长度为偶数）， 边和到间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。 同理可证中任意两节点间无边存在。 故中的每条边必具有形式，其中， 即是具有互补节点子集和的一个二部图。 利用定理7.5.1可以很快地判断出图7-57中的、是二部图，而则不是二部图。图7-57例7.5.1 六名间谍被擒，已知懂汉语、法语和日语，懂德语、俄语和日语，懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。 解 以六人为顶点，在懂共同语言的人的顶点间连边得图（如图7-58所示），因为中没有奇圈，所以是二部图（如图7-58所示），

4、故至少应有两间房间即可。 图7-587.5.2 匹配二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。首先看实际中常碰见的问题：给个工作人员安排项任务，个人用表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？例如，现有五个人，五项工作。已知能胜任和，能胜任和，能胜任和，能胜任和，能胜任、和。如何安排才能使每个人都有工作做，且每项工作都有人做？显然，我们只需构造这样的数学模型：以和（i，j=1，2，3，4，5）为顶点，在与

5、其胜任的工作之间连边，得二部图，如图7-59所示，然后在中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。图7-59匹配问题示意图定义7.5.2 设无向图，中有边集，且在中任意两条边都没有公共的端点，称边集为图的一个匹配(Matching)。中一条边的两个端点，叫做在下是配对的。如果中不存在匹配，使得，则称为最大匹配(Maximum Matching)。对于的一个匹配，若节点与中的边关联，则称是饱和的(Saturated)，否则称是不饱和的。定义7.5.3 设二部图，是的一个匹配。若，均是饱和的，则称是对的完全匹配（简

6、称完全匹配）；若，均是饱和的，则称是对的完全匹配（简称完全匹配）。若既是完全匹配，又是完全匹配（即图的每个顶点都是饱和的），则称是完全匹配(Complete Matching)。显然，完全匹配是最大匹配，但反之不然。例7.5.2（1）在图7-59中，边集是一个匹配，而且是是一个最大和完全匹配。（2）在图7-60中，边集和，都是图的最大匹配，也是完全匹配，但不是完全匹配。在图7-60中，边集是完全匹配。图7-60为了寻求二部图的最大匹配，下面交替路和可扩路两个概念。定义7.5.4 设是一个二部图，是图的一个匹配，是中的一条路，如果是由属于和不属于的边交替出现组成，则称为的交替路(Alternat

7、ing Path)。如果交替路的始点和终点都是不饱和点，则称为的可扩路(Extensible Path)。例如，在图7-60中，对于匹配，路，都是交替路，其中的始点和终点都是不饱和点，所以这两条路是可扩路。可扩路具有如下性质：可扩路的长度必为奇数，且属于的边比不属于的边少1条。如果在一条可扩路中把属于中的边从匹配中去掉，把不属于中的边添入到匹配中， 则得到新的匹配，的边数比多。例如，在图7-60中，对于匹配，是可扩路，将中属于中的边，从匹配中去掉， 把不属于中的边添入到匹配中，则得到新的匹配，中的边数由中的3条增至4条。如果图中还存在可扩路， 再按上面的步骤做， 所得到的匹配的边数又多，一直到

8、图中不存在可扩路为止。用此方法可逐步得到较大的匹配，直至得到最大匹配。这就是下面的定理。 定理7.5.2 在图中，为最大匹配的充分必要条件是不存在可扩路。证明 先证必要性。用反证法。假设中存在一条可扩路，则可以得到比的边数多的匹配，与为最大匹配矛盾。所以中不存在可扩路。再证充分性。用反证法。假设不是最大匹配，则存在匹配，使得。令（为对称差运算），设由导出的的子图，因为和都是的匹配，所以的任意顶点或是只与（或）中的一条边相关联，或是同时与的一条边及的一条边相关联，其度数至多为2，于是的每个连通分支或者是一个边交错地属于与的长度为偶数的回路，或者是边交错地属于与的长度为奇数的交错路。 由于，因而中

9、必有一个连通分支，它所含的属于的边比属于的边多，不是回路（因为回路的长度均为偶数），它的起点和终点都是不饱和的，也一定是中的不饱和点，因此在中存在关于的可扩路，这与假设矛盾。 求一般图的最大匹配过程比较复杂，下面仅讨论如何在二部图中求最大匹配的问题。设二部图，在中求最大匹配的关键是寻找可扩路。通常是先构造的一个匹配，再看中有没有不饱和点。 如果没有，那么肯定是最大匹配了；如果有， 我们就从这些点出发找可扩路，由可扩路做出一个更大的匹配。寻找可扩路的一个有效方法是标记法， 其过程如下： 首先在中作一个匹配，用（*）标记中所有不饱和点， 然后交替地进行以下步骤（）和（）。 （）选一个的新标记过的节

10、点，比如， 用（）标记不通过中的边与邻接且未标记过的的所有节点。 对所有新标记过的节点重复这一过程。 （）选一个的新标记过的节点，比如， 用（）标记通过中的边与邻接且未标记过的的所有节点。对所有新标记过的节点重复这一过程。 执行以上步骤， 直至标记到一个中的不饱和点。从该节点倒向追踪到标记有（*）的节点，就得到一条可扩路。于是也就得到一个边数为|的匹配， 再返回（）。 如果已不可能标记更多的节点，而的所有标记的节点均为饱和点，则说明中已不存在可扩路，这时就是最大匹配。 例7.5.3 图7-61是一个二部图， 求其最大匹配。 图7-61解 取图7-61图的一个匹配。用（*）标记中所有不饱和点。（

11、1）选的新标记过的节点，用（）标记不通过中的边与邻接且未标记过的的节点；类似地，用（）标记。(2) 选的新标记过的节点， 用（）标记通过中的边与邻接且未标记过的的节点；类似地，用（）标记。(3) 选的新标记过的节点，因为不存在不通过中的边与邻接的的节点，所以不用（）标记的节点；用（）标记或，假定用（）标记。是不饱和点，标记结束。从倒向追踪到标记有（*）的节点，就得到一条可扩路或，取前者，由此得匹配。 对匹配再用标记法（见图7-61知， 图中已不存在可扩路，所以就是最大匹配。 定理7.5.3（霍尔定理） 二部图有完全匹配，当且仅当对中任一子集，和所有与邻接的点构成的点集，恒有 证明 先证必要性。

12、假设是二部图的一个完全匹配，则中的每个顶点均是饱和的。对的任一子集，因的每个顶点在下和中不同的顶点配对，所以有。再证充分性。假设是满足对任何的子集，的二部图，但中没有使中每个顶点饱和的完全匹配，设是的一个最大匹配，由假设，不使中所有顶点饱和。设是中的不饱和点，并设是与有关于交错路相连通的所有顶点的集合。由于是一最大匹配，由定理7.5.2可知：为中唯一的不饱和点。 令=，显然，中的顶点都关于饱和，即它与中的顶点在下配对，于是，且，又因中的每个顶点有关于交错路与相连通，因此，所以 与假设矛盾。例7.5.4 设有4个人，现有5项工作需要做，每个人所能胜任工作的情况如图7-62所示，问能否使每个人都能

13、分配到一项工作？ 图7-62解 这个问题即为：二部图是否存在完全匹配。当取=时，=，因此，根据霍尔定理，二部图没有完全匹配，所以要使每个人都能分配到一项工作是不可能的。习题7.51求下面两个二部图的最大匹配。图7-632假定是二部图，如何安排中顶点的次序可使的邻接矩阵呈 形式，0为零矩阵。3某单位有7个工作空缺要招聘，有10个应聘者。他们能胜任的工作岗位集合分别为：，。如果规定每个应聘者最多只能安排一个工作，试给出一种分配方案使落聘者最少？4设图是二部图，证明。7.6 平面图7.6.1 平面图的定义在一些实际问题中，常常需要考虑一些图在平面上的画法，希望图的边与边不相交或尽量少相交。如印刷电路

14、板上的布线、线路或交通道路的设计、地下管道的铺设等。下面举一个简单的例子。 例7.6.1 一个工厂有 3 个车间和 3 个仓库。 为了工作需要， 车间与仓库之间将设专用的车道。为避免发生车祸，应尽量减少车道的交叉点，最好是没有交叉点，这是否可能？如图7-64所示，是3个车间，是3座仓库。经过努力表明，要想建造不相交的道路是不可能的，但可以使交叉点最少（如图7-64所示）。此类实际问题涉及到平面图的研究。近年来，由于大规模集成电路的发展，也促进了平面图的研究。本节介绍平面图的一些基本概念和常用结论。图7-64定义7.6.1 设是一无向图。如果能把的所有节点和边画在平面上，使得任何两条边除公共端点

15、外没有其他的交点，则称是一个平面图(Planar Graph)，或称该图能嵌入平面；否则，称是一个非平面图。直观上说所谓平面图就是可以画在平面上，使边除端点外彼此不相交的图。应当注意，有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。 图7-65平面图和非平面图示例例如，图7-65是无向完全图，它是平面图。图7-65是无向完全图，它表面上看有相交边，但是把它画成图， 则可以看出它是一个平面图。图是平面图。图经改画后得到图，图经改画后得到图，由定义知它们都是平面图。而图、是无向完全图，和图7-64中的两个图，无论怎样调整边的位置，都不能使任何两边除公共端点外没有其他的交点，所以

16、它们不是平面图，它们是两个最基本、最重要的非平面图，在平面图理论的研究中有非常重要的作用。设是平面图，的以无交边的方式画在平面上的图称为平面图的平面嵌入(Imbedding)。如图7-65 中的、分别为图、的平面嵌入。关于平面图，以下两个结论是显然的。定理7.6.1 若是平面图，则的任何子图是平面图。定理7.6.2 若是非平面图，则的任何母图是非平面图。推论：无向完全图和二部图都是非平面图。定义7.6.2 设是平面图。将嵌入平面后，由的边将所在的平面划分为若干个区域，每个区域称为的一个面(Face)。其中面积无限的面称为无限面或外部面(Exterior Face)，面积有限的面称为有限面或内部

17、面(Interior Face)。包围每个面的所有边组成的回路称为该面的边界(Bound)，边界长度称为该面的次数(Degree)，面的次数记为。例如，图7-65共有2两个面，每个面的次数均为3。7-65共有4四个面，每个面的次数均为3。图7-65 共有3个面，每个面的次数均为4。图7-65 共有6个面，每个面的次数均为3。图7-66所示平面图有4个面，的边界为，的边界为，。图7-66关于面的次数，我们有下述定理。 定理7.6.3 在一个有限平面图中，所有面的次数之和等于边数的二倍，即其中，为的面数，为边数。 证明 注意到等式的左端表示的各个面次数的总和，在计数过程中，的每条边或者是两个面的公

18、共边界，为每一个面的次数增加1；或者在一个面中作为边界重复计算两次，为该面的次数增加2。因此在计算面的次数总和时，每条边都恰计算了两次，故等式成立。 由定理7.6.3可以立即得出： 推论：在任何平面图中次数为奇数的面的个数是偶数。 的不同平面嵌入的面的次数数列可能是不同的。图7-67中的，是同一个图的平面嵌入，但它们的面的次数数列分别是3,3,5,5和3,3,4,6。 图7-67 7.6.2 欧拉公式在1750年数学家欧拉发现，任何一个凸多面体的顶点数，棱数和面数之间满足关系式： 这就是著名的欧拉公式。 更一般地，对任意平面图，欧拉公式依然成立。这就是下面的定理和推论。 定理7.6.4 设为一

19、个连通平面图，它有个节点，条边和个面，则有。 证明 对的边数进行归纳证明。当=0时，由于是连通的，因此只能是平凡图。这时，=1，=0，=1，成立。设时，结论成立，下面证明当时，结论也成立。易见，一个具有条边的连通平面图可以由条边的连通平面图添加一条边后构成。因为一个含有条边的连通平面图上添加一条边后仍为连通图，则有三种情况：（1）所增边为悬挂边（见图7-68），此时的面数不变，节点数增1，边数增1，欧拉公式成立。（2）所增边为一个环，此时的面数增1（见图7-68），边数增1，但节点数不变，欧拉公式成立。（3）在图的任意两个不相邻节点间增加一条边（见图7-68），此时的面数增1，边数增1，但节点

20、数不变，欧拉公式成立。图7-68 定理7.6.5 设是连通的平面图，且每个面的次数至少为，则证明 由定理7.6.3知 (为的面数)再由Euler公式得故 。推论1 平面图的平面嵌入的面数与的嵌入方法无关。 于是的一个平面嵌入的面数，可直接称为平面图的面数。 推论2 设是有个节点()，条边的简单平面图，则。 证明 不妨设是连通的，否则可在的连通分支间加边而得到连通图，的节点数仍为，边数，所以若定理对成立，则对也成立。 由于是有个节点()的简单连通平面图，所以的每一个面至少有3条边围成。如果中有个面，则面的总次数即有代入欧拉公式，可得从而得到。 推论2也可直接由定理7.6.5推出，只需令即可。推论

21、3 若有个节点()的简单连通平面图不以为子图，则。证明 由于是有个节点(3)的简单连通平面图，且中不含，所以的每个面至少由4条边围成，即，代入定理7.6.5，立即得 。推论4 若是一个简单平面图，则至少有一个节点的度数小于等于5。 证明 当的节点数小于等于6时，结论显然成立。当的节点数大于等于7时，设的最小度节点的度数为，若，即，由握手定理知故与推论2矛盾，所以图中至少有一个节点的度数小于等于5。 例7.6.2 证明和都不是平面图。 证明 （1）的节点数=5，边数，若它是平面图，则由推论2得，即 ，这是一个矛盾不等式，故不是平面图。 （2）的节点数=6，边数，且其不含子图，由推论3可知，即，这

22、也是一个矛盾不等式，故是非平面图。上面给出的定理7.6.4和推论2、推论3、推论4都是一个图是平面图的必要条件，它们可用来判断某个图不是平面图。我们希望找出一个图是平面图的充分必要条件。经过几十年的努力，波兰数学家库拉托夫斯基（Kuratowski）于1930年给出了平面图的一个非常简洁的充分必要条件。下面就来介绍库拉托夫斯基定理。为此先引入同胚的概念。定义7.6.3 设为一个无向图，是的一条边，在中删去边，增加新的节点，使均与相邻接，则称在中插入一个2度节点； 设为的一个2度节点，与相邻接，在中删去节点及与相连接的边，同时增加新边，则称在中消去一个2度节点。如图7-69 所示。 图7-69

23、定义7.6.4 如果两个无向图与同构或通过反复插入或消去2度节点后是同构的，则称与是同胚的(Homeomorphic)。 例如，图7-70所示的4个图是同胚的。图7-70 定理7.6.6 (库拉托夫斯基定理) 一个无向图是平面图当且仅当它不含有与或同胚的子图。 库拉托斯基定理的必要性容易看出，因为和均不是平面图，因此与或同胚的图也不是平面图。一个无向图若是平面图，则它自然不会含有非平面图作为它的子图。 库拉托夫斯基定理的充分性证明较复杂，这里不再引述。有兴趣的读者可参阅邦迪(J.A.Bondy)和默蒂(U.S.R.Murty)的图论及其应用。 例7.6.3 证明图7-71中的（彼得森图）是非平

24、面图。 图7-71证明 在彼得森图中有同胚于的子图(见图7-71、)，由库拉托夫斯基定理知, 彼得森图不是平面图。 7.6.3 平面图的着色平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1852年，英国青年盖思瑞（Guthrie）提出了用四种颜色可以对地图着色的猜想（以下简称四色猜想）。1879年肯普（Kempe）给出了这个猜想的第一个证明，但到1890年希伍德（Hewood）发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了，但却可以证明用五种颜色就够了，即五色定理成立。此后四色猜想一直成为图论中的难题

25、。许多人试图证明猜想都没有成功。直到1976年美国数学家阿佩尔（K.Appel）和哈肯(W.Haken)利用计算机分析了近2000种图形和100万种情况，花费了1200个机时，进行了100多亿个逻辑判断，证明了四色猜想。从此四色猜想便被称为四色定理。但是，不依靠计算机而直接给出四色定理的证明，仍然是数学界的一个令人困惑的问题。为了叙述图形着色的有关定理，下面先给出对偶图的概念。定义7.6.5 给定平面图，其面的集合。若有图满足下列条件：（1）对于任意一个面，其内部有且仅有一个节点；（2）对于中的面和的公共边，有且仅有一条边，使得，且与相交； （3）当且仅当只是一个面的边界时，存在一个环且与相交

26、；则称图是图的对偶图(Dual Graph)。例如，在图7-72中，的边和节点分别用实线和“”表示，而它的对偶图的边和结点分别用虚线和“ ”表示。图7-72 从对偶图的定义可以看出，若是平面图的对偶图，则也是的对偶图。定理7.6.7一个连通平面图的对偶图也是平面图，而且有， ，其中和分别是和的节点数，边数和面数。证明 由定义7.6.5对偶图的构造过程可知，G*也是连通的平面图，且，和显然成立，下证。因为和均是连通的平面图，所以由欧拉公式有 由，可得。定义7.6.6 若图的对偶图同构于，则称是自对偶图(Self-dual Graph)。例如，图7-73给出了一个自对偶图。图7-73 定理7.6.

27、8 若平面图是自对偶图，且有个节点，条边，则。证明 由欧拉公式知 由于图是自对偶图，则有，从而有即。从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的节点的着色问题。因此，四色问题可以归结为证明：对任意平面图一定可以用四种颜色，对其节点进行着色，使得相邻节点都有不同颜色。定义7.6.7 平面图的正常着色(Proper Coloring)（简称着色）是指对的每个节点指派一种颜色，使得相邻节点都有不同的颜色。若可用种颜色对图着色，则称是可着色的。对图着色时，需要的最少颜色数称为的着色数(Chromatic Number)，记为。于是，四色定理可简单地叙述如下：定理7.6.9

28、（四色定理）任何简单平面图都是4可着色的。证明一个简单平面图是5可着色的很容易。定理7.6.10（五色定理）任何简单平面图，均有。证明 只需考虑连通简单平面图的情形。对施行归纳证明。当时，显然，。假设对所有的平面图，当时有。现在考虑图，的情形。由定理7.6.5的推论4可知，存在，使得。在图中删去，得图。由归纳假设知，是5可着色的，即。因此只需证明在中，节点可用5种颜色中的一种着色并与其邻接点的着色都不相同即可。若，则与邻接节点数不超过4，故可用与的邻接点不同的颜色对着色，得到一个最多是五色的图。若，但与邻接的节点的着色数不超过4，这时仍然可用与的邻接点不同的颜色对着色，得到一个最多是五色的图。

29、若，且与邻接的5个节点依顺时针排列为和，它们分别着不同的颜色红、白、黄、黑和蓝。如图7-74所示。 图7-74考虑由节点集合所诱导的的子图。若属于的不同连通分支，如图7-75所示。则将所在的连通分支中的红色与黄色对调，这样并不影响的正常着色，然后将涂上红色即可得到的一种五着色。若和属于的同一个连通分支，则由节点集所诱导的的子图中含有一个圈，而和不能同时在该圈的内部或外部，即与不是邻接点，如图7-76所示。于是，考虑由节点所诱导子图，由于圈的存在，至少有两个连通分支，一个在的内部，一个在的外部（否则图中将有边相交，与图是平面图的假设矛盾），则和必属于的不同连通分支，作与上面类似的调整，又可得到的

30、一种五着色。故。由归纳原理，定理得证。图7-75图7-76习题7.61 图7-77和所示的平面图各有几个面？写出它们各面的边界及次数。 图7-772 证明图7-78和是非平面图。图7-783证明：小于30条边的简单平面图中存在度数小于等于4的节点。4设是简单平面图，面数，证明中存在次数小于或等于4的面。5设是一个连通平面图， 它有个节点，条边，且每个面由条边围成。 试证6证明具有个节点和12条边的简单平面图，它的每一个面都是由条边围成的。 7设简单图的节点数11，则与的补图 中至少有一个不是平面图。 7.7 树与生成树 树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，

31、1857年凯莱在计算有机化学中的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。 7.7.1 无向树 定义7.7.1 一个连通无圈无向图称为无向树(Undirected Tree) (简称为树)，记作。树中度数为1的节点称为树叶(Leaf)（或叶节点），度数大于的节点称为分枝点(Branch Point )（或内点(Inner Point)）。 一个无圈图称为森林(Forest)。 显然若图是森林，则的每个连通分支是树。 例如，图7-79和所示的图是树；所示的图是森林。 图7-79 树和森林示意图 定理7.7.1 设是一个无向

32、图，则以下关于的命题是等价的。 (1) 是树；（2）无圈且； (3) 连通且；（4）无圈，但增加任一新边，得到且仅得到一个圈。（5）连通，但删去任一边便不连通()。（6）的每一对节点间有唯一的一条通路()。证明 (1) （2）由树的定义可知无圈。下证。对进行归纳证明。 当时，显然。 假设时结论成立，现证明时结论也成立。 由于树是连通而无圈的，所以至少有一个度数为1的节点，在中删去及其关联边，便得到个节点的连通无圈图。由归纳假设它有条边。再将顶点及其关联边加回得到原图，所以中含有个顶点和条边，故结论成立。 所以树是无圈且的图。(2) （3） 用反证法。若不连通，设有个连通分支() ，其节点数分别

33、是，边数分别为，于是得出矛盾。所以是连通且的图。(3) （4） 首先证明无圈。对作归纳证明。 当时，显然无圈。 假设节点数为时无圈，今考察节点数是时的情况。此时至少有一个节点其度数。我们删去及其关联边得到新图，根据归纳假设无圈，再加回及其关联边又得到图，则也无圈。 其次，若在连通图中增加一条新边，则由于中由到存在一条通路，故必有一个圈通过，。若这样的圈有两个，则去掉边，中仍存在通过，的圈，与无圈矛盾。故加上边得到一个且仅一个圈。(4) （5） 若不连通，则存在两个节点和，在和之间没有路，若加边不会产生圈，但这与假设矛盾，故是连通的。又由于无圈，所以删去任一边，图便不连通。(5) （6） 由连通

34、性知，任意两点间有一条路径，于是有一条通路。若此通路不唯一，则中含有圈，删去此回路上任一边，图仍连通，这与假设不符，所以通路是唯一的。(6) （1）显然连通。下证无圈。用反证法。若有圈，则圈上任意两点间有两条通路，此与通路的唯一性矛盾。故是连通无圈图，即是树。定理7.7.2 任一棵树中，至少有两片树叶(节点数时)。证明 设是一棵树（），由定理7.7.1， 有 （1）若中无树叶，则中每个节点的度数，则 （2）若中只有一片树叶，则中只有一个节点度数为1，其他节点度数，所以 （3）(2)，(3)都与(1)矛盾。所以中至少有两片树叶。 由定理7.7.1 所刻画的树的特征可见：在节点数给定的所有图中，树

35、是边数最少的连通图， 也是边数最多的无圈图。 由此可知，在一个图中， 若， 则是不连通的； 若，则必定有圈。例7.7.1 设是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求的树叶数。 解 设树有片树叶，则的节点数 的边数 又由得 所以，即树有9片树叶。7.7.2 无向图中的生成树与最小生成树 1无向图中的生成树 定义7.7.2 若无向(连通图) 的生成子图是一棵树，则称该树是的生成树或支撑树(Spanning Tree)，记为。生成树中的边称为树枝。图中其他边称为的弦。所有这些弦的集合称为的补。 例如，图7-80中、所示的树、是图的生成树，而所示的树不是图的生成树。、所示的树是图的生

36、成树。一般的，一个图的生成树不唯一。图7-80考虑生成树，可知是的树枝，是的弦，集合是的补。生成树有其一定的实际意义。例7.7.2 某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如图7-80的无向边铺设。为使这处都有道路相通，问至少要铺几条路？ 解：这实际上是求的生成树的边数问题。 一般情况下，设连通图有个节点，条边。由树的性质知，有个节点，1条树枝，条弦。 在图7-80中，则，所以至少要修条路才行。 由图7-80可见，要在一个连通图中找到一棵生成树，只要不断地从的回路上删去一条边，最后所得无回路的子图就是的一棵生成树。于是有以下定理。定理7.7.3 无向图有生成树的充分必要条件是为连

37、通图。证明 先采用反证法来证明必要性。若不连通，则它的任何生成子图也不连通，因此不可能有生成树，与有生成树矛盾，故是连通图。再证充分性。设连通，则必有连通的生成子图，令是的含有边数最少的生成子图，于是中必无回路（否则删去回路上的一条边不影响连通性，与含边数最少矛盾），故是一棵树，即生成树。 2无向图中的最小生成树 定义7.7.3 设是一连通的带权图，则的生成树为带权生成树，的树枝所带权之和称为生成树的权(Weight)，记为。中具有最小权的生成树称为的最小生成树(Minimal Spanning Tree)。 最小生成树有很广泛地应用。例如要建造一个连接若干城市的通讯网络，已知城市和之间通讯线

38、路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树。 下面介绍求最小生成树的克鲁斯克尔（Kruskal)算法。 此方法又称为“避圈法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下： 1) 在中选取最小权边，置边数i1。 2) 当i1时，结束。否则，转3)。 3) 设已选择边为，在中选取不同于的边，使无圈且是满足此条件的最小权边。 4) 置i为i1， 转2)。证明 设为由上述算法构造的一个的子图，它的节点是的个节点，的边是，且无圈。由定理7.7.1可知是一棵树，且为图的生成树。下面证明是最小生成树。设图的最小生成树是。若与相同，则是图的最小生成树。若与不同，则在中至少存

39、在一条边，使得不是的边，但是的边。因为是树，我们在中加上边，必有一个圈，而是树，所以中必存在某条边不在中。对于树，若以边置换，则得到一棵新树，树的权，因为是最小生成树，故，即或。因为是的边，且在中无圈，故不可能成立，否则在中，自之后将取而不能取，与题设矛盾。于是，因此也是的最小生成树，但是与的公共边比与的公共边数多1，用置换，重复上述过程直到得到与有条公共边的最小生成树，这时就是，故是最小生成树。 例7.7.3 求图7-81(0)中有权图的最小生成树。 解 因为图(a)中8，所以按算法要执行17次，其过程见图7-81(b)(h)所示。 图7-81 例7.7.4 图7-82所示的赋权图表示七个城

40、市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。图7-82解 该问题相当于求图的最小生成树问题，此图的最小生成树为图7-82中的，因此如图架线使各城市间能够通讯，且总造价最小，最小造价为： 习题7.71一棵树有5个度为2的节点，3个度为3的节点，4个度为4的节点，2个度为5的节点，其余均是度为1的节点，问有几个度为1的节点？2一棵树有个2度节点，个3度节点，个度节点，求其叶节点的数目。3 求出中所有不同构的生成树。4对于图7-83和，利用克鲁斯克尔算法求一棵最小生成树。图7-835今有煤气站，将给一居民区供应煤气，居民区各用户所在位置

41、如图7-84所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。图7-846设是个正整数（），若，则存在一棵无向树，其节点度数分别为。7.8 根树及其应用7.8.1 有向树定义 7.8.1 一个有向图，若不考虑边的方向，它是一棵树，则称这个有向图为有向树(Directed Tree )。 一棵有向树，如果恰有一个节点的入度为，其余所有节点的入度都为，则称为根树(Rooted Tree)，其中入度为的节点称为树根(Root)，出度为的节点称为树叶，出度不为的节点称为分枝点或内点。例如，图7-85、和均为有向树，其中只有和为根

42、树。在根树图中，为树根，为分枝点，其余节点为树叶。习惯上我们把根树的根画在上方，叶画在下方，这样就可以省去根树的箭头，如图7-85所示。在根树中，称从树根到节点的距离为该点的层次。这样对图7-85中的根树，的层次为，的层次为，其余节点的层次均为。 图7-85 定义7.8.2 在根树中，若从到可达，则称是的祖先，是的后代；又若，是根树中的有向边，则称是的父亲，是的儿子；如果两个节点是同一节点的儿子，则称这两个节点是兄弟。 定义7.8.3 在根树中，任一节点及其的所有后代和从出发的所有有向路中的边构成的子图称为以为根的子树。根树中的节点的子树是以的儿子为根的子树。 在现实的家族关系中，兄弟之间是有

43、大小顺序的，为此我们引入有序树的概念。 定义7.8.4 如果在根树中规定了每一层次上节点的次序，这样的根树称为有序树(Ordered Tree)。在有序树中规定同一层次节点的次序是从左至右。例如，图7-85和均为有序树。定义7.8.5一个有向图，如果它的每个连通分支是有向树，则称该有向图为(有向)森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林是有序森林。例如，图7-86是一个有序森林。图7-867.8.2 叉树 在树的实际应用中，我们经常研究完全叉树。 定义7.8.6 在根树中，若节点的最大出度为，则称为叉树(-ary Tree)。如果的每个分枝点的出度都恰好等于，则称为完全

44、叉树(Complete -ary Tree)。若叉树的所有叶节点在同一层，则称它为正则叉树(Regular -ary Tree)。二叉树(Binary Tree )的每个节点至多有两棵子树，分别称为的左子树和右子树。若节点只有一棵子树，则称它为的左子树或右子树均可。若是（正则）叉树，并且是有序树，则称为元有序（正则）树。例如，在图7-87是一棵二叉树，而且是正则二叉树；图7-87是一棵完全二叉树；图7-87是一棵三叉树，而且是正则三叉树；图7-87是一棵完全三叉树。图7-87有很多实际问题可用二叉树或叉树表示。例7.8.1 甲、乙两人进行球赛， 规定三局两胜。图7-88表示了比赛可能出现的各种情况（图中节点标甲者表示甲胜，标乙者表示乙胜），这是一棵完全二叉树。 图7-88叉树中，应用最广泛的是二叉树。由于二叉树在计算机中最易处理，所以常常需要把一棵有序树转换为二叉树。其一般步骤为： (1) 从根开始，保留每个父亲与其最左边儿子的连线，删除与别的儿子的连线； (2) 兄弟间用从左向右的有向边连接；(3) 用如下方法选定二叉树的左儿子和右儿子：直接处于给定节