2005-2006(1A)离散数学期末试卷答案

第一篇：2005-2006(1A)离散数学期末试卷答案

安徽大学2005-2006学年第一学期 《离散数学》期末考试试卷（A卷答案）

一、选择题（210=20分）

C,B,C,B,D,D,D,B,A,A

二、填空题（每空2分，总215=30分）1．PQ，PQ，PQ

2．x(R(x)Q(x))，x(Q(x)R(x)Z(x))

3．{,{,{}},{{}},{}} 4．{1}和{2}，{1,2}，，无

5．2，5 6．{1,1,2,2,1,2,2,1,3,3,4,4,3,4,4,3} 7．f(f19(B))B，Bf1(f(B))

三、计算题（每小题8分，总28=16分）

1.用等值演算法求命题公式((PQ)R)(PQ)的主析取范式和主合取范式。解：

((PQ)R)(PQ)((PQ)R)(PQ)((PQ)R)(PQ)(PQ)(PQ)R(P(QQ))RPR4分

(PQR)(PQR)（主合取范式）(0，2)(1,3,4,5,6,7)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）2．设A3，解：因为

8分

(B)16，(AB)64，试求B，AB，AB和AB。

。于(B)16，所以B4；因为(AB)64，所以AB6（2分）是集合A,B的文氏图如下：

所以，AB1（4分），AB2（6分），AB5（8分）。

四、证明题（1、2小题每小题9分，3、4小题每小题8分，总分34）1． 用CP规则证明P(QR)，Q(RS)，PQS。证： ①Q P（附加前提）1分 ②Q(RS)P 2分 ③RS T①②I 3分 ④P(QR)P 4分 ⑤P P 5分 ⑥QR T④⑤I 6分 ⑦R T①⑥I 7分 ⑧S T③⑦I 8分 ⑨QS CP 9分 2． 设R1和R2是A上的关系，证明下列各式：（a）r(R1R2)r(R1)r(R2)（b）s(R1R2)s(R1)s(R2)

（c）t(R1R2)t(R1)t(R2)证：

（a）r(R1R2)R1R2I(R1I)(R2I)r(R1)r(R2)

（这里I是A上的相等关系）3分

（b）s(R1R2)(R1R2)(R1R2)(R1R2)(R1R2)

~~~~~(R1R)(R2R2)s(R1)s(R2)6分

（c）因为t(R1R2)R1，t(R1R2)R2且关系t(R1R2)具有传递特性，根据传递闭包定义 t(R1R2)t(R1)，t(R1R2)t(R2)，所以t(R1R2)t(R1)t(R2)。9分

3． 设函数f:RRRR，f定义为：f(x,y)xy,xy。（1）证明f是单射；（2）证明f是满射。证明：（1）x1,y1，x2,y2RR，若f(x1,y1)f(x2,y2)，即

x1y1x2y2则，易得x1x2，y1y2，x1y1,x1y1x2y2,x2y2，x1y1x2y2从而是单射。4分

（2）p,qRR，由f(x,y)p,q，通过计算可得而p,q的原象存在，f是满射的。8分 4． 设AN，B(0,1)。证明ABc。证明：

定义一个从AB到实数R的函数f：

x(pq)/2，从

y(pq)/2f:ABR，f(n,x)nx，其中nN，x(0,1)

因为f是单射且Rc，所以ABc。4分

此外，作映射g:(0,1)AB，g(x)0,x，其中x(0,1)。因为g是单射，故cAB。

所以ABc。8分

第二篇：离散数学期末试卷

北京工业大学经管学院期末试卷

《离散数学》（A）

学号姓名：成绩

一、单项选择题（每题2分，共18分）

1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）．

A．P→Q

C．P∧Q B．P∨Q D．P∧Q

p→q，蕴涵式，表示假设、条件、“如果，就”。

“→”与此题无关

2.关于命题变元P和Q的极大项M1表示(C)。书P15-P20，此题换作p、q更容易理解

A.┐P∧QB.┐P∨Qp∨┐q----01----1-----M

1C.P∨┐QD.P∧┐Q

3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D）

4.在论域D={a,b}中与公式（x）A（x）等价的不含存在量词的公式是（B）

A.A(a)A(b)

C.A(a)A(b)

5．下列命题公式为重言式的是（C）

A．Q→（P∧Q）

C．（P∧Q）→PB．P→（P∧Q）D．（P∨Q）→QB.A(a)A(b)D.A(b)A(a)

牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况

6.设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是(A)

A.R=｛<1,a>,<2,a>,<3,a>｝

B.R=｛<1,a>,<2,b>｝

C.R=｛<1,a>,<1,b>,<2,a>,<3,a>｝

D.R=｛<1,b>,<2,a>,<3,b>,<1,a>｝

-第 1页

7.偏序关系具有性质（D）背

A.自反、对称、传递

B.自反、反对称

C.反自反、对称、传递

D.自反、反对称、传递

8.设R为实数集合，映射:RR,(x)x22x1,则 是(D).(A)单射而非满射(C)双射(B)满射而非单射(D)既不是单射也不是满射.书P96.设函数f：A→B

（1）若ranf=B，则f是满射的【即值域为B的全集，在本题中为R，该二次函数有最高点，不满足】

（2）若对于任何的x1,x2∈A , x1≠x2,都有f(x1)≠f(x2)，则称f是单射的【即x,y真正一一对应，甚至不存在一个y对应多个x。显然，本题为二次函数，不满足】

（3）若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满足，既不是单射也不是满射】

二、填空题（每空2分，共22分）

１.设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，,∈S,*=, 则*运算的幺元是_____<1,0>_____。∈S, 若a≠0，则的逆元是______<1/a,-b>______。书P123定义

２.在个体域D中，公式xG(x)的真值为假当且仅当__某个G(x)的真值为假__，公式xG(x)的真值为假，当且仅当__所有G(x)的真值都为假__。

３.给定个体域为整数域，若F（x）：表示x是偶数，G（x）：表示x是奇数；那么，(x)F(x)(x)G(x)是一个(x)(F(x)G(x))是一个

４.设Aa,b,c　,A上的二元关系Ra,b,b,c,则r(R)

{,,,,,} 。

书P89、P85.自反闭包：r(R)= R U R0

={,} U {,,,} ={,,,,,}对称闭包：s(R)= R U R-1 = {,} U {,} = {,,,}-第 2页

传递闭包：t(R)= RUR2 UR3U……

５.设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有___8___个.书P96，B上A的概念：

设Ａ、Ｂ为集合，所有从Ａ到Ｂ的函数构成集合ＢA，读作“B上A”

如果|A| = m，|B| = n，m、n不全是0，则|BA| = nm

即，若题中给出集合A有m个元素，B有n个元素，可直接用nm 计算出A到B的函数个数。本题中为23 = 8

６.设，a,bG，则（a-1）-1，（ab）-1b-1 * a-1。

书P139公式

7.设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，则fg=__{<1,3>,<2,1>,<3,1>}___，gf=__{<1,3>,<2,3>,<3,2>}__。书P82-8

3合成：FG = {|xGz∧zFy}

需要说明的是，这里的合成FG是左复合，即G先作用，然后将F复合到G上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。

三、计算题（每题9分，共36分）

1.设集合A＝{1, 2, 3,4,5}，A上的关系R＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,3>,<3,5>,<4,4>,<5,5>}

(1)画出R的关系图；

(2)问R具有关系的哪几种性质(自反、对称、传递、反对称).自反性、传递性

书P87表格，根据关系图可直接判断性质……

(3)给出R的传递闭包。

R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}

-第 3页

R2 = RR = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}R3 = R2R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}……

所以，t(R)= {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

2.集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆

元。*abcde

abaccc

babcde

cccccc

dedcba

edecdb

幺元：b

零元：c

逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e

书P123定义

3．求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式及成真赋值。

A = P→((┐P∨Q)∧(Q∧P))

= P→((┐P∨Q)∧(Q∧P))

= P→((┐P ∧Q∧P)∨(Q∧Q∧P))

= P→(Q∧P)

= ┐P∨(Q∧P)

=(┐P∧(Q∨┐Q))∨(Q∧P)

=(cP∧Q)∨(┐P∧┐Q)∨(P∧Q)

=(┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)

= m0∨m1∨m

3成真赋值为00，01，1

14．求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数？-第 4页

完全平方数的个数：1000=1000000，所以有1000个（即1到1000）

完全立方数的个数：1003 =1000000，所以有100个（即1到100）

既是完全平方数又是完全立方数的重复部分：106 =1000000，所以有10个（即16到106）所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10)= 998910

2四、证明题（每题8分，共24分）

1．若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？（给出相应推理的证明过程）

2．给出关系不满足对称性的条件并证明。

∃∈R∧∉R

⇔∃∈R∧∉R

⇔┐∀(∈R∧∈R)

3．如果关系R和S为X上的等价关系，证明：R∩S也是X上的等价关系。

(1)自反

设x∈X【推∈R∩S】

∵R和S为X上的等价关系

∴R和S均为X上的自反关系

∵x∈X

∴∈R, ∈S

∴∈R∩S

∴R∩S在X上是自反的(2)对称

设∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的对称关系

∴∈R,∈S

∴∈R∩S

-第 5页

∵此时∈R∩S

∴R∩S在X上是对称的【∈R∩S时，必有∈R∩S】

(3)传递

设∈R∩S，∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的传递关系

∴∈R,∈S

∴∈R∩S

∵此时∈R∩S，∈R∩S

∴R∩S在X上是传递的【∈R∩S，∈R∩S时，必有∈R∩S】

综上所述，R∩S在X上是自反、对称、传递的∴R∩S为X上的等价关系

书P90

等价关系：自反、对称、传递

偏序关系：自反、反对称、传递

因此要证明某关系在非空集合上是等价关系或偏序关系，一般需分为三个性质分别证明，同时，题目条件中若给出等价关系或偏序关系，也可分为三部分选择使用。这类题条件较多（自己设的、题目推的），一定要思路清晰，否则容易写乱自己绕不出来„„

这道题三部分每个部分所设的条件都是该性质定义里的“若”，想要推出定义里的“则”，即用定义证明。这就是思路很重要的一部分。

-第 6页

第三篇：离散数学浙师大2008期末试卷

浙江师范大学《离散数学》考试卷

考试形式闭卷使用学生 计(非师范): 02班

考试时间120 分钟出卷时间 2008 年5月28日

说明：考生应将全部答案都写在答题纸上，否则作无效处理。

一。选择题（每题2分，共20分）：

1．命题公式p(qp)为（）。

A．重言式B．可满足式C．矛盾式D．等值式

2．设集合A = {1，a}，则P(A)=（）。

A．{{1}，{a}}B．{，{1}，{a}}

C．{，{1}，{a}，{1，a}}D．{{1}，{a}，{1，a}}

3．下列命题中正确的结论是：（）

A．集合上A的关系如果不是自反的，就一定是反自反的；

B．若关系R,S都是反自反的，那么RS必也为反自反的；

C．若关系R,S都是自反的，那么RS必也为自反的；

D．每一个全序集必为良序集.4．下列结论中不正确的结论是：（）

A．三个命题变元的布尔小项pqr的编码是m010；

B．三个命题变元的布尔大项pqr的编码是M101；

C．任意两个不同的布尔小项的合取式必为永假式；

D．任意两个不同的布尔大项的合取式必为永假式.5．设集合A和二元运算*，可交换的代数运算是（）。

A．设AP({x,y}),a,bA,abab

B．设A{1,1,2,3,4,5},a,bA,ab|b|

C．设AMn(R)，运算是矩阵的乘法

D．设AZ,a,bA,aba2b

6．以下命题中不正确的结论是（）

A．素数阶群必为循环群；B．Abel群必为循环群；

C．循环群必为Abel群D．4阶群必为Abel群.7．设代数系统(K1,)和(K2,)，存在映射f:K1K2，如果a,bK1，都有（），称K1与K2同态。

A．f(ab)f(a)f(b)B．f(ab)f(a)f(b)

C．f(ab)f(a)f(b)D．f(ab)f(a)f(b)

8．图G有21条边，3个4度结点，其余均为3度结点，则G有（）个结点。A．13B．15C．17D．19

9．以下命题中正确的结论是（）

A．n2k时，完全图Kn必为欧拉图

B．如果一个连通图的奇结点的个数大于2，那么它可能是一个Euler图；

C．一棵树必是连通图，且其中没有回路；

D．图的邻接矩阵必为对称阵.10．若连通图GV,E，其中|V|n,|E|m，则要删去G中（）条边，才能确定G的一棵生成树。

A．nm1B．nm1C．mn1D．mn

1二．填空题（每题2分，共20分）

11．在有界格中命题a00的对偶命题为

12．设G是有限群,H是G的子群，则H在G中的右陪集数为。

13．设集合A = {a,b,c,d}，A上的二元关系R = {,,,}，那么Dom(R)= Ran(R)=。

11014．设集合B = {a,b,c}上的二元关系R的关系矩阵MR001，则R具有的性质

000

是，且它的对称闭包S(R)＝。

15．设集合A = {a,b}，B = {1,2}，则从A到B的所有函数是，其中双射的函数

16．设无向图GV,E是哈密顿图，对于任意的V1V且V1均有 其中，p(GV1)为GV1的连通分支数。

17．公式(a(bc)def)(g(hi)j)的前缀符号法表示为。

18．已知下图，它的点连通度(G)为，边连通度(G)为

20．若二部图Km,n为完全二部图，则其边数为

三．计算题(一)（每小题5分，共30分）

21．符号化下述两个语句，并说明其区别：

（1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游。

22．将下命题化为主析取范式和主合取范式：(p(qr))(pqr).23．设R={<0,1>,<1,0>,<0,2>,<2,0>}，求：⑴ R*R；⑵ R*R-1； ⑶R[{0}]

24．设集合Ａ＝｛１，２，３，４｝，Ａ上的二元关系Ｒ，其中Ｒ＝｛<1,1>,<1,4>,<2,2>, <2,3>,<3,2>,<3,3>,<4,1>,<4,4>｝，说明Ｒ是否Ａ上的等价关系。

25．设A{1,2,,12}，为整除关系，B{2,3,4}，(1)画出偏序集A,的哈斯图；

（2）找出A的极大元、极小元、最大元、最小元；（3）在A,中求B的上界、下界、最小上界、最大下界.26．设代数系统(Z,),其中Z是整数集，二元运算定义为

a,bZ,abab2。aZ,求a的逆元.三．计算题(二)（每小题7分，共14分）

27．设Ga是15阶循环群.(1)求出G的所有生成元；（2）求出G的所有子群.28．求下图D的邻接矩阵A(D)，并算出其可达矩阵P(D)

五．证明题（每小题8分，共16分）

29．在自然推理系统F中，构造下面推理的证明：

每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所有的人不喜欢步行。（个体域为人类集合）

30．证明：设S,,是具有两个二元运算的代数系统，且对于和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得S,构成一个格，且a,bS，有abab，abab.

第四篇：苏州大学离散数学期末试卷

苏州大学2011—2012年上学期离散数学期末试卷

一、名词解释

1、等势：

2、阿贝尔群：

3、偏序关系：

4、命题：

5、平面图：

二、求(p∧r)∨(p←→q)的主析取和主合取范式。

三、符号化下面的命题并推证其结论。

任何人如果他喜欢音乐，他就不喜欢美术，每个人或者喜欢美术或者喜欢体育，有的人不喜欢体育。所以存在有人不喜欢音乐。

四、证明：

1）A∩（A∪B）＝A 2）若关系R是对称和传递的，试证明R°R=R。

五、已知映射f和g，f和g都是双射，试证明f°g也为双射。

六、证明：[0,1]是不可数的。

七、设是一个分配格，那么，对于任意的a，b，c∈A,如果有：

a∧b＝a∧c，a∨b＝a∨c 成立，则必有b＝c。

八、有关独异点的证明，证明某一代数系统是可交换的独异点。

九、简单无向图G，有N个结点，N+1条边，证明G中至少有一个结点的次数大于等于3。

十、简述欧拉定理，并证明该定理成立。

注：该份试题是参加完离散考试后整理出来的，除第八大题记不清具体题目外，其他都是原题。希望对学弟学妹的离散数学期末复习有所帮助。另外说明该份试卷是马小虎老师班上考的，徐汀荣老师班上不知道是不是和该份试卷一样。

第五篇：离散数学期末试卷06-07

安徽大学2006—2007学年

A.4，20 ； B.4，22 ； C.5，22 ； D.5，24。

图1-8

9．设G是具有w个连通分支的平面图，若G中有n个结点，m条边，k个面，则必有（）A.nmk2 ； B.nmkw ； C.nmkw1 ； D.nmkw1。

10．设G=(V,E)为(n,m)连通图，则要确定G的一颗生成树必删去G中边数为（）A．n-m-1 ； B． n-m+1 ； C．m-n+1 ； D．m-n-1。

二、填空题（每空2分，共22分）

1．设G={1,5,7,11}，为群，其中*为模12乘法，则5的阶（即周期）为__________，有__________个真子群。

2．令A={a,b,c}，是群，a是单位元，则b2=__________，c的阶（即周期）为__________。3．设H{0,4,8}，H,12是群N12,12的子群，其中N12{0,1,2,...,11}，12是模12加法，则N12,12有__________个真子群，H的左培集3H__________，4H__________。4．若连通平面图G有4个结点，3个面，则G有__________条边。

5．设T是无向树，它有40个1度点，20个2度点，31个3度点，且没有6度或6度以上的顶点。则T中有__________个4度点，有__________个5度点。

6．无向图G是有k（k2）棵树组成的森林，至少要添加_______条边才能使G成为一棵树。

三、综合题（每小题6分，共18分）

1．Q为有理数集，Q上定义运算*为：a*babab。（共6分）

（1）求的幺元；（2分）

（2）求中元素a的逆元（若存在逆元）；（2分）

（3）求2*（-5）；7*12。（2分）

2．图3-2是格L所对应的哈斯图。（共6分）

《

离散数学

》试卷

（1）若a,b,d,0的补元存在，写出它们的补元；（2分）（2）L是否是有补格？说明理由；（2分）（3）L是否是分配格？说明理由。（2分）a d b e c 0 图3-2 3．画出所有具有6个顶点的无向树。（6分）

四、证明题（每小题8分，共40分）

1．设G,*是一个群，证明：对于G中任意的a,b,c,d,a1,b1,c1,d1，如果a*ca1*c1，a*da1*d1，b*cb1*c1。则有b*db1*d1。

2．设G是交换群，证明G中一切有限阶元素所成集合H是G的一个子群。

《

离散数学

》试卷

3．设L,为一个格，试证明：L,为分配格的充要条件是对于任意的a,b,cL，有(ab)*ca(b*c)。

4．证明在无向完全图Kn中（n3）任意删去n-3条边后，所得到的图是哈密尔顿图。

5．设简单平面图G中结点数n7，边数m15，证明：G是连通的。

《

离散数学

》试卷

安徽大学2006—2007学年

图3.3（注，直接画出以上六个图形得6分，写出分析过程并正确可得3分。）

四、证明题（每小题8分，共40分）

1．证明：因为G,*是一个群，则x,yG，有(x*y)1y1*x1，x*x1e（1分）。所以，（2分）

=(b*c)*(c1*a1)*(a*d)（3分）b*db*(c*c1)*(a1*a)*d =(b1*c1)*(a*c)1*(a1*d1)（4分）=(b1*c1)*(a1*c1)1*(a1*d1)（5分）=(b1*c1)*(c1*a1)*(a1*d1)（6分）

=b1*(c1*c1)*(a1*a1)*d1（7分）

=b1*d1（8分）

2．证明：

(1)eH，所以H；（2分）

(2)对任x,yH，存在m,nZ，使xme，yne，G是交换群，(x,y)mnxmnymne，即xy也是有限阶元素，所以xyH；（6分）(3)对任xH，存在mZ，使xme，所以(x1)m(xm)1e1e，所以x1H。（8分）

3．证明：

设L,是分配格。由a*ca，(b*c)(b*c)，可得

(a*c)(b*c)a(b*c)，而(ab)*c(a*c)(b*c)所以(ab)*ca(b*c)。（2分）

反之，若对于任意的a,b,cL，有(ab)*ca(b*c)，则可得

(ab)*c((ba)*c)*c

《

离散数学

》试卷

1111(b(a*c))*c 由已知条件 ((a*c)b)*c

(a*c)(b*c)由已知条件（6

分）

又由a*c(ab)*c和b*c(ab)*c，可得

(a*c)(b*c)(ab)*c

于是有(ab)*c(a*c)(b*c)（8分）

4．证明：

我们已经知道，一个n阶无向简单图是哈密尔顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（2分）

现证在无向完全图Kn中任意删去n-3条边后所得的图G，其不同两点的度数之和大于等于n。用反证法。

设图G中存在两点vi和vj，其度数之和不大于等于n，即

deg(vi)+deg(vj)n-1 删去这两个点后，至多删去图G中的n-1条边，由题设条件可知，图G的边数

m(n1) n(n1)22

(n3)(n1)

1（6(n2)(n3)分）

(n2)(n3)2(n2)(n3)21由此可知，在图G中删去点vi和vj后，余下的图为具有n-2个点，且至少有但这样的简单无向图是不存在的。因为具有n-2个点的简单无向图最多有

条边，条边。所以图G中任意不同的两点的度数之和大于等于n，图G为哈密尔顿图。（8分）

5．证明：

设G为非连通的，具有2个连通分支G1,G2,...,G。设Gi的结点数为ni，边数为mi，i1,2,...,。

若存在nj1，则必为2，因为只有此时G为一个平凡图并上一个K6才能使其边数为15，可是K6不是平面图，这矛盾于G为平面图这个事实，所以不存在nj1。（2分）

若存在nj2，Gj中至多有一条边（简单图），另外5个结点构成K5时边数最多，但其值也仅为10条边，这与G有15条边矛盾。（4分）

综上所述，ni必大于等于3，i1,2,...,。由简单平面图可得：

mi3ni6，i1,2,...,

求和得：m3n6。（6分）将n7，m15代入得：152161。这与2矛盾。故G必为连通图。（8分）

《

离散数学

》试卷