离散数学(本)阶段练习四

离散数学形成性考核作业4作业与答案离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2. 在线提交word文档．3. 自备答题纸张，将答题过程手工书写，并拍照上传．一、公式翻译题1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．设Ｐ：小王去上课Ｑ:小李去上课则：命题公式Ｐ∧Ｑ2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．设Ｐ：他去旅游Ｑ：他有时间则命题公式为Ｐ→Ｑ3．请将语句“有人不去工作”翻译成谓词公式．设Ａ（x）:x是人Ｂ（x）：去工作则谓词公式为∃x（A(x)∧－B（x）)4．请将语句“所有人都努力学习．”翻译成谓词公式．设A（x）: x是人B（x）:努力学习则谓词公式为∀x（A（x）∧B（x））二、计算题1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）(A-B)；（2）(A∩B)；（3）A×B．解：（1）（A-B）＝{{1}，{2}}（2）（A∩B）＝{1，2}（3）A×B＝{<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1,2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>}2．设A={1，2，3，4，5}，R={<x，y>|x∈A，y∈A且x+y≤4}，S={<x，y>|x∈A，y∈A且x+y<0}，试求R，S，R•S，S•R，R-1，S-1，r(S)，s(R)．解：R＝{<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}S=空集R•S=空集S•R =空集R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>}S-1=空集r(S) ={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}s(R) ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}3．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}．(1) 写出关系R的表示式；(2) 画出关系R的哈斯图；(3) 求出集合B的最大元、最小元．4．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．答：（1）（2）（3）deg(v1)=1, deg(v2)=2 ,deg(v3)=4 ,deg(v4)=3,deg(v5)=2(4)5．图G=<V, E>，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：（1）（2）（3）其中权值是：76．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解：权值：657．求P→Q∨R的析取范式，合取范式、主析取范式，主合取范式．解：8．设谓词公式()((,)()(,,))()(,)x P x y z Q y x z y R y z ∃→∀∧∀．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．9．设个体域为D ={a 1, a 2}，求谓词公式(∀y )(∃x )P (x ,y )消去量词后的等值式；三、证明题1．对任意三个集合A , B 和C ，试证明：若A ⨯B = A ⨯C ，且A ≠∅，则B = C ．证明：设x ∈A, y ∈B,则<x,y>∈A ⨯B因为A ⨯B ＝A ⨯C ，故<x, y>∈A ⨯C, 则有y ∈C所以 B ⊆C设x ∈A, z ∈C ，则<x, z>∈A ⨯C因为A ⨯B ＝A ⨯C ，故<x, z>∈A ⨯B, 则有z ∈B所以 C ⊆B故得A ＝B2．试证明：若R 与S 是集合A 上的自反关系，则R ∩S 也是集合A 上的自反关系．证明：R 和S 是自反的，∀x ∈A, <x,x>∈R, <x,x>∈S则<x, x>∈R ⋂S所以R ⋂S 是自反的3．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．4．试证明 (P →(Q ∨⌝R ))∧⌝P ∧Q 与⌝ (P ∨⌝Q )等价．5．试证明：⌝(A ∧⌝B )∧(⌝B ∨C )∧⌝C ⇒⌝A ．以上为离散数学形成性考核作业4作业与答案，请教师指正。

2016年秋国家开放大学《离散数学》形考4试题及答案(答案全部正确)０4任务_0001试卷总分:1００测试时间:0单项选择题一、单项选择题(共１0 道试题，共10０分。

)1．无向树T有8个结点，则T的边数为（)．A. ６Ｂ. 7 C. 8 Ｄ. 92．图G如图三所示，以下说法正确的是（).Ａ．{(a，ｄ)}是割边Ｂ．{(a, d)}是边割集Ｃ. ｛(a, d) ,(b, d）｝是边割集 D. {(ｂ, d）}是边割集3. 设有向图(a）、(b)、(ｃ)与（ｄ）如图所示,则下列结论成立的是（ )．A. （ａ)只是弱连通的B. （ｂ)只是弱连通的C. （ｃ）只是弱连通的Ｄ． (d）只是弱连通的４．如图一所示，以下说法正确的是（).A. {(ａ, e)｝是割边B. ｛(a,e)}是边割集Ｃ. ｛(a, e）,(b，ｃ)}是边割集 D. {(d，e)}是边割集5. 设G是有ｎ个结点,ｍ条边的连通图，必须删去G的(）条边,才能确定G的一棵生成树．Ａ. m－ｎ+1Ｂ． m-n C. m＋n+1D． n-m+1６. 设G是连通平面图,有v个结点,ｅ条边，r个面，则r= ().A. e－v+2Ｂ. ｖ+ｅ－2 C. ｅ-v－2D．e+v＋27. 设无向图G的邻接矩阵为，则G的边数为（）.A．６ B. 5Ｃ．４ D. 38．如图所示，以下说法正确的是 ( )．A. ｅ是割点B. {a，ｅ}是点割集C．｛ｂ, e}是点割集D．｛d}是点割集9. 无向简单图Ｇ是棵树，当且仅当（).A. Ｇ连通且边数比结点数少１B. G连通且结点数比边数少1C. G的边数比结点数少１D. Ｇ中没有回路．10．以下结论正确的是( ).Ａ. 无向完全图都是欧拉图 B. 有n个结点n-1条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边0４任务＿０002试卷总分:１00 测试时间：0单项选择题一、单项选择题（共10 道试题，共1０0 分。

★ 形成性考核 作业 ★离散数学作业4姓 名： 学 号： 得 分：教师签名：离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3 次，内容主要分别是集合论部分、 图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业， 使同学自己检验学习成果， 找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要 认真及时地完成图论部分的综合练习作业．要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2. 在线提交 word 文档3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题1．已知图 G 中有 1个 1度结点，2个 2度结点，3个 3度结点，4个 4度结点，则 G 的边数是15．2．设给定图 G(如右由图所示 )，则图 G 的点割集是 {f,c}．3．设 G 是一个图，结点集合为 V ，边集合为 E ，则 G 的结点度数之和等于边数的两倍．4．无向图 G 存在欧拉回路， 当且仅当 G 连通且所有结点的度数全为偶数 ． 5．设 G= <V ，E>是具有 n 个结点的简单图，若在 G 中每一对结点度数之和 大于等于n-1，则在 G 中存在一条汉密尔顿路．6．若图 G=<V , E> 中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S ，在 G 中删除 S 中的所有结点得到的连通分支数为W ，则 S 中结点数 |S| 与 W 满足的关系式为 W ≤∣ S ∣ ．．设完全图K n有 n 个结点 (n 2)，m 条边，当 n 为奇数 时， K n中存在欧 7拉回路．8．结点数 v 与边数 e 满足e= v － 1关系的无向连通图就是树．9．设图 G 是有 6 个结点的连通图，结点的总度数为18，则可从 G 中删去4条边后使之变成树．1★ 形成性考核作业★10．设正则 5 叉树的树叶数为17，则分支数为 i = 4 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图 G 是无向图，且其结点度数均为偶数，则图 G 存在一条欧拉回路．答：不正确，图G 是无向图，当且仅当G 是连通，且所有结点度数均为偶数，这里不能确定图G 是否是连通的。

2021年国家开放大学《离散数学（本）》形考任务（1-4）试题及答案解析形考任务1（正确答案解析附题目之后）单项选择题题目1正确获得5.00分中的5.00分未标记标记题目题干设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )．选择一项：A. 无、2、无、2B. 8、2、8、2C. 8、1、6、1D. 6、2、6、2反馈你的回答正确正确答案是：无、2、无、2题目2正确获得5.00分中的5.00分未标记标记题目题干设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．选择一项：A. 自反和传递B. 传递C. 自反D. 对称反馈你的回答正确正确答案是：对称题目3正确获得5.00分中的5.00分未标记标记题目题干若集合A的元素个数为10，则其幂集的元素个数为（）．选择一项：A. 1024B. 1C. 100D. 10反馈你的回答正确正确答案是：1024题目4正确获得5.00分中的5.00分未标记标记题目题干设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）．选择一项：A. 最大下界B. 下界C. 最小元D. 最小上界反馈你的回答正确正确答案是：最小上界题目5正确获得5.00分中的5.00分未标记标记题目题干设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )．选择一项：A. {4, 5, 6, 7}B. {1, 2, 3, 5}C. {2, 3, 4, 5}D. {1, 2, 3, 4}反馈你的回答正确正确答案是：{1, 2, 3, 4}题目6正确获得5.00分中的5.00分未标记标记题目题干设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．选择一项：A. 极大元B. 最大元C. 最小元D. 极小元反馈你的回答正确正确答案是：极大元题目7正确获得5.00分中的5.00分未标记标记题目题干设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）．选择一项：A. g◦gB. g◦fC. f◦fD. f◦g反馈你的回答正确正确答案是：f◦g题目8正确获得5.00分中的5.00分未标记标记题目题干设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的关系R={<x, y>| y = x +1｝，则R= ( )．选择一项：A. {<2, 2>, <3, 3>, <4, 6>}B. {<2, 1>, <4, 3>, <6, 5>}C. {<2, 3>, <4, 5>, <6, 7>}D. {<2, 1>, <3, 2>, <4, 3>}反馈你的回答正确正确答案是：{<2, 3>, <4, 5>, <6, 7>}题目9正确获得5.00分中的5.00分未标记标记题目题干集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, yA}，则R的性质为（）．选择一项：A. 反自反B. 不是对称的C. 传递的D. 不是自反的反馈你的回答正确正确答案是：传递的题目10正确获得5.00分中的5.00分未标记标记题目题干集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, yA}，则R的性质为（）．选择一项：A. 传递且对称的B. 反自反且传递的C. 自反的D. 对称的反馈你的回答正确正确答案是：对称的未标记标记题目信息文本判断题题目11正确获得5.00分中的5.00分未标记标记题目题干空集的幂集是空集．（）选择一项：对错反馈正确的答案是“错”。

离散数学课后习题答案第四章离散数学课后习题答案第四章第⼗章部分课后习题参考答案4．判断下列集合对所给的⼆元运算是否封闭：（1）整数集合Z 和普通的减法运算。

封闭,不满⾜交换律和结合律，⽆零元和单位元（2）⾮零整数集合普通的除法运算。

不封闭（3）全体n n ?实矩阵集合（R ）和矩阵加法及乘法运算，其中n2。

封闭均满⾜交换律，结合律，乘法对加法满⾜分配律；加法单位元是零矩阵，⽆零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。

不封闭（5）正实数集合和运算，其中运算定义为：不封闭因为 +?-=--?=R 1111111ο（6）n关于普通的加法和乘法运算。

封闭，均满⾜交换律，结合律，乘法对加法满⾜分配律加法单位元是0，⽆零元；乘法⽆单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n运算定义如下：封闭不满⾜交换律，满⾜结合律，（8）S =关于普通的加法和乘法运算。

封闭均满⾜交换律，结合律，乘法对加法满⾜分配律（9）S = {0,1},S 是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满⾜交换律，结合律（10）S = ,S 关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满⾜交换律，结合律10．令S={a ，b}，S 上有四个运算：*，分别有表10.8确定。

(a) (b) (c) (d)(1)这4个运算中哪些运算满⾜交换律，结合律，幂等律？(a) 交换律，结合律，幂等律都满⾜，零元为a,没有单位元； (b)满⾜交换律和结合律，不满⾜幂等律，单位元为a,没有零元b b a a ==--11,(c)满⾜交换律,不满⾜幂等律,不满⾜结合律 a b a b b a b a a b b a ====οοοοοο)(,)(b b a b b a οοοο)()(≠ 没有单位元, 没有零元(d) 不满⾜交换律，满⾜结合律和幂等律没有单位元, 没有零元 (1) 求每个运算的单位元，零元以及每⼀个可逆元素的逆元。

离散数学（第五版）清华大学出版社第4章习题解答4．1 A：⑤；B：③；C：①；D：⑧；E：⑩4．2 A：②；B：③；C：⑤；D：⑩；E：⑦4．3 A：②；B：⑦；C：⑤；D：⑧；E：④分析题4.1-4.3 都涉及到关系的表示。

先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题4.1中的Is ={<1,1>,<2,2>}, Es ={<1,1>,<1,2>,<2,1>,<2,2>}Is ={<1,1>,<1,2>,<2,2>};而题4.2中的R={<1,1>,<1,4>,<2,1>,<3,4>,<4,1>}.为得到题4.3中的R须求解方程x+3y=12，最终得到R={<3,3>,<6,2>,<9,1>}.求RoR有三种方法，即集合表达式、关系矩阵和关系图的主法。

下面由题4.2的关系分别加以说明。

1°集合表达式法将domR,domRUran,ranR的元素列出来，如图4.3所示。

然后检查R的每个有序对，若<x,y>∈R，则从domR中的x到ranR中的y画一个箭头。

若danR中的x 经过2步有向路径到达ranR中的y，则<x,y>∈RoR。

由图4.3可知RoR={<1,1>,<1,4><4,1>,<4,4>,<2,1>,<2,4>,<3,1>}.如果求FoG，则将对应于G中的有序对的箭头画在左边，而将对应于F中的有序对的箭头画在右边。

对应的三个集合分别为domG,ranUdomF,ranF，然后，同样地寻找domG到ranF的2步长的有向路径即可。

2° 矩阵方法若M是R的关系矩阵，则RoR的关系矩阵就是M·M，也可记作M，在计算2 48乘积时的相加不是普通加法，而是逻辑加，即0+0=0，0+1=1+0=1+1=1，根据已知条件得⎡1 0 0 1⎤⎡1 0 0 1⎤⎡1 0 0 1⎤⎢1 0 0 0⎥⎢1 0 0 0⎥⎢1 0 0 1⎥2 ⎢⎥⎢⎥⎢⎥M =⎢⎥⋅⎢⎥=⎢⎥⎢0 0 0 1⎥⎢0 0 0 1⎥⎢1 0 0 0⎥⎣1 0 0 0⎦⎣1 0 0 0⎦⎣1 0 0 1⎦M2中含有7个1，说明RoR中含有7个有序对。

离散数学章节练习4K E Y(总5页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除离散数学 章节练习 4范围：代数系统一、单项选择题 1. <G,*>是群，则对* ( A ) A 、有单位元，可结合 B 、满足结合律、交换律 C 、有单位元、可交换 D 、有逆元、可交换2. 设N 和Z 分别表示自然数和整数集合，则对减法运算封闭的是 ( B )A 、NB 、{x ÷2|x ∈Z}C 、{x|x ∈N 且x 是素数}D 、{2x+1| x ∈Z }3. 设Z 为整数集，A 为集合，A 的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是群的代数系统的有 ( B ) A.〈Z ，+，÷〉 B.〈Z ，÷〉 C.〈Z ，－，÷〉 D.〈P(A)，⋂〉 4. 设S={0，1}，*为普通乘法，则< S , * >是 ( B ) A 、半群，但不是独异点； B 、只是独异点，但不是群； C 、群； D 、环，但不是群。

5. 设f 是由群<G,☆>到群<G ',*>的同态映射，则ker (f)是 ( B ) A 、G '的子群 B 、G 的子群 C 、包含G ' D 、包含G 6. 在整数集Z 上,下列哪种运算不是封闭的 ( C ) A + B - C ÷ D X 7. 设S={0，1}，*为普通乘法，则< S , * >是 ( B )A 、半群，但不是独异点；B 、只是独异点，但不是群；C 、群；D 、环，但不是群。

8. 设R 是实数集合，“⨯”为普通乘法，则代数系统<R ，×> 是（ A ）。

A ．群； B ．环； C ．半群 Ｄ.都不是 9. 设︒是集合S 上的二元运算，如果集合S 中的某元素eL,对∀x ∈S 都有 eL ︒x=x ,则称eL 为 ( C ) A 、右单位元 B 、右零元 C 、左单位元 D 、左零元 10. <Z,+> 整数集上的加法系统中0是 ( A ) A 单位元 B 逆元 C 零元 D 陪集 11. 若V=<S,︒>是半群，则它具有下列那些性质 ( A ) A 、封闭性、结合性 B 、封闭性、交换性 C 、有单位元 D 、有零元 二、判断题 1．若半群<S,*>含有零元，则称为独异点。

第四章习题1．对于下列各种情况求从X 到Y 的关系S 的各元素。

（1）X={0.1.2}. Y={0.2.4}. }.|.{Y X y x y x S ∈><= (2) X={1.2.3.4} Y={1.2.3} }|.{2y x y x S =><= 解：（1） }.|,{Y X y x y x S ∈><= ={<0.0>,<0.2>,<2.0>,<2.2>}(2) }2.4,1.1{}|.{2><><==><=y x y x S2.设集合S 及其关系R 如下给定，试问关系R 具有哪些性质？ （1）S 为正整数集，R={><y x .|y x +为偶数} （2）S 为整数集，R={<y x .>|x-y 被7整除}（3）S 为四维实欧式空间>><><<>><><<44332211,,,,,,y x y x R y x y x 当且仅当))(())((12343412x x y y x x y y --=--解：（1）1°自反性；S x ∈∀均为x x +为偶数，即R x x >∈<.。

2°对称性；若R y x >∈<.，则y x +为偶数，所以x y +也是偶数，那R x y >∈<,。

3°传递性；若R y x >∈<.且R z y >∈<,则y x +及z y +均为偶数，从而y z x z y y x 2)()(++=+++为偶数，因此 y x +必为偶数，即R z x ∈,。

⑵ 1°自反性：S x ∈∀，有0=-x x 能被7整除，即R x x ∈,。

2°对称性：若R y x ∈,，则y x -被7整除，从而x y -也能被7整除，即R x y ∈, 3°传递性：若R y x ∈,且R z y ∈,，则y x -及z y -被7整除，从而()()z y y x z x -+-=-也能被7整除，即R z x ∈,。

离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q ∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p →（11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→15、设p ：2+3=5.q ：大熊猫产在中国.r ：太阳从西方升起.求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→解：p=1，q=1，r=0， ()(110)1p q r ∧∧⌝⇔∧∧⌝⇔，(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型：（2）()p p q →⌝→⌝解：列出公式的真值表，如下所示：20、求下列公式的成真赋值：（4）()p q q ⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒00p q ⇔⎧⎨⇔⎩ 所以公式的成真赋值有：01，10，11。

习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式，所以成真赋值为011，111。

*6、求下列公式的主合取范式，并求成假赋值：（2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式，所以成假赋值为100。

离散数学图论部分形成性考核书面作业4答案离散数学作业4离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f} ．3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍．4．无向图G 存在欧拉回路，当且仅当G 连通且 等于出度 ． 5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W(G-V1) ≤∣V 1∣ ．7．设完全图K n 有n 个结点(n ≥2)，m 条边，当 n 为奇数 时，K n中存在欧拉回路．8．结点数v 与边数e 满足 e=v-1 关系的无向连通图就是树．姓 名： 学 号： 得 分： 教师签名：4．设G是一个有7个结点16条边的连通图，则G为平面图．解：(1) 错误假设图G是连通的平面图，根据定理，结点数v，边数为e，应满足e小于等于3v-6，但现在16小于等于3*7-6，显示不成立。

所以假设错误。

5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．(2) 正确根据欧拉定理，有v-e+r=2，边数v=11，结点数e=6，代入公式求出面数r=7三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．解：(1)οοοοvοv vv v(2) 邻接矩阵为⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0110010110110110110000100(3) v 1结点度数为1，v 2结点度数为2，v 3结点度数为3，v 4结点度数为2，v 5结点度数为2(4) 补图图形为2．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ),(c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形； （2）写出G 的邻接矩阵； （3）求出G 权最小的生成树及其权值． （1）G 的图形如下：οο ο οv οv v vv（2）写出G的邻接矩阵（3）G权最小的生成树及其权值3．已知带权图G如右图所示．(1) 求图G的最小生成树；(2)计算该生成树的权值．解：(1) 最小生成树为(2) 该生成树的权值为(1+2+3+5+7)=184．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．12357权为 2*5+3*5+5*4+7*3+17*2+31=131四、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．35251717311362．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G 才能使其成为欧拉图．。