交大版《离散的数学结构》标准答案.doc

=精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=交大版离散的数学结构标准答案离散数学辅助教材 概念分析结构思想与推理证明 离散数学习题解答 习题六 1从日常生活中列举出三个例子，并这些例子自然地导出两个无向图及一个向图。 解 用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=是全国铁路交通图。是一个无向图。 V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=是中国象棋中“马”所能走的路线图。是一个无向图。 用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+是FORTRAN程序的调用关系图。是一个有向图。 2画出下左图的补图。 解 左图的补图如右图所示。 3证明下面两图同构。图G v1 1 v1 v6 v6 v2 v5 v5证 存在双射函数?:VV及双射函数? : EE ? (v1)=v1 ? (v2)=v2 ? (v3)=v3 ? (v4)=v4 ? (v5)=v5 ? (v6)=v6 ? (v1，v2)=(v1，v2) ? (v2，v3)=(v2，v3) ? (v3，v4)=(v3，v4) ? (v4，v5)=(v4，v5) ? (v5，v6)=(v5，v6) ? (v6，v1)=(v6，v1) ? (v1，v4)=(v1，v4) ? (v2，v5)=(v2，v5) ? (v3，v6)=(v3，v6) 显然使下式成立： ? (vi，vj)=(vi,vj)? ? (vi)=v i? (vj)=vj(1ij6) 于是图G与图G同构。 4证明，中的两个图都是不同构的。 v1 v5 v2G G G G v6 v8 v7 v4 v1? v5? v3 v2? v6? v8? v7? v3? v3 v4? v2 v1 v5v2? v4 v3? v1? v5 v4? 2 图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图G中却没有这样的圈，因为它中的四个度为3的顶点v1?，v5?，v7?，v3?不成长度的4的圈。 图G中有四个二度结点，v6?，v8?，v4?，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有。 在中，图G?中有一2度结点v3?，它相邻的两个项点v2?，v4?的度均为4，而在图G中却没有这样的点。 5一个图若同构于它的外图，则称此图为自补图。在满足下列条件的无向简单图中：1) 给出一个五个结点的自补图； 2)有三个或一结点的自补图吗？为什么？ 3）证明：若一个图为自补图，则它对应的完全图的边数不清必然为偶数。 解 1) 五个结点的自补图如左图G所示同构函数? : VV及? : EE如下：? (a)=a ? (b)=c ? (c)=e ? (d)=b ? (e)=d ?(a，b)=(a，c) ?(b，c)=(c，e) ?(c，d)=(e，d) ?(d，e)=(b，d) (e，a)=(d，a) G G b c d a e b a e c d 2)没有三个结点的自补图。因为三个结点的完备图的边数为3(3?1)=3为2奇数，所以下面3)的结论，不可能有自补图。 有五个结点的自补图。1）中的例子即是一个五个结点的自补图。 3）证：一个图是一个自补图，则它对应的完全图的边数必为偶数。 3 因为若一个图G是自补图，则GG=对应的完全图，而且EE=，G现G同构，因此它们的边数相等，即|E|=|E|，因此对应的完全图的边数|E*|=|E|+|E|=2|E|，是偶数。 实际上，n个项点的自补图G，于其对应的完全图的边数|E*|=n(n?1)n(n?1)，因此有=2|E|，为偶数。这里n4。对于所有大于或等22于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2，?。其中只有n=4k，4k+1，才能使或4k+1形式， 6证明在任何两个或两个以上人的组内，总存在两个人在组内有相同个数的朋友。 证 令上述组内的人的集合为图G的项点集V，若两人互相是朋友，则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简单图G中，若|V|2，则在G中恒存在着两个项点，v1，v2V，使得它们的度相等，即deg(v1)=deg(v2)。其证明如下： 若存在着一个项点vV，使得deg(v)=0，则图G中各项点的度最大不超过n-2。因此n个项点的度在集合0，1，2，?，n-2里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点的度相同。 若不存在一个度为零的项点，则图G中各项点的度最大不超过n-1。因此n个项点的度在集合1，2，?，n-1中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。 7设图G的图示如右所示：1) 找出从A到F的所有初级路； 2）找出从A到F的所有简单路； 3）求A到F的距离。 解 1）从A到F的初级路有7条 D E F A B C n(n?1)为偶数，所以自补图的项点数只能是4k2P1 : (A，B，C，F)，P2 (A，B，C，E，F)，P3 : (A，B，E，F) P4 : (A，B，E，C，F)，P5 : (A，D，C，E，F)，P6 : (A，D，E，C，F) P7 : (A，D，E，B，C，F)。2）从A到F的简单路有9条 除了上述1）中7条外，不有P8 : (A，D，E，C，B，E，F) 4 P9 : (A，D，E，B，C，E，F)。3）从A到F的距离为3。 图可看出，显然从A到F，一步不可能到达，二步也不可到达；但有长度为3的路，比如P1，P3，P5等能从A到F，故从A到F的距离为3。 8在下面的图中，哪此是边通图？哪些是简单图？ (b)(c) 解 图与图不连通，它们能分成两个边通支。所以只有图是连能图。 图是简单图，图为它显然无平等边，无自环。图、是多重图有平行边有自环。 9求出所有具有四个结点的简单无向连通图。 解 在不同构的意义下，具有四个结点的简单无向连通图共有6个。 如下面所示：G1 G2 G2 G3 G4 G4 G5 G5 G6 G6 ?lya定理得证。参见卢o。 10设G是一个简单无向图，且为图，若 1m?(n?1)(n?2) 2证明G是连通图。 5 3）画一个图示，使它没有一条E圈，但有一条H圈； 4）画一个图示，使它既没有一条E圈，又没有一条H圈； 解 图1既有E-圈，又有H圈。 图2有E-圈，但没有H-圈。 圈3有H-圈，但没有E-圈。 图4既没有E-圈，又没有H-圈。 图1 图2 图3 图4 图2不存在H-圈，是因为存在着S=中间点，使W=2个连通支数，而| S |=1，从而W?| S |故定理1判定H-图的必要条件可知不存在H-圈。 图3不存在E圈，是因为G中存在8个结点的度均为3，是奇数。图4中不存在H圈，因为G是一个偶图，而偶图要有圈，必须结点数为偶数，而G的结点数为11个，是奇数，不是偶数。 23若G=有Hamilton路，证明对V中任一非空子集S，均有W(GS)| S |+1。 证 设G=中的Hamilton路为C，路的两个端点为v1，及v2。我们给G增加一个新结点，v*及两个新边和而得到图G*，于是G*中就有Hamilton圈G*。令S*=Sv*，则显然有GS=C*S*。从而根据定理1有Hamiltou圈的必要条件，有 W=W|S*|=|S|+1 。 24雄辩地证明下面的图示中没有Hamilton路。 图1 证 将图1标记为图3。 图2 图3中存在着Hamilton路，此如H= 21 但是，图3中不存在Hamilton圈。因为，结点e，j均为2度结点，故若Hamilto圈，则引H-必通过e，j及其关联的四条边，因此在边及上各增加一个结点l，m，得到图4，显然，图1，即图3有H-圈当且仅当图4有H-圈。 取S=a，e，l，g，i，c，则GS=m，f，j，k，b，h，d这7个孤立点，因此W=7，而|S|=6，故此有 W(GS)?|S| 根据定理1，有H-圈的必要条件，知图4中没有H-圈，因此图中没有H-圈。 图2中不存在H路。 证法一：将图中偶结点全标为A，奇结点全标为B，取S=偶结点则GS为8个孤立奇结点，于是W=8，而| S |=6。从而有W?|S|+1，于是根据第23题的结论，有H-路的必要条件，知无H-路存在。 证法二：注意到图中的标号，奇、偶结点交错，A B B B B A A B A B A B B B A 图5 因此是一个偶图于是若有H-路，则奇偶结点之差不得超过1。但是这里奇结点有8个，偶结点有6个，其差为2。所以不可能有一条H-路。 25有七位客人入席，A只会讲英语；B会讲汉语；C会讲英语，意大利语及俄语；D会讲汉语及日语；E会讲意大利语及德语；F会讲法语，日语及俄语；G会讲德语和法语。问主人能否把诸位安排在一张圆桌上，使每一位客人与左右邻不用翻译便可交谈。若能安排，请给出一个方案。 解 能安排，其方案为： H=将每个人作为一个项点，如果两个人会讲同一种语言，就在代表他们的二个项点间连一条边，边上标明二人公用的语言，这样就可得一简单无向图G。所求问题转化为图G中有无Hamilton圈问题。 图G E C 英语 G 德语 F 俄语 英语 D B 英语 A 而上边指出的圈H正好是图G的一条Hamilton圈，因此问题得到解决。 26假设在一次集合上，任意两人合起来能够认识其余n-2 个人。证明这n个人可以排成一行，使得除排头与排尾外，棋逢对手余的每个人都认识自己的左右邻。 22 证 我们来构造一个n阶图G，图G的项点代表n个人，两个认识的人对应的顶点间连一条边，从而图G满足： 对任意二顶点u和v，都有deg(u)+deg(v)h-2。 所求问题转化为，证明图G中存在一条Hamilton路。为此，我们证明： 对任意二顶点u和v，都有deg(u)+deg(v)h-。分情况证明如下：1）若u和v相邻，则有 deg(u)+deg(v) (n-2)+2=nn-1 2）若u和v不相邻则仍有 deg(u)+deg(v) n-1n-2 否则，已知deg(u)+deg(v)n-2知deg(u)+deg(v)=n-2。那么，G中除u和v外的余n-2个点，每个顶点都恰与u或v之一相邻。今考察其中一点w，设它与v相邻，则它必不与u相邻。于是对于v，w这一对顶点，它们都不与除去它们之后的n-2个顶点中之一顶点u相邻，这就与题设条件：任二顶点合起来都与其余n-2个项点相邻，相矛盾。 综合1），2）并且根据定理2，有Hamiltou路的充分条件，可知图G中存在着一条H路。 27如何无向图G的邻接矩阵判断G是否为二分图？ 解 二分图G=实际上是项点集V的一个划分X，Y，有两上划分块，而划分和等价关系对应，因此我们将判定G是二分图转化为判定某一相应的关系是等价关系。 u v w 其余n-2个 顶点 ?1,当(vi,vj)或(vjvi)? 令A：=(aij)nxn，其中aij=? 0,否则? No2. 求A：=AA=(a(2)(2)ij)nxn，其中a(2)ij=?(aikakj)。 k?1nvi，vjXVY，(2)=1? vi，vjY aijNo3. 令B：=EA(2)=(bij)，其中 23 ,当i?j时?1bij=?(2) a,当i?j时.(则B显然是自反的对称的.)?ijNo4. 求B=BB=E是n阶单位）其中b(2)ij=k?1?(bikbkj)。 nNo5. 求B(2)=B，输出“图G是二分图”，出口；否则输出“G不是二分图”，出口。 n228证明：如果G是二分图G为图，那么m? 。 4证 设二分图G=的项点集V是划分为二部分X，Y。因为| V |=n，所以不妨设|X|?nn?k，从而|Y|?k。 22因于二分图的边数小于其对应的完全二分图的边数 故此： nnn2n22?k?m?(?k)(?k)? 222429设G=是二分圈，V=V1V2，证明：1）若G中有H圈，则| V1 |=| V2 |； 2）若G中有H路，则| V2|-1| V1|V2|+1 。 证 1）证法一：若G中有H图，于G是二分图，则在G 中去掉V2后，就只剩下V1中的| V1 |个孤立点；同样，在G中去掉V1后，就只剩下V2中的| V2 |个孤立点。因此定理1，有Hamilton圈的必要条件，可知： | V1 |=W(GV2)| V2 |，| V2 |=W(GV1)| V1 | 因此，可得| V1 |=| V2 |。 证法二：设C=是二分图中的一条Hamilton圈，从而有V=v1，v2，?vl，于是| V |=l。 不妨设v1V1，观察圈C中的各结点，有： v1V1?v2V2?v3V1? v4V2?vV2 从而有v1，v3?，v-1V1V2，故此V1=v1，v3，?v-1，V2=v2，v4，?v 所以 24 | V1 |=?=| V2 |。 22）证法一：若G中有H路，于G是二分图，则在G中去掉2后，就只剩下V1中的| V1 |个孤立点；同样，在G中去掉V1后，就只剩下V2中的| V2 |个孤立点。因此习题23有Hamilton路的必要条件，可知 | V1 |=W(GV2)|V2 |+1 | V2 |=W(GV1)| V1 |+1，于是| V2|-1|V1| 故此 | V1 |-1| V1 |V2 |+1。 证法二：设C=是二分图中的一条Hamilton路，从而V=v1，v2，?，v ，于是| V |=。根据1）的证法二： 若v1V1，vV1，则v-1V2 故此-1为偶数，为奇数，于是 | V1 |=?1?-1?1, 而| V2|? 因此 22| V1 |=|V2 |+1 若v1V1 vV1，则为偶数，于是 | V1 |=?=| V2| 2若v1V2，vV1，同可证| V1 |=|V2|若v1V2，vV2，则同可证| V2 |=|V1|+1，即|V2|-1=| V1| 综合以上四点，有 | V2|-1|V1|V2|+1。 30在下面的图示中，是否存在v1，v2，v3，v4到u1，u2，u3，u4，u5的完美匹配？若存在，请指出它的一个完美匹配。 u1 u2 u3 25 u4 u5 v1 v2 v3 v4 解 不存在v1，v2，v3，v4到u1，u2，u3，u4，u5的完美匹配。 因为这两个互补结点子集的结点个数不相同。 31某展览会共有25个展室，布置如下图所示，有阴影的展室陈列实物，无阴影的展室陈列图片，邻室之间均有门可通。有人希望每个展室都恰去一次，您能否为他设计一条路线？ 解 不能。 因为，若我们将每个展室看作一个项点，并且V1是无阴影展室的项点集，V2是有阴影展室的项点集，将邻室之间的门通道看作相应两顶点的边，于是我们得到一个二分图G。从而问题转化为问图G中是否有从起点uv1到终点vV2的一条Hamilton路？而这样的H路存在的必须条件是| V1|=| V2|证法=b)。但是|V1|=1213=|V2|，故不满足必要条件，所以没有从u到v的Hamilton路。 32证明：小于30条边的平面简单图有一个结点的度数小于等于4。 证 用反法：假设简单平面图的所有结点的度数都大于4，因而都大于等于5，则2定理1，有 2m?故此 nnn入口u 入口 uu ?deg(v)?5?5n ii?1i?12m 5于简单平面图无平等边，自环，所以任一区域都至少三条或以的边围成，故利用欧拉公式的推论公式：m3n6，有 m32m?6 5因此，m30，这与已知条件m30矛盾。所以，假设错误，小于30条边的简单平面图必有一个结点的度数小于等于4。 33在2个结点构成的r2个正方形网格所组成的平面图上，验证Euler公式的正确性。 证 如此的平面图，结点数n=(r+1)2 26 边数m=(r+1)r+(r+1)r=2(r+1)r =2r2+2r 面数f=r2+1于是 n-m+f=(r+1)2-(2r2+2r)+(r2+1)=(r2+2r+1)-(2r2+2r)+(r2+1)=2 故此Euler公式对此类图正确。 34运用kuratowski定理证明下图是非平面图。 证给图G中结点打上标号，并用黑点标记要删去的边。 1 6 2 7 5 3 4 图G 去掉图G中打黑点的边，得图G的子图。 27 3 4 2 7 1 6 5 图G 图G的子图 对图G的子图进行变形。 1 6 2 5 7 3 4 图G的子图 用kuratowski技术对图G的子图进行处理： 从而，在kwratowski技术下，与K33同构，因而根据Kwratowski定理，此图G是非平面图。 1 2 5 4 3 7 28 1 离散数学习题解答 习题七 1证明树是只有一个区域的平面图。 证 证法一 于树无圈套在，因此根据kuratowski定理，可知树是平面图，因此可用Euler定理。对于树，m=n-1，故此n-m+r=2，得树的区域数 r=2+m-n=2+-n=1 证法二 用归纳法，施归纳于树的结点个数n。 当n=1时，只显然为平面图只有一个区域，题意为真 当n=k时，假设题意为真。 当n=k+1时，我们来证题意为真。 事实上，于T是树，故T中至少有一个悬挂点，在T中删去此结点，得到一个k个结点的边通图T，显然T中无圈。于T是一个具有k个结点的树，于是根据归纳假设，T是只有一个区域的平面图。这时将删去的结点重新扦入T中以得到T，于悬挂点不改变图的平面性和区域数，因此T仍是中仍一