第9章习题答案
3. 画出有三个顶点四条弧的所有可能的简单有向图(注意: 同构的图看作同一个图)。
解：
4. 画出有三个顶点的所有可能的简单无向图，但不能出现同构的图。
解：
5. 证明图9.25中的有向图D 1和D 2同构。
证明：因为在两个图的顶点集合之间存在双射f ： ()15f v u =, ()21f v u = ()32f v u =
()43f v u =, ()54f v u = 并且 边有如下对应关系：
1251,,v v u u ?，1453,,v v u u ?，2514,,v v u u ?，
3221,,v v u u ?，3423,,v v u u ?，4534,,v v u u ?
5145,,v v u u ?，5342,,v v u u ?
所以两图同构。
6. 证明图9.26中的无向图G 1和G 2不同构。
证明：因为在图G 1中，每个3度顶点都有2个3度顶点与之邻接，而图G 2中，每个3度顶点只有一个3度顶点与之邻接。所以两图不同构。
7. 证明在n 个顶点的简单无向图中(n ≥2)，至少有两个顶点次数相同。
证明：反证法，假设n 个顶点的次数互不相同。由于n 个顶点的简单无向图中，每个顶点的次数均小于n ，则n 个顶点的次数分别为0，1，2，?n-1。次数为0的顶点为孤立点，因此，图中次数为0和n-1的顶点不可能同时存在，故假设错误。所以在n 个顶点的简单无向图中(n ≥2)，至少有两个顶点次数相同。 9. 设G 是有四个顶点的完全无向图， (1) 画出G 的所有不同构的子图。
(2) 指出哪些是生成子图，哪些是导出子图。
解：(1) G 的所有不同构的子图如下：
(1) (2) (3) (4) (5) (6)
其中(8)至(18)是生成子图，(1)、(3)、(7)、(18)是导出子图。 12. 证明在有向图D 中，任何一个回路总包含有一个基本回路。
证明：设121n u u u u 是有向图D 中的任意一条回路。除1u 外，若回路中无重复出现的顶点，则它是一条基本回路，否则存在i j <，使得i j u u =。我们把12i i j u u u ++ 从回路中删去，所得结果仍为一条回路。若这条新回路除1u 外仍有重复出现的顶点，就重复前边的操作，直到无重复出现的顶点为止。最后得到的回路就是一条基本回路。这表明，任何一条回路中必包含有一条基本回路。
13. 判别图9.28及图9.29中的有向图是否为强连通的，单向连通的或弱连通的
解：两图均为单向连通的。
17. 证明在一个连通无向图中。任何两条最长的基本链必有公共顶点。
证明：假设图中两条最长的基本链分别为P 1=（a 0，a 1，a 2，?，a n ，），P 2=（b 0，b 1，b 2，?b m ，），m ≤n ，P 1与P 2没有公共顶点。由于此图是连通图，则P 1中必有一顶点a i ，P 2中必有一顶点b j ，a i 和b j 连通，令a i 到b j 的链为P 3=（a i ，c 1，c 2，?c k ，b j ），则｜P 3｜≥1，a i 和b j 分别将链P 1，P 2分成两部分，则P 1的较长部分与P 3和P 2的较长部分构成的链长度大于m ，这与P 2是两条最长基本链中之一矛盾。因此，任何两条最长的基本链必有公共顶点。 18. 证明在一个无向图G 中，如果有两个且仅有两个奇顶点，则这两个顶点是连通的。
证明：假设无向图G 中恰有两个奇度顶点U 和V ，若U 和V 不连通，则U 和V 分别在G 的两个不同的连通分支中，不妨把这两个连通分支分别记为G1和G2，于是G1和G2中各含一个奇数顶点。这与推论：“在任何图中，度数为奇数的顶点个数必定是偶数”相矛盾。故U 和V 两顶点必连通。
19. 设G 是具有n 个顶点的简单无向图，并且G 中任何两个顶点的次数之和大于或等于n-1，证明G 为连通图。
证明: 假设G 不是连通图，有k （k >1）个连通分支，令它们的顶点数分别为n 1，n 2，?，n k ，则第i 个连通分支n i 的每个顶点的次数至多为n i -1。设u ，v 分别为任意两个不同连通分支i 和j 的顶点，则它们的顶点次数之和至多为n i +n j -2，因为n 1+n 2+?+n k =n ，所以n i +n j -2< n-1，这与G 中任何两个顶点的次数之和大于或等于n-1矛盾，故G 必为连通图。
20. 设给定无向图G=
证明：因为G 是不连通图，不妨设G 有k 个连通分支，则k ≥2。由已知条件，在G ˊ图
(8) (9) (10) (12)
(11) (15) (16) (14) (18)
(13)
(17) (7)
中，G的不同连通分支中的两个顶点之间有边相连。若u和v是G的同一连通分支中的两个不同顶点，则在Gˊ中，u和v与G的另一连通分支中的顶点w邻接，故u和v连通。所以，Gˊ是连通图。
23. 设有2n个电话局，如果每一个电话局至少可以与另外n个电话局通话，证明在这2n 个电话局的任何两个电话局之间都可以通话(也可能要通过另外的电话局)
证明：设电话局为顶点，在能通话的电话局之间连一条边，则得无向简单图G。由题意可知，G有2n个顶点，G的每个顶点的度数大于等于n，证明G为连通图。反证法如下：假设G不是连通图，则G至少有两个连通分支。由于G有2n个顶点，故必存在一个最多有n个顶点的连通分支，令其为G1。由于G是无向简单图，因此其连通子图G1中的每个顶点的度数 n-1，这与G的每个顶点的度数大于等于n矛盾，因此G必为连通图。这就是说，G的2n个顶点中，任何两个顶点都可达。也即表明2n个电话局的任何两个电话局之间都可以通话。