图论及代数系统答案A.doc

《图论及代数系统答案A.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机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分）若是群，则应满足

2、M

3、ê

4、G

5、，但

6、M

7、=2，

8、G

9、=5，故不是群。（酌情给1~5分）二、证明：必要性设f是入射。因为f(e)=e’，所以e∈Ker(f)。若另有a∈G，使得f(a)=e’，则f(a)=f(e

10、)，由于f是入射，故必有a=e，因此Ker(f)={e}。（酌情给1~5分）充分性设Ker(f)={e}。对于a,b∈G1，如果f(a)=f(b)，则有f(b*a-1)=f(b)Df(a-1)=f(a)Df(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中的任意一个元素，如果都

11、是a的补元，则有故有。（酌情给1~10分）其它正确的证明方法。（酌情给1~10分）五、解：G与的并为完全图Kn，因为n为奇数，所以Kn中每个顶点的度为n-1，为偶数。若G中有一个奇数度顶点v，此顶点在中必为奇数度顶点，因而与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中存在欧拉回路相矛盾。故

12、欧拉图中无割边。（酌情给1~10分）其它正确的证明方法。（酌情给1~10分）七、解：（1）是平面图，其平图如下图1，对偶图如图2v4v2v3v1（酌情给1~10分）图1图2（2）因为此图是完全图所以其色数为：f(k4)=t(t-1)(t-2)(t-3)。（酌情给1~5分）一、解：（1）关联矩阵如下（酌情给1~5分）（2）则（酌情给1~5分）（3）（酌情给1~5分）其它正确的求解方法。（酌情给1~5分）