离散数学练习题1、设>< ,G 为群，其中G 是实数集，运算 为k b a b a ++= ，k 为G 中固定常数，则在群>< ,G 中，元素x 的逆元是 。

2、在有6个顶点、12条边的连通平面简单图中，每个区域用 条边围成；具有n 个顶点的连通无向图，其任意一个生成树里含有 边。

3、设图G 的邻接矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=001011110M ，则G 的可达性矩阵为____ __。

4、设A 是非空有限集合，代数系统>< ,),(A P 中，P(A)对∪运算的幺元是 ，零元是 。

5、设><,*G 是非零实数乘法群，G G f →:是同态映射，xx f 1)(=，则f (G )= ，Ker (f )= 。

6、设e 为无向完全图4K 的一条边，则}{4e K -的连通度为 ，匹配数为 。

7、[3,5],<≤>的全下界是 ，全上界是 。

8、任何具有k 个面的连通平面(n,m)图恒有 。

9、66,N <+>的子半群有 ， ， ， 。

10、长度为偶数n 的基本回路n C 的0()n C χ= 。

11、在n 个顶点的有向简单图中最多只有 条边。

12、设图G = < V ，E >，},,,{4321v v v v V =的邻接矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0001001111011010A ，则1v的入度 )(deg 1v -= ，4v 的出度)(deg 4v += ，从2v 到4v 的长度为2的路有 条。

13、含5个结点，4条边的无向连通图（不同构）有 个，它们是 。

14、在具有n 个结点的有向图中，任何基本通路的长度都不超过 。

15、任何图的点连通度)(G κ，边连通度)(G λ，最小点度)(G δ的关系为 。

16、结点数n （3≥n ）的简单连通平面图的边数为m ，则m 与n 的关系为 。

17、代数系统>∙+<,,A 是环，若对运算“· ”还满足 则>∙+<,,A 是整环。

18、设G 是连通平面图，G 中有6个顶点8条边，则G 的面的数目是（ ）A ．2个；B ．4个；C ．3个；D ．5个。

19、设连通的简单平面图G 中有10条边和5个面，则G 的结点数为（ ）A.6；B.7；C.8；D.9。

20、设Z 是整数集，+,﹒分别是普通加法和乘法，则<Z,+,﹒>是（ ）A ．域；B ．整环和域；C ．整环；D ．含零因子环。

21、在设H,K 是群>< ,G 的子群，下面哪个代数系统仍是>< ,G 的子群？（ ）A. >< ,HK ；B. >< ,K H ；C. >-< ,H K ；D. >-< ,K H 。

22、下面哪个偏序集构成有界格？（ ）A.≤><,N ；B.≥><,Z ；C.><|},12,6,4,3,2{；D.⊆><),(A P ，其中，|为整除关系，A ={a ,b,c }。

23、设G 为有n 个节点的简单图，则有（ ）。

A ．n G <∆)(；B ．n G ≤∆)(；C ．n G >∆)(；D ．n G ≥∆)(。

24、设21:R R f →是环同态满射，b a f =)(，那么下列结论错误的是（ ）A ．若是零元，则是零元；B ．若是幺元，则是幺元；C ．若不是零因子，则不是零因子；D ．若2R 是不交换的，则1R 不交换.25、设 R 为实数集合，⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧∈⎪⎪⎭⎫ ⎝⎛=为实数域R R b a b a R M ,,00)(2关于矩阵的乘法运算( )A.可交换且有幺元B.可交换且无幺元C.不可交换且有幺元D.不可交换且无幺元26、含有5个结点、3条边的不同构的简单图有（ ）A ．2个B ．3个C ．4个D ．5个27、二元运算*有两个左零元，则*一定（ ）A ．满足结合律B ．满足交换律C ．不满足结合律D ．不满足交换律28、下面哈斯图为分配格的是（ ）A. B. C. D29、一个无向图有4个结点，其中3个度数为2,3,3，则第4个结点度数不可能是（ ）A ．0B ．1C ．2D ．430、设无向树T 中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T 中的树叶数为（ ）A.10B.11C.12D.1331、完全二部图4,5K 删去（ ）条边可以得到树。

A ．4；B ．10；C ．5；D ．12。

32、设G 为连通的无向图，若G 仅有2个结点的度数是奇数，则G 一定具有（ ）A ．欧拉路径；B ．欧拉回路；C ．哈密尔顿路径；D ．哈密尔顿回路。

33、设<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 ∈+=。

34、设A={1，2，…，10 }，则下面定义的运算*关于A 封闭的有（ ）。

A 、 x*y=max(x ,y)；B 、x*y=质数p 的个数使得y p x ≤≤；C 、x*y=gcd(x , y)； (gcd (x ,y)表示x 和y 的最大公约数)；D 、x*y=lcm(x ,y) （lcm(x ,y) 表示x 和y 的最小公倍数）。

35、六阶群的子群的阶数可以是（ ）。

A 、1，2，5；B 、2，4；C 、3，6，7；D 、2，3 。

36、><,*G 是群，则对*（ ）。

A 、满足结合律、交换律；B 、有单位元，可结合；C 、有单位元、可交换；D 、每元有逆元，有零元。

37、下面（ ）哈斯图所描述的偏序关系构成分配格。

38、给定下列序列，（ ）可以构成无向简单图的结点度数序列。

A 、（1，1，2，2，3）；B 、（1，1，2，2，2）；C 、（0，1，3，3，3）；D 、（1，3，4，4，5）。

39、设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。

A 、点与边；B 、边与点；C 、点与点；D 、边与边。

40、一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。

A 、5；B 、7；C 、9；D 、8。

41、连通非平凡的无向图G 有一条欧拉回路当且仅当图G ( )。

A 、只有一个奇度结点；B 、只有两个奇度结点；C 、只有三个奇度结点；D 、没有奇度结点。

42、设无向图>=<E V G ,是连通的且m E n V ==,若（ ）则G 是树。

A 、M=N+1 ；B 、n=m+1 ；C 、63-≤n m ；D 、63-≤m n 。

43、设布尔代数}1,0,',,,1,,,0⊕*b a 上的布尔表达式()321321*,,x x b x a x x x f *⊕*=，试求其主析取范式和主合取范式。

44、设{}Q b a i b a F ∈+=,|3，其中i 为虚数单元，+和*为常规的复数加法和乘法，试证明*+,,F 是一个域。

45、设><,*G 是群，对任一G a ∈，令},**|{G y y a a y y H ∈==，证明：><,*H 是><,*G 的子群。

46、给定集合{}654321,,,,,ππππππ=G ，其中， ⎪⎪⎭⎫ ⎝⎛=3213211π， ⎪⎪⎭⎫ ⎝⎛=3123212π， ⎪⎪⎭⎫ ⎝⎛=1233213π， ⎪⎪⎭⎫ ⎝⎛=2313214π， ⎪⎪⎭⎫ ⎝⎛=1323215π， ⎪⎪⎭⎫ ⎝⎛=2133216π。

G 在合成运算 下组成的群>< ,G ，试求>< ,G 的所有正规子群和每个正规子群的陪集。

47、证明若G 是每个区域至少由k （3k ≥）条边围成的连通平面图，其中n 、m 分别是图G 的顶点数和边数，则(2)2k n m k -≤-。

48、设66,Z <+>是一个群，这里6+是模6加法，6{[0],[1],[2],[3],[4],[5]}Z =，试求出66,Z <+>的所有子群及其相应左陪集。

49、试求n=12的格,n S D <>的所有子格。

50、试证明，在格中如果有a b c ≤≤，则,()()()()a b b c a b b c b a b a c ⊕=**⊕*==⊕*⊕。

51、证明如果G 是二部图，它有n 个顶点，m 条边，则24n m ≤。

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

53、设S = R - {-1}（R 为实数集），ab b a b a ++=*。

（1）说明>*<,S 是否构成群； （2）在S 中解方程732=**x 。

54、设>< ,H 和>< ,K 都是群>< ,G 的子群，问>⋂< ,K H 和>⋃< ,K H 是否是>< ,G 的子并说明理由。

55、设>*<,S 是半群，L O 是左零元，对任L O x S x *∈,是否是左零元？为什么？56、某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）57、设G 是每个面至少由k （3≥k ）条边围成的连通平面图，试证明2)2(--≤k v k e ，其中v 为结点数，e 为边数。

58、设,a b 是群,G <> 中的元素，则对n N ∈，有()n n n a b a b = 。

（ ）59、设无向图G 中具有割点，则G 中一定不存在哈密尔顿回路。

（ ）60、不满足分配率的格（非分配格）同样也满足模不等式。

（ ）61、设*是S 上的可结合运算，若S a ∈是可逆的，则a 也是可约的（ ）62、在有界分配格中，一个元素若有补元，则补元不一定是唯一的。

（ ）63、分配格一定是模格。

（ ）64、在代数系统< S , *> 中，若一个元素的逆元是唯一的，其运算*必是可结合的。

（ ）65、每一个有限整环一定是域，反之也对。

（ ）66、有割点的连通图可能是哈密尔顿图。

（ ）67、任何循环群必定是阿贝尔群，反之亦真。

（ ）68、根树中最长路径的端点都是叶子。

（ ）69、若G 是欧拉图，则其边数e 合结点数v 的奇偶性不能相反。

（ ）70、图G 为（n , m ）图，G 的生成树G T 必有n 个结点。