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个顶点
不是图