离散数学试卷及答案.doc

《离散数学试卷及答案.doc》由会员分享，可在线阅读，更多相关《离散数学试卷及答案.doc（153页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、. .离散数学试题与答案试卷一一、填空 20% 每题2分1设N：自然数集，E+正偶数那么。2A，B，C表示三个集合，文图中阴影局部的集合表达式为A B C。3设P，Q 的真值为0，R，S的真值为1，那么的真值= 。4公式的主合取X式为。5假设解释I的论域D仅包含一个元素，那么在I下真值为。6设A=1，2，3，4，A上关系图为那么 R2 = 。7设A=a，b，c，d，其上偏序关系R的哈斯图为那么 R= 。8图的补图为。9设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是，有逆元的元素为，它们的逆元分别为。

2、10以下图所示的偏序集中，是格的为。二、选择 20% 每题 2分1、以下是真命题的有A； B；C； D。2、以下集合中相等的有 A4，3；B，3，4；C4，3，3；D 3，4。3、设A=1，2，3，那么A上的二元关系有个。 A 23 ；B 32 ；C； D。4、设R，S是集合A上的关系，那么以下说法正确的选项是 A假设R，S 是自反的，那么是自反的； B假设R，S 是反自反的，那么是反自反的； C假设R，S 是对称的，那么是对称的； D假设R，S 是传递的，那么是传递的。5、设A=1，2，3，4，PAA的幂集上规定二元系如下那么PA/ R=AA ；BP(A) ；C1，1，2，1，2，3，1，2

3、，3，4；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3那么A上包含关系“的哈斯图为7、以下函数是双射的为Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。注：I整数集，E偶数集， N自然数集，R实数集8、图中从v1到v3长度为3 的通路有条。A 0；B 1；C 2；D 3。9、以下图中既不是Eular图，也不是Hamilton图的图是10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点那么该树有个4度结点。A1；B2；C3；D4 。三、证明 26

4、%、 R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。8分、 f和g都是群到的同态映射，证明是的一个子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由kk3条边围成的连通平面图，那么，由此证明彼得森图Peterson图是非平面图。11分四、逻辑推演 16%用CP规那么证明下题每题 8分1、2、五、计算 18%1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。9分2、如以下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总

5、造价最小。分试卷一答案：一、填空 20% 每题2分1、0，1，2，3，4，6； 2、；3、1； 4、； 5、1；6、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% 每题 2分题目12345678910答案C DB、CCADCADBA三、证明 26%1、 证：“假设由R对称性知，由R传递性得“假设，有任意，因假设所以R是对称的。假设，那么即R是传递的。2、 证，有，又 是 的子群。3、 证：设G有r个面，那么，即。而故即得。8分彼得森图为，这样不成立，所以彼得森图非平面图。3分二、 逻辑推演 16%1、 证明：P

6、附加前提TIPTITITIPTICP2、证明P附加前提USPUSTIUGCP三、 计算 18%1、 解：，t (R)= , , , , , , , , 2、 解：用库斯克Kruskal算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。试卷二试题与答案一、填空 20% 每题2分1、 P：你努力，Q：你失败。“除非你努力，否那么你将失败的翻译为；“虽然你努力了，但还是失败了的翻译为。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF那么公式真值为。2、 设S=a1 ，a2 ，a8，Bi是S的子集，那么由B31

7、所表达的子集是。3、 设A=2，3，4，5，6上的二元关系，那么R= 列举法。R的关系矩阵MR=。5、设A=1，2，3，那么A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。*a b cabca b cb b cc c b6、设代数系统，其中A=a，b，c,那么幺元是；是否有幂等性；是否有对称性。7、4阶群必是群或群。8、下面偏序格是分配格的是。9、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是。10、公式的根树表示为。二、选择 20% 每题2分1、在下述公式中是重言式为A；B；C； D。2、命题公式中极小项的个数为，成真赋值的个数为。A0； B1； C2；

8、 D3 。3、设，那么有个元素。A3； B6； C7； D8 。4、 设，定义上的等价关系那么由 R产生的上一个划分共有个分块。A4； B5； C6； D9 。5、设，S上关系R的关系图为那么R具有性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性。6、设为普通加法和乘法，那么是域。A BC D= N 。7、下面偏序集能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有条。A1； B2； C3； D4 。9、在如下各图中欧拉图。10、设R是实数集合，“为普通乘法，那么代数系统 是。A群； B独异点； C半群。三、证明 46%1、 设R是A

9、上一个二元关系，试证明假设R是A上一个等价关系，那么S也是A上的一个等价关系。9分2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。11分3、 假设是从A到B的函数，定义一个函数对任意有，证明：假设f是A到B的满射，那么g是从B到的单射。10分4、 假设无向图G中只有两个奇数度结点，那么这两个结点一定连通。8分5、 设G是具有n个结点的无向简单图，其边数，那么G是Hamilton图8分四、计算 14%1、 设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出的所有子群及其相应左陪集。7分2、 权数1，4，9，16，25，36，49，

10、64，81，100构造一棵最优二叉树。7分试卷二答案：一、 填空 20%每题2分1、；2、T 3、4、R=,； 5、R=,；R=, 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、；图中无奇度结点且连通 10 、二、 选择 20%每题 2分题目12345678910答案B、DD；DDBDABBBB、C三、 证明 46%1、9分（1） S自反的，由R自反，（2） S对称的（3） S传递的由1、2、3得；S是等价关系。2、11分证明：设P(x)：x是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华上述句子符号化为：前提：、结论：3分PPUSTITITITIEG1

11、1分、0分证明：。4、8分证明：设G中两奇数度结点分别为u 和v，假设 u，v不连通，那么G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论根本定理矛盾，因而u，v一定连通。5、8分证明：证G中任何两结点之和不小于n。反证法：假设存在两结点u，v 不相邻且,令，那么G-V1是具有n-2个结点的简单图，它的边数,可得，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。所以G为Hamilton图.四、 计算 14%1、 7分解：子群有；0的左陪集：0，1；2，3；4，50，3的左陪集：0，3；1

12、，4；2，50，2，4的左陪集：0，2，4；1，3，5Z6的左陪集：Z6 。2、 7分试卷三试题与答案一、 填空 20% 每空 2分1、 设 f，g是自然数集N上的函数，那么。2、 设A=a，b，c，A上二元关系R= , , , 那么sR= 。3、 A=1，2，3，4，5，6，A上二元关系，那么用列举法 T= ；T的关系图为；T具有性质。4、 集合的幂集= 。5、 P，Q真值为0 ；R，S真值为1。那么的真值为。6、 的主合取X式为。7、 设 Px：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。那么谓词的自然语言是。8、 谓词的前束X式为。二、 选择 20

13、% 每题 2分1、 下述命题公式中，是重言式的为。A、； B、；C、； D、。2、 的主析取X式中含极小项的个数为。A 、2； B、 3； C、5； D、0； E、 8 。3、 给定推理PUSPESTIUG推理过程中错在。A、-; B、-; C、-; D、-; E、-4、 设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在条件下X与集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X与S1，S5中任何集合都不等。5、 设R和S是P上的关系，P是所有人的集合，那么表示关系。A、；B、；C、； D、。6、

14、 下面函数是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。7、 设S=1，2，3，R为S上的关系，其关系图为那么R具有的性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。8、 设，那么有。A、1,2 ；B、1,2 ； C、1 ； D、2。9、 设A=1 ,2 ,3 ，那么A上有个二元关系。A、23； B、32； C、； D、。10、全体小项合取式为。A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP规那么证明 16% 每题 8分1、2、四、14%

15、集合X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明R是X上的等价关系。10分2、 求出X关于R的商集。4分五、10%设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。4分 2、用矩阵运算求出R的传递闭包。6分六、20%1、10分设f和g是函数，证明也是函数。2、10分设函数，证明有一左逆函数当且仅当f是入射函数。答案：五、 填空 20%每空2分1、2(x+1)；2、；3、；4、反对称性、反自反性；4、；5、1；6、；7、任意x，如果x是素数那么存在一个y，y是奇数且y整除x ；8、。六、 选择 20%每题 2分题目123456

16、78910答案CCCCABDADC七、 证明 16%(每题8分)1、P附加前提TIPTITITIPTICP2、P附加前提TEESPUSTIEGCP八、 14%（1） 证明：1、 自反性：2、 对称性：3、 传递性：即由123知：R是X上的先等价关系。2、X/R=九、 10%1、；关系图2、t (R)= , , , , , , , , 。六、 20%1、12。2、证明：。试卷四试题与答案一、 填空 10% 每题 2分1、 假设P，Q，为二命题，真值为0 当且仅当。2、 命题“对于任意给定的正实数，都存在比它大的实数令F(x)：x为实数，那么命题的逻辑谓词公式为。3、 谓词合式公式的前束X式为。4

17、、 将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的局部不变，这种方法称为换名规那么。5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，那么被称为存在量词消去规那么，记为ES。二、 选择 25% 每题 2.5分1、 以下语句是命题的有。A、 明年中秋节的晚上是晴天； B、；C、当且仅当x和y都大于0； D、我正在说谎。2、 以下各命题中真值为真的命题有。A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+24当且仅当3是奇数； D、2+24当且仅当3不是奇数；3、 以下符号串是合式公式的有A、；B、；C、；D、。4、 以下等价式成

18、立的有。A、；B、；C、； D、。5、 假设和B为wff，且那么。A、称为B的前件； B、称B为的有效结论C、当且仅当；D、当且仅当。6、 A，B为二合式公式，且，那么。A、为重言式； B、；C、； D、； E、为重言式。7、 “人总是要死的谓词公式表示为。论域为全总个体域M(x)：x是人；Mortal(x)：x是要死的。A、； B、C、；D、8、 公式的解释I为：个体域D=2，P(x)：x3, Q(x)：x=4那么A的真值为。A、1； B、0； C、可满足式； D、无法判定。9、 以下等价关系正确的选项是。A、；B、；C、；D、。10、 以下推理步骤错在。PUSPESTIEGA、；B、；C、

19、；D、三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式的类型。10分2、 以下问题，假设成立请证明，假设不成立请举出反例：10分（1） ，问成立吗？（2） ，问成立吗？3、 如果厂方拒绝增加工资，那么罢工就不会停顿，除非罢工超过一年并且工厂撤换了厂长。问：假设厂方拒绝增加工资，面罢工刚开场，罢工是否能够停顿。10分四、计算10%1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。5分2、 利用主析取X式，求公式的类型。5分五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草。并推证其结论。六、证明：10%设论域D=a , b ,

20、 c，求证：。答案：十、 填空 10%每题2分1、P真值为1，Q的真值为0；2、；3、；4、约束变元；5、，y为D的某些元素。十一、 选择 25%每题2.5分题目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)十二、 逻辑判断 30%1、1等值演算法2真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。2、1不成立。假设取但A与B不一定等价，可为任意不等价的公式。2成立。证明：即：所以故。3、解：设P：厂方拒绝增加工资；Q：罢工停顿；R罢工超壶过一年；R：撤换厂长前提：结论：PPTIPTITETI罢工不会停顿是有

21、效结论。四、计算 10%（1） 解：（2）它无成真赋值，所以为矛盾式。五、谓词逻辑推理 15%解：证明：PESTITIPUSTITEUSUSTIUG十三、 证明10%试卷五试题与答案一、填空15%每空3分1、设G为9阶无向图，每个结点度数不是5就是6，那么G中至少有个5度结点。2、n阶完全图，Kn的点数X (Kn) = 。3、有向图中从v1到v2长度为2的通路有条。4、设R，+，是代数系统，如果R，+是交换群R，是半群那么称R，+，为环。5、设是代数系统，那么满足幂等律，即对有。二、选择15%每题3分1、 下面四组数能构成无向简单图的度数列的有。A、2，2，2，2，2； B、1，1，2，2，3

22、；C、1，1，2，2，2； D、0，1，3，3，3。2、 以下图中是哈密顿图的为。3、 如果一个有向图D是强连通图，那么D是欧拉图，这个命题的真值为A、真； B、假。4、 以下偏序集能构成格。5、 设，*为普通乘法，那么S，*是。A、代数系统； B、半群； C、群； D、都不是。三、证明 48%1、10%在至少有2个人的人群中，至少有2 个人，他们有一样的朋友数。2、8%假设图G中恰有两个奇数度顶点，那么这两个顶点是连通的。3、8%证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。4、10%证明循环群的同态像必是循环群。5、12%设是布尔代数，定义运算*为，求证B，*是阿贝尔群。四

23、、计算22%1、在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T。5分2） 求T对应的二元前缀码。5分2、 以下图所示带权图中最优投递路线并求出投递路线长度邮局在D点。答案：一、填空15%每空3 分1、 6；2、n；3、2；4、+对分配且对+分配均成立；5、。二、选择15%每题3分题目12345答案A,BB,DBCD三、证明48%1、10分证明：用n个顶点v1，vn表示n个人，构成顶点集V=v1，vn，设，无向图G=V，E现证G中至少有两个结点度数一样。事实上，1假设G中孤立点个数大于等于2，结论成立。2假设G中有一个孤立点，那么G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数

24、均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，n-1，由鸽巢原理，必然至少有两个结点度数是一样的。2、8分证：设G中两个奇数度结点分别为u，v。假设 u，v不连通那么至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。38分证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8由图论根本定理知：，而，所以必有，即每个面用3条边围成。410分证：设循环群A，的生成元为a，同态映射为f，同态像为fA，*，于是都有对n=1有n=2, 有假

25、设n=k-1时有对n=k时，这说明，f(A)中每一个元素均可表示为，所以f(A),*为f(a) 生成的循环群。5、证：（1） 交换律：有（2） 结合律：有而：（3） 幺：有（4） 逆：综上所述：B，*是阿贝尔群。四、计算22%1、10分15分由Huffman方法,得最正确二叉树为：25分最正确前缀码为：000，001，01，10，112、12分图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF复制道路EG、GF，得图G，那么G是欧拉图。由D开场找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10

26、+23=281。试卷六试题与答案一、 填空 15% 每题 3分1、 n阶完全图结点v的度数d(v) = 。2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，假设G中有Nk个k度顶点，Nk+1个k+1度顶点，那么N k = 。3、 算式的二叉树表示为。4、 如图给出格L，那么e的补元是。5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，那么幺元是。二、选择 15% 每题 3分1、设S=0,1,2,3,为小于等于关系，那么S，是。A、群；B、环；C、域；D、格。2、设a , b , c，*为代数系统，*运算如下：*abcaabcbbaccccc那么零元为。A、a； B、b； C、c；

27、D、没有。3、如右图相对于完全图K5的补图为。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。那么T有4度结点。A、1； B、2； C、3； D、4。5、设A，+，是代数系统，其中+，为普通加法和乘法，那么A=时，A，+，是整环。A、； B、；C、； D、。三、证明 50%1、设G是n,m简单二部图，那么。10分2、设G为具有n个结点的简单图，且，那么G是连通图。10分3、记“开为1，“关为0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0101001000110101证明它是一个环，并且是一个域。14分4、 是一代数格，“为自然偏序，那么L，是偏序格。16分四

28、、10%设是布尔代数上的一个布尔表达式，试写出的析取X式和合取X式10分五、10%如以下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价单位：万元，试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答案：一、填空 15%每题3分1、n-1；2、n(k+1)-2m；3、如右图；4、0 ；5、臂力小者二、选择 15%每题 3分题目12345答案DCAAD三、证明 50%（1） 证：设G=V，E对完全二部图有当时，完全二部图的边数m有最大值故对任意简单二部图有。（2） 证：反证法：假设G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2

29、，显然与假设矛盾。所以G连通。（3） 10，1，+，是环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，是半群乘：由“运算表知封闭群：000=000=0 ；001=001= 0；010=010=0 ；011=011=0；111=111=0 。对+的分配律 0x+y=0=0+0=(0x)+(0y)； 1x+y当x=y (x+y)=0 那么；当那么所以均有同理

30、可证：所以对+ 是可分配的。由得，0，1，+，是环。20，1，+，是域因为0，1，+，是有限环，故只需证明是整环即可。乘交环：由乘法运算表的对称性知，乘法可交换。含幺环：乘法的幺元是1无零因子：11=10因此0，1，+，是整环，故它是域。4、证：1 “是偏序关系，自然偏序反自反性：由代数格幂等关系：。反对称性：假设即：，那么传递性：那么：2在L中存在x,y的下上确界设那么：事实上：假设x , y 有另一下界c，那么是x , y 最大下界，即同理可证上确界情况。四、14%解：函数表为：00000011010001111000101111011111析取X式：合取X式：五、10%解：用库斯克Kru

31、skal算法求产生的最优树。算法为：结果如图：树权C(T)=23+1+4+9+3+17=57万元即为总造价试卷七试题与答案一、 填空 15% 每题 3分1. 任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。2. 当n为 时,非平凡无向完全图Kn是欧拉图。3. 一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,那么T中有个1度顶点。4. n阶完全图Kn的点色数X(KN)= 。5. 一组学生,用两两扳腕子比赛来测定臂力大小,那么幺元是 。二、 选择 15% 每题 3分1、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4；

32、 C、 2,1,1,1,2； D、 3,3,5,6,0。2、图 的邻接矩阵为( )。A、；B、；C、；D、。3、以下几个图是简单图的有( )。A. G1=(V1,E1), 其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de；B. G2=(V2,E2)其中V2=V1,E2=,；C. G=(V3,E3), 其中V3=V1,E3=ab,be,ed,cc；D. G=(V4,E4),其中V4=V1,E4=a,a,a,b,b,c,e,c,e,d。4、以下图中是欧拉图的有( )。5、，其中，为集合对称差运算，那么方程的解为。A、； B、； C、； D、。三、 证明 34% 1、 证明：在至少

33、有2 个人的人群中，至少有2 个人，他的有一样的朋友数。8分2、 假设图G中恰有两个奇数顶点，那么这两个顶点是连通的。8分3、 证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。8分4、 证明循环群的同态像必是循环群。10分四、 中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1点。五、 根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最正确前缀码写出求解过程。六、 10%设B4=e , a , b , ab ，运算*如下表，*那么是一个群称作Klein四元群答案：十

34、四、 填空 15%每题3分1、；2、奇数；3、5；4、n；5、臂力小者十五、 选择 15%每题 3分题目12345答案BCBBA十六、 证明 34%1、10分证明：用n个顶点v1，vn表示n个人，构成顶点集V=v1，vn，设，无向图G=V，E现证G中至少有两个结点度数一样。事实上，1假设G中孤立点个数大于等于2，结论成立。2假设G中有一个孤立点，那么G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中顶点数到值只能是1，2，n-1这n-1个数，因而取n-1个值的n个顶点的度数至少有两个结点度数是一样的。2、8分证：设G中两个奇数度结点分别为u，v。假设 u，v不连通，即它们中无任何通路，那么至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3、8分证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=