国防科学技术大学计算机学院离散数学课后习题答案——图论

国防科学技术大学计算机学院离散数学课后习题答案——图论 第七章 图论 7.1 1. a) 非简单图；（有自圈） b) 非简单图；（有自圈） c) 简单图。 3. 因为n个顶点的有向简单图中，每两个不同顶点之间最多有两条边，因此其边数最多 为：2。 2C,n(n,1)n 4. 利用定理7.1.3 因为任何图均有偶数个奇结点，而3度正则图的所有结点度数均为3，即均为偶结点。所以，3度正则图必有偶数个奇结点。 5. 利用定理7.1.3 1, 2, 1 5 3 6, 3, 6 2 4 5, 4, 6. 证明：假设六个人分别为：a, b, c, d, e, f。则分两种情况讨论。 ? 若a认识的人大于等于3个，即b, c, d, e, f中至少有3个与a认识。不妨设c, d, e与a 认识，则c, d, e必定互相不认识。（否则，c, d, e中互相认识的两人与a就构成三个人互相都 认识。产生矛盾。） ? 若a认识的人小于3个，即b, c, d, e, f中至少有3个与a不认识。不妨设b, c, d与a均不 认识。则因为没有3个人彼此都认识，所以b, c, d中必有两个人互相不认识。假设c, d互相 不认识，则a, c, d三个人彼此都不认识。 8. a ) 图中有一个与两个度数为3的结点邻接的结点，其度数也为3。 而b ) 图中没有任何一个度数为3的结点与两个度数为3的结点邻接。 所以，a ) 与b ) 不同构。 - 1 - 第七章 图论 9. b ) 图的中心结点其入度为0，而a ) 图中没有入度为0 的结点。所以两图不同构。 10. n阶简单无向图的结点度数不可能超过n-1，即取值范围为：{0, 1, 2, … , n-1}。 证明n（n>1）阶图中必有两个结点度数相等，抽屉原则应该可以使用，但n个结点，n种度数可能，抽屉原则似乎用不上。但我们发现，若图中有孤立点，则所有结点的度数只可能从 0到n-2中取值，即只有n-1种可能性。于是分两种情况： ? 若G中无孤立点（度数为0的结点），则G中n个结点的度数只能从1到n-1中取值。n个结点，n-1种可能的度数取值，由抽屉原则，G中必有两个结点的度数相等。 ? 若G中有孤立点，则G中n个结点的度数只能从0到n-2中取值。n个结点，n-1种可能的度数取值，由抽屉原则，G中必有两个结点的度数相等。 11. 根据定理7.1.1可知无向图中所有结点的度数和是边数的两倍。所以， ，即。 kn，(k，1)(n,n),2mn,(k，1)n,2mkkk 7.2 2. 显然G[V,]重任意两点之间必定互有有向边，并且无自圈、无平行边。 4. (1) 自反的； (2) 反对称的、传递的； (3) 自反的、对称的、传递的； (4) 自反的、传递的； (5) 无； (6) 对称的； (7) 自反的、反对称的、传递的； (8) 对称的； (9) 对称的； (10) 反对称的； (11) 自反的、反对称的； (12) 反对称的、传递的。 4. a) A上共有2n,n2个不相同的自反关系； 2n,nb) A上共有2个不相同的反自反关系； 2n，n 2c) A上共有2个不相同的对称关系； - 2 - 第七章 图论 2n,nn2d) A上共有个不相同的反对称关系； 2，3 ne) A上共有2个不相同的既是对称的又是反对称的关系； 2.3 1. 最多能有n(A) 个元素为1。 2. 证明： -1i) R , R为A上包含R的最小对称关系 -1-1? R , R , R。所以，R,R包含R。 -1-1? 因为对于任意 , R , R，有 , R或 , R。 -1-1若 , R，则 , R；若 , R，则 , R。 -1-1因此， , R , R。所以，R,R为A上的对称关系。 ? 设R,为任意的A上包含R的对称关系，则 -1-1对于任意 , R , R，有 , R或 , R。 若 , R，由于R,包含R，所以 , R,； -1若 , R，则 , R，由于R,包含R，所以 , R,，而R,对称，所以 , R,。 -1 因此，总有 , R,。所以，R , R, R,。 -1由???可知，R , R为A上包含R的最小对称关系。 -1ii) R , R为A上包含在R中的最大对称关系 -1-1? R , R , R。所以，R , R包含在R中。 -1-1? 因为对于任意 , R , R，有 , R且 , R。 -1-1 , R，所以 , R； , R，所以 , R。 -1-1因此， , R , R。所以，R , R为A上的对称关系。 ? 设R,为任意的A上包含在R中的对称关系，则 对于任意 , R,，由于R,包含在R中，所以 , R； -1又由于R,对称，所以 , R,，而R,包含在R中，所以 , R，因此， , R； -1-1因此，总有 , R , R。所以，R , R,R。 -1由???可知，R , R为A上包含在R中的最大对称关系。 2.4 1. R , R = {}； R , R = {, }； 2112 22R = {, , }； R = {, }； 12 2. m = 1, n = 16。 - 3 - 第七章 图论 4. A = {1, 2, 3} 令R = {<1, 2>, <1, 3>}；R = {<2, 2>}；R = {<3, 2>}；则 123 R , ( R , R) = ,；( R , R ) , ( R , R) = {<1, 3>}； 123 1213 所以，R , ( R , R) , ( R , R ) , ( R , R) 。 123 1213 令R = {<2, 2>}；R = {<2, 3>}；R = {<2, 1>, <3, 1>}；则 234 ( R , R) , R= ,；( R , R ) , ( R , R) = {<2, 1>}； 23 4 2434 所以，( R , R) , R, ( R , R ) , ( R , R) ； 23 4 2434 5. a) 正确。 b) 不正确。令A = {1, 2}，则R = {<1, 2>}, R = {<2, 1>}都是反自反的，但R , R={<1, 1>}1212 不是反自反的。 c) 不正确。令A = {1, 2, 3}，则R = {<1, 2>, <2, 1>}, R = {<2, 3>, <3, 2>}都是对称的，但12 R , R= {<1, 3>}不是对称的。 12 d) 不正确。令A = {1, 2, 3}，则R = {<1, 2>, <3, 1>}, R = {<2, 3>, <1, 1>}都是反对称的，12 但R , R= {<1, 3>, <3, 1>}不是反对称的。 12 e) 不正确。令A = {1, 2, 3}，则R = {<1, 2>, <3, 1>, <3, 2>}, R = {<2, 3>, <1, 1>}都是传递12 的，但R , R= {<1, 3>, <3, 1>, <3, 3>}不是传递的。 12 7. 证明： st s+ksktkt+ka) 对于任意k , N，因为R = R，所以R = R ,R = R ,R = R 。 b) 用关于k的归纳法证明。 s+is+i i) 当k=0时，R = R。所以命题成立。 s + mp + is + i ii) 假设当k=m时命题成立，即R = R。 s + (m+1) p + is + p + mp+ it + mp + itmp+i smp+i s + mp + i 则当k=m+1时，因为R=R=R=R ,R=R ,R=R。 s + (m+1) p + is + mp + i s + i 由归纳假设，R = R= R。 s + kp + is + i 由i) ii)可知对于任意k, i , N，均有R = R 。 k01t-1d) 若k , t-1，则R , {R, R, …, R}； 若k , t，则k = s + (t-s)q + r，即k = s + pq + r；（其中，q, N, 0 , r < t-s = p） ks + pq + rs + r01t-1 此时，由b)可知R = R = R , {R, R, …, R}。 k01t-1 所以，若k , N，则R , {R, R, …, R}。 2.5 2. 使t (R , R) , t ( R ) , t ( R ) 的R 和R 的具体实例如下： 121212 A = {1, 2}，R = {<1, 2>}，R = {<2, 1>}； 11 则t ( R ) = R ，t ( R ) = R ，t (R , R) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}， 112212 故真包含。 4. b) 使s (R , R) , s ( R ) , s ( R ) 的R 和R 的具体实例如下： 121212 - 4 - 第七章 图论 A = {1, 2}，R = {<1, 2>}，R = {<2, 1>}； 11 则s ( R ) = s ( R ) = {<1, 2>, <2, 1>}，s (R , R) = s(,) = ,。 1212故真包含：s (R , R) , s ( R ) , s ( R )。 1212 b) 使t (R , R) , t ( R ) , t ( R ) 的R 和R 的具体实例如下： 121212A = {1, 2, 3}，R = {<1, 2>, <2, 1>}，R = {<1, 3>, <3, 1>}； 11则t ( R ) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}，t ( R ) = {<1, 3>, <3, 1>, <1, 1>, <3, 3>}， 12t (R , R) = s(,) = ,。 12 故真包含：t (R , R) , t ( R ) , t ( R )。 1212 6. 令A = {1, 2}，R = {<1, 2>}，则 ts(R) = t ({<1, 2>, <2, 1>}) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>} st(R) = s ({<1, 2>}) = {<1, 2>, <2, 1>} 所以，st(R) , ts(R)。 2.6 1. a) 正确； b) 正确； c) 不正确；（不自反） d) 不正确；（不自反） e) 不正确；（不一定对称） f) 正确。 2. R的所有极大相容类为：{x, x, x}，{x, x, x}，{x, x, x}，{x, x, x}。 123136345356 2n,n 23. A上共有2个不相同的相容关系。 2.7 1. a) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > , R, < 0, 1 > , R, 但<-1, 1> , R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时， , R） - 5 - 第七章 图论 2. 不对。 应加上条件：对于任意x,A，总存在y,A使得 , R。 3. 证明： ? 已知条件：若 , R， , R，则 , R。 先证对称性：若 , R，则由于R自反，所以 , R，由上式有 , R。 所以R对称。 再证传递性：若 , R， , R，则因为R对称，所以 , R。由已知条件，因为 , R且 , R，所以 , R。 所以R传递。 因此，R时等价关系。 ? 已知条件：R是等价关系。 若 , R， , R，则因为R对称，所以 , R。又由于R传递，所以， ,R。 因此，若 , R， , R，则 , R。 2.8 1. a) 半序； b) 半序、全序、良序； c) 无；（不是反对称的） d) 无；（不是传递的） e) 半序； f) 无；（不是传递的） g) 无；（不是传递的） h) 拟序。 4. 设R是集合A上的二元关系，证明： a) R是A上的半序，当且仅当R , R-1* = II且R = R。 A 自反、反对称 ___________ _______传递 -1+b) R是A上的拟序，当且仅当R , R = , 且R = R。 反自反 ___________ _______传递 6. a) 断言中为真的有：xRx, xRx。 4111 b) P的最小元：无；P的最大元：x； 1 P的极小元：x和x；P的极大元：x。 451 c) {x, x, x}的上界：x；下界：x；上确界：x；下确界：x。 2341414 {x, x, x}的上界：x, x；下界：无；上确界：x；下确界：无。 345133 {x, x, x}的上界：x；下界：x；上确界：x；下确界：x。 1231414 - 6 - 第七章 图论 7. a) < I, , >中的非空子集I无最小元。 b) < I, |>（“|”为整除关系）中的非空子集{x | x >4}无最大元。 + c) 中的非空子集(0, 1)由下确界0，但无最小元。 d) 书上例4中的非空子集{4}有上界8和12，但无上确界。 8. 归纳法。 9. 归纳法。 - 7 -