离散数学第5章作业答案

20春国家开放⼤学离散数学形考任务5资料参考答案离散数学形考任务5单项选择题
题⽬1
下列公式( A )为重⾔式．
选择⼀项：
A.
B.
C.
D.
题⽬2
下列等价公式成⽴的为( A )．
选择⼀项：
A. ┐P∧P┐Q∧Q
B. ┐P∨P Q
C. P∧Q P∨Q
D. ┐Q→P P→Q
题⽬3
下列等价公式成⽴的为( D )．
选择⼀项：
A. Q→(P∨Q)┐Q∧(P∨Q)
B. ┐P∧┐Q P∨Q
C. ┐P∨(P∧Q)Q
D. P→(┐Q→P)┐P→(P→Q)
题⽬4
下列公式中( C )为永真式．
选择⼀项：
A.
B.
C.
D.
题⽬5
前提条件的有效结论是( C )．
选择⼀项：
A. ┐P
B. P
C. ┐Q
D. Q
题⽬6
设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别是( B )．选择⼀项：
A. 0, 0, 0
B. 1, 0, 0
C. 0, 1, 0
D. 0, 0, 1
题⽬7
设个体域D是整数集合，则命题的真值是（ C ）．选择⼀项：
A. F
B. 不确定
C. T
D. 以上说法都不是
题⽬8
设个体域为整数集，则公式的解释可为( A )．选择⼀项：
A. 对任⼀整数x存在整数y满⾜x+y=0
B. 存在⼀整数x对任意整数y满⾜x+y=0
C. 存在⼀整数x有整数y满⾜x+y=0
D. 任⼀整数x对任意整数y满⾜x+y=0
题⽬9。

第5章 习题解答5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数S S ⨯2n .这样的函数有个.因此上的二元运算有个.S S S f →⨯:2n n },{b a 162=n n 下面说明通过运算表判别二元运算性质及求特导元素的方法.1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律.2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律.,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立.z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元.,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元.i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素.θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的,321,,f f f而不是可交换的.再看幂等律.四个运算表表头元素排列都是,其中主对角4f b a ,线元素排列为的只有,所以, 遵从幂等律.下面考虑幺元.如果某元素所b a ,4f 4f 在的行和列元素的排列都是,该元素就是幺元.不难看出只有中的a 满足这b a ,2f 一要求,因此,a 是的幺元,其他三个运算都不存在幺元.最后考虑零元.如果a 2f 所在的行和列元素都是a,那么a 就是零元;同样的,若b 所在的行和列元素都是b,那么b 就是零元.检查这四个运算表,中的a 满足要求,是零元,其他运算都没1f 有零元.在的运算表中,尽管a 和b 的列都满足要求,但行不满足要求.因而4f 4f 中也没有零元.5.2 A:①; B:③; C:⑤; D:⑦; E:⑩分析 对于用解析表达式定义的二元运算 °和 *,差别它们是否满足交换律,结合律,幂等律,分配律和吸收律的方法总结如下:任取,根据 °运算的解析表达式验证等式是否成立.如果成y x ,x y y =x 立 °运算就满足交换律.2 ° °运算的地合律任取根据°运算的解析表达式验证等式是否成立. z y x ,,)y (z y)(z x x =如果成立, °运算就是可结合的.3 ° °运算的幂等律任取x,根据 °运算的解析表达式验证等式是否成立.如果成立, °x x x = 运算满足幂等律.4 ° °运算对*运算的分配律任取,根据 °和*运算的解析表达式验证等式z y x ,,和是否成立。

习题5.11.设A=⎨a,b,c⎬，B=⎨1,2,3⎬，试说明下列A到B二元关系，哪些能构成A到B的函数？⑴f1=⎨<a,1>,<a,2>,<b,1>,<c,3>⎬⑵f2=⎨<a,1>,<b,1>,<c,1>⎬⑶f3=⎨<a,2>,<c,3>⎬⑷f4=⎨<a,3>,<b,2>,<c,3>,<b,3>⎬⑸f5=⎨<a,2>,<b,1>,<b,2>⎬解：⑴不能构成函数。

因为<a,1>∈f1且<a,2>∈f1⑵能构成函数⑶不能构成函数。

因为dom f3≠A⑷不能构成函数。

因为<b,2>∈f4且<b,3>∈f4⑸能构成函数。

2.试说明下列A上的二元关系，哪些能构成A到A的函数？⑴A=N(N为自然数集合)，f1=⎨<a,b>| a∈A∧b∈A∧a＋b＜10⎬⑵A=R(R为实数集合)，f2=⎨<a,b>| a∈A∧b∈A∧b=a2⎬⑶A=R(R为实数集合)，f3=⎨<a,b>| a∈A∧b∈A∧b2=a⎬⑷A=N(N为自然数集合)，f4=⎨<a,b>| a∈A∧b∈A∧b为小于a的素数的个数⎬⑸A=Z(Z为整数集合)，f5=⎨<a,b>| a∈A∧b∈A∧b=|2a|＋1⎬解：⑴不能构成函数。

由于1+1＜10且1+2＜10，所以<1,1>∈f1且<1,2>∈f1。

⑵能构成函数。

⑶不能构成函数。

由于12=1且(-1)2=1，所以<1,1>∈f3且<1,-1>∈f3。

⑷能构成函数。

⑸能构成函数。

3. 回答下列问题。

⑴设A=⎨a,b⎬，B=⎨1,2,3⎬。

求B A，验证|B A|= |B||A|。

离散数学第五章习题答案题目1: 定义一个关系R在集合A上，如果对于所有的a, b, c属于A，满足以下条件：- 如果(a, b)属于R，则(b, a)属于R。

- 如果(a, b)属于R且(b, c)属于R，则(a, c)属于R。

证明R是传递的。

答案：根据题目给出的条件，R是对称的和传递的。

首先，对称性意味着如果(a, b)属于R，那么(b, a)也必须属于R。

其次，传递性意味着如果(a, b)和(b, c)都属于R，那么(a, c)也必须属于R。

结合这两个性质，我们可以得出结论：对于任意的a, b, c属于A，如果(a, b)和(b, c)都属于R，那么(a, c)也属于R，从而证明了R的传递性。

题目2: 给定一个函数f: A → B，如果对于A中的每个元素a，都有唯一的b属于B使得f(a) = b，那么称f为单射（或一一映射）。

证明如果函数f是单射，那么它的逆函数f^-1也是单射。

答案：要证明f^-1是单射，我们需要证明对于B中的任意两个元素b1和b2，如果f^-1(b1) = f^-1(b2)，则b1 = b2。

假设f^-1(b1) = a且f^-1(b2) = a'，其中a, a'属于A。

由于f是单射，我们知道f(a) = b1且f(a') = b2。

根据f^-1的定义，我们有b1 = f(a) = f(a') = b2。

因此，如果f^-1(b1) = f^-1(b2)，则b1必须等于b2，这证明了f^-1是单射。

题目3: 证明一个函数f: A → B是满射（或到上映射）当且仅当对于B中的每个元素b，都存在A中的元素a使得f(a) = b。

答案：首先，我们证明如果f是满射，那么对于B中的每个元素b，都存在A 中的元素a使得f(a) = b。

假设f是满射，这意味着B中的每个元素都是A中某个元素的像。

因此，对于B中的任意元素b，我们可以找到一个a属于A，使得f(a) = b。

习题答案（P151~P153）1．用枚举法给出下列集合解：（2）{-3，2}（4）{5，6，7，8，9，10，11，12，13，14，15}2．用抽象法说明下列集合解：（2）{x|x为素数，10<x<20}（4）{x|x为中国的省会}（6）{x|x=2k+1，k∈I}3．判断下列哪些∈关系成立，为什麽？解：根据只有集合中的元素才与该集合有∈关系，故（1）、（4）、（6）、（7）成立，（2）、（3）、（5）、（8）不成立。

4．判断下列哪些集合相等（全集是整数集合I）解：A=G，B=E，C=F6．写出下列集合的幂集解：（2）ρ（{1，∅}）={∅，{1}，{∅}，{1，∅}}（4）ρ（{∅，{a}，{∅}}）={∅，{∅}，{{a}}，{{∅}}，{∅，{a}}，{∅，{∅}}，{{a}，{∅}}，{∅，{a}，{∅}}}7．当把“⊆”插入空位时哪一个为真？解：（1）、（2）、（3）、（6）为真，（4）、（5）为假。

8．设A、B、C分别是集合，若A∈B，B∈C，哪麽A∈C一定成立吗？解：不一定，例如，A={a}，B={{a}}，C={{{a}}}，虽然A∈B，B∈C，但A∈C不成立。

10．设U={1，2，3，4，5}，A={1，4}，B={1，2，5}和C={2，4}试写出下列集合（8）ρ（A）-ρ（C）解：ρ（A）-ρ（C）={∅，{1}，{4}，{1，4}}-{∅，{2}，{4}，{2，4}}={{1}，{1，4}}11．证明下列恒等式（1）A-（B⋂C）=（A-B）⋃（A-C）（2）（A-B）⋂B=∅解：（1）A-（B⋂C）= A⋂~（B⋂C）= A⋂（~B⋃~C）=（A⋂~B）⋃（A⋂~C）=（A-B）⋃（A-C）（2）（A-B）⋂B=（A⋂~B）⋂B= A⋂（~B⋂B）= ∅12．设A、B、C是集合，下列等式成立的条件是什么？（1）（A-B）⋃（A-C）=A（2）（A-B）⋃（A-C）= ∅解：（1）因为（A-B）⋃（A-C）= （A⋂~B）⋃（A⋂~C）= A⋂（~B⋃~C）= A⋂~（B⋂C）= A-（B⋂C）所以（A-B）⋃（A-C）=A 当且仅当A-（B⋂C）=A 由-的定义可知A⋂（B⋂C）=∅（2）由（1）可知，（A-B）⋃（A-C）=A-（B⋂C）所以（A-B）⋃（A-C）=∅当且仅当A-（B⋂C）=∅由定理5.11可知A⊆（B⋂C）13. 设A，B是集合（1）A-B=B，问A和B有何关系？（2）A-B=B-A, 问A和B有何关系？解：（1）A=B=φ。

第三章1、用枚举法写出下列集合。

①英语句子“I am a student”中的英文字母；解：{I,a,m,s,t,u,d,e,n}②大于5小于13的所有偶数；解：{6,,8,10,12}③20的所有因数；解：{1,2,4,5,10,20}④小于20的6的正倍数。

解：{6,12,18}2、用描述法写出下列集合。

①全体奇数；解：S={x|x是奇数}②所有实数集上一元二次方程的解组成的集合；解：S={x|x是实数集上一元二次方程的解}③二进制数；解：S={x|x是二进制数}④能被5整除的整数集合。

解：S={x|x是能被5整除的整数}3、求下列集合的基数。

①“proper set”中的英文字母；解：S={p,r,o,e,s,t}所以 cardS=|S|=6②{{1,2}，{2,1,1}，{2,1,2,1}}；解： cardS=|S|=3③{x|x=2或x=3或x=4或x=5}；解：cardS=|S|=4④{{1，{2,3}}}。

解：cardS=|S|=14、求下列集合的幂集。

①“power set”中的英文字母；解：S={p,o,w,e,r,s,t}(S)是所有S的子集构成的集合，这里不一一列举了。

②{3,6,9}；解：℘(S)={Φ ,{3},{6},{9},{3,6},{3,9},{6,9},{3,6,9}} ③小于20的5的正倍数；解：S={5,10,15} ℘(S)={Φ,{5},{10},{15},{5,10},{5,15},{10,15},{5,10,15}} ④{{1,3}}。

解：℘(S)={Φ,{1,3}}5、设Φ=A ，B=a ，求P(A) ，P(P(A)) ，P(P(P(A))) ，P(B) ，P(P(B)) ，P(P(P(B)))。

解：P(A)={Φ};P(P(A))={Φ,{Φ}};P(P(P(A)))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}P(B)={Φ,a };P(P(B))={Φ,{Φ},{a},{Φ,a}};P(P(P(B)))={Φ,{Φ},{{Φ}},{{a}},{{Φ,a}},{Φ,{Φ}},{Φ,{a}},{Φ,{Φ,a}},{{Φ},{a}},{{Φ},{Φ,a}},{{a},{Φ,a}},{Φ,{Φ},{a}},{Φ,{Φ},{Φ,a}},{Φ,{a},{Φ,a}},{{Φ},{a},{Φ,a}},{{Φ,{Φ},{a},{Φ,a}}}.6、如果集合A 和B 分别满足下列条件，能得出A 和B 之间有什么联系？ ①A ∪B=A ； ②A ∩B=A ； ③A －B=A ； ④A ∩B=A －B ； ⑤A －B=B －A ； ⑥A B A =⊕。

离散数学第5次作业参考答案一、(每问5分，共10分)设S Q Q =⨯，Q 是有理数集，*为S 上的二元运算，,,,a b x y S ∀<><>∈有：,*,,a b x y ax ay b <><>=<+>(1) *运算在S 上是否可交换、可结合？是否为幂等？ (2) *运算是否有单位元、零元？如果有，请指出，并求出S 中所有可逆元素的逆元。

. 解：(1) 因为,*,,a b x y ax ay b <><>=<+>， 而,*,,x y a b xa xb y <><>=<+>，所以，不具有交换律。

对任意的,,,,,a b x y w t S <><><>∈，有(,*,)*,,a b x y w t axw axt ay b <><><>=<++>，且 ,*(,*,),a b x y w t axw axt ay b <><><>=<++>。

因此，满足结合律。

因为2,*,,,a b a b a ab b a b <><>=<+>≠<>，所以不是幂等的。

(2)因为没有交换律，所以要求单位元，需要先求出左单位元，右单位元，当左单位元和右单位元相等的时候，那么就称为单位元。

零元也是一样，没有交换律，就要先求出左零元和右零元，如果左右零元相等，就叫做零元。

求零元：假设左零元为<a , b >.那么根据左零元的定义，对任意的,x y S <>∈，有,*,,,a b x y ax ay b a b ax a ay b b<><>=<+>=<>⇒=+=且，由于对任意的,x y <>都成立，所以左零元为0,,b b Q <>∈.但是,*0,0,x y b bx y <><>=<+>，对任意的,x y <>，显然0,0,bx y b <+>≠<>，因此，0,b <>不是右零元。

第五章习 题1． 解：4个顶点的所有非同构连通图如下图所示：2． 解：图G 是1-可着色的当且仅当G 是空图。

3． 解：(1)设w 为分图个数，由公式m ≤12(n −w )(n −w +1)知，w=3时，m ≤12(6−3)(6−3+1)=6。

所以分图个数w>2时，边数不能超过6条。

现在有7条边，所以分图个数不超过2。

(2)由一个孤立顶点和一个K n-1组成的图。

4． 解： 以所有二位三进制数作为顶点，在这顶点集{aa,ab,ac,ba,bb,bc,ca,cb,cc}中，若顶点u 的后一个字母与顶点v 的前一个字母相同，则u 到v 有一个弧。

这样所得图如下图所示，其中e 0=aaa,e 1=aab,e 2=aac,e 3=aba,e 4=abb,e 5=abc,e 6=aca,e 7=acb,e 8=acc,e 9=baa, e 10=bab,e 11=bac,e 12=bba,e 13=bbb,e 14=bbc,e 15=bca,e 16=bcb,e 17=bcc,e 18=caa,e 19=cab, e 20=cac,e 21=cba,e 22=cbb,e 23=cbc,e 24=cca,e 25=ccb,e 26=ccc 。

此图有一条欧拉回路:（e 0,e 1,e 3,e 11,e 7,e 21,e 10,e 4,e 14,e 16,e 22,e 13,e 12,e 9,e 2,e 8,e 26,e 25, e 23,e 15,e 20,e 6,e 19,e 5,e 17,e 24,e。

5． 解：(a) 邻接矩阵为A=[0 1 0 10 0 1 10 1 0 10 1 0 0]；(b) A (2)=[0 1 1 10 2 0 10 1 1 10 0 1 1]，A (3)=[0 2 1 20 1 2 20 2 1 20 2 0 1]，A (4)=[0 3 2 30 4 1 30 3 2 30 1 2 2];由A ，A (2)，A (3)，A (4)可知从v 1到v 4长度为1，2，3，4的路径分别为1，1，2，3条。

离散数学第五章答案离散数学第五章答案【篇一：3~离散数学习题解答(第五章)格与布尔代数5】题五（第五章格与布尔代数）1．设〈l，?〉是半序集，?是l上的整除关系。

问当l取下列集合时，〈l，?〉是否是格。

a) l={1，2，3，4，6，12}b) l={1，2，3，4，6，8，12}c) l={1，2，3，4，5，6，8，9，10}[解] a) 〈l，?〉是格，因为l中任两个元素都有上、下确界。

631b) 〈l，?〉不是格。

因为l中存在着两个元素没有上确界。

例如：8?12=lub{8，12}不存在。

12 63 1c) 〈l，?〉不是格。

因为l中存在着两个元素没有上确界。

倒例如：4?6=lub{4，6}不存在。

712．设a，b是两个集合，f是从a到b的映射。

证明：〈s，?〉是〈2b，?〉的子格。

其中s={y|y=f (x)，x∈2a}[证] 对于任何b1∈s，存在着a1∈2a，使b1=f（a1），由于f(a1)={y|y∈b∧(?x)(x∈a1∧f (x)=y)}b 所以b1∈2b，故此s?2b；又b0=f (a)∈s (因为a∈2a)，所以s非空；对于任何b1，b2∈s，存在着a1，a2∈2a，使得b1=f (a1)，b2=f (a2)，从而l∪b{b1，b2}=b1∪b2=f (a1)f (a2)=f (a1∪a2) （习题三的8的1））由于a1∪a2?a，即a1∪a2∈2a，因此f (a1∪a2)∈s，即上确界l∪b{b1，b2}存在。

对于任何b1，b2∈s，定义a1=f –1(b1)={x|x∈a∧f (x)∈b1}，a2=f-1(b2)={x|x∈a∧f (x)∈b2}，则a1，a2∈2a，且显然b1=f (a1)，b2=f (a2)，于是glb{b1，b2}=b1∩b2=f (a1)∩f (a2)f (a1∩a2) （习题三的8的2））又若y∈b1∩b2，则y∈b，且y∈b2。

由于y∈b1=f(a1)={y|y∈b∧(?x)(x∈a1∧f (x)=y)}，于是存在着x∈a1，使f(x)=y，但是 f (x)=y∈b2。

5.1习题参考答案1、阮允准同学提供答案:解：设度数小于3的结点有x个，则有3×4＋4×3＋2x≥2×16解得：x≥4所以度数小于3的结点至少有4个所以G至少有11个结点2、阮允准同学答案：证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。

若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。

若度数为5的结点数为6,8个，结论显然成立。

由上可知，G中至少有5个6度点或至少有6个5度点。

3、晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.4 \阮同学给出证明如下：证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。

所以结论成立。

5、试证明下图中两个图不同构。

晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。

我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。

6、画出所有5个结点3条边，以及5个结点7条边的简单图。

解：如下图所示：(晓津与阮同学答案一致)7、证明：下图中的图是同构的。

证明如下：在两图中我们可以看到有a→e,b→h,c→f,d→g两图中存在结点与边的一一对应关系，并保持关联关系。

8、证明：下面两图是同构的。

阮同学给出证明如下：证明：找出对应关系：a---q, b----r, c-----s, d----t, e-----u,f------v, g-----w, h----x9、证明：三次正则图必有偶数个结点。

阮同学证明如下：由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。

《离散数学1-4-5章》练习题第1章集合1、在0（）Φ之间写上正确的符号。

(1) = (2) ⊆(3) ∈(4) ∉2、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。

3、设P={x|(x+1)2≤4且x∈R},Q={x|5≤x2+16且x∈R},则下列命题哪个正确（） (1) Q⊂P (2) Q⊆P (3) P⊂Q (4) P=Q4、若A-B=Ф，则下列哪个结论不可能正确？( )(1) A=Ф (2) B=Ф(3) A⊂B (4) B⊂A5、判断下列命题哪几个为正确？( )(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}⊆{Ф,{{Ф}}} (3) Ф∈{{Ф}}(4) Ф⊆{Ф} (5) {a,b}∈{a,b,{a},{b}}6、设Ａ，Ｂ，Ｃ是三个集合，证明：a、A⋂ (B－C)＝(A⋂B)－(A⋂C)b、(A－B)⋃(A－C)=A－(B⋂C)第4章关系1、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R 和R-1的集合表示和关系矩阵表示。

2、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)R R (2) R-1。

3、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {( )}。

4、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：5、R是A={1,2,3,4,5,6}上的等价关系，R=I⋃{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}A求R诱导的划分。

6．画出下列集合关于整除关系的哈斯图.(1){1, 2, 3, 4, 6, 8, 12, 24}.(2){1,2,…..,9}.并指出它的极小元，最小元，极大元，最大元。

第5章函数1.设A＝{1，2，3}，B＝{a，b，c}，确定下列关系是否为从A到B的函数，为什么？如果是函数，是单射、满射还是双射，并指出其定义域和值域。

离散数学第五版习题答案【篇一：自考2324离散数学第五章课后答案】txt>5.1习题参考答案1、设无向图g有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：g中至少有几个结点。

阮允准同学提供答案:解：设度数小于3的结点有x个，则有解得：x≥4所以度数小于3的结点至少有4个所以g至少有11个结点2、设无向图g有9个结点，每个结点的度数不是5就是6，证明：g中至少有5个6度结点或至少有6个5度结点。

阮允准同学答案：证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。

若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。

若度数为5的结点数为6,8个，结论显然成立。

由上可知，g中至少有5个6度点或至少有6个5度点。

3、证明：简单图的最大度小于结点数。

阮同学认为题中应指定是无向简单图.晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.4、设图g有n个结点，n+1条边，证明：g中至少有一个结点度数≥3 。

阮同学给出证明如下：证明：设g中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以g的边数必小于等于n，这和已知g有n+1条边相矛盾。

所以结论成立。

5、试证明下图中两个图不同构。

晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。

我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。

6、画出所有5个结点3条边，以及5个结点7条边的简单图。

解：如下图所示： (晓津与阮同学答案一致)7、证明：下图中的图是同构的。

证明如下：在两图中我们可以看到有a→e,b→h,c→f,d→g两图中存在结点与边的一一对应关系，并保持关联关系。