图论及代数系统答案A

计算机04级代数系统及图论试题（A）答案一、证明：（1）由表1可得{e,a},*的运算表如下：*aeaeaeae（酌情给1~5分）由表可知，幺元为e，a的逆元为a，显然运算满足封闭性、结合律，故{e,a},*是一个群。（酌情给1~5分）（2）设{e,a}=M，则M的所有左陪集有bM={a,b}，cM={b,c}，dM={c,e}（酌情给1~5分）若G,*是群，则应满足|M||G|，但|M|=2，|G|=5，故G,*不是群。（酌情给1~5分）二、证明：必要性设f是入射。因为f(e)=e’，所以e∈Ker(f)。若另有a∈G，使得f(a)=e’，则f(a)=f(e)，由于f是入射，故必有a=e，因此Ker(f)={e}。（酌情给1~5分）充分性设Ker(f)={e}。对于a,b∈G1，如果f(a)=f(b)，则有f(b*a-1)=f(b)f(a-1)=f(a)f(a-1)=f(a*a-1)=f(e)=e’,故b*a-1∈Ker(f)，所以b*a-1=e，因此有（b*a-1）*a=e*a，即b=a，所以f是入射。（酌情给1~5分）三、(a)不是格，(b),(c),(d)都是格；（酌情给1~4分）其中(b)是有界格、分配格；(c)是有界格、分配格、有补格；(d)是有界格、有补格。（酌情给1~6分）四、证：设a是L中的任意一个元素，如果21,aa都是a的补元，则有)()()()()()()()(2112212221211211aaaaaaaaaaaaaaaaaaaa故有21aa。（酌情给1~10分）其它正确的证明方法。（酌情给1~10分）五、解：G与G的并为完全图Kn，因为n为奇数，所以Kn中每个顶点的度为n-1，为偶数。若G中有一个奇数度顶点v，此顶点在G中必为奇数度顶点，因而G与G的奇数度顶点个数相同。（酌情给1~10分）其它正确的证明方法。（酌情给1~10分）六、证：因为G存在欧拉回路，因而G是连通图。若G中存在割边e=(u,v)，则u,v分别属于G-e的两个连通分支G1与G2。设w为G1中的一个结点，可从w出发走一条欧拉回路C：从w开始，一旦行到u，沿割边到达v，则在G2中行遍后无法回到G1达到w，这与G中存在欧拉回路相矛盾。故欧拉图中无割边。（酌情给1~10分）其它正确的证明方法。（酌情给1~10分）七、解：（1）是平面图，其平图如下图1，对偶图如图2（酌情给1~10分）图1图2（2）因为此图是完全图所以其色数为：f(k4)=t(t-1)(t-2)(t-3)。（酌情给1~5分）八、解：（1）关联矩阵如下0110110010100010110100000001100100000111B（酌情给1~5分）（2）011011001010001011010000000110011B001010000000001011010000000000011B则6)2101010011310001det(0110101011000011100110000100000100101000000000101101000000000001)det(11TBB（酌情给1~5分）v4v2v3v1（3）11010000011011001010001010100101fS10010011010110000010101100001101fC（酌情给1~5分）其它正确的求解方法。（酌情给1~5分）