离散数学王元元习题解答(10)

第九章 特 殊 图

9.1 二分图

内容提要

9.1.1 二分图的基本概念

定义9.1 无向图G = 称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = ?，且对每一e?E，?(e) = (x, y)，x?X，y?Y。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边e?E，使?(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当?X? = m，?Y? = n时，完全二分图G记为Km,n。

定理9.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

9.1.2 匹配

定义9.2 设G = 为二分图，M?E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 定义9.3 设G = ，M为G的一个匹配。

（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。

（2）G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各

''

顶点均为M-顶点）。特别地，当一边（v, v）两端点均为非M-顶点，通路（v, v）亦称为交替链。

以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被称为匈牙利算法，其步骤如下：

（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2），（3）。

（2）选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点xi，然后用（xi）去标记Y中顶点y，如果xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过。重复步骤（2），直至对刚标记过的X中顶点全部完成一遍上述过程。 （3）选取一个刚标记（在步骤（2）中用（xi）标记）过的Y中结点，例如yi，用（yi）去标记X中结点x，如果yi与x为同一匹配边的两端点，且在本步骤中x尚未被标记过。重复步骤（3），直至对刚标记过的Y中结点全部完成一遍上述过程。

（2），（3）交替执行，直到下述情况之一出现为止：

（Ⅰ）标记到一个Y中顶点y，它不是M-顶点。这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。

（Ⅱ）步骤（2）或（3）找不到可标记结点，而又不是情况（Ⅰ）。 （4） 当 （2），（3）步骤中断于情况（Ⅰ），则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边（从而得到一个比原匹配多一条边的新匹配），回到步骤（1），同时消除一切现有标记。

（5）对一切可能，（2）和（3）步骤均中断于情况（Ⅱ），或步骤（1）无可标记结点，算法终止（算法找不到交替链）。

1

定理9.2 设图G = 。G有X-完全匹配的充分必要条件是：对每一S?X有

?N(S)?≥? S ?

习题解答

练习9.1

1、判别下列各图（图9.8）是否为二分图，是否为完全二分图。

图9.8

解 （1）是二分图，但不是完全二分图。

（2）是完全二分图。

（3）不是二分图。

2、假定G是二分图。如何安排G中顶点的次序可使G的邻接矩阵呈(

0B)形，其中B，C0C为矩阵，0为零矩阵。

解 因为 G是二分图，故可把G中所有顶点分为X、Y两个集合，使得 ?e(e?E→?(e)=(x, y)∧x?X∧y?Y) 只要按顺序先排X中的顶点，再排Y中的顶点，就可形成(0B)形的邻接矩阵 C03、六名间谍a，b，c，d，e，f被我捕获，他们分别懂得的语言是{汉语，法语，日语}，{德语，日语，俄语}，{英语，法语}，{汉语，西班牙语}，{英语，德语}，{俄语，西班牙语}，问至少用几个房间监禁他们，才能使同一房间的人不能互相直接对话。 解 如下图所示，顶点表示间谍，边表示间谍间能够直接对话 aefdbc 由于此图是二分图，因此只需要两个房间，分别监禁{a, e, f}和{b, c, d}，就可包证同一房间的人不能互相直接对话。 n24、设（n, m）图G为二分图，证明m≤。 4证 由于（n, m）图G是简单二分图，因此可将G中顶点分为X、Y两个集合，G中任一边均关联X、Y的各一个顶点，且 |X| ≥ 1， |Y| ≥ 1，|X| + |Y| = n 2 设 |X| = n1，则 |Y| = n－n1，那么边数m满足

n2n2n2?(n1?)≤ m ≤ |X|?|Y| = n1(n?n1)?

442n2故 m≤ 4 5、作一个二分图G = ，使它恰有4！个X-完全匹配 。 解 如下图所示，完全二分图K4, 4共有4！个X-完全匹配（Y-完全匹配） x1x2x3x4y1y2y3y4 6、用匈牙利算法求图9.9中二分图的最大匹配。 x3 x4 x6 x5 x1 x2 y3 y1 y2 y4 y5 y6 图9.9

解 （1）置M=?，对x1~x6标记（*）

（2）找到交替链(x1, y3)，置M={(x1, y3)}

（3）找到交替链(x2, y1)，置M={(x1, y3)，(x2, y1)}

（4）找到交替链(x3, y2)，置M={(x1, y3)，(x2, y1)，(x3, y2)}

（5）找到交替链(x5, y4)，置M={(x1, y3)，(x2, y1)，(x3, y2)，(x5, y4)} （6）找不到新的交替链，算法终止。匹配

M={(x1, y3)，(x2, y1)，(x3, y2)，(x5, y4)} 即为最大匹配，如下图所示 x3 x4 x6 x1 x2 x5

y3 y1 y2 y4 y5 y6

7、某单位有7个岗位空缺，它们是p1，p2,…,p7 。应聘的10人m1，m2,…,m10所适合的岗位分别是{p1，p5，p6}，{p2，p6，p7}，{p3，p4}，{p1，p5}，{p6，p7}，{p3}，{p2, p3}，

3

{p1，p3}，{p1}，{p5}。如何聘用可使落聘者最少。 解 求落聘者最少的聘用方案，即为求下图的最大匹配。 p1p2p3p4p5p6p7m1m2m3m4m5m6m7m8m9m10 由于 M={(p1, m9), (p2, m2), (p3, m6), (p4, m3), (p5, m4), (p6, m1), (p7,m5)} 为P-完全匹配，因此M即为最大匹配，取M作聘用方案可使落聘者最少（4人）。 8、有六位未婚女子L1，L2，L3，L4，L5，L6和六位未婚男子G1，G2，G3，G4，G5，G6相互结识。六位女子L1—L6分别对下列集合中的男子中意： L1:{G1，G2，G4}，L2:{G3，G5}，L3:{G1，G2，G4}， L4:{G2，G5，G6}, L5:{G3，G6}，L6:{G2，G5，G6} 而六位男子G1—G6则分别对下列集合中的女子钟情； G1:{L1，L3，L6}，G2:{L2，L4，L6}，G3:{L2，L5}， G4:{L1，L3}， G5:{L2，L6}， G6: {L3，L4，L5} 问，如何配偶能使双方满意的夫妻最多。 解 分别用顶点和边表示未婚男女和互相满意关系，如下图所示 L1L2L3L4L5L6G1G2G3G4G5G6 图中存在完全匹配 M={(L1, G1), (L2, G3), (L3, G4), (L4, G2), (L5, G6), (L6, G5)}。 所以，按照M配偶，可以使得所有的夫妻都互相满意。 9、简单无向图G为二分图当且仅当G是可2-着色的。 证 先证充分性（当G可2-着色时G是二分图）。 不妨设G的顶点分别着了红白二色，用X表示红色顶点集合，Y表示白色顶点集合，则X∪Y=V，X∩Y=?，且G中任一条边的两个端点必分属X、Y两个集合（分别着不同颜色）。所以，G满足二分图的定义，即G是一二分图。

再证必要性（当G是二分图时G可二着色）。

因为G是二分图，所以可将G中的顶点分成两个集合X和Y，使得X∪Y=V，X∩Y=?，且G中任一条边的两个端点分属X、Y两个集合。现将X中所有顶点着一色，Y中所有顶点着另一色，则所有边的两个端点都着上了不同颜色，即G是可二着色的。

命题得证。

4

9.2 平面图

内容提要

9.2.1 平面图的基本概念

定义9.4 无向图G称为平面图（planar graph），如果G可以在一个平面上图示出来，而使各边仅在顶点处相交。否则称G为非平面图。

定义9.5 平面连通图中各边所界定的区域称为平面图的面（regions）。有界的区域称为有界面，无界的区域称为无界面。界定各面的闭的拟路径称为面的边界（boundary），它的长度称为面的度（degree）。

定义9.6 称平面简单图G是极大平面图（maximal planar graph），如果在G中添加任一边（它不是环，也不是其他边的平行边）后所得的图均非平面图。

定理9.3 极大平面图所有有界面都是三度的面，无界面也是三度的。即所有面的边界均为K3 。

定理9.4 顶点个数n≥4的极大平面图中，顶点的最小度数不少于3 。

9.2.2 欧拉公式和库拉托夫斯基定理

定理9.5 设G为一平面连通图，n为其顶点数，m为其边数，r为其面数，那么 n – m + r = 2

定理9.6 如果平面连通图G的每个面的边界都具有长度l(l≥3)，那么 m =

l(n?2)

l?2其中m为G的边数，n为G的顶点数。

定理9.7 设G为一平面连通简单图，其顶点数n≥3，其边数为m，那么 m ≤ 3n – 6

定理9.8 设G为一平面简单连通图，其顶点数n≥4，边数为m，且G不以K3为其子图，那么

m ≤ 2n – 4

定理9.9 顶点数n不少于4的平面连通简单图G，至少有一个顶点的度数不大于5。

定理9.10 （库拉托夫斯基定理）图G是平面图，当且仅当对G或G的子图作任何同胚运算后所得图均不以K5及K3,3为子图。

9.2.3 着色问题

定义9.7 对连通平面图G实施下列步骤所得到的图G*称为G的对偶图（dual of graph）： （1）在G的每一个面ri的内部作一个G*的顶点vi。

（2）若G中面ri与ri有公共边界，那么过边界的每一边ek作关联vi与vj的一条边ek。ek与G*的其它边不相交。

（3）当ek为面ri的边界而非ri与其它面的公共边界时，作vi的一条环与ek相交（且仅交于一处）。所作的环不与G*的边相交。

定义9.8 图G称为可k-着色的（k-chromatic），如果可用k种颜色给G的所有顶点着

5

******

色，使每个顶点着一种颜色，而同一边的两个不同端点着不同颜色。 定理9.11 任何平面图都是可5-着色的。

习题解答

练习9.2

1、给出图9.19中各面的度，并作一与此图同构的图，使标记2的面在该图的图示中为一无界面。

1 2 3 4

5

6

图9.19 解 面1为2度；面2为3度；面3为3度；面4为8度；面5为5度；面6为1度。 下图与此图同构，且原标记2的面在该图的图示中为一无界面。 235641

2、证明定理9.7，不直接引用定理9.6。 证 由于平面连通简单图每个面的度数至少为3（当n≥3时），故 2m≥3r 又因为n – m + r=2，故 2m≥3(2 – n + m) 即m≤3n – 6

3、证明：有n (n≥3)个顶点，r个面的平面连通简单图满足 r ≤ 2n – 4 证 据定理9.7， m≤3n – 6 又因为n – m + r=2，故

n + r – 2≤3n – 6 即r≤2n – 4 。

4、证明：少于30条边的平面连通简单图至少有一个顶点的度不大于4 。

证 用反证法。假设任一顶点的度均大于或等于5，则5n≤2m＜60，即n＜12。 又因为

5n≤2m≤6n – 12

于是5n≤6n – 12，即n≥12。矛盾。因此至少有一个顶点的度不大于4

6

5、证明：在有6个顶点和12条边的连通平面简单图中，每个面的度均为3。 证 根据欧拉公式n – m + r=2，有

r=2 – n + m=8 故每个面的平均度数为2m / r = 3

又因为连通平面简单图（n≥3）中每个面的度数均大于或等于3，因此该图每个面的度数均为3 。

6、设G为简单无向图，其顶点数n≥11，证明G或G的补G是非平面图。

证 用反证法。假设G和G的补G都是平面图，且G的边数为m，G的边数为m’，则有m≤3n – 6，m’≤3n – 6 （注意，定理9.7对非连通简单平面图同样成立）。进而

m + m’≤6n – 12

又因为 m + m’=n(n – 1)/2，故

n(n – 1)/2≤6n – 12 得3≤n≤10，与n≥11，矛盾。因此G和G的补G中至少有一个是非平面图。

7、证明图9.20中的图都是非平面图。

图9.20 证 (1) 下图中(b)为(a)之子图，而(b)经同胚操作（对虚线内顶点做贯通操作）后为(c)，此乃K3, 3。所以，根据定理9.10，图9.20左图为非平面图。 (a)(b)(c) (2) 同上，下图中(b)为(a)之子图，而(b)经同胚操作（对虚线内顶点做贯通操作）后为(c)，此乃K3, 3。所以，根据定理9.10，图9.20右图为非平面图。 (a)(b)(c) 7

8、作出图9.19的对偶图，再作出你在第一题中所作的平面图的对偶图，并比较这两个对偶图。

解 如下图所示，(a)为9.19的对偶图，(b)为第一题所作平面图的对偶图。经比较可看出两图不同构。 (a)(b) 9、如果平面连通图G的对偶图G*同构于G，则称G为自对偶图，请给出一个自对偶图的例子。 解 10、如果一自对偶图有n个顶点、m条边，证明： m = 2 (n – 1) 证 由于G同构于G*，那么 G的面数r等于其顶点数n。 又因为 n – m + r=2 故m = 2 (n – 1) 。 11、(G*)*未必等同于G，试举例说明之。 解 G(G*)* 12、平面图G称为是完全正则的，如果G的顶点的度都相等，并且G的面的度也相等。 （1）试作出一个完全正则图。 8

*（2）证明：只有五种可能的连通简单图是完全正则的（不算顶点度为1，2的平凡情况）。

解 （1）

证（2）设连通简单图是完全正则的，其各顶点度为j，各面的度为k 。那么

jn?kr?2m又因为 n?m?r?2 故

,m?jnjn ,r?2kn?jnjn??2 2k n(2k?jk?2j)?4k (a) j = 3 时

n(2k?3k?6)?4k

于是 6 – k >0, k可取值为1，2，3，4，5。而k取值为1，2时，不合要求，因此

1）k=3, 则n=4, m=6, r=4 . 2）k=4, 则n=8, m=12, r=6. 3）k=5, 则n=20, m=30, r=12 . (b) j = 4 时

n(2k?4k?8)?4k

于是 4 – k >0, k可取值为1，2，3。而k取值为1，2时，不合要求，因此 4）k=3, 则n=6, m=12, r=8 . (c) j = 5 时

n(2k?5k?10)?4k

于是 10 – 3k >0, k可取值为1，2，3。而k取值为1，2时，不合要求，因此 5）k=3, 则n=12, m=30, r=20 . (c) j = 6 时

n(2k?6k?12)?4k

于是 12 – 4k >0, k可取值为1，2。而k取值为1，2时，不合要求。

当j > 6时，同上可证k<3,不可能构成完全正则的连通简单图。因此，完全正则的连通简单图只有以上五种可能。

13、证明：定理9.9的结论可加强为“至少有3个顶点的度数不大于5”。

证 用反证法。假设度数不大于5的顶点数可以少于3个，但由于n不小于4且为连通图，所以每个顶点的度数最小为1。因此6(n – 2) + 2≤2m。

由于m≤3n – 6，故

6(n – 2) + 2≤2m≤6n – 12，即6n – 10≤6n – 12 矛盾。因而度数不大于5的顶点数至少有3个。

9

14、给出一个平面图，使它是可4-着色的，但不是可3-着色的。 解 15、证明：若图G的最大顶点度数是d，那么G是可(d+1)-着色的。 证 用数学归纳法。 显然，当G的顶点数n≤d+1时，G是可(d+1)-着色的。 设G的顶点数n=k时，G是可(d+1)-着色的，现考虑n=k+1的情况。设v为G中任一点，G’=G – v，则根据归纳假设，G’ 是可(d+1)-着色的。而v的度数不超过d，即与v相邻接的节点所着的颜色不超过d种，则必可以从d+1种颜色中选择一种为d着色，使其与相邻节点均不同色。因此G也是可(d+1)-着色的。 归纳完成，命题得证。 9.3 树

内容提要

9.3.1 树的基本概念

定义9.9 连通无回路的无向图称为无向树，简称为树（tree）。树中的悬挂点又称为树叶（leave），其它结点称为分支点（branched node）。单一孤立结点称为空树（null tree）。诸连通分支均为树的图称为森林（forest），树是森林。

定理9.12 树和森林都是可2-着色的，从而都是二分图。

定理9.13 树和森林都是平面图，其面数为1。

定理9.14 设图T为一树，其顶点数、边数分别是n, m, 那么 n – m = 1 或 m = n – 1

定理9.15 任何多于一个顶点的树都至少有两片叶。 定理9.16 命题“（n，m，）图T为树”与下列5命题中的每一命题等价： （1）T无回路且m = n – 1 。 （2）T连通且m = n – 1 。

（3）T无回路，但添加任一关联T中两顶点的边时，T中产生唯一的一条回路。 （4）T连通，但删去任一边时便不再连通（T的每一边均为割边）。

（5）任意两个不同顶点之间有且仅有一条通路。

9.3.2 生成树

定义9.10 图T称为无向图G的生成树（spanning tree），如果T为G的生成子图且T为树。

定理9.17 任一连通图G都至少有一棵生成树。

定理9.18 设G为连通无向图，那么G的任一回路与G – T(任一生成树T的关于G的补)，至少有一条公共边。

定理9.19 设G为连通无向图，那么G的任一割集与任一生成树至少有一条公共边。 定义9.11 设T为图G的生成树，称T中的边为树枝（branch），称G – T 中的边为弦

10

（chord）。对每一树枝t，T–t分为两个连通分支T1，T2，那么t及两端点分别在T1，T2中的弦组成G的一个割集，它被称为枝t-割集（t-cut set）；而每一条弦e与T中的通路构成一回路，它被称为弦e-回路（e-circuit）。

定理9.20 在连通无向图G中，任一回路与任一割集均有偶数条公共边。 定理9.21 设G为一连通无向图，T是G的生成树， S = {e1, e2, e3,…,ek}

为枝e1-割集，那么e1必在弦ei-回路中（i = 2，3,…，k），不在其它弦e-回路中。 定理9.22 设G为一连通无向图，T是G的生成树， C =（e1, e2,…,ek）

为弦e1-回路，那么e1必定在枝ei-割集中（i = 2，3,…，k），不在其它任何枝e1-割集中。

定理9.23 设G是连通边赋权图，且各边的权互不相等。若C是G中的一条回路，那么C上权最大的边e必定不在G的最小生成树上。

9.3.3 根树

递归地定义根树的概念。

定义9.12 树T称为根树（rooted tree），如果 （1）T为一孤立结点v0 。v0又被称为T的树根。

（2）T1，T2,…,Tk为以v1，v2,…，vk为树根的根树，T由T1，T2,…,Tk及与v1，v2,…，vk相邻的结点v0所组成。v0称为T的树根。 定义9.13 在定义9.12中，

（1）v1，v2,…，vk称为v0的儿子，v0称为它们的父亲。vi，vj同为一顶点v的儿子时，称它们为兄弟。 （2）顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1 (i = 1, 2,…, l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。 （3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又称为T的真子树。

定义9.14 除了树叶外，每个结点都有两个儿子的根树称为完全2元树（binary tree）。 完全2元树有以下性质。

定理9.24 完全2元树的顶点个数n必定是奇数。 定理9.25 完全二元树中叶的数目l? 定理9.26 完全二元树高h满足 ?log2(n?1)?1??h?n?1,其中n为树的顶点数。 2n?1 2这里n为二元树的顶点个数，[a]表示大于等于a的最小整数。

定义9.15 每个结点都至多有两个儿子的根树称为二元树（quasibinary tree）。类似地，每个结点都至多有n个儿子的根树称为n元树。 对各分支结点的诸儿子规定了次序（例如左兄右弟）的n 元树称为n元有序树；若对各分支结点的已排序的诸儿子规定了在图示中的位置（例如左、中、右），那么该n元有序树又称n元位置树。2元位置树各分支结点的左右儿子分别称为左儿子和右儿子。

二元位置树被大量用于数据的表示，例如表示算术表达式及各种字符串。这时，常常需要遍访每一个结点，以下是三种遍访二元树的算法。 （1）先根算法

（1.1） 访问二元树树根r。

11

（1.2） 如果r有左儿子，那么又以先根算法遍访r的左子树（以r的左儿子为根的子树）。

（1.3） 如果r有右儿子，那么又以先根算法遍访r的右子树（以r的右儿子为根的子树）。

（2）中根算法

（2.1） 如果二元树树根r有左儿子，那么以中根算法遍访r的左子树。 （2.2） 访问二元树树根r。

（2.3） 如果二元树树根r有右儿子，那么又以中根算法遍访r的右子树。 （3）后根算法

（3.1） 如果二元树树根r有左儿子，那么以后根算法遍访r的左子树。 （3.2） 如果二元树树根r有右儿子，那么又以后根算法遍访r的右子树。 （3.3） 访问二元树树根r。

习题解答

练习9.3

1．证明定理9.12、定理9.13。 证（1）定理9.12

由于树无回路，即回路长度为0。根据定理9.1，树是二分图。又根据练习9.1之9，树是可2-着色的。

又由于森林的诸连通分支均为树，故森林也是二分图，可2-着色。

（2）定理9.13

由于树无回路，因而无论怎样切割、贯通操作也不可能以K3,3、K5为子图。根据定理9.10，树是平面图，面数为1（无回路）。

又由于森林的诸连通分支均为树，因此森林也是平面图，面数为1 。

2．证明定理9.16之（3）?（4），（4）?（5）。 证（1）（3）?（4）已知T无回路，添加任一边时产生唯一的回路，欲证T连通且删去任一边时便不再连通。

假设T不连通，则至少存在两个顶点vi，vj不可达。在T中添加关联vi、vj的边e，根据(3)，产生唯一回路C，且e在C中（否则与T无回路矛盾）。从C中删去e，vi、vj仍然可达，与假设矛盾。所以，T连通。

假设e是关联vi、vj的边，删除e后T仍然连通，即vi、vj之间有一条不经过e的通路。则在T中，该通路与e构成一回路，与前提矛盾。所以，删去任一边时T不再连通。

（2）（4）?（5）已知T连通，但删去任一边时便不再连通，欲证T的任意两个不同顶点之间有且仅有一条通路。

因为T连通，所以任意两个不同顶点之间至少有一条通路。现假设存在两个顶点vi、vj，vi到vj有不止一条通路，则两条通路构成一闭路径，从闭路径上删去任一边e，T – e 仍连通，与前提矛盾。所以，任意两个不同顶点之间有且仅有一条通路。 3．（1）试画出所有具有五个顶点的、不同构的树。 （2）描述恰有两片叶的树的特征，并证明你的描述是正确的。 解（1） 12

（2）恰有两片叶的树是一条链，除两端的两个悬挂点外，其余皆为2度分支点。证明如下 ：

设树共有n个顶点，其中恰有2片叶，其余n–2个节点的度数均≥2，而它们的平均度数为

2m?22(n?1)?2??2n?2n?2所以，除叶之外，其余节点的度数均为2。为证明它是一条链，用数学归纳法。

显然，当n=2时，树为具有两片叶的链。

假设n=k (k≥2) 时，恰有两片叶的树为一条链。现在考虑n=k+1时的情况。设v为两片叶之一，T’=T–v，则T’仍为一棵恰有两片叶的树（否则添加v后叶的数目将超过2）。根据假设，T’为一链，而在T中，与v相关联的节点只能是T’中的叶，因为其余节点的度数已经达到2，再与v关联将超过2，也就是说，T也是一条链。

归纳完成，命题得证。

4．一棵树有两个2度顶点，1个3度顶点，3个4度顶点，问：它有几个1度的顶点。 解 假设共有k个1度顶点，则

k + 2?2 + 1?3 + 3?4 = 2m = 2(n–1) = 2(k+2+1+3–1) 解得k=9，即共有9个1度顶点

5．一棵树有n2个2度顶点，有n3个3度顶点，……, 有nk个k度顶点，问：它有几个1度的顶点。

解 假设共有n1个1度顶点，则

?ni?1ki?i?2(?ni?1)i?1kkn1??ni(i?2)?2i?2

6. （1）证明：n 个顶点的树，其顶点度数之和为2n – 2。 ?（2）设d1, d2, … , dn 为n个正整数，n≥2,并且

?di?1ni?2n?2。

证明：有树T使T的n个顶点的度数分别是d1, d2, … , dn 。

证 （1）由于

?di?1ni?2m，而m=n – 1（T为树）

故

?di?1ni?2n?2

（2）用数学归纳法。

当n=2时，因为d1 + d2 = 2，d1, d2为正整数，所以d1 =d2 =1，显然两节点组成的树满足要求。

假设当n=k (k≥2) 时，命题成立，现在考虑n=k+1的情况。

13

∵ d1, d2, … , dk+1 为k+1个正整数，并且

?di?1k?1i?2k

k?1i?1 ∴d1, d2, … , dk+1中必存在某个di =1（1≤i≤k+1），否则

?dk?1i?1i?2k?2，

d1, d2, … , dk+1中必存在某个dj≥2（1≤j≤k+1），否则

?di?k?1?2k，

不失一般性，设i＜j，对于 k个正整数d1, d2, … ,di-1, di+1, … , dj–1, … , dk+1，它们的和为2k–2，根据归纳假设，存在一棵有k个节点的树T，其各节点的度数与这k个整数一一对应。现在T上添加顶点vi，并增加vi与vj的关联边，得到T’，T’仍为树，且vj的度数从dj–1变成了dj，vi的度数为1 (di)，其余各节点度数不变，即T’各节点的度数分别与d1, d2, … , dk+1一一对应。 归纳完成，命题得证。 7．给出图9.35的最小生成树，并写出关于这一生成树的枝割集系和弦回路系。 89106475311 图9.35 解 最小生成树如下图所示 89106475311 共有4条枝，5条弦，因为各边权重各不相同，所以以下用相应的权来记边 枝3-割集是{3，8，9，10} 枝4-割集是{4，7，9，10，11} 枝5-割集是{5，10，11} 枝6-割集是{6，7，8，9，10，11} 弦7-回路是{7，4，6} 弦8-回路是{8，3，6} 弦9-回路是{9，3，4，6} 弦10-回路是{10，3，4，5，6} 弦11-回路是{11，4，5，6}

8．证明定理9.22。

证 设S为任一枝ei -割集（i=2, 3, …, k），例如S为枝e2 -割集，则C与S有偶数条公共边，其中之一是e2，由于C中e1为弦，其余均为枝，而S中除e2外均为弦，所以C与S还应有的公共边只能是e1，故e1在枝e2 -割集中。由于证明过程对一切ei（i=2, 3, …, k）均

14

成立，因此定理的前半部分得证。

设S为枝e -割集，而e≠e2, e3, …, ek，若e1在S中，那么C与S只能有e1一条公共边，因为S中只有e为枝，而C中只有e1为弦，故e1?S， 定理的后半部分得证。

由此，定理得证。

9. 判断下列断言的真假：

（1）连通无向图G的任何边，都是G的某一棵生成树的枝。 （2）连通无向图G的任何边，都是G的某一棵生成树的弦。 解 （1）假。因为环不是任何生成树的枝。

（2）假。G的割边不是任一生成树的弦。

10．设G为连通无向图，证明：

（1）G的任一生成树T的关于G的补G – T 中不含有G的割集。

（2）G的任一割集S的关于G的补G –S（从G中删除所有S中的边）中不含有G的生成树。

证（1）用反证法。假设存在某个T，使得G – T 中含有G的割集，那么根据割集的定义，T不连通，与T为树矛盾，所以，原命题得证。

（2）用反证法。假设存在某个S，使得G – S 中含有G的生成树，则根据树的定义，G – S仍连通，与S为割集矛盾。所以，原命题得证。

11．设C是连通无向图G的一条回路，a , b是C中任意两条边。证明：存在G的割集S，使得S与C仅以a , b为公共边。

证 设T为以a为枝，以b为弦的G的生成树（这总是可以办到的，因为a、b同在一条回路C上），则C为T的弦b-回路。用S表示枝a-割集，因为a?C，根据定理9.22，b必在S中。所以，a、b同为C和S的公共边。除此而外，C、S不可能再有其它的公共边，因为S中只有枝a，C中只有弦b。定理得证。

12．T是连通无向图G的生成树的充分必要条件是：T是G的连通生成子图，且T有n – 1条边，这里n是G的顶点数。

证 必要性。

设T是G的生成树，那么T是G的生成子图，且T为树，即T是连通图，m = n – 1 。 充分性。

设T连通且m = n – 1，那么根据树的定义，可知T为树。又因为T是G的生成子图，故 T是G的生成树。

13．设T1，T2为连通无向图G的两棵不同的生成树，边a在T1中，但它不在T2中。证明：T2中存在边b , 使b不在T1中，并且（T1 – a）? {b}以及（T2 – b）? {a}都是图G的生成树。

证 由于a在T1中，而不在T2中，故存在T1的枝a-割集S，T2的弦a-回路C。根据定理9.20，S和C除了a之外至少还有一条公共边，记为b，则b为T2的枝，T1的弦，即b属于T2，不属于T1。

又因为对T1来说，a属于弦b-回路，对T2来说，b属于弦a-回路，因此

15

（T1 – a）? {b}以及（T2 – b）? {a}都是无回路的图，且仍满足m = n – 1 故（T1 – a）? {b}以及（T2 – b）? {a}都是图G的生成树。

14. 修改克鲁斯克尔算法,使它能作出平面连通边赋权图的最大生成树。 解 设连通边赋权图G=有n个顶点m条边，并设 W(e1)＞W(e2)＞W(e3)＞…＞W(em) （1）设置变量k，A。置k为1，A为Φ

（2）若G的子图不包含回路，那么置A为A∪{ek} （3）当|A| = n – 1时算法终止，否则置k为k+1，回到步骤（2） 即为所求的最大生成树。

15. 给出一个简明而又充分的条件,使得满足这一条件的平面连通边赋权图的最小生成树是唯一的。

解 边权互不相等的平面连通边赋权简单图的最小生成树是唯一的。若不然，根据本练习第13题，将有T1，T2为连通无向图G的两棵不同的生成树，但它们的边权之和相等。那么必有a在T1中，而不在T2中，b在T1中，而不在T2中，不妨设W(a)＞W(b)。于是（T1 – a）? {b}是一棵边权之和更小的生成树。导出矛盾。

16．试将定理9.25、定理9.26推广到完全n元树上，并证明你的推广是正确的。

证 （1）定理9.25的推广：完全n元树中叶的数目l?(n?1)x?1，其中x为树的顶n点数。

设完全n元树T有x个顶点，l片叶和m条边，那么除根（n度）以外它有x– l–1个分支节点，各为n+1度，于是

n + l + (n+1)( x– l–1) = 2m =2(x–1)

(n?1)x?1 nx?1 将n=2代入得l?，与原定理同。

2 解出l?（2）定理9.26的推广：完全n元树高h满足?logn[(n?1)x?1]?1??h?中x为树的顶点数，?a?表示上取整。

如果高为h的n元树的树根到每片叶的通路长度均为h，那么它的顶点数应是

x?1，其nnh?1?1 n?n?n?...?n?

n?1012hnh?1?1 因此，≥x，即h??logn[(n?1)x?1]?1?

n?1另一方面，如果完全n元树的每个分支节点的n个儿子中都只有一个不是叶，这时它的顶点树达到最少，即

n?h?1?x

16

h?x?1 nx?1 nx?1 将n=2代入得?log2(x?1)?1??h?，与原定理同。

2 综上，有?logn[(n?1)x?1]?1??h? 17．（1）用二元位置树表示命题公式

（A→B）∧（┐（C∨B）?┐B）

注意，请将一元运算符的运算对象取做运算符结点的右儿子。

（2）用3种遍访算法遍访你作出的二元位置树，写出相应的线性表达式，并像式（9-4）（9-5）那样，用横线标出其波兰表示和逆波兰表示的运算进程。 解 （1） ∧→AB┐∨CA?┐B （2）先根算法：∧→AB?┐∨CA┐B

中根算法：A→B∧┐C∨A?┐B

后根算法：AB→CA∨┐B┐?∧

18．将图9.36（a）中的有序树及（b）中的有序森林，表示为2元位置树。

(a) (b) 图9.36 解

(a)(b)17

19．有8枚硬币，其中可能有1枚是假币（但假币不多于1枚），假币与真币重量不等。试用一架天平来称量，3次称出假币或断言假币不存在，请用根树表示你的称量策略。 解 {1,2,3}-{6,7,8}左低右低水 平{1,2}-{3,6}{4}-{5}{3,6}-{7,8}左低水 平右低左低水 平右低左低水 平右低{1}-{2}{7}-{8}{4}-{1}{1}-{5}{1}-{2}{7}-{8}左低水 平右低{3}Φ{6}左低右低 重左低水 平水 平右低 重左低右低左低水 平右低{1}{6}{2}{8}{7}{4}{5}{4}{5}{2}{1}{7}{3}{8} 重 轻 重 轻 轻 重 轻 轻 重 轻 轻 重 轻 重注：1. Φ表示伪币不存在 2. 伪币下面的说明文字指出伪币比真币重还是轻

18

本文来源：https://www.bwwdw.com/article/o4b2.html