离散数学第九章习题的答案ppt课件

1、第第9章习题答案章习题答案 6. 证明图证明图9.26中的无向图中的无向图G1和和G2不同构。不同构。证明：因为在图证明：因为在图G1中，每个中，每个3度顶点都有度顶点都有2个个3度顶点度顶点与之邻接，而图与之邻接，而图G2中，每个中，每个3度顶点只有一个度顶点只有一个3度顶点度顶点与之邻接。所以两图不同构。与之邻接。所以两图不同构。 7. 证明在证明在n个顶点的简单无向图中个顶点的简单无向图中(n2)，至少有两个，至少有两个顶点次数相同。顶点次数相同。证明：反证法，假设证明：反证法，假设n个顶点的次数互不相同。由于个顶点的次数互不相同。由于n个顶点的简单无向图中，每个顶点的次数均小于个顶点的

2、简单无向图中，每个顶点的次数均小于n，则则n个顶点的次数分别为个顶点的次数分别为0，1，2，n-1。次数为。次数为0的的顶点为孤立点，因而，图中次数为顶点为孤立点，因而，图中次数为0和和n-1的顶点不可的顶点不可能同时存在，故假设错误。所以在能同时存在，故假设错误。所以在n个顶点的简单无个顶点的简单无向图中向图中(n2)，至少有两个顶点次数相同。，至少有两个顶点次数相同。 12. 证明在有向图证明在有向图D中，任何一个回路总包含有一个中，任何一个回路总包含有一个基本回路。基本回路。证明：设是有向图证明：设是有向图D中的任意一条回路。除外，若回中的任意一条回路。除外，若回路中无重复出现的顶点，则

3、它是一条基本回路，否则路中无重复出现的顶点，则它是一条基本回路，否则存在，使得。我们把从回路中删去，所得结果仍为一存在，使得。我们把从回路中删去，所得结果仍为一条回路。若这条新回路除外仍有重复出现的顶点，就条回路。若这条新回路除外仍有重复出现的顶点，就重复前边的操作，直到无重复出现的顶点为止。最后重复前边的操作，直到无重复出现的顶点为止。最后得到的回路就是一条基本回路。这表明，任何一条回得到的回路就是一条基本回路。这表明，任何一条回路中必包含有一条基本回路。路中必包含有一条基本回路。 17. 证明在一个连通无向图中。任何两条最长的基本证明在一个连通无向图中。任何两条最长的基本链必有公共顶点。链

4、必有公共顶点。证明：假设图中两条最长的基本链分别为证明：假设图中两条最长的基本链分别为P1=（a0，a1，a2，an，），），P2=（b0，b1，b2，bm，），），mn，P1与与P2没有公共顶点。由于此图没有公共顶点。由于此图是连通图，则是连通图，则P1中必有一顶点中必有一顶点ai，P2中必有一顶点中必有一顶点bj，ai和和bj连通，令连通，令ai到到bj的链为的链为P3=（ai，c1，c2，ck，bj），那么），那么P31，ai和和bj分别将链分别将链P1，P2分成分成两部分，则两部分，则P1的较长部分与的较长部分与P3和和P2的较长部分构成的较长部分构成的链长度大于的链长度大于m，这与，

5、这与P2是两条最长基本链中之一矛是两条最长基本链中之一矛盾。因而，任何两条最长的基本链必有公共顶点。盾。因而，任何两条最长的基本链必有公共顶点。18. 证明在一个无向图证明在一个无向图G中，如果有两个且仅有两个中，如果有两个且仅有两个奇顶点，则这两个顶点是连通的。奇顶点，则这两个顶点是连通的。证明：假设无向图证明：假设无向图G中恰有两个奇度顶点中恰有两个奇度顶点u和和v，若，若u和和v不连通，则不连通，则u和和v分别在分别在G 的两个不同的连通分支的两个不同的连通分支中，不妨把这两个连通分支分别记为中，不妨把这两个连通分支分别记为G1和和G2，于是，于是G1和和G2中各含一个奇数顶点。这与推论

6、：中各含一个奇数顶点。这与推论：“在任何在任何图中，度数为奇数的顶点个数必定是偶数相矛盾。图中，度数为奇数的顶点个数必定是偶数相矛盾。故故u和和v两顶点必连通。两顶点必连通。 19. 设设G是具有是具有n个顶点的简单无向图，并且个顶点的简单无向图，并且G中任中任何两个顶点的次数之和大于或等于何两个顶点的次数之和大于或等于n-1，证明，证明G为连为连通图。通图。证明证明: 假设假设G不是连通图，有不是连通图，有kk1个连通分支，个连通分支，令它们的顶点数分别为令它们的顶点数分别为n1，n2，nk，则第，则第i个个连通分支连通分支ni的每个顶点的次数至多为的每个顶点的次数至多为ni-1。设。设u，

7、v分别为任意两个不同连通分支分别为任意两个不同连通分支i和和j的顶点，则它们的顶点，则它们的 顶 点 次 数 之 和 至 多 为的 顶 点 次 数 之 和 至 多 为 n i + n j - 2 ， 因 为， 因 为n1+n2+nk=n，所以，所以ni+nj-2 n-1，这与，这与G中任中任何两个顶点的次数之和大于或等于何两个顶点的次数之和大于或等于n-1矛盾，故矛盾，故G必必为连通图。为连通图。 20. 设给定无向图设给定无向图G=，按如下方式构造无向，按如下方式构造无向图图G=，使得，使得V=V，E=(u,v)*uVvV(u,v)E，证明，证明: 如果如果G是不连通的，是不连通的，则则G是

8、连通的。是连通的。证明：因为证明：因为G是不连通图，不妨设是不连通图，不妨设G有有k个连通分个连通分支，则支，则k2。由已知条件，在。由已知条件，在G图中，图中，G的不同连的不同连通分支中的两个顶点之间有边相连。若通分支中的两个顶点之间有边相连。若u和和v是是G的的同一连通分支中的两个不同顶点，则在同一连通分支中的两个不同顶点，则在G中，中，u和和v与与G的另一连通分支中的顶点的另一连通分支中的顶点w邻接，故邻接，故u和和v连连通。所以，通。所以，G是连通图。是连通图。 23. 设有设有2n个电话局，如果每一个电话局至少可以与另个电话局，如果每一个电话局至少可以与另外外n个电话局通话，证明在这

9、个电话局通话，证明在这2n个电话局的任何两个电个电话局的任何两个电话局之间都可以通话话局之间都可以通话(也可能要通过另外的电话局也可能要通过另外的电话局)证明：设电话局为顶点，在能通话的电话局之间连一条证明：设电话局为顶点，在能通话的电话局之间连一条边，则得无向简单图边，则得无向简单图G。由题意可知，。由题意可知，G有有2n个顶点，个顶点，G的每个顶点的度数大于等于的每个顶点的度数大于等于n，下面证明，下面证明G为连通图。为连通图。假设假设G不是连通图，则不是连通图，则G至少有两个连通分支。由于至少有两个连通分支。由于G有有2n个顶点，故必存在一个最多有个顶点，故必存在一个最多有n个顶点的连通分支，个顶点的连通分支，令其为令其为G1。由于。由于G是无向简单图，因此其连通子图是无向简单图，因此其连通子图G1中中的每个顶点的度数的每个顶点的度数 n-1，这与，