文档介绍：;;; 。(3)很明显,〈{0,1},*〉构成代数系统;满足结合律,为半群;1是幺元,为独异点; 而0为零元;结论:仅为独异点,而不是群。所以选[C] ;; ; 。 3-2 在自然数集合上,下列那种运算是可结合的[A] *y= max(x,y) ;*y = 2x+y ; *y =x 2 +y 2;*y =︱ x-y ︱.. 分析与题解:,( x*y )*z=x*(y*z) 时,才可以得出满足结合律的结论. 3-3 设N为自然数集合,在 N上定义二元运算。,对于所有 x,y∈N都有 x。y=x-y 试问?在 N上二元运算。能否构成代数系统,何种代数系统?为什麽?( 综合题) 分析与题解:判别一个代数系统是否是群,当然要满足群的定义条件。然而,判别过程要分步走。,针对结合律进行讨论。第三步, 要讨论特殊元素及其对代数结构的作用。本题中,自然数上的减法运算不满足封闭性,不能构成代数系统。接下来的问题,就不必讨论了。最后, 结论是:自然数上的减法运算不构成代数系统。第二部分图论方法第四章图 4-1 10个顶点的简单图 G中有 4个奇度顶点,问 G的补图中有 r个偶数度顶点。题解分析:提到图的补图, 10阶完全图的每个顶点的度数都是 n-1=9 ――为奇数。这样一来,一个无向简单图 G的某顶点的度数是奇数, 其补图的相应顶点必偶数,, G的补图中应有相同数个偶数度顶点。所以选[C] =10 ;=6;=4;=9。 4-2 是非判断: 无向图 G 中有 10 条边,4个3 度顶点, 其余顶点度数全是 2, 共有 8 个顶点.[是] 分析与题解:由握手定理有: 20=4x3 +2x,所以, x=4,即 4个2度顶点,共 8个顶点. 4-3 填空补缺: 1 条边的图 G 中,所有顶点的度数之和为 2。分析与题解:,所有顶点的度数之和都是边的两倍. 第五章树(5-1 ),( 5-2 )为计算题 5-1 概述无向图与无向树的关系。(简答题) 分析与题解:本题希望同学们掌握以下四点: (1)生成树的定义--- 生成子图概念;( 2)生成子图与母图的关系---- 顶点数相同; (3)何种图才有生成树---- 连通图;( 4)连通图中的那种边永远不会进入任何一颗生成树中--- 环。( 5)连通图中的那种边必然会进入其生成树中--- 桥。 5-2 握手定理的应用(指无向树) (1)在一棵树中有 7片树叶, 3个3度顶点,其余都是 4度顶点,共几个顶点[11] (2)一棵树有两个 4度顶点, 3个3度顶点,其余都是树叶,问有几片叶[9] 题解分析:对于图论中树的有关问题的解决,无非是利用握手定理以及利用树是连续而无回路的性质,即Σd(Vi)=2m定理和利用 n—1=m定理。所以有如下结果: (1)有 1个4度顶点。即: 1+7+3 =11;(2)9个1度顶点。 5-3 求最优 2元树:用 Huffman 算法求带权为 1,2,3,5,7,8的最优 2元树 T。试问: T的权 W(