试卷五试题与附标准答案

《试卷五试题与附标准答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试卷五试题与答案一、填空1、n阶完全图结点v的度数d(v)=。2、设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。矚慫润厲钐瘗睞枥庑赖。3、如图给出格L，则e的补元是。4、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是。二、选择1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（）。A、群；B、环；C、域；D、格。2、设[{a,b,c}，*]为代数系统，*运算如下：*abcaabcbbaccccc则零元为（）。A、a；B、

2、b；C、c；D、没有。3、如右图相对于完全图K5的补图为（）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（）4度结点。A、1；B、2；C、3；D、4。5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（）时，[A，+，·]是整环。A、；B、；C、；D、。三、证明1、设G是（n,m）简单二部图，则。（10分）2、设G为具有n个结点的简单图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：

3、聞創沟燴鐺險爱氇谴净。+01·01001000110101证明它是一个环，并且是一个域。（14分）4、是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）四、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。残骛楼諍锩瀨濟溆塹籟。答案一、填空1、n-1；2、n(k+1)-2m；3、0；4臂力小者二、选择题目12345答案DCAAD一、证明1、证：设G=（V，E）对完全二部图有当时，完全二部图的边数m

4、有最大值故对任意简单二部图有。2、证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然酽锕极額閉镇桧猪訣锥。与假设矛盾。所以G连通。3、（1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……结合律成

5、立。幺：幺元为0。逆：0，1逆元均为其本身。②[{0，1}，·]是半群乘：由“·”运算表知封闭群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0。③·对+的分配律Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)；Ⅱ1·（x+y）当x=y(x+y)=0则；当（）则所以均有同理可证：所以·对+是可分配的。由①②③得，[{0，1}，+，·]是环。（2）[{0，1}，+，·]是域

6、因为[{0，1}，+，·]是有限环，故只需证明是整环即可。①乘交环：由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。4、证：（1）“≤”是偏序关系，≤自然偏序①反自反性：由代数格幂等关系：。②反对称性：若即：，则③传递性：则：（2）在L中存在{x,y}的下（上）确界设则：事实上：若{x,y}有另一下界c，则是{x,y}最大下界，即同理可证上确界情况。四、解：用库斯克（Kruskal）算法求产生的最优树。算法为：结果如图：树权

7、C(T)=23+1+4+9+3+17=57（万元）即为总造价