试卷五试题与答案。
1、 n阶完全图结点v的度数d(v
2、 设n阶图g中有m条边,每个结点的度数不是k的是k+1,若g中有nk个k度顶点,nk+1个k+1度顶点,则n k
3、 如图。
给出格l,则e的补元是。
4、 一组学生,用二二扳腕子比赛法来测定臂力的大小,则幺元是。
1、设s=,≤为小于等于关系,则是。
a、群;b、环;c、域;d、格。
2、设[,*为代数系统,*运算如下:
则零元为。a、a; b、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,反映电路规律的代数系统[,+的加法运算和乘法运算。如下:
证明它是一个环,并且是一个域。(14分)
4、 是一代数格,“≤为自然偏序,则[l,≤]是偏序格。(16分)
四、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价(单位:万元),试给出一个设计方案,使得各城市之间既能够通信又使总造价最小。
答案。1、n-1;2、n(k+1)-2m ;4臂力小者。
二、选择 二、 证明。
1、 证:设g=(v,e)
对完全二部图有。
当时,完全二部图的边数m有最大值。
故对任意简单二部图有。
2、 证:反证法:若g不连通,不妨设g可分成两个连通分支g1、g2,假设g1和g2的顶点数分别为n1和n2,显然。
与假设矛盾。所以g连通。
3、 (1)[,是环。
[,+是交换群。
乘:由“+”运算表知其封闭性。由于运算表的对称性知:+运算可交换。
群: (0+0)+0=0+(0+0)=0 ;(0+0)+1=0+(0+1)=1;
结合律成立。
幺:幺元为0。
逆:0,1逆元均为其本身。
[,·是半群。
乘:由“· 运算表知封闭。
群: (0·0)·0=0·(0·0)=0 ;(0·0)·1=0·(0·1)= 0;
·对+的分配律
0·(x+y)=0=0+0=(0·x)+(0·y);
1·(x+y)
当x=y (x+y)=0 则。
当()则。所以均有。
同理可证:所以·对+ 是可分配的。
由①②③得,[,是环。
2)[,是域。
因为[,+是有限环,故只需证明是整环即可。
乘交环: 由乘法运算表的对称性知,乘法可交换。
含幺环:乘法的幺元是1
无零因子:1·1=1≠0
因此[,+是整环,故它是域。
4、证:(1 )“是偏序关系, ≤自然偏序
反自反性:由代数格幂等关系:。
反对称性: 若即:,则
传递性:则:
2)在l中存在的下(上)确界。
设则:事实上:
若有另一下界c,则。
是最大下界,即。
同理可证上确界情况。
四、解: 用库斯克(kruskal)算法求产生的最优树。算法为:
结果如图:树权c(t)=23+1+4+9+3+17=57(万元)即为总造价。
离散数学试题 A卷答案
一 证明题 10分 1 p q p q r p q p r t 证明 左端 p q p q r p q p r 摩根律 p q p q p r p q p r 分配律 p q p r p q p r 等幂律 t 代入 2 x p x q x xp x x p x q x 证明 x p x q x x...
离散数学试题 A卷答案
一 10分 某项工作需要派a b c和d 4个人中的2个人去完成,按下面3个条件,有几种派法?如何派?1 若a去,则c和d中要去1个人 2 b和c不能都去 3 若c去,则d留下。解设a a去工作 b b去工作 c c去工作 d d去工作。则根据题意应有 acd,b c cd必须同时成立。因此。acd...
2019离散数学试题 A 答案
一 填空题。答案1答案 2 答案3 a,c,a b 没有。答案4 1 答案5 二,1 d 2 c 3 d 4 a 5 c 三答案 15 1关系图。2 对称,对称,传递闭包矩阵 四 10 答案解 用库斯克 kruskal 算法求产生的最优树。算法为 结果如图 树权c t 23 1 4 9 3 17 5...