华东师范大学离散数学章炯民课后习题第8章答案 VIP免费

(P147)2，32.一房子的平面图如图。问能否从前门进去，最后从后门出去，走过所有的门且每扇门只经过一次？解：建立无向图图模型如下：顶点表示房间和前后门区域，边表示房间(区域)之间的门。原问题等价于如下的问题：在表示前门区域和后门区域的顶点之间，是否存在欧拉通路？答案是：存在，因为这个图是连通图，且这两顶点的度为奇数，而其余顶点的度均为偶数（图需重画）3.对于有16个扇区和4个探测器的磁鼓，给出一种合理的0-1赋值。解：00001001101011115.说明下图不是哈密顿图。解：从图中删除所标记的6个顶点，所得到的图由7个孤立点组成，有7个连通分量。所以，该图不满足哈密顿图的必要条件，因而不是哈密顿图（图需改，怎么改请看InABCDEOut解答）*补充：为了测试计算机网络上的所有连接和设备，可以在网络上发一个诊断消息。为了测试所有的连接，应当使用什么种类的通路？为了测试所有的设备呢？解：测试连接：欧拉通路；测试设备：哈密顿通路*13.证明任意竞赛图都有有向哈密顿通路。证明：考虑竞争图的某条长度最大的有向基本通路l，证明l含有所有的顶点，从而l是有向哈密顿通路。采用反证法，假定存在不在l上的顶点。不妨设顶点v不在l上，l=v1v2…vk-1vk。v和vk之间的有向边必从v指向vk，否则l将不是最长的基本通路。类似地，v和v1之间的有向边必从v1指向v。从v2开始，顺着l找到第1个顶点vi，v和vi之间的有向边从v指向vi，（这样的顶点一定存在，因为vk就是这样的顶点）。显然，v1v2…vi-1vvi…vk-1vk是基本通路，长度大于l。这与l是长度最大的基本通路矛盾。于是，l含有所有的顶点。（需加图，请看证明）14.设简单连通图G有n个顶点、e条边。若G是平面图，则e≤3n-6。证明：简单图任何回路的长度均不小于3，故简单平面图每个面的次数均大于等于3，所以e≤3(n-2)/(3-2)=3n-6（欧拉公式的推论）17.若简单连通图G有n个顶点、e条边，则G的厚度至少为e/(3n-6)。（简单图G的厚度是指G的平面子图的最小个数，这些子图的并是G。）证明：设简单连通图G的厚度为t。于是，G可分为t个简单平面子图，G1，G2，…，Gt，不妨设其顶点数分别为v1，v2，…，vt，边数分别为e1，e2，…，et。ei≤3vi-6≤3v-6，i=1,2,…,t（对简单连通或不连通平面图都成立），所以e=ei≤t(3v-6)，t≥e/(3v-6)，从而G的厚度至少为e/(3v-6)23.若一个无向图有n个顶点、e条边、p个连通分量，则n-p≤e。证明：显然，在p个连通分量之间添加p-1条边即可将G改造为连通图，其边数e+p-1≥n-1，所以n-p≤e29.证明连通图的割边一定是每棵生成树的边。证明：删除割边后的图一定不连通，其中不存在生成树。所以，每课生成树都包含割边*补充：证明树的色数不大于2。证明：分两种情况：（1）树仅有1个顶点。显然，树的色数为1，从而结论成立（2）树的顶点数大于1。任取树的一个顶点，记为v。v到每个顶点都存在唯一的基本通路，可根据该通路的长度的奇偶性标记顶点，具有相同奇偶性的顶点必定不相邻（否则将产生回路，参见下图），从而可以根据顶点的奇偶性对顶点进行着色，从而树的色数为2，结论成立。（加图，请看明白上述证明）33.有且仅有一个顶点的入度为0，而其他顶点的入度均为1的有向图是否一定是根树？为什么？解：不是。反例：根数+有向环37.若完全m叉树有n0个叶子，n′个分支结点，则n0=(m-1)n′+1。解：完全m叉树只有出度为m和0的顶点，所以顶点的入度之和为mn′，顶点总数为n′+n0。于是，mn′=n′+n0-1（握手定理、树的边数=顶点数-1），从而n0=(m-1)n′+1*补充：79个外表完全一样的硬币中有一个是假的，这个假硬币比真硬币轻。请设计一种辨别假币的方法，其中只能使用一架天平，要求称量次数最少。请给出证明。解：将含假币的硬币尽可能平均地分为3组，各组中的硬币数量至多相差1，其中至少有2组，它们所含的硬币数量相等，每次称这2组。第一次称两组硬币，每组各26个。如果平衡，则假币在剩下的27个硬币中，否则在较轻的那组中。第二次称量类似地进行，所得到的含假币的组最多包括9个硬币。第三次称量所得到的含假币的组最多包括3个硬币。第四次称量得到的含假币的组只包括1个硬币，即找到了假币。证...