《华东师范大学离散数学章炯民课后习题第7章答案》由会员分享，可在线阅读，更多相关《华东师范大学离散数学章炯民课后习题第7章答案（6页珍藏版）》请在金锄头文库上搜索。
1、Attention:某些答案有问题的已用灰色标出，请大家注意(P123)2，6，71.6个学生：Alice、Bob、Carol、Dean、Santos和tom，其中,Alice和Carol不和，Dean和Carol不和，Santos、Tom和Alice两两不和。请给出表示这种情形的图模型。2. 至少含一个顶点的C3的子图有多少个？答：9个。单个顶点有三种，单条边有三种，两条边时有三种，共9个子图。3. 证明：在顶点个数不小于2的简单无向图中，必有度数相同的顶点。证明：假设简单图G有n(n2)个顶点，各顶点的度数均不相同，因为简单图W所以度数列应为，-其中的度顶点应与其余所有顶点邻接，而这与中有
2、度顶点矛盾，故中必有度数相同的顶点。4. 对哪些n值来说下列图是偶图？答：a)Knb)Cnc)Wnd)Qna) K完全图n=2时是偶图nb) C圈图n为偶数时候为偶图nc) Wn轮图不是偶图nd) Qn立方图n为自然数时是偶图n(P123)4，*12，*补充1. 简单无向图G有n个顶点，n+1条边，证明G中至少有一个顶点的度大于或等于3。证明：因为IEI=n+1,所以工d(V)=2n+2，假设G中所有顶点度数都小于3,则工d(V)W矛盾。得证。2. 一天晚上张先生夫妇参加了一个聚会，参加聚会的人中还有另外三对夫妇，他们相互握了手。假设没有人自己与自己握手，没有夫妻之间的握手，且同两个人握手不超
3、过一次。当其他人告诉张先生，他或她握了多少次手时，答案都不相同。问张先生和太太分别握了几次手？答：因为当其他人告诉张先生，他或她握了多少手时，答案都不相同，所以除张先生外，其他人握手次数为0，1，2，3，4，5，6。所以握6次手和握0次手的为夫妇，类似的握5次与握1次的为夫妇，握4次和握2次的为夫妇，所以张先生和太太都握了3次手。3. 证明：若平面上有100个点，且其中任意两点间的距离至少是1，则相距恰为1的顶点对最多有300个。(提示：建立图模型，每个顶点的度均不超过6)证明：以一个顶点为圆心，以1为半径画圆，则在圆周上最多有6个顶点为之相连(因为其中任意两点间的距离至少是1),所以对任意顶
4、点V,d(V)W6工d(V)W0由握手定理得(P123)14,*15,16,171. 设简单无向图G=(V,E)，若&(G)三k(k1),则G有长度为k的基本通路。证明：我们假设存在k-1的基本通路，则存在k个顶点，通路最后一个顶点与通路上顶点相连的度数至多为k-1。因为&(G)三k(k1)，所以该顶点必定与其他顶点相连，那么存在长度为K的基本通路。得证。2. 证明：若无向图G没有长度为奇数的基本回路，则G没有任何长度为奇数的回路。证明：若无向图G没有长度为奇数的基本回路，则G有长度为奇数的回路。即证G中存在长度为奇数的回路，则G中有长度为奇数的基本回路。假设G中有任意长度为奇数的回路，设为R
5、。若R为简单回路，则与条件相矛盾。若不是简单回路，则其中存在相同的边，设Ei=Ej,所以Vi=Vj。所以R的序列ViEi+1Vi+1构成一个回路，此回路为基本回路，若长度为奇数，则得证。若长度为偶数，则从中删除此回路，保留，则得到一新通路，长度为奇数，若仍不是一基本通路，则重复上述删除过程。最后一次删除结束后，所得回路必为长度为奇数的简单回路。3. 证明：在任何无向图中，任何奇数度的顶点都有通路到某个其他的奇数度顶点。证明：在任何简单图中，假设存在奇数度顶点，由无向图有偶数个奇数度顶点可知必都有通路到某个其他的奇数度顶点。4. 分别求出下列三个无向图的各个连通分量。G1：三个连通分支g2：个连
6、通分支g3：两个连通分支(P123)21，241. 无向图的色数为1意味着什么？答：无向图只含孤立点，无边。2. 一大学有5个专业委员会：物理、化学、数学、生物、计算机，6位院士：B、C、D、G、S、W。专业委员会由院士组成，物理委员会有院士：C、S和W,化学委员会有院士：C、D和W；数学委员会有院士：B、C、G和S；生物委员会有院士：B和G；计算机委员会有院士：D和Go每个专业委员会每周开一小时例会，所有成员都不能缺席。如果某院士同时是两个专业委员会的成员，那么这两个专业委员会的例会就不能安排在同一个时间。现要为这些例会安排时间，希望它们的时间尽可能集中。问最少需要几个开会时间？请给出一种安
7、排。答：顶点表示各个专业委员会，边表示两委员会有共同委员。画出如下无向图：对该图着色，可得最少的开会时间为3个。一种开会方案为数学，生物和化学，物理和计算机。(P123)26，291. 有3个顶点的不同构的简单无向图有多少个？答：四个。单独三个顶点，只有一条边，两条边，三条边都有。2. 证明：若无向图G不是连通图，则其补图必为连通图。证明：若无向图G不是连通图，那么不妨假设它包含两个连通分量Pl,P2。P1中任意两个相连的顶点，那么它们在补图都将与P2中某个顶点相连，所以还是连通的。P1中无相连的两个顶点则在补图是连通的。所以其补图必为连通图。(P147)2，31.一房子的平面图如图。问能否从
8、前门进去，最后从后门出去，走过所有的门且每扇门只图模型In与Out寻找欧拉通路。根据推论：连接无向图中两个不同的顶点之间有欧拉通路当且仅当它们的度为奇数且其他顶点的度为偶数。满足条件，所以它存在欧拉通路。2.对于有16个扇区和4个探测器的磁鼓，给出一种合理的0-1赋值。0000100110101111。(P147)5，13*，补充1. 说明下图不是哈密顿图。S为剩下的六个点集合，剩下7个连通分量。不满足哈密顿图的条件，所以不是哈密顿图。2. 为了测试计算机网络上的所有连接和设备，可以在网络上发一个诊断消息。为了测试所有的连接，应当使用什么种类的通路？为了测试所有的设备呢？答：欧拉通路。哈密顿通
9、路。3. 证明任意竞赛图都有有向哈密顿通路。证明：在竞争图中选择一个顶点，然后再找到邻接它的另外一个顶点。我们将此时通路为R。那么对其他顶点必可以加入到R中，形成新的通路，直到所有顶点都加入到R中。(P147)14，171. 设简单连通图G有n个顶点、e条边。若G是平面图，则eW3n-6。证：因为每个区域都大于或等于3的度数，所以2e三因此3由欧拉公式-得Wv-2,所以eW3n-6.2. 若简单连通图G有n个顶点、e条边，则G的厚度至少为e/(3n-6)。(简单图G的厚度是指G的平面子图的最小个数，这些子图的并是G。)证明：设简单连通图G的厚度为t。于是，可以把它分为t个简单平面子图，G,G2,，Gt，其中的顶点数分别设为V,v2，vt，边数分别设为e,e2，片。ei3vi-63v-6，i=l,2,t(对简单连通或不连通平面图都成立)所以e=,eit(3v-6),t三e/(3v-6),即G的厚度至少为e/(3v-6)
