第9章习题答案

第9章习题答案3.画出有三个顶点四条弧的所有可能的简单有向图(注意:同构的图看作同一个图)。解：4.画出有三个顶点的所有可能的简单无向图，但不能出现同构的图。解：5.证明图9.25中的有向图D1和D2同构。证明：因为在两个图的顶点集合之间存在双射f：15fvu,21fvu32fvu43fvu,54fvu并且边有如下对应关系：1251,,vvuu，1453,,vvuu，2514,,vvuu，3221,,vvuu，3423,,vvuu，4534,,vvuu5145,,vvuu，5342,,vvuu所以两图同构。6.证明图9.26中的无向图G1和G2不同构。证明：因为在图G1中，每个3度顶点都有2个3度顶点与之邻接，而图G2中，每个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中，任何一个回路总包含有一个基本回路。证明：设121nuuuu是有向图D中的任意一条回路。除1u外，若回路中无重复出现的顶点，则它是一条基本回路，否则存在ij，使得ijuu。我们把12iijuuu从回路中删去，所得结果仍为一条回路。若这条新回路除1u外仍有重复出现的顶点，就重复前边的操作，直到无重复出现的顶点为止。最后得到的回路就是一条基本回路。这表明，任何一条回路中必包含有一条基本回路。13.判别图9.28及图9.29中的有向图是否为强连通的，单向连通的或弱连通的解：两图均为单向连通的。17.证明在一个连通无向图中。任何两条最长的基本链必有公共顶点。证明：假设图中两条最长的基本链分别为P1=（a0，a1，a2，，an，），P2=（b0，b1，b2，bm，），mn，P1与P2没有公共顶点。由于此图是连通图，则P1中必有一顶点ai，P2中必有一顶点bj，ai和bj连通，令ai到bj的链为P3=（ai，c1，c2，ck，bj），则｜P3｜1，ai和bj分别将链P1，P2分成两部分，则P1的较长部分与P3和P2的较长部分构成的链长度大于m，这与P2是两条最长基本链中之一矛盾。因此，任何两条最长的基本链必有公共顶点。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）个连通分支，令它们的顶点数分别为n1，n2，，nk，则第i个连通分支ni的每个顶点的次数至多为ni-1。设u，v分别为任意两个不同连通分支i和j的顶点，则它们的顶点次数之和至多为ni+nj-2，因为n1+n2++nk=n，所以ni+nj-2n-1，这与G中任何两个顶点的次数之和大于或等于n-1矛盾，故G必为连通图。20.设给定无向图G=V,E，按如下方式构造无向图Gˊ=Vˊ,Eˊ，使得Vˊ=V，Eˊ={(u,v)*｜u∈V∧v∈V∧(u,v)E}，证明:如果G是不连通的，则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个电话局的任何两个电话局之间都可以通话。