代数结构与图论暨大2011.pdf

《代数结构与图论暨大2011.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、暨南大学考试试卷2011–2012学年度第___1______学期课程类别必修[√]选修[]教课程名称：_____代数结构与图论______________师考试方式填开卷[]闭卷[√]授课教师姓名：____陈双平_____________写试卷类别答案考试时间:___2012___年___1_____月_13___日[A]共8页考生学院(校)专业班(级)填写姓名学号内招[]外招[]题号一二三四五六七八九十总分得分得分评阅人一、填空题（共4小题8空，每空2分，共16分）123412341.，24314321-1σ=(142

2、)(3)，τσ=(234)(1).2.设A={2，4，6，8}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点中，单位元是8，零元是2。3.设G是n(n≧3)阶m条边的极大平面图，则m和n之间满足什么关系？m=3n-6。4.欧拉图的充分必要条件是连通无奇度顶点/由连通不相交的环组成。5.Z8的全部生成元是1357，它有4个子群。得分评阅人二、选择题（共9小题，每小题2分，共18分）1.下列说法正确的是(C)（A）货郎担问题很难（B）货郎担问题无解第1页共8页暨南大学《代数结构与图论》试卷A卷考生姓名、学号：（C）货郎担问题计算量很大（D）

3、货郎担问题就是哈密顿问题2.下列说法错误的是(C)（A）欧拉图必连通（B）对偶图必连通（C）平面图必连通（D）哈密顿图必连通3.下面不是二部图的是(C)（A）树（B）无圈图（C）完全图K5（D）平凡图4.关于群的说法正确的是A（A）群都有子群(B)群的陪集也是群（C）群的并是群（D）有限群只有2个生成元5.下列论述错误的是C（A）满足充分条件的集合必然满足必要条件（B）满足充分条件的集合必然满足充分必要条件（C）满足必要条件的集合必然满足充分必要条件（D）满足充分必要条件的集合必然满足必要条件6.点连通度和边连通度的关系是C（A）大于等于（B）大于（C）小于等于

4、（D）小于7.关于无零因子环，正确的是B（A）没有零元（B）xy=0，则x和y中必有一个是0（C）没有零因子(D)零元不唯一8.关于单位元，正确的说法是C（A）单位元就是1（B）单位元就是0（C）有单位元，说明有左右单位元（D）单位元不唯一9.一颗树有2个2度结点，1个3度结点和3个4度结点，则1度结点数为（C）。A、5；B、7；C、9；D、8。第2页共8页暨南大学《代数结构与图论》试卷A卷考生姓名、学号：得分评阅人三、证明题（共2小题，每小题8～12分，共20分）1.（12分）证明实数域关于加法和乘法是域.证明：加法是代数系统封闭性半群结合律独异点0可逆群交换

5、群交换律(6分)乘法是代数系统封闭性半群结合律(1分)乘法关于加法的分配律(1分)以上说明它是环(1分)乘法交换律交换环乘法单位元1含幺环(1分)乘法无零因子无零因子环(1分)故是整环乘法除零外可逆故R为域(1分)第3页共8页暨南大学《代数结构与图论》试卷A卷考生姓名、学号：2.（8分）如果无向简单图的最小度为2，证明该图必含有长度至少为3的圈.证明：用扩大路径法设起点为1它有2个度必然连到另一个点记为22还有一个度必然连到点33要么连回1要么连到另一个点4，如此反复下厨直到点n因为是简单图故必有圈，且圈的长度至少为3.也可反证，因它不是树那么连通分支里必然存在

6、圈，又是简单图，故长度至少为3得分评阅人四、计算题（4小题，每小题6～10分，共30分）1.（10分）对于二部图G=Kr,s（1）求支配数γ0，G中有非最小支配集的极小支配集吗？（2）求点覆盖数α0，G中有非最小点覆盖集的极小点覆盖集吗？（3）求点独立数β0（4）求匹配数β1，G能有完美匹配吗？为什么？（5）求边覆盖数α1Min(2,r,s)有另外一个集合（2分）Min(r,s)有（2分）Max(r,s)（1分）Min(r,s)（1分）当r=s完美匹配，不等时无因完美匹配要求全配对（3分）Max（r，s）（1分）第4页共8页暨南大学《代数结构与图论》试卷A卷考生

7、姓名、学号：2.（6分）设G的运算表如下表所示，问G是否为循环群？如果是，求出它所有的生成元和子群；解：是生成元为bf（2分）子群为{a}{abcdef}{ace}{ad}（4分）3.（7分）下面两组数，是否是可以简单图化的？若是，请给出3个非同构的无向简单图以它为度数列。（1）2，2，2，3，3，6（2）2，2，2，2，3，3（1）不可（2分）（2）可（2分）以下任何3个每个1分第5页共8页暨南大学《代数结构与图论》试卷A卷考生姓名、学号：4.（7分）n=5时，所有不同构的格有哪些？请做出他们的哈斯图，并判断他们是不是分配格，有补格，以及布尔代数？共5种每个1

8、分除了钻石和五角不是分配