离散数学图论部分形成性考核书面作业

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

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

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年11月7日前完成并上交任课教师（不收电子稿）。

并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。

一、填空题1．设集合{1,2,3},{1,2}==，则P(A)-P(B )= {{3}，{1,3}，{2,3}，A B{1,2,3}} ，A⨯ B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，∈R⋂x∈>y且=且∈<{B,,xAyAyBx}则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=<>∈x,,x,2{ByA那么R－1＝{<6,3>,<8,4>}5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是没有任何性质．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素{<c,b>,<d,c>}，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1,1>,<2,2>} ．9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1,1>,<2,2>,<3,3> 等元素．10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是{<1, a >, <2, b >}或{<1, b >, <2, a >} ．二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则(1) R是自反的关系；(2) R是对称的关系．（1）错误。

离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外)安排练习题目，目的是通过综合性书面作业,使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习,争取尽快掌握．本次形考书面作业是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业．要求:学生提交作业有以下三种方式可供选择:1. 可将此次作业用A4纸打印出来，手工书写答题,字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2。

在线提交word文档3。

自备答题纸张，将答题过程手工书写,并拍照上传．一、填空题1．命题公式的真值是1或T．2．设P:他生病了，Q：他出差了．R：我同意他不参加学习。

则命题“如果他生病或出差了,我就同意他不参加学习”符号化的结果为P∨Q→R．3．含有三个命题变项P,Q,R的命题公式P∧Q的主析取范式是（P∧Q∧┐R)∨（P∧Q∧R）4．设P(x）：x是人，Q（x）:x去上课，则命题“有人去上课．”可符号化为∃x ( P （x) ∧Q （x））．5．设个体域D＝{a，b｝,那么谓词公式消去量词后的等值式为（A（a)∨A （b））∨(B(a) ∧B（b））．6．设个体域D＝｛1，2，3｝,A(x）为“x大于3”，则谓词公式（∃x)A （x）的真值为0 ．7．谓词命题公式（∀x)((A（x）∧B（x）) ∨C(y））中的自由变元为y．8．谓词命题公式（∀x)(P（x)→Q（x)∨R（x，y)）中的约束变元为x．三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式．解：设P：今天是天晴则该语句符号化为P2．请将语句“小王去旅游，小李也去旅游．"翻译成命题公式．解:设P：小王去旅游，Q:小李也去旅游则该语句符号化为P∧Q3．请将语句“他去旅游,仅当他有时间．”翻译成命题公式．解：设P：他去旅游Q：他有时间则该语句符号化为P→Q4．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．解：命题P:41次列车下午5点开;命题Q:41次列车下午6点开；P或Q。

离散数学形成性考核作业9参考答案离散数学作业9姓名：学号：得分：教师签名：离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在09任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( B )．A．Q?P B．P?Q C．P?Q D．?P??Q2．设命题公式G：?P?(Q?R)，则使公式G取真值为1的P，Q，R赋值分别是 (D )．A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 03．下列命题公式成立的为( C )．A．?P??Q?P?Q B．?B?A ? A?B C．P ? Q ?Q D．?A? (A?B) ?B4．下列公式 ( C )为重言式．A．P?Q ??P?Q B．(B?(A?B)) ?(?A?(A?B))C．?(P?Q)??P??Q D．A??B?A?B 5．命题公式?(P?Q)的析取范式是( A )．A．P??Q B?P?Q C．?P?Q D．P??Q 6．设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为(D )．A．??x(C(x)??G(x)) B．??x(C(x)??G(x))C．??x(C(x)??G(x)) D．??x(C(x)??G(x))7．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是( B )． A．P(x, y) B．P(x, y)?Q(z) C．R(x, y) D．P(x, y)?R(x, y)8．谓词公式?xP(x)?(?x?Q(x)???xQ(x))的类型是( A )．1 / 6A．永真式 B．永假式 C．非永真的可满足式 D．蕴含式二、填空题1．命题公式P?(Q?P)的真值是 1 ．2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P∨Q)→R ．3．设A，B为任意命题公式，C为重言式，若A?C?B?C，那么A?B是言重式式(重言式、矛盾式或可满足式) ．4．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是（P∧ Q∧R）∧（P∧ Q ∧?R）．5．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”为(?χ)(PCχ)→Q(χ)) ．6．设个体域D＝{a, b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为(A(a)∨A(b))∨(B(a)∧B(b)) ．7．设个体域D＝{1, 2, 3, 4}，A(x)为“x小于3”，则谓词公式(?x)A(x) 的真值为．8．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为χ．三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式．解: 设P: 今天晴天则命题公式为P2．请将语句“如果明天天下雪，我就去市里”翻译成命题公式．解: 设P:天下雨. Q我明天去市里.则命题公式为P→Q3．请将语句“除非你去，否则我不去”翻译成命题公式．解: 设P:你去.Q我去.则命题公式为��P→��Q或Q→P2 / 64．请将语句“我去书店，仅当天不下雨”翻译成命题公式．解: 设P:我去书店. Q天不下雨则命题公式为P→Q5．请将语句“有人不去工作”翻译成谓词公式．解: 设P(χ): χ是人. Q(χ): χ去工作 .则谓词公式为(?χ)(P (χ)∧?Q(χ))6．请将语句“所有人都努力工作．”翻译成谓词公式．解: 设P(χ): χ是人. Q(χ): χ努力工作 . 则谓词公式为(?χ)(P (χ)→Q(χ))四、判断说明题（判断下列各题，并说明理由．）1．命题公式┐P∧P的真值是1．2．命题公式┐P∧（P→┐Q）∨P为永真式．答：正确┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式如果P的值为真，则┐P∧（P→┐Q）∨P为真如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真也即┐P∧（P→┐Q）∨P为真。

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

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

一、填空题1．设集合{1,2,3},{1,2}==，则P(A)-P(B )= {{3}, {1,2,3}, {1, 3 },A B{2,3}} ，A⨯B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，∈∈R⋂x∈>且=且y<{BA,,}yxAyBx则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3>．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=>x∈<,,x,2{ByA那么R－1＝{<6，3>，<8，4>}5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性，反对称性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c, b>, <d, c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>} ．9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>, <2, 2>, <3, 3> 等元素．10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是{<1, a >, <2, b >}，或{<1, b >, <2, a >}二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则(1) R是自反的关系；(2) R是对称的关系．(1) R 不是自反关系，因为没有有序对<3,3>. (2) R 不是对称关系，因为没有有序对<2,1>2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1∩R 2是自反的” 是否成立？并说明理由．解：成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2。

离散数学作业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 关系的无向连通图就是树．9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4 条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = 5 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．．姓 名： 学 号： 得 分： 教师签名：(1) 不正确，缺了一个条件，图G应该是连通图，可以找出一个反例，比如图G是一个有孤立结点的图。

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

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

要求：将此作业用a4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．已知图g中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则g的边数是 15 ．2．设给定图g(如右由图所示)，则图g的点割集是．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|．7．设完全图kn有n个结点(n?2)，m条边，当n为奇数时，kn中存在欧拉回路．8．结点数v与边数e满足-关系的无向连通图就是树． 9．设图g是有6个结点的连通图，结点的总度数为18，则可从g中删去10．设正则5叉树的树叶数为17，则分支数为i二、判断说明题（判断下列各题，并说明理由．）1．如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．错。

缺了一个条件，图g应该是连通图。

如反例，图g是一个有孤立结点的图。

2．如下图所示的图g存在一条欧拉回路．错。

图中有奇数度结点，所以不存在欧拉回路。

离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业．要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2. 在线提交word文档3. 自备答题纸张，将答题过程手工书写，并拍照上传．一、填空题1．设集合{1,2,3},{1,2}A B==，则P(A)-P(B )={{1,2},{2,3},{1,3},{1,2,3}} ，A⨯B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，R⋂y∈x=且且<>∈∈{B,,xAyAyBx}则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}yyx∈=<>∈A2,x,,xy{B那么R－1＝{<6,3>,<8,4>} ．5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c,b>,<d,c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1,1>,<2,2>} ．9．设R 是集合A 上的等价关系，且1 , 2 , 3是A 中的元素，则R 中至少包含 <1,1>,<2,2>,<3,3> 等元素．10．设A ={1，2}，B ={a ，b }，C ={3，4，5}，从A 到B 的函数f ={<1, a >, <2, b >}，从B 到C 的函数g ={< a ，4>, < b ，3>}，则Ran(g ︒ f )= {<1,a>,<2,b>}或{<1,b>,<2,a>} ．二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R ={<1, 1>，<2, 2>，<1, 2>}，则(1) R 是自反的关系； (2) R 是对称的关系．解：(1) 结论不成立．因为关系R 要成为自反的，其中缺少元素<3, 3>． (2) 结论不成立． 因为关系R 中缺少元素<2, 1>2．设A ={1，2，3}，R ={<1，1>, <2，2>, <1，2> ，<2，1>}，则R 是等价关系．解：(1) 结论不成立．因为关系R 要成为自反的，其中缺少元素<3, 3>． (2) 结论不成立．因为关系R 中缺少元素<2, 1>3．若偏序集<A ，R >的哈斯图如图一所示， 则集合A 的最大元为a ，最小元不存在． 答： 错误，按照定义，图中不存在最大元和最小元。

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

离散数学形成性考核作业（三）集合论与图论综合练习本课程形成性考核作业共4次，内容由中央电大确定、统一布置。

本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。

一、单项选择题1．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．A．{a，{ a }}∈A B．{ a }⊆AC．{2}∈A D．∅∈A2．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（）．A．{2}∈B B．{2, {2}, 3, 4}⊂BC．{2}⊂B D．{2, {2}}⊂B3．若集合A={a，b，{1，2 }}，B={1，2}，则（）．A．B⊂ A，且B∈A B．B∈ A，但B⊄AC．B ⊂ A，但B∉A D．B⊄ A，且B∉A4．设集合A = {1, a }，则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}}C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}5．设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b>⎢a , b∈A , 且a +b = 8}，则R具有的性质为（）．A．自反的B．对称的C．对称和传递的D．反自反和传递的6．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R从A到B的二元关系，R ={<a , b>⎢a∈A，b∈B且1a}=-b则R具有的性质为（）．A．自反的B．对称的C．传递的D．反自反的7．设集合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．以上都不对8．非空集合A上的二元关系R，满足( )，则称R是等价关系．A．自反性，对称性和传递性B．反自反性，对称性和传递性C．反自反性，反对称性和传递性D．自反性，反对称性和传递性9．设集合A={a, b}，则A上的二元关系R={<a, a>，<b, b>}是A上的( )关系．A ．是等价关系但不是偏序关系B ．是偏序关系但不是等价关系C ．既是等价关系又是偏序关系D ．不是等价关系也不是偏序关系10．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如右图所示,若A 的子集B = {3 , 4 , 5}，则元素3为B 的（ ）．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对11．设函数f ：R →R ，f (a ) = 2a + 1；g ：R →R ，g (a ) = a 2．则（ ）有反函数．A ．g ∙fB ．f ∙gC ．fD ．g12．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡01110010000011100000100 则G 的边数为( )．A ．5B ．6C ．3D ．413．下列数组中，能构成无向图的度数列的数组是( ) ．A ．(1, 1, 2, 3)B ．(1, 2, 3, 4, 5)C ．(2, 2, 2, 2)D ．(1, 3, 3) 14．设图G ＝<V ,E >，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(15．有向完全图D ＝<V ，E >， 则图D 的边数是( )． A ．∣E ∣(∣E ∣－1)/2 B ．∣V ∣(∣V ∣－1)/2C ．∣E ∣(∣E ∣－1)D ．∣V ∣(∣V ∣－1) 16．给定无向图G 如右图所示，下面给出的结点 集子集中，不是点割集的为（ ） A ．{b , d } B ．{d } C ．{a , c } D ．{g , e }17．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋218．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点 19．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能5 f确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 20．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 ． A ．8 B ．5 C ．4 D ． 3二、填空题1．设集合A B =={,,},{,}12312，则A ⋃B = ，A ⋂B = ，A – B = ，P (A )-P (B )= ．2．设A , B 为任意集合，命题A -B =∅的条件是 ． 3．设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ． 4．设集合A = {1，2，3，4，5，6 }，A 上的二元关系A b a b a R ∈><=,,{且1=-b a }，则R 的集合表示式为 ．5．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R 从A 到B 的二元关系， R ={<a , b >⎢a ∈A ，b ∈B 且2≤a + b ≤4}则R 的集合表示式为 ．6．设集合A ={0,1,2},B ={0,2,4},R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且 则R 的关系矩阵M R ＝．7．设集合A ={1, 2, 3, 4 }，B ={6, 8, 12}， A 到B 的二元关系R ＝},,2,{B y A x x y y x ∈∈=>< 那么R －1＝8．设集合A ={a ,b ,c }，A 上的二元关系R ={<a ,b >,<c .a >}，S ={<a ,a >,<a ,b >,<c ,c >}则(R ∙S )－1= ．9．设集合A =｛a ,b ,c ｝，A 上的二元关系R ={<a , b >, <b , a >, <b , c >, <c , d >}，则二元关系R 具有的性质是 ．10．设集合A = {1 , 2 , 3 , 4 }上的等价关系R = {<1 , 2>，<2 , 1>，<3 , 4>，<4 , 3>}⋃I A ． 那么A 中各元素的等价类为 ．11．设A ，B 为有限集，且|A |=m ，|B |=n ,那末A 与B 间存在双射，当且仅当 ．12．设集合A ={1, 2},B ={a , b }，那么集合A 到B 的双射函数是 ．13．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．14．设给定图G (如由图所示)，则图G 的点 割集是 ．15．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 ，则在G 中存在一条汉密尔顿路．16．设无向图G ＝<V ,E >是哈密顿图，则V 的任意非空子集V 1，都有 ≤∣V 1∣．17．设有向图D 为欧拉图，则图D 中每个结点的入度 ． 18．设完全图K n 有n 个结点(n ≥2)，m 条边，当 时，K n 中存在欧拉回路． 19．图G （如右图所示）带权图中最小生成树的权是20．连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ．三、判断说明题1．设A 、B 、C 为任意的三个集合，如果A ∪B =A ∪C ，判断结论B =C 是否成立？并说明理由．2．如果R 1和R 2是A 上的自反关系，判断结论：“R -11、R 1∪R 2、R 1⋂R 2是自反的” 是否成立？并说明理由．3．设R ，S 是集合A 上传递的关系，判断 R ⋃S 是否具有传递性，并说明理由．bc d4．若偏序集<A ，R >的哈斯图如右图所示，则 集合A 的最小元为1，最大元不存在．5．若偏序集<A ，R >的哈斯图如右图所示，则 集合A 的极大元为a ，f ；最大元不存在．6．图G (如右图)能否一笔画出？说明理由．若能画出，请写出一条通路或回路．7．判断下图的树是否同构？说明理由．8．给定两个图G 1，G 2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由．v 123 图Gg 图G 2 图G 1f(c )9．判别图G(如下图所示)310．在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？为什么？四、计算题1．设}4,2{=,1{=,2=E，求：,3AB=C,4,25},,1{5},},,1{4（1）(A⋂B)⋃~C；（2）P(A)－P(C)；（3）A⊕B．2．设集合A＝{a, b, c}，B={b, d, e}，求（1）B⋂A；（2）A⋃B；（3）A－B；（4）B⊕A．3．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}．（1）写出关系R的表示式；（2）画出关系R的哈斯图；（3）求出集合B的最大元、最小元．关系图如右图所示．（1）写出R的表达式；（2）写出R的关系矩阵；（3）求出R2．5．设A={0，1，2，3，4}，R={<x，y>|x∈A，y∈A且x+y<0}，S={<x，y>|x∈A，y∈A且x+y<=3}，试求R，S，R︒S，R-1，S-1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)．6．设图G=<V，E>，其中V={a1, a2, a3, a4, a5},E={<a1, a2>，<a2, a4>，<a3, a1>，<a4, a5>，<a5, a2>}（1）试给出G的图形表示；（2）求G的邻接矩阵；（3）判断图D是强连通图、单侧连通图还是弱连通图？7．设图G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }．（1）试给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数（4）画出图G的补图的图形．8．图G=<V, E>，其中V={a, b, c, d, e, f }，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) }，对应边的权值依次为5，2，1，2，6，1，9，3及8．（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．（1）求图G的最小生成树；（2）计算该生成树的权值．10．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树；（2）计算它们的权值．五、证明题1．试证明集合等式：A⋃ (B⋂C)=(A⋃B) ⋂ (A⋃C)．2．证明对任意集合A，B，C，有C=⨯⋂⋂⨯)(．CAA⨯BAB3．设R是集合A上的对称关系和传递关系，试证明：若对任意a∈A，存在b∈A，使得<a, b>∈R，则R是等价关系．4．若非空集合A 上的二元关系R 和S 是偏序关系，试证明：S R 也是A 上的偏序关系．5．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．6．设G 是连通简单平面图，则它一定有一个度数不超过5的结点．（提示：用反证法）7．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．8．证明任何非平凡树至少有2片树叶．。

离散数学形成性考核作业〔三〕集合论与图论综合练习本课程形成性考核作业共4次，内容由中心电大确定、统一布置。

本次形考作业是第三次作业，大伙儿要认真及时地完成图论局部的形考作业，字迹工整，抄写题目，解答题有解答过程。

一、单项选择题1．假设集合A ＝{2，a ，{a }，4}，那么以下表述正确的选项是(B)． A ．{a ，{a }}∈A B ．{a }⊆A C ．{2}∈A D ．∅∈A2．设B ={{2},3,4,2}，那么以下命题中错误的选项是〔B 〕．A ．{2}∈B B ．{2,{2},3,4}⊂BC ．{2}⊂BD ．{2,{2}}⊂B3．假设集合A ={a ，b ，{1，2}}，B ={1，2}，那么〔B 〕． A ．B ⊂A ，且B ∈A B ．B ∈A ，但B ⊄A C ．B ⊂A ，但B ∉A D ．B ⊄A ，且B ∉A4．设集合A ={1,a }，那么P (A )=(C)． A ．{{1},{a }}B ．{∅,{1},{a }}C ．{∅,{1},{a },{1,a }}D ．{{1},{a },{1,a }}5．设集合A ={1，2，3，4，5，6}上的二元关系R ={<a ,b >⎢a ,b ∈A ,且a +b =8}，那么R 具有的性质为〔B 〕． A ．自反的B ．对称的C ．对称和传递的D ．反自反和传递的6．设集合A ={1，2，3，4，5}，B ={1，2，3}，R 从A 到B 的二元关系，R ={<a ,b >⎢a ∈A ，b ∈B 且1=-b a } 那么R 具有的性质为〔〕．A ．自反的B ．对称的C ．传递的D ．反自反的[注重]：此题有误！自反性、反自反性、对称性、反对称性以及传递性指 某一个集合上的二元关系的性质。

7．设集合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 的〔C 〕闭包．A ．自反B ．传递C ．对称D ．以上都不对8．非空集合A 上的二元关系R ，满足(A)，那么称R 是等价关系． A ．自反性，对称性和传递性B ．反自反性，对称性和传递性 C ．反自反性，反对称性和传递性 D ．自反性，反对称性和传递性9．设集合A ={a ,b }，那么A 上的二元关系R={<a ,a >，<b ,b >}是A 上的(C)关系．A ．是等价关系但不是偏序关系B ．是偏序关系但不是等价关系C ．既是等价关系又是偏序关系D ．不是等价关系也不是偏序关系10．设集合A ={1,2,3,4,5}上的偏序关系的哈斯图如右图所示,假设A 的子集B ={3,4,5}， 那么元素3为B 的〔C 〕．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对11．设函数f ：R →R ，f (a )=2a +1；g ：R →R ，g (a )=a 2．那么〔C 〕有反函数． A ．g •f B ．f •g C ．f D ．g12．设图G 的邻接矩阵为 那么G 的边数为(D)． A ．5B ．6C ．3D ．413．以下数组中，能构成无向图的度数列的数组是(C)． A ．(1,1,2,3)B ．(1,2,3,4,5)C ．(2,2,2,2)D ．(1,3,3) 14．设图G ＝<V ,E >，那么以下结论成立的是(C)． A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v Vv 2)deg(=∑∈D ．E v Vv =∑∈)deg(解；C 为握手定理。

离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业．要求：将此作业用A4纸打印出来，并在03任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）．一、填空题1．设集合{1,2,3},{1,2}==，则P(A)-P(B )= {{3}, {1,2,3}, {1, 3 },A B{2,3}} ，A⨯B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，∈∈R⋂x=且且y<>∈B{B,,}xAAyyx则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3>4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}x∈yy∈=,>x<2,x,{BAy那么R－1＝{<6，3>，<8，4>}5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性，反对称性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c, b>, <d, c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x∈A，y∈A, x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>} ．9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>, <2, 2>, <3, 3> 等元素．10．设A={1，2}，B={a，b}，C={3，4，5}，从A到B的函数f ={<1, a>, <2,b>}，从B到C的函数g={< a，4>, < b，3>}，则Ran(g︒ f二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则(1) R是自反的关系；(2) R是对称的关系．解：（1）错误，R不是自反关系，因为没有有序对<3,3>.（2）错误，R不是对称关系，因为没有有序对<2,1>2．设A={1，2，3}，R={<1，1>, <2，2>, <1，2> ，<2，1>}，则R是等价关系．解：错误, 即R不是等价关系.因为等价关系要求有自反性x R x, 但<3, 3>不在R中.3．若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．解：错误．集合A的最大元不存在，a是极大元．οοοοab cd图一οοοg e fh ο4．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判断下列关系f是否构成函数f：A→，并说明理由．B(1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}；(2) f={<1, 6>, <3, 4>, <2, 2>}；(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．解：(1) f不能构成函数．因为A中的元素3在f中没有出现．(2) f不能构成函数．因为A中的元素4在f中没有出现．(3) f可以构成函数．因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件．三、计算题1．设}4,2{==CE，求：AB=5,4,3,2,1{=},},5,2,1{},4,1{(1) (A⋂B)⋃~C；(2) (A⋃B)-(B⋂A) (3) P(A)－P(C)；(4) A⊕B．解：(1)因为A∩B=｛1,4｝∩｛1,2,5｝=｛1｝,~C=｛1,2,3,4,5｝-｛2,4｝=｛1,3,5｝所以(A∩B ) ⋃~C=｛1｝⋃｛1,3,5｝=｛1,3,5｝（2）(A⋃B)-(B⋂A)= {1,2,4,5}-{1}={2,4,5}(3)因为P(A)=｛φ,｛1｝, ｛4｝, ｛1,4｝｝P(C)=｛φ,｛2｝,｛4｝,｛2,4｝｝所以P(A)-P(C)={ φ,{ 1},{ 4},{ 1,4}}-{φ,{ 2},{ 4},{2,4 }}(4) 因为A⋃B={ 1,2,4,5}, A⋂B={ 1}所以A⊕B=A⋃B-A⋂B={1,2,4,5}-{1}={2,4,5}2．设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}>}3．设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>}, \R-1={<1,1>,<2,1>,<3,1>,<1,2 >,<2,2>,<1, 3>}S=φ, 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>}R∙S=φS∙R=φ4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}．(1) 写出关系R的表示式；(2 )画出关系R的哈斯图；(3) 求出集合B的最大元、最小元．解：R={<1,1>,<1,2>,<1,3>,<1,4,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8> ,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>}（2）关系R的哈斯图如图四（3）集合B没有最大元，最小元是：2四、证明题1．试证明集合等式：A⋃ (B⋂C)=(A⋃B) ⋂ (A⋃C)．证明：设，若x∈A⋃ (B⋂C)，则x∈A或x∈B⋂C，即x∈A或x∈B且x∈A或x∈C．即x∈A⋃B且x∈A⋃C，即x∈T=(A⋃B) ⋂ (A⋃C)，所以A⋃ (B⋂C)⊆ (A⋃B) ⋂ (A⋃C)．反之，若x∈(A⋃B) ⋂ (A⋃C)，则x∈A⋃B且x∈A⋃C，即x∈A或x∈B且x∈A或x∈C，7即x∈A或x∈B⋂C，即x∈A⋃ (B⋂C)，所以(A⋃B) ⋂ (A⋃C)⊆ A⋃ (B⋂C)．因此．A⋃ (B⋂C)=(A⋃B) ⋂ (A⋃C)．2．试证明集合等式A⋂ (B⋃C)=(A⋂B) ⋃ (A⋂C)．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，则x∈A且x∈B∪C，即x∈A且x∈B或x∈A且x∈C，也即x∈A∩B或x∈A∩C，即x∈T，所以S⊆T．反之，若x∈T，则x∈A∩B或x∈A∩C，即x∈A且x∈B 或x∈A且x∈C也即x∈A且x∈B∪C，即x∈S，所以T⊆S．因此T=S．3．对任意三个集合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．故得B=C．4．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：R1和R2是自反的，∀x∈A，<x, x> ∈R1，<x, x> ∈R2，则<x, x> ∈R1∩R2，所以R1∩R2是自反的．。

离散数学作业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) V1．有n个结点(n2)，m条边，当n为奇数时，7．设完全图KnK中存在欧拉回路．n8．结点数v与边数e满足e=v-1 关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = 5 ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(1) 不正确，缺了一个条件，图G应该是连通图，可以找出一个反例，比如图G是一个有孤立结点的图。

2．如下图所示的图G存在一条欧拉回路．(2) 不正确，图中有奇数度结点，所以不存在是欧拉回路。

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

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

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 ．2．设给定图G(如右由图所示)，则图G的点割集是．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 7．设完全图Kn有n个结点(n≥3)，m条边，当 n为奇数时，Kn中存在欧拉回路． 8．结点数v与边数e满足9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 10．设正则5叉树的树叶数为17，则分支数为i二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．★形成性考核作业★解错误．只有当G是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路．2．如下图所示的图G存在一条欧拉回路．解错误．因为图G是有两个结点b、c的度数均为奇数3，不是偶数，所以不存在欧拉回路．3．如下图所示的图G不是欧拉图而是汉密尔顿图．解正确． G图G有4个3度结点a，b，d，f，所以图G不是欧拉图．图G有汉密尔顿回路abefgdca，所以图G是汉密尔顿图．4．设G是一个有7个结点16条边的连通图，则G为平面图．解错误．因为图G中 v=7, 3v-6=15, e=16>15，不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6.”这个定理，所以不是平面图．5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．解正确．因为连通平面图G有v=6个结点，e=11条边，那么由欧拉公式：v-e+r=2计算得：r =2+ 11- 6 = 7个面．三、计算题 2★形成性考核作业★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）G的图形为：（2）图G的邻接矩阵为：⎛0 0A= 1 00⎝0100⎫⎪0110⎪1011⎪⎪1101⎪0110⎪⎭（3）图G的每个结点的度数为：deg(v1)=1，deg(v2)=2，deg(v3)=4，deg(v4)=3，deg(v5)=2．（4）图G的补图为：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的图形表示如图3：★形成性考核作业★图3（2）邻接矩阵：⎡0⎢1⎢A(G)=⎢1⎢⎢0⎢⎣11101⎤0011⎥⎥0011⎥⎥1101⎥1110⎥⎦（3）粗线表示最小的生成树，如图4图4最小的生成树的权为：1+1+2+3=7.3．已知带权图G如右图所示．(1) 求图G的最小生成树； (2)计算该生成树的权值．解（1）图G有6个结点，其生成树有5条边，用Kruskal 算法求其权最小的生成树T，做法如下：①选边1；②选边2；③选边3；④选边5；⑤选边7最小生成树为{1,2,3,5,7}．所求最小生成树T如右图．（2）该最小生成树的权为W(T)=1+2+3+5+7=18．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优 4★形成性考核作业★二叉树的权．解方法（Huffman算法）：（1）｛2，3，5，7，17，31｝（2）｛5，5，7，17，31｝（3）｛7，10，17，31｝（4）｛17，17，31｝（5）｛｝得最优二叉树，如图6所示.该最优二叉树的权为：(2+3)×5+5×4+7×3+17×2+31×1=131.四、证明题1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．证明设G=<V,E>，G=<V,E'>．则E'是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u∈V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n-1 (≥2)度），于是若u∈V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．证明由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． k故最少要加条边到图G才能使其成为欧拉图． 2k条边才能2。

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

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

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题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 ?|S|．7．设完全图K n 有n 个结点(n ?2)，m 条边，当n 为奇数时，K n 中存在欧拉回路．8．结点数v 与边数e 满足e=v -1关系的无向连通图就是树．9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i =5．二、判断说明题（判断下列各题，并说明理由．）1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．． 错。