Ch6

3

设是恰有个奇度顶点的连通图，证明：中存在条边不重的行迹，使得 。

将图的个奇度顶点分成组，再将图分割成个子图，且每个子图恰好包含两个奇数顶点。
对每个子图来说，根据推论6.1，子图均存在2个奇度顶点，所以子图均有行迹，每个子图的行迹都恰好遍历了这个子图里的所有边。
把这个行迹取并，就可以遍历中所有边。

4

如何将16个二进制数字（8个0，8个1）拍成一个圆形，使得16个长为4的二进制数在其中都出现且只出现一次。

转化成图论问题。
定义顶点，定义构造图.

每个3位二进制数向左移位，可在其最右补0或1，则每个顶点有.
由可知图为图。
根据其中一条回路可构造出排列。

8

求图6.28的一条最优投递路线。

使用EJ算法。
（1）图的奇度顶集，.
（2）由算法：


（3）构成带权完成图:

（4）上图的最佳匹配.
在中间最短轨为
（5）图如右图：

（6）在图找到回路即为最优投递路线。
不妨设出发点（邮局）为，则其中一条回路为：

9

设是二分图，证明：若是，则必有偶数个顶点。习题1中的图6.27是图吗？为什么？

证明：设二分图, 若是，则.
.
同理.
.
有偶数个顶点。
在图6.27中，, 且没有边

图为二分图，且有11个顶点
不是图

Ch5

1*

分别求出和中不同完美匹配的个数。

的完备匹配个数等于将个元素划分成个大小为2的集合，个数为

的完备匹配可以对第一部分标号，第二部分与第一部分的匹配可以看成全排列，个数为.

2*

树至多有一个完备匹配

证明：
假设存在两个完备匹配和，设，与的顶点集合相同，任取一个顶点，在与中各有一个与其相连的边，设这两条边的另一个顶点为. 在中有一条与相连的边，在中有一条与相连的边，若这两条边的另一个顶点相同，设这个顶点为，则为圈，与树中无圈矛盾。若这两条边的顶点不同，设为，以此类推，必然会出现顶点相同的情况，为圈，与树中无圈矛盾。
故树之多有一个完备匹配。

7*

证明：二分图有完备匹配的充要条件是，对任意，都有。这个条件对一般图是否成立？

证明：
设,
则.
（必要性）：
因为二分图有完备匹配，所以中的顶点都被许配。
由定理，有. 同理，.

（充分性）：
不妨设，取，由定理，存在匹配，使得中的顶点都被匹配。

中的顶点也相应地都被匹配。所以匹配即为二分图的完备匹配。
对一般图不成立，例如满足，但是没有完备匹配。

13*

用定理来证明定理。

定理：图（G为一般图，不一定是二分图）由完备匹配，都有.
定理：二分图，且，存在将中的顶点都许配的匹配都有，其中为的邻顶集合。
证明：
对二分图，当为偶数时，加一些边使得为完全图；当时奇数时，加一些边和顶点使得是完全图。图变成完全图，中存在将中所有顶点都许配的匹配的充要条件是有完备匹配。此时定理等价于有完备匹配的充要条件是.
（必要性）：
, 由定理，
在中，中点都是孤立点，所以
.
（充分性）：
对，并设，且.
因为是一个完全图，则在中删去不会增加连通片个数，且最多产生一个奇片. 删去可能会使得中有孤立顶点，设此时中的孤立顶点为，则，则有
若，则；
若，则；
若为偶数，则；
若为奇数，则；
综上，对，都有. 由定理，为有完备匹配的图。

14

证明：树有完备匹配，当且仅当对任意，都有。

证明：
（必要性）：
树T有完备匹配，由定理，, 都有.
令，则.
由于树T由完备匹配，即为偶数，则为奇数。
.
综上，.
（充分性）：
，都有，则为偶数。
删去后，树被划分成若干个连通片，且只有一个连通片为奇片，设奇片中与相连的顶点为，在树中，确定一个后，由于，所以被唯一确定。
被唯一确定。
是任意的
所有相对应的的集合就是T的完备匹配。
综上，树具有完备匹配。

17

设有四个人，有四分工作，每个人做某份工作的效率如下面的矩阵所示，试求最佳的工作分配方案

按照算法一步步计算即可。
构造相等子图

无完备匹配，取D为未被许配的点，可得：



，重新构造相等子图：

最佳分配方案为：.

19

证明：算法中修改顶标后，仍然是可行顶标。

证明：
修改的可行顶标

对,
(1) 若，则.
(2) 若，
，
.
对,
.
综上，算法修改顶标后，仍然是可行顶标。

Ch4

20*

设是平面上个点的集合，，其中任何两点之间的距离至少是1. 证明：最多有个点对，其距离恰好是1.

证明：
不妨设中顶点之间的距离恰好为1，只要证明中最多有条边。
由推论4.2，只要证是平面图即可。
（反证）：
假设有边在除顶点外交叉，交叉点设为。



不妨设,
则有
即距离小于1，矛盾。
图是平面图。得证。

Ch3

1*

是k-边连通图，是的 条边的集合，则 。

根据边割集的性质，去掉条边后仍然是连通图，即

此时在删去一条边后连通分支的数量最多加一，即

2

给出一个连通图G以及k个顶点的集合，使得。

星图

3*

是简单图， ， 则有 。

只有两种情况：

1. 此时G是完全图，显然有

2. 假设，则假设删去个顶点后图失去连通性，因为，所以对于剩下 的三个顶点都至少与一个顶点相邻，即是连通的，矛盾！同理可证明更小 的时候也无法分割。

   若移出某个度数为的顶点的所有相邻顶点，则可以导致其不连通，所以

7*

任给三个非负整数，都存在简单图 ，满足。

该题证明存在行即可。

• 时，完全图满足条件

• 时，取两个完全图，并分别记做，取 中 个顶点(记为),中 个顶点(记为)

  中每个顶点向中的顶点连接一条边，使得一共有条边，且中每个顶点都有边被连接。此时图满足条件

13*

证明定理3.4

(定理边版本)给定图G中的两个顶点,中两两无公共边的 轨道的最大 数量等于最小 边割集的边数，即：

这里仿照 点版本的证明，使用归纳假设法，对边的条数作归纳。

令，因为是的子图有：

由归纳假设得：

因为得边割集加上必为的边割集：

如果上述的两个不等式都成立，则命题对多一条边的图也成立

此时假设两个等式都成立，注意第二个不等式的取等条件， 是 的边割集，但不是

的边割集，是 G 的边割集，这说明 必有一条过 的路。

移出所有 后，整个图被分成 和两部分然后对 和 分别进行收缩操作(这里以收缩 V

为例，在边 上的点不会被收缩)。

对于收缩以后图的边连通度(因为是收缩图，所以最小边割集数不会减小;由的最小性知不会增加)，

再利用归纳假设(注意这里收缩图可以通过细分顶点和加边操作得到原图)，可以得出收缩图的边连通度不变。

Ch2

、

2*

一棵树T有 个 度数为 的顶点， , 其余顶点都是树叶，则T有几片树叶？

由图的性质有：

由树的性质有：

上面两个式子联立可得：

4*

证明：如果T是树，且 ，则T至少有n片树叶

由2.2题的结论我可以可以得到：

得证

6*

证明：树有一个中心或两个中心，且有两个中心时，这两个中心相邻

方法一

可以使用删除叶子节点的方法，即证明删除中所有叶子结点后，新树的中心不变。

对于 ，如果要使最大，v显然是叶子。那么删除所有 中叶子结点后，必然有：

所以u仍为的中心。

重复执行上述操作，最后只能得到这两种情况，即一个顶点或者两个相邻顶点，得证。

方法二

可以用最长轨法证明最长轨的中点为树的中心。

11*

求 生成树的个数

14*

用Kruskal算法求图中边权图最小的生成树

Kruskal的算法是有限选择边权较小的边，选择的顺序是和Prim算法不一样的是，如下图所示，红色标记的是最小生成树，序号则是顺序。

15*

边权图里的最小生成森林是权最小的生成森林，并且在生成森林中 保持原图中任意两个顶点的连通性。如何修改 Kruskal 算法来构造最小 生成森林，并指出时间复杂度。

**Kruskal算法 ** ：

• 输入：加权图
• 输出：G的一棵生成树的边子集

过程如下：

1. 从E中选权最小的边;
2. 若已经选定边，则从中选取边，使得
   • (i)边导出子图不含圈；
   • (ii)在满足(i)的前提下，的权最小，即
3. 反复执行第(2)步，直到选出为止

下面分类讨论：

1. 如果知道G的连通片数，设为k

   则在各连通片上分别执行原Kruskal算法，时间复杂度为：

2. 如果不知道G的连通片数， 则需修改循环中止条件：

   改为反复执行第(2)步，直到从剩余边集中选出任意一条边都会使边导出子图含圈

   时间复杂度为

20*

画出带权 0.2,0.17,0.13,0.1,0.1,0.08,0.06,0.07,0.03 的 Huffman 树

需要注意的是此题的权重之和并不是1，许多人误以为权重之和必须是1。

22*

证明引理2.1

给定，则存在一课Huffman树，使得对应的顶点时兄弟，且这两个顶点在二叉树中的深度都等于树高

不妨设对应的顶点为，假设任意Huffman树中中的深度不等于树高，即存在，使得的深度大于树高 ，显然有。

因为

且

交换的位置，得到 ，则有

1. 当时，，与树同为Huffman树；
2. 当时，，与树为Huffman矛盾；

则的深度等于树高，且同理可证得

若无兄弟，则由Huffman树WPL最小规则，得深度还可以再缩短直至有兄弟。