试卷五试题与答案

文档均来自网络,如有侵权请联系我删除文档

1 / 5 试卷五试题与答案

一、 填空

1、 n 阶完全图结点v 的度数d(v) = 。

2、 设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = 。

3、 如图

给出格L ，则e 的补元是 。

4、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。

二、选择

1、设S={0,1,2,3},≤为小于等于关系，则{S ，≤}是（ ）。

A 、群；

B 、环；

C 、域；

D 、格。

2、设[{a , b , c}，*]为代数系统，*运算如下：

则零元为（ ）。

A 、a ；

B 、b ；

C 、c ；

D 、没有。

3、如右图 相对于完全图K 5的补图为（ ）。

文档均来自网络,如有侵权请联系我删除文档

2 / 5

4、一棵无向树T 有7片树叶，3个3度顶点，其余顶点均为4度。则T 有（ ）

4度结点。

A 、1；

B 、2；

C 、3；

D 、4。

5、设[A ，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A ，

+，·]是整环。

A 、},2|{Z n n x x ∈=；

B 、},12|{Z n n x x ∈+=；

C 、},0|{Z x x x ∈≥且；

D 、},,5|{4R b a b a x x ∈+=。

三、证明

1、设G 是（n,m ）简单二部图，则42

n m ≤。（10分）

2、设G 为具有n 个结点的简单图，且)2)(1(21-->n n m ，则G 是连通图。（10分）

3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：

（144、 ],,[⊕?L 是一代数格，“≤”为自然偏序，则[L ，≤]是偏序格。（16分）

文档均来自网络,如有侵权请联系我删除文档

3 / 5

四、如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。

答 案

一、填空

1、n-1；

2、n(k+1)-2m ；

3、0 ；4臂力小者 二、选择 二、 证明

1、 证：设G=（V ，E ）n n n n Y n X Y X V =+==?=2121

,,,

对完全二部图有

4)2()(2

2112

1

1121n n n n n n n n n n n m +

--=+-=-=?= 当

21n

n =

时，完全二部图),(m n 的边数m 有最大值42n 故对任意简单二部图),(m n 有

42

n m ≤

。 2、 证：反证法：若G 不连通，不妨设G 可分成两个连通分支G 1、G 2，假设G 1和G 2

的顶点数分别为n 1和n 2，显然n n n =+21

11112121-≤-≤∴≥≥n n n n n n 2)2)(1(2)2)(1(2)1(2)1(212211--=-+-≤-+-≤

∴n n n n n n n n n m

与假设矛盾。所以G 连通。 3、 （1）[{0，1}，+，·]是环

文档均来自网络,如有侵权请联系我删除文档

4 /

5 ①[{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 ……

结合律成立。

幺：幺元为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 。

③·对+的分配律 }1,0{,∈?y x

Ⅰ 0·（x+y ）=0=0+0=(0·x)+(0·y)；

Ⅱ 1·（x+y ）

当x=y (x+y)=0 则

)1()1()11()11()01()01(1100001)(1y x y x ?+?=???????+??+?=??????++==?=+?；

当y x ≠（1=+y x ）则

)1()1()11()01()01()11(1001111)(1y x y x ?+?=???????+??+?=??????++==?=+?

所以}1,0{,,∈?z y x 均有)()()(y z x z y x z ?+?=+?

同理可证：)()()(z y z x z y x ?+?=?+

所以·对+ 是可分配的。

由①②③得，[{0，1}，+，·]是环。

（2）[{0，1}，+，·]是域

因为[{0，1}，+，·]是有限环，故只需证明是整环即可。

①乘交环： 由乘法运算表的对称性知，乘法可交换。

②含幺环：乘法的幺元是1

③无零因子：1·1=1≠0

因此[{0，1}，+，·]是整环，故它是域。

文档均来自网络,如有侵权请联系我删除文档

5 / 5 4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序 a b a L

b a =?∈?, ①反自反性：由代数格幂等关系：a a a a a ≤∴=?。 ②反对称性：L b a ∈?, 若 a b b a ≤≤, 即：b a b a b a =?=?,，

则 b a b b a a =?=?= a b ≤

③传递性：c b b a ≤≤,则： a b a b a a b

c b b a c b a a

b a b a

c b a c a =?≤==?≤?=??==?≤??=?即即结合律

即 c b )()(

c a ≤∴

（2）L y x ∈?,在L 中存在{x,y}的下（上）确界

设L y x ∈,则：},inf{y x y x =?

事实上：y x y x x y x x ?=??=??)()(

y y x x y x ≤?≤?∴:同理可证

若{x , y }有另一下界c ，则c y c y x c y x c =?=??=??)()( y x c ?≤∴ y x ?∴是{x , y }最大下界，即},inf{y x y x =? 同理可证上确界情况。

四、解： 用库斯克（Kruskal ）算法求产生的最优树。算法为： 61615454434337337272277117123

),(17

),(3

),(9

),(4

),(1

),(v v e v v w v v e v v w v v e v v w v v e v v w v v e v v w v v e v v w ============选选选选选选

结果如图：

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

本文来源：https://www.bwwdw.com/article/aach.html