文档库 最新最全的文档下载
当前位置:文档库 › 2014年9月份考试离散数学第三次作业

2014年9月份考试离散数学第三次作业

2014年9月份考试离散数学第三次作业
2014年9月份考试离散数学第三次作业

2014年9月份考试离散数学第三次作业

一、填空题(本大题共40分,共 10 小题,每小题 4 分)

1. 设P:我生病,Q:我去学校(1)命题“我虽然生病但我仍去学校”符号化为 ______ 。(2)命题“只有生病的时候,我才不去学校”符号化为

______ 。(3)命题“如果我生病,那么我不去学校”符号化为 ______ 。2. 某集合A上的二元关系R具有对称性,反对称性,自反性和传递性,此关系R是 ______ ,其关系矩阵是 ______

3. 设A={1,2},B={α,β,γ},则AoB= ______ 。

4. 设A={2,3,{2,3},φ},则A-{{2,3}}= ______ 。

5. 设A={1,{2},φ},则A的幂集有元素 ______ 个。

6. 设A={1,2,3},B={x,y},f:A B,则不同的函数个数为 ______ 个。

7. 设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度结点,该图有 ______ 个顶点。

8. 集合A={1,2},B={a,b,c,d},C={c,d,e},则A*(B-C)为 ______ 。

9. 求命题公式的主析取范式 ______ 。

10. 命题公式P→Q∧R的对偶式为 ______

二、作图题(本大题共6分,共 1 小题,每小题 6 分)

根据下列条件如果能则画出一个欧拉图,如果不能则说明理由。(1)偶数个顶点,偶数条边(2)奇数个顶点,奇数条边(3)偶数个顶点,奇数条边(4)奇数个顶点,偶数条边

三、计算题(本大题共30分,共 5 小题,每小题 6 分)

1. 分别列出:广群、半群、独异点、群的概念

2. 判定下图是否能够一笔画,若不能,请说明为什么,若能,请标出路径。

3. 设S={1,2,3,4,6,12},D为S上的整除关系,(1)试写出该关系并画出哈斯图;(2)设子集B={2,3,6},试求B的最大元、最小元、极大元和极小元;(3)试求B的上界、上确界、下界和下确界。

4.

所有的有理数是实数,某些有理数是整数,因此某些实数是整数。

1)请符号化该命题。2)使用谓词演算的推理论证,证明结论成立。

5.

画出满足下列条件的图来

a)画一个有一条欧拉回路和一条汉密尔顿回路的图。

b)画一个有一条欧拉回路,但没有一条汉密尔顿回路的图。c)画一条没有一

条欧拉回路,但有一条汉密尔顿回路的图。

四、分析题(本大题共24分,共 4 小题,每小题 6 分)

1. 设I是整数集, <,>,=,是I上的二元关系,分别表示小于、大于、等于、小于等于、大于等于,不等于。那么这些关系会满足什么性质?试填写下表:

2. 求出下图的最小生成树,并计算出权。

3. 分析集合A={1,2,3}上的下述5个关系 (1)R={,,,} (2) S={,,,,} (3) T={,,,} (4) 空关系 (5) 全域关系判断上述关系是否为a)自反的 b)对称的

c)可传递的 d)反对称的。

4. 一棵数有两个结点度数为2,一个结点度数为3,三个结点度数为4,问有几个度数为1的结点?

答案:

一、填空题(40分,共 10 题,每小题 4 分)

1.

参考答案:

(1)P∧Q (2) P??Q (3)P→?Q

解题方案:

评分标准:

2.

参考答案:

恒等关系恒等矩阵

解题方案:

评分标准:

答案正确得满分,错误不得分

3.

参考答案:

{<1, α>,<1,β>,<1,γ> ,<2,α>,<2,β>,<2,γ>}解题方案:

评分标准:

4.

参考答案:

{2,3,φ}

解题方案:

评分标准:

5.

参考答案:

8

解题方案:

评分标准:

6.

参考答案:

8

解题方案:

评分标准:

7.

参考答案:

4

解题方案:

评分标准:

8.

参考答案:

{<1,a>,<1,b>,<2,a>,<2,b>}

解题方案:

评分标准:

9.

参考答案:

解题方案:

评分标准:

10.

参考答案:

P∧(Q∨R)

解题方案:

评分标准:

二、作图题(6分,共 1 题,每小题 6 分)

0.

参考答案:

(1)、(2)均可画出。依次如下:

其中(3)(4)不能画出一个欧拉图,因此具有n个结点的连通图如果存在一条包含所有节点的回路,则该图至少有n条边。对于(3)(4)而言,则必然还有其余的边,使的图中存在奇数度结点,故它们没有欧拉回路,不能构成欧拉图。

解题方案:

评分标准:

三、计算题(30分,共 5 题,每小题 6 分)

1.

参考答案:

解题方案:

评分标准:

参考答案:

可以一笔画(路径略)

解题方案:

评分标准:

3.

参考答案:

(1)哈斯图为:

(2)B的最大元为6,最小元为1,极大元为6,极小元为1. (3)B的上界为:6,12;上确界为6;下界为:1,下确界为1.

解题方案:

评分标准:

4.

参考答案:

解题方案:

评分标准:

参考答案:

解题方案:

评分标准:

四、分析题(24分,共 4 题,每小题 6 分)

1.

参考答案:

解题方案:

评分标准:

2.

参考答案:

权=1+2+2+3+5=13

解题方案:

权=1+2+2+3+5=13

评分标准:

7

3

3.

参考答案:

(1)可传递的(2)自反、对称、可传递的(3)都不是(4)自反、对称和传递的(5)自反、对称、传递的

解题方案:

(1)可传递的(2)自反、对称、可传递的(3)都不是(4)自反、对称和传递的(5)自反、对称、传递的

评分标准:

2 2 2 2 2

4.

参考答案:

设有x个度数为1的结点。则结点总数为:2+1+3+x=6+x; 树的边树=结点数-1,故该树中边数为:5+x; 因为:2e=Sdeg(vi) 故:2(5+x)=2*2+1*3+3*4+x

x=9

解题方案:

设有x个度数为1的结点。则结点总数为:2+1+3+x=6+x; 树的边树=结点数-1,故该树中边数为:5+x; 因为:2e=Sdeg(vi) 故:2(5+x)=2*2+1*3+3*4+x

x=9

评分标准:

3 3 4

离散数学第二次在线作业

第二次在线作业 1.( 2.5分)代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案:正确此题得分:2.5分 2.(2.5分)设< L*1*2> 是代数系统,其中是*1*2二元运算符,如果*1*2都满足交换律、结合律,并且*1和*2满足吸收律,则称< L*1*2> 是格 ?正确 ?错误 我的答案:正确此题得分:2.5分 3.(2.5分)对实数的普通加法和乘法,0是加法的幂等元,1是乘法的幂等元 ?正确 ?错误 我的答案:正确此题得分:2.5分 4.(2.5分)零元是不可逆的 ?正确 ?错误 我的答案:正确此题得分:2.5分 5.(2.5分)群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案:正确此题得分:2.5分

6.(2.5分)设abc是阿贝尔群< G+> 的元素,则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案:正确此题得分:2.5分 7.(2.5分) < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案:正确此题得分:2.5分 8.(2.5分)一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案:正确此题得分:2.5分 9.(2.5分)在有向图中,结点v的出度deg+(v)表示以v为起点的边的条数,入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案:正确此题得分:2.5分 10.(2.5分)一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案:正确此题得分:2.5分

11.(2.5分)不含回路的连通图是树 ?正确 ?错误 我的答案:正确此题得分:2.5分 12.(2.5分)简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案:正确此题得分:2.5分 13.(2.5分)树一定是连通图 ?正确 ?错误 我的答案:正确此题得分:2.5分 14.(2.5分)无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案:正确此题得分:2.5分 15.(2.5分)不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案:正确此题得分:2.5分

离散数学期末考试试题(有几套带答案)

离散数学试题(A卷及答案) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分) 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D

(7) R∨S 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数,证明:在任取m+1个整数中,至少有两个整数,它们的差是m的整数倍 证明设 1 a,2a,…,1+m a为任取的m+1个整数,用m去除它们所得余数 只能是0,1,…,m-1,由抽屉原理可知, 1 a,2a,…,1+m a这m+1个整 数中至少存在两个数 s a和t a,它们被m除所得余数相同,因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (15分)证明∵x∈ A-(B∪C)? x∈ A∧x?(B∪C)? x∈ A∧(x?B∧x?C)?(x∈ A∧x?B)∧(x∈ A∧x?C)? x∈(A-B)∧x∈(A-C)? x∈(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={| x,y∈N∧y=x2},S={| x,y∈N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}](10分) 解:R-1={| x,y∈N∧y=x2},R*S={| x,y∈N∧y=x2+1},S*R={| x,y∈N∧y=(x+1)2}, 七、若f:A→B和g:B→C是双射,则(gf)-1=f-1g-1(10分)。 证明:因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数

《离散数学》第2次作业

一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1,g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中,则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中, _______________________________是其Euler 路 . 5. 设有向图G = (V , E ),V = {v 1,v 2,v 3,v 4},若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2.集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3.若R 和S 是集合A 上的两个关系,则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4.集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是..t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5.设p :我们划船,q :我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q

离散数学期末试题及答案完整版

离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ), )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ).

北邮离散数学第一次阶段作业

北京邮电大学 离散数学 第一次阶段作业 判断题 1. 如果A∪B=B,则A?B。【答案:A】 A. 正确 B. 错误 2. 如果a∈A∪B,则a?A或a?B。【答案:B】 A. 正确 B. 错误 3. a∈{a,a}。【答案:A】 A. 正确 B. 错误 4.{?}是空集。【答案:B】 A. 正确 B. 错误 5.设ρ是集合A上的等价关系,则当a,b∈ρ时,aρ=bρ。【答案:A】 A. 正确 B. 错误 单项选择题 1. 设A={a,a},则下列各式中错误的是【答案:B】 A. a∈2A B. {a}?2A C. {a}∈2A D. {a}?2A 解:2A={?,a,a, a,a} 2. 下列各式中不正确的是【答案:C】 A. ??? B. ?∈{?} C. ??? D. ?∈{?,?} 3. 设ρ是集合A上的关系,则()不是ρ为反对称关系的充分必要条件【答案:D】 A. ρ是反对称关系 B. ρ∩ρ?i A C. 对任意x,y∈A,当x,y∈ρ且x≠y时y,x?ρ D. 对A的某两个元素x, y,当x,y,y,x∈ρ时有x=y 4. 设A,B,C是集合,ρ,μ分别是A到B,B到C的关系,x∈A,z∈C,则存在y∈B使得x,y∈ρ且y,z∈μ是x,z∈ρ°μ的()条件【答案:C】 A. 充分而非必要 B. 必要而非充分 C. 充分必要

D. 既非充分又非必要 5. 设A={0,b},B={1,b,3},则A∪B的恒等关系为【答案:A】 A.{0,0,1,1,b,b,3,3} B. {0,0,1,1,3,3} C. {0,0,b,b,3,3} D. {0,1,1,b,b,3,3,0}

离散数学考试题详细答案

离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去看电影,否则就在家里读书或看报。 设P表示命题“上午下雨”,Q表示命题“我去看电影”,R表示命题“在家里读书”,S表示命题“在家看报”,命题符号化为:(PQ)(PRS) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:Q→P或P→Q c)仅当你走,我将留下。 设P表示命题“你走”,Q表示命题“我留下”,命题符号化为:Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”,Q(x)表示“x是有理数”,命题符号化为: x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋值。 (5分) (P→(Q→R))(R→(Q→P))(PQR)(PQR) ((PQR)→(PQR)) ((PQR) →(PQR)). ((PQR)(PQR)) ((PQR) (PQR)) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (PQR(PQR(PQR(PQR(PQR(PQR 2.设个体域为{1,2,3},求下列命题的真值(4分) a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。(4分) x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分)

2013年4月考试离散数学第二次作业

2013年4月考试离散数学第二次作业 一、单项选择题(本大题共50分,共 25 小题,每小题 2 分) 1. 下列语句中为命题的是() A. 暮春三月,江南草长. B. 这是多么可爱的风景啊! C. 大家想做什么,就做什么,行吗? D. 请勿践踏草地! 2. 2.设G是n个顶点的无向简单图,则下列说法不正确的是() A. 若G是树,则其边数等于n-1 B. 若G是欧拉图,则G中必有割边 C. 若G中有欧拉路,则G是连通图,且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1,则G中有汉密尔顿路 3. 集合|A|=3,|B|=2,则A B上不同的函数个数为()。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ,则以下正确的是()。 A. A=B B. A?B C. B?A D. 以上都不对 5. 设R为实数集,函数f:R→R,f(x)=2x,则f是() A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4},以下哪个关系是从B到C的单射函数?() A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算,其中可交换且可结合的运算是()。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中,为真的命题是() A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习,q:小李取得好成绩,命题“只有小李努力学习,他才能取得好成绩”的符号化形式为()。 A. B. C.

【浙江工商大学】《离散数学》期末考试题(B)

《离散数学》期末考试题(B) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ),)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二、单选题(每小题3分,共15分) 1.设R 是集合A 上的偏序关系,1-R 是R 的逆关系,则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数,则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合,≤是其上的小于等于关系,则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分,共15分): 正确打“√”,错误打“×”. 1.若一个元素a 既存在左逆元l a ,又存在右逆元r a ,则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0,1,2,3,4,5,6,7}中,2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( )

《离散数学》第一次在线作业

第一次 第1题 空集不是任何集合的真子集 您的答案:错误 题目分数:0.5 此题得分:0.5 批注:本题考查空集的基本概念 第2题 一个集合可以是另一个集合的元素 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查集合的基本概念 第3题 设A、B为集合,如果集合A的元素都是集合B的元 素,则称A是B的子集 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查子集的基本概念 第4题 如果一个集合包含了所要讨论的每一个集合,则称该 集合为全集,记为U 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查全集的基本概念 第5题 在笛卡儿坐标系中,平面上点的坐标< 1,2> 与< 2,1> 代表不同的点 您的答案:正确 题目分数:0.5

此题得分:0.5 批注:本题考查笛卡儿坐标系的基本概念 第6题 复合运算不满足交换律,但复合运算满足结合律您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查复合运算的是否满足交换律和结合律 第7题 映射也可以称为函数,是一种特殊的二元关系 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查映射的基本概念 第8题 映射的复合运算不满足交换律 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题为映射的基础知识 第9题 空集是唯一的 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查空集的唯一性 第10题 对任意的集合A,A包含A 您的答案:正确 题目分数:0.5 此题得分:0.5

批注:本题考查集合的包含概念 第11题 集合上的三种特殊元是单位元、零元及可逆元 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查集合上的三种特殊元 第12题 集合A上的偏序关系的三个性质是自反性、反对称性和传递性 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查集合偏序关系的三个性质 第13题 设f:A→B, g:B→C。若f, g都是满射,则gf也是满射 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查复合关系的满射概念 第14题 设f:A→B, g:B→C。若f, g都是双射,则gf也是双射 您的答案:正确 题目分数:0.5 此题得分:0.5 批注:本题考查复合关系的双射概念 第15题 设f:A→B, g:B→C。若f, g都是单射,则gf也是单射 您的答案:正确 题目分数:0.5 此题得分:0.5

离散数学考试试题(A卷及答案)

离散数学考试试题(A卷及答案) 一、(10分)证明?(A∨B)→?(P∨Q),P,(B→A)∨?P A。 证明:(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1),E (3)P P (4)A∨B T(2)(3),I (5)(B→A)∨?P P (6)B→A T(3)(5),I (7)A∨?B T(6),E (8)(A∨B)∧(A∨?B) T(4)(7),I (9)A∧(B∨?B) T(8),E (10)A T(9),E 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题,设A:甲参加了比赛;B:乙参加了比赛;C:丙参加了比赛;D:丁参加了比赛。 依题意有, (1)甲和乙只有一人参加,符号化为A⊕B?(?A∧B)∨(A∧?B); (2)丙参加,丁必参加,符号化为C→D; (3)乙或丁至多参加一人,符号化为?(B∧D); (4)丁不参加,甲也不会参加,符号化为?D→?A。 所以原命题为:(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件,有且仅有两人参加竞赛,故?A∧B∧?C∧?D为F。所以只有:(A∧?B∧?C∧D)∨(A∧?B∧D)?T,即甲、丁参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误?为什么?给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1),US (3)?xP(x) P (4)P(y) T(3),ES (5)Q(y) T(2)(4),I (6)?xQ(x) T(5),EG 解 (4)中ES错,因为对存在量词限制的变元x引用ES规则,只能将x换成某个个体常元c,而不能将其改为自由变元。所以应将(4)中P(y)改为P(c),c为个体常元。 正确的推理过程为: (1)?xP(x) P (2)P(c) T(1),ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3),US (5)Q(c) T(2)(4),I (6)?xQ(x) T(5),EG 四、(10分)设A={a,b,c},试给出A上的一个二元关系R,使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设R={},则

中石油北京19春《离散数学》第二次在线作业

------------------------------------------------------------------------------------------------------------------------------ 1.(2.5分)代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案: 2.(2.5分)设< L,*1,*2> 是代数系统,其中是*1,*2二元运算符,如果*1,*2都满足交换律、结合律,并且*1和*2满足吸收律,则称< L,*1,*2> 是格 正确 错误 正确答案: 3.(2.5分)对实数的普通加法和乘法,0是加法的幂等元,1是乘法的幂等元 正确 错误 正确答案: 4.(2.5分)零元是不可逆的 正确 错误 正确答案: 5.(2.5分)群中每个元素的逆元都是惟一的 正确 错误 正确答案: 6.(2.5分)设a,b,c是阿贝尔群< G,+> 的元素,则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案: 7.(2.5分) < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案: 8.(2.5分)一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案: 9.(2.5分)在有向图中,结点v的出度deg+(v)表示以v为起点的边的条数,入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案: 10.(2.5分)一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案: 11.(2.5分)不含回路的连通图是树

离散数学期末考试试题及答案

离散数学试题(B卷答案1) 一、证明题(10分) 1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((P∨Q)∧R)∨((Q∨P)∧R) ((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2) x (A(x)B(x))xA(x)xB(x) 证明:x(A(x)B(x))x(A(x)∨B(x)) x A(x)∨xB(x) xA(x)∨xB(x) xA(x)xB(x) 二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R)) (P∧(Q∨R))∨(P∧Q∧R) (P∧Q)∨(P∧R))∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D,(C∨D)E, E(A∧B),(A∧B)(R∨S)R∨S证明:(1) (C∨D) E ?P (2) E(A∧B) ??P (3) (C∨D)(A∧B) T(1)(2),I (4) (A∧B)(R∨S)??P (5) (C∨D)(R∨S) ? T(3)(4),I (6) C∨D P (7) R∨S T(5),I 2) x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x)) 证明(1)xP(x) P

(2)P(a) T(1),ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3),US (5)Q(y)∧R(a) T(2)(4),I (6)Q(y) T(5),I (7)R(a) T(5),I (8)P(a)∧R(a) T(2)(7),I (9)x(P(x)∧R(x)) T(8),EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9),I 四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解:A,B,C分别表示会打排球、网球和篮球的学生集合。则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 先求|A∩B|。 ∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。 于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。 证明:∵x A-(B∪C) x A∧x(B∪C) xA∧(xB∧x C) (x A∧x B)∧(x A∧xC) x(A-B)∧x(A-C) x(A-B)∩(A-C) ∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={| x,yN∧y=x2} R*S={| x,y N∧y=x2+1} S*R={<x,y>| x,yN∧y=(x+1)2},R{1,2}={<1,1>,<2,4>},S[{1,2}]={1,4}。 七、设R={<a,b>,,<c,a>},求r(R)、s(R)和t(R) (15分)。 解:r(R)={,,,<b,b>,

2013年9月份考试离散数学第一次作业

2013年9月份考试离散数学第一次作业 一、单项选择题(本大题共40分,共20 小题,每小题2 分) 1. 下列语句中不是命题的只有()。A. 鸡毛也能飞上天?B. 人的死或重于泰山,或轻于鸿毛。C. 不经一事,不长一智。 D. 牙好,胃口就好。 2. 设A={1,2,3,4,5},A上二元关系R={〈1,2〉,〈3,4〉,〈2,2〉},S={〈2,4〉,〈3,1〉,〈4,2〉},则S-1oR-1的运算结果是()。 A. {〈4,1〉,〈2,3〉,〈4,2〉} B. {〈2,4〉,〈2,3〉,〈4,2〉} C. {〈4,1〉,〈2,3〉,〈2,4〉} D. {〈2,2〉,〈3,1〉,〈4,4〉} 3. 下列集合关于所给定的运算成为群的是()。 A. 已给实数a的正整数次幂的全体,且a∈{0,1,-1},关于数的乘法 B. 所有非负整数的集合,关于数的加法 C. 所有正有理数的集合,关于数的乘法 D. 实数集,关于数的除法 4. 在有n个结点的连通图中,其边数() A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条 5. 一个连通的无向图G,如果它的所有结点的度数都是偶数,那么它具有一条() A. 汉密尔顿回路 B. 欧拉回路 C. 汉密尔顿通路 D. 初级回路 6. .以下命题公式中,为永假式的是() A. .p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) 7. 在布尔代数L中,表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是()。 A. b∧(a∨c) B. (a∧b)∨(a∧b) C. (a∨b)∧(a∨b∨c)∧(b∨c) D. (b∨c)∧(a∨c) 8. 所有使命题公式为真的赋值为()。 A. 010,100,101,110,111 B. 010,100,101,111 C. 全体赋值 D. 不存在 9. 设i是虚数,·是复数乘法运算,则G=<{i,-i,1,-1},?>是群,下列是G的子群是()。 A.

离散数学作业 (2)

离散数学作业布置 第1次作业(P15) 1.16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。 解:(1)p∨(q∧r)=0∨(0∧1)=0 (2)(p?r)∧(﹁q∨s)=(0?1)∧(1∨1)=0∧1 =0 (3)(﹁p∧﹁q∧r)?(p∧q∧﹁r)=(1∧1∧1)? (0∧0∧0)=0 (4)(r∧s)→(p∧q)=(0∧1)→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2 也是无理数。另外只有6能被2整除,6才能被4整除。” 解:p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。 1.19 用真值表判断下列公式的类型: (4)(p→q) →(﹁q→﹁p) (5)(p∧r) ? (﹁p∧﹁q) (6)((p→q) ∧(q→r)) →(p→r) 解:(4) p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式,最后一列全为1 (5)公式类型为可满足式(方法如上例),最后一列至少有一个1 (6)公式类型为永真式(方法如上例,最后一列全为1)。 第2次作业(P38) 2.3 用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解:(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)(p→(p∨q))∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?¬(p∨q) ∨ (p∧r) ? (¬p∧¬q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111

离散数学期末考试试题及答案

离散数学试题(B卷答案1) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E,?E→(A∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2),I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4), I (6) C∨D P (7) R∨S T(5),I 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P

离散数学第一次作业(命题逻辑) 1、证明下列各式是重言式

离散数学第一次作业(命题逻辑) 1、证明下列各式是重言式 (1)((P∧Q)→P)?T ù((?(P∧Q) ∨ P) ?T ù(?P∨?Q∨P) ?T ù(T∨?Q)?T ùT?T 所以此式为重言式 (2)?(?(P∨Q)→? P)?F ù?((P∨Q)∨? P)?F ù?(T∨Q)?F ù?T?F ùF?F 所以此式为重言式 (3)(Q→P)∧(? P→Q)∧(Q?Q)? P ù(? Q∨P)∧(P∨Q)∧T? P ù((? Q∨P)∧P) ∨((? Q∨P)∧Q) ? P ù(P∨((? Q∨P)∧Q) ? P ù(P∨P) ? P

ùP? P 所以此式为重言式 (4)(P→? P)∧(? P→P)?F ù(? P∨? P)∧(P∨P)?F ù(? P∧P)?F ùF?F 所以此式为重言式 2、求出下列公式的最简等价式:(1)((P→Q)?(? Q→? P))∧R ù((P→Q)?(P→Q))∧R ùT∧RùR (2)P∨? P∨(Q∧?Q) ùT∨FùT (3)(P∧(Q∧S))∨(? P∧(Q∧S))ù((P∨? P )∧(Q∧S))) ùT∧(Q∧S) ù(Q∧S)

3、(1)与非运算符↑(又叫悉菲(Sheffer)记号)用下述真值表定义,可以看出P↑Q??(P∧Q),试证明: (a)P↑P?? P;(b)(P↑P)↑(Q↑Q)? P∨Q; (c)(P↑Q)↑(P↑Q)? P∧Q 证明: (a)P↑P??(P∧P)??P (b) (P↑P)↑(Q↑Q)??P↑?Q??(?P∧?Q) ? P∨Q (c) (P↑Q)↑(P↑Q)??(P∧Q)↑?(P∧Q) ??(?(P∧Q)∧?(P∧Q)) ???(P∧Q) ? P∧Q (2)或非运算符↓(又叫皮尔斯(Peirce)箭头)用下述真值表定义,它与?(P∨Q)逻辑等价。对下述每一式,找出仅用↓表示的等价式。(a)? P;(b)P∨Q;(c)P∧Q。 P Q P↑Q P↓Q 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 证明: (a)? Pù? P∧Tù? P∧?Fù?(P∨F)ùP↓ F (b)P∨Qù??(P∨Q)ù?(P↓Q)ù(P↓Q)↓ F (c)P∧Qù?(?P∨?Q) ù??(? P↓? Q)ù? P↓? Qù(P↓ F)↓(Q↓ F)

离散数学期末考试试卷(A卷)

离散数学期末考试试卷(A卷) 一、判断题:(每题2分,共10分) (1) (1) (2)对任意的命题公式, 若, 则 (0) (3)设是集合上的等价关系, 是由诱导的上的等价关系,则。(1) (4)任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 (0) (5)设是上的关系,分别表示的对称和传递闭包,则 (0) 二、填空题:(每题2分,共10分) (1) 空集的幂集的幂集为()。 (2) 写出的对偶式()。 (3)设是我校本科生全体构成的集合,两位同学等价当且仅当他们在 同一个班,则等价类的个数为(),同学小王所在 的等价类为()。 (4)设是上的关系,则满足下列性质的哪几条:自反的,对称的,传递的,反自反的,反对称的。 () (5)写出命题公式的两种等价公式( )。 三、用命题公式符号化下列命题(1)(2)(3),用谓词公式符号化下列命题(4)(5)(6)。(12分) (1)(1)仅当今晚有时间,我去看电影。 (2)(2)假如上午不下雨,我去看电影,否则就在家里读书。 (3)你能通你能通过考试,除非你不复习。 (4)(4)并非发光的都是金子。 (5)(5)有些男同志,既是教练员,又是国家选手。 (6)(6)有一个数比任何数都大。 四、设,给定上的两个关系和分别是

(1)(1)写出 和 的关系矩阵。(2)求 及 (12分) 五、求 的主析取范式和主合取范式。(10分) 六、设 是 到 的关系, 是 到 的关系,证明: (8分) 七、设 是一个等价关系,设 对某一个 ,有 ,证明: 也是一个等价关系。(10分) 八、(10分)用命题推理理论来论证 下述推证是否有效? 甲、乙、丙、丁四人参加比赛,如果甲获胜,则乙失败;如果丙获胜,则乙也获 胜,如果甲不获胜,则丁不失败。所以,如果丙获胜,则丁不失败。 九、(10分) 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行,他就不喜欢乘汽车,每一个人或喜欢乘汽车,或喜欢骑 自行车(可能这两种都喜欢)。有的人不爱骑自行车,因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后,有人问他们,谁的成绩最好, 甲说:“不是我,”乙说:“是丁,”丙说:“是乙,” 丁说:“不是我。” 四人的回答只有一人符合实际,问若只有一人成绩最 好,是谁? 离散数学期末考试试卷答案(A 卷) 一、判断题:(每题2分,共10分) (1)}}{{}{x x x -∈ ( ∨) (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) (3)设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系,则L R =。 ( ∨ ) (4) 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 ( ? ) (5)设R 是A 上的关系,)(),(R t R s 分别表示R 的对称和传递闭包,则 )()(R st R ts ? ( ? ) 二、填空题:(每题2分,共10分)

电大离散数学作业答案作业答案

离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。 一、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 . 2.设给定图G (如右由图所示),则图G 的点割集是 {}f {}c e ,. 3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍. 4.无向图G 存在欧拉回路,当且仅当G 连通且 不含奇数度结点 . 5.设G=是具有n 个结点的简单图,若在G 中每一对结点度数 之和大于等于︱V ︱ ,则在G 中存在一条汉密尔顿回路. 6.若图G=中具有一条汉密尔顿回路,则对于结点集V 的每个非空子集S ,在G 中删除S 中的所有结点得到的连通分支数为W ,则S 中结点数|S|与W 满足的关系式为 S W ≤ . 7.设完全图K n 有n 个结点(n ?2),m 条边,当n 为奇数时,K n 中存在欧拉回路. 8.结点数v 与边数e 满足 e= v -1 关系的无向连通图就是树. 9.设图G 是有6个结点的连通图,结点的总度数为18,则可从G 中删去 条边后使之变成树. 10.设正则5叉树的树叶数为17,则分支数为i = 4 . 二、判断说明题(判断下列各题,并说明理由.) 1.如果图G 是无向图,且其结点度数均为偶数,则图G 存在一条欧拉回路.. 答:错误。应叙述为:“如果图G 是无向连通图,且其结点度数均为偶数,则图G 存在一条欧拉回路。” 2.如下图所示的图G 存在一条欧拉回路. 答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G 不是欧拉图而是汉密尔顿图. 答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V 中的非空子集1V ,都有)(1V G P -??V 1?。其中)(1V G P -是从图中删除1V 结点及其关联的边。 4.设G 是一个有7个结点16条边的连通图,则G 为平面图. 答:错误。若G 是连通平面图,那么若63,3-≤≥v e v 就有, 而16>3×7-6,所以不满足定理条件,叙述错误。 5.设G 是一个连通平面图,且有6个结点11条边,则G 有7个面. 姓 名: 学 号: 得 分: 教师签名: G

相关文档
相关文档 最新文档