2016年10月自考离散数学

离散数学（本）2016年10月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A

C．{1,2,3}?A D．? ?A

2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2

5．设个体

离散数学（本）2016年10月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A

C．{1,2,3}?A D．? ?A

2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2

5．设个体

1/6 第10章

第十章 树

10.1画出所有不同构的，有5个顶点的树。

解

图10.1 习题1图

10.2 证明：一棵树的顶点度数之和为2(|V| ?1)，其中V是顶点集。

证明

一棵树的所有顶点的度数之和

?deg(v)?2|E|，因为树的|E|?|V|?1，所以

ii?1n?deg(v)?2|E|?2(|V|?1)。

ii?1n故一棵树的顶点度数之和为2(|V| ?1)。

10.3 一棵树有3个2度顶点，5个3度顶点，8个4度顶点，问有几个一度顶点？

解

设树T有n个一度顶点，则

?deg(v)=3?2?5?3?8?4?1?n?2(3?5?8?n?1)，

从而有n?23。

即该棵树有23个一度顶点。

10.4 一棵树n2个顶点的度数为2，n3个顶点的度数为3，…，nk个顶点度数为k，问有几个顶点度数为1个顶点。

解

设有n1个度数为

1

的顶点。顶点数v?n1?n2?..?.nk，边数

e?v?1?(n1?n2?..?.nk)?1。由握手定理知：

2e?2(v?1)??deg(vi)，故2(n1?n2?...?nk)?2?n1?1?n2?2?...?nk?k，

i?1n因此，n1?n3?2n4?...?(k?2)nk?2

10.5 证明：一棵树若有

离散数学

离散数学第10 章 网 络 模 型

H LP-DM

离散数学

国外计算机科学教材序列

离散数学(第6版)Richard Johnsonbaugh 石纯一 等译电子工业出版社

H LP-DM

离散数学

主题网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配

H LP-DM

离散数学

10.1 网络模型b 3 码头a 码头 5 d 2 e b 2 4 2 c 4 炼油厂z 炼油厂

求出从码头到炼油厂的最大流量H LP-DM

离散数学

定义 10.1.1一个传输网络是一个满足下列条件的简 单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容 量

H LP-DM

离散数学

例10.1.2 网络模型b 3 源a 5 d 2 e b 2 4 2 c 4 汇z

一个网络的流量是对每边赋流量值，该值不超过 一个网络的流量是对每边赋流量值， 所在边的容量。 所在边的容量。H LP-DM

离散数学

定义10.1.3 定义G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij ≤Cij

∑ Fij =∑ Fj Ii i

流入=流出 流量守恒

H LP-DM

离散数学

10.1.4b3,2

2,2 b 2,1

c 4,3

离散数学

离散数学第10 章 网 络 模 型

H LP-DM

离散数学

国外计算机科学教材序列

离散数学(第6版)Richard Johnsonbaugh 石纯一 等译电子工业出版社

H LP-DM

离散数学

主题网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配

H LP-DM

离散数学

10.1 网络模型b 3 码头a 码头 5 d 2 e b 2 4 2 c 4 炼油厂z 炼油厂

求出从码头到炼油厂的最大流量H LP-DM

离散数学

定义 10.1.1一个传输网络是一个满足下列条件的简 单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容 量

H LP-DM

离散数学

例10.1.2 网络模型b 3 源a 5 d 2 e b 2 4 2 c 4 汇z

一个网络的流量是对每边赋流量值，该值不超过 一个网络的流量是对每边赋流量值， 所在边的容量。 所在边的容量。H LP-DM

离散数学

定义10.1.3 定义G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij ≤Cij

∑ Fij =∑ Fj Ii i

流入=流出 流量守恒

H LP-DM

离散数学

10.1.4b3,2

2,2 b 2,1

c 4,3

www.4juan.com 专注于收集各类历年试卷和答案

更多试卷答案下载 免费试听网校课程

全国2006年4月高等教育自学考试

离散数学试题

课程代码：02324

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列命题公式为重言式的是（ ） A．p→ (p∨q) C．q∧┐q

2．下列语句中不是命题的只有（ ） ．．A．这个语句是假的。 C．飞碟来自地球外的星球。

B．1+1=1.0

D．凡石头都可练成金。 B．(p∨┐p)→q D．p→┐q

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是

（ ）

A．┐p∧q C．┐p→┐q

4．下列等价式正确的是（ ） A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A C．┐(?x)A?(?x)┐A

D．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)

5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ ） A．自由

★ 形成性考核作业 ★

离散数学作业5

姓 名： 学 号： 得 分： 教师签名： 离散数学图论部分形成性考核书面作业

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

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题

1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 ．

2．设给定图G(如右由图所示)，则图G的点割集是 {f,c}．

3．设G是一个图，结点集合为V，边集合为E，则 G的结点 度数之和 等于边数的两倍．

4．无向图G存在欧拉回路，当且仅当

全国2006年4月高等教育自学考试

一、单项选择题（本大题共15小题，每小题1分，共15分） 1．下列命题公式为重言式的是（ ）

A．p→ (p∨q) B．(p∨┐p)→q C．q∧┐q D．p→┐q 2．下列语句中不是命题的只有（ ） ．．

A．这个语句是假的。 B．1+1=1.0 C．飞碟来自地球外的星球。 D．凡石头都可练成金。

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是

（ ）

A．┐p∧q B．┐p→q C．┐p→┐q D．p→┐q 4．下列等价式正确的是（ ）

A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A

C．┐(?x)A?(?x)┐A D．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) 5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ ）

A．自由变元 B．约束变元

C．既是自由变元，又是约束变元

D．既不是自由变元，又不是约束变元

6．设A={1，2，3}，A上二元关

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d

离散数学（本）2015年7月份试题

一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1, 2, 3 }?A B．A ? {1, 2 }

C．{1, 2, 3 }?A D．{1, 2}?A

2．已知无向图G 有10条边，则G的结点度数之和为（ ）． A．10 B．20 C．30 D．5

3．无向图G是棵树，边数为10，则G的结点数是（ ）． A． 5 B． 10 C． 9 D． 11

4．设A（x）：x是金属，B（x）：x是金子，则命题“有的金属是金子”可符号化为（ ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x) →B(x)) C．(?x)(A(x)∧B(x))