下载文档原格式
离散数学（本）一、单项选择题1.集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, yA}，则R的性质为（）．A.自反的B.对称的C.传递且对称的D.反自反且传递的正确答案: B2.如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A.0B.2C.1D.3正确答案: B3.设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )．A.{1, 2, 3, 4}B.{1, 2, 3, 5}C.{2, 3, 4, 5}D.{4, 5, 6, 7}正确答案: A4.若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是（）．A.{a，{a}}AB.{1，2}AC.{a}AD.A正确答案: C5.若集合A的元素个数为10，则其幂集的元素个数为（）．A.1024B.10C.100D.1正确答案: A6.设函数f：N→N，f(n)=n+1，下列表述正确的是（）．A.f存在反函数B.f是双射的C.f是满射的D.f是单射函数正确答案: D7.设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）．A.下界B.最小上界C.最大下界D.最小元正确答案: B8.设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．A.最大元B.最小元C.极大元D.极小元正确答案: C9.设集合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.自反和传递正确答案: C10.集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, yA}，则R的性质为（）．A.不是自反的B.不是对称的C.传递的D.反自反正确答案: C11.图G如图三所示，以下说法正确的是 ( )．A.a是割点B.{b,c}是点割集C.{b, d}是点割集D.{c}是点割集正确答案: B12.设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A.e－v＋2B.v＋e－2C.e－v－2D.e＋v＋2正确答案: A13.图G如图四所示，以下说法正确的是 ( ) ．A.{(a, d)}是割边B.{(a, d)}是边割集C.{(a, d) ,(b, d)}是边割集D.{(b, d)}是边割集正确答案: C14.设无向图G的邻接矩阵为，则G的边数为( )．A.6B.5C.4D.3正确答案: B15.无向图G存在欧拉回路，当且仅当（）．A.G中所有结点的度数全为偶数B.G中至多有两个奇数度结点C.G连通且所有结点的度数全为偶数D.G连通且至多有两个奇数度结点正确答案: C16.无向完全图K4是（）．A.欧拉图B.汉密尔顿图C.非平面图D.树正确答案: B17.无向树T有8个结点，则T的边数为( )．A.6B.7C.8D.9正确答案: B18.若G是一个汉密尔顿图，则G一定是( )．A.平面图B.对偶图C.欧拉图D.连通图正确答案: D19.若G是一个欧拉图，则G一定是( )．A.平面图B.汉密尔顿图C.连通图D.对偶图正确答案: C20.设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．图五A.（a）是强连通的B.（b）是强连通的C.（c）是强连通的D.（d）是强连通的正确答案: A21.命题公式为( )A.矛盾式B.可满足式C.重言式D.合取范式正确答案: B22.设个体域为整数集，则公式的解释可为( )．A.存在一整数x有整数y满足x+y=0B.任一整数x对任意整数y满足x+y=0C.对任一整数x存在整数y满足x+y=0D.存在一整数x对任意整数y满足x+y=0正确答案: C23.设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别是 ( )．A.0, 0, 0B.0, 0, 1C.0, 1, 0D.1, 0, 0正确答案: D24.设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．A.B.C.D.正确答案: D25.下列公式 ( )为重言式．A.┐P∧┐Q↔P∨QB.(Q→(P∨Q)) ↔(┐Q∧(P∨Q))C.Q→(P∨(P∧Q))↔Q →PD.(┐P∨(P∧Q)) ↔Q正确答案: C26.下列等价公式成立的为( )．A.┐P∧P┐Q∧QB.┐Q→P P→QC.P∧Q P∨QD.┐P∨P Q正确答案: A27.谓词公式(x)(A(x)→B(x)∨C(x，y))中的（）。
第十五章欧拉图与哈密顿图15」欧拉图—、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义務定义15・1通过图（无向图或有向图）中所有边一次jl仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。
从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。
在这里做个规定，即平凡图是欧拉图。
(1) ⑵图15.1在图15」所示各图中QiSSgs为（1冲的欧拉回路所以（1禺为欧拉图oCiGSGb 为（2）中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以（2 ）为半欧拉图。
（3 ）中既没有欧拉回路，也没有欧拉通路（为什么？），所以（3 ）不是欧拉图，也不是半欧拉图。
CI6C3C4为（4）图中的欧拉回路，所以（4）图为欧拉图。
（5 ） , （ 6 ）图中都既没有欧拉回路，也没有欧拉通路（为什么？）二、判别定理拓定理15・1无向图G是欧拉图当11仅当G是连通图，11 G中没有奇度顶点。
证若G是平凡图，结论显然成立，下面设G为非平凡图，设G是m条边的n阶无向图。
并设G的顶点集V ={v h v2,...,v n}.必要性。
因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，VVi,VjeV , v 都在C上，因而Vi,Vj连通，所以G为连通图。
又V Vi eV，"在C 上每出现一次获得2度，若岀现k次就获得2k度，即d(Vi)二2k ,所以G中无奇度顶点。
充分性，由于G为非平凡的连通图可知，G中边数m21.对m作归纳法。
(1) m=l时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。
(2) 设mwk(k21)时结论成立，要证明m二K+1时，结论也成立。
由G的连通性及无奇度顶点可知，&(G)、2•类似于例14.8 ,用扩大路径法可以证明G中存在长度大于或等于3的置，设C为G中一个圏，删除C上的全部边，得G的生成子图G,设G有s个连通分支G I,G‘2,...,G；,每个连通分支至多有k条边，且无奇度顶点，并且设G i与C*的公共顶点为, i=l,2，…,S ,由归纳假设可知，G I,G‘2，…,G；都是欧拉图,因而都存在欧拉回路Cl , i=l,2，…,s.最后将C还原(即将删除的边重新加上)，并从C上的某顶*点*开始行遍,每遇到% ,就行遍G'i中的欧拉回路Cl , i二1,2,…,s ,最后回到v r,得回路V「... ... ... "... "... b ... b ...Vr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路(演示这条欧拉回路)，故G为欧拉图。
离散数学欧拉图第7讲基本概念定义7.1◆通过无向图中所有边一次且仅一次行遍所有顶点的迹称为欧拉迹。
◆通过无向图中所有边一次且仅一次行遍所有顶点的闭迹称为欧拉环游。
◆具有欧拉环游的图称为欧拉图。
回忆思考哥尼斯堡七桥问题即下图是否是欧拉图的问题。
CA BD定理7.1设G是非平凡无向图，则G是欧拉图 G是连通图且G中没有奇点。
证明“”连通，显然。
因为所有的边都在欧拉环游上出现一次且仅一次，所以每个顶点的度=该顶点在欧拉环游上出现的次数的2倍。
故每个点都是偶点。
证：证明“”任一个无奇点的无向图，从任一条边开始都能长出一条闭迹。
设P 是G 中最长的闭迹，则P 是G 的欧拉环游。
（想想为什么？）故G 是欧拉图。
证：定理7.1（其中的必要性就足够了）回答了（实际上是否定）哥尼斯堡七桥问题。
CA BD推论设G 是非平凡无向图，则G有欧拉迹 G是连通图且G中至多有2个奇点。
一个图有欧拉迹，在中国古代被称为是“一笔画”的。
比如“日”可一笔画，而“田”不可一笔画。
思考上述定理给出了欧拉图的判定条件,那么如何找出欧拉环游呢?Fleury算法——一种求欧拉环游的方法(1) 任取v0∈V(G)，令P0= v0。
(2) 设P i= v0e1v1e2… e i v i已经选取，按下面方法来从E(G)-{e1,e2… e i}中选取e i+1：(a) e i+1与v i相关联；(b) 除非无别的边可供选择，否则e i+1不为G i=G-{e1,e2… e i}中的桥。
(3) 当(2)不能再进行时，算法停止。
123 456 789谢谢观看。
欧拉图交叉关系举例
欧拉图（Euler Graph）交叉关系是图论（Grap Theory）中一种重要概念，用
于构建两个节点间的连接，又名为欧拉图交叉桥。
欧拉图交叉关系结构中最重要的特征是：每个节点只能有两个边，其中一条连
接特定的另一个节点，另一条边则连接该节点的同种节点。
交叉关系的核心在于，它的结构使得节点间的联系更加充分。
欧拉图交叉关系的应用领域非常广泛，从基础设施规划（Infrastructure planning）和资源优化（Resource optimization），到社交网络（Social network）管理、视频会议（Video conferences）及地图信息（Map information）技术，都广泛使用欧拉图交叉关系技术。
在路网（Road network）分析中，欧拉图交叉关系用于构建各个节点之间的图
形拓扑，关系独立而具有层次性，可以帮助改进公路网络的管理效率。
在传输通信（Transmission communications）系统中，欧拉图交叉关系可以
为复杂的网络结构提供帮助，它具有连接性良好、可靠性高以及负载分担调节机制。
另外，欧拉图交叉关系在我们日常生活中也拥有重要应用。
例如，它可以为位
置服务（Location services）应用提供关键的网络链接，从而满足用户的位置查找、导航及定位需求。
总之，欧拉图交叉关系已经成为当今信息技术社会一个重要技术组件，它可以
有效解决许多不同行业碰撞出的现实问题，为社会带来积极的变化。
所有A都是B 所有A都不是B 有A是B 有A不是B
A B A B A B
A B
A B A B B A
A B
A B
B A
所有A都是B 所有A都不是B 有A是B 有A不是B
所有A都是B
上图的非阴影部分是否非空未作断定，如果非空，则是种属关系，否则是全同关系。
所有A都不是B
A B
有A是B
上图的非阴影部分分左右两部分。
如果两部分都空，则是全同关系；如果左不空，右空，则是属种关系；如果左空，右不空，则是种属关系；如果两部分都不空，则是交叉关系。
有A不是B
上图的非阴影部分分左右两部分。
如果左不空，右空，则是属种关系；如果左空，右不空，则是不相容关系；如果两部分都不空，则是交叉关系。
[例] 藏獒是世界上最勇猛的狗，一只壮年的藏獒能与5只狼搏斗。
所有的藏獒都对自己的主人忠心耿耿，而所有忠实于自己主人的狗也为人所珍爱。
如果以上陈述为真，以下陈述都必然为真，除了
．．：
A．有些为人所珍爱的狗不是藏獒。
B．任何不为人所珍爱的狗不是藏獒。
C．有些世界上最勇猛的狗为人所珍爱。
D．有些忠实于自己主人的狗是世界上最勇猛的狗。
答案是A
试题类型：逻辑推断
藏獒忠实人爱
为什么A不一定为真？
藏獒人爱
所有校足球队员都获得了校长特别奖。
张柯和李航都是校足球队员。
校长特别奖不授予一年级新生。
从以上断定能推出哪项结论？
I 校足球队员都不是一年级新生。
II 张柯和李航都获得了校长特别奖
III 获得校长特别奖的不都是校足球队员
校长特别奖
校足球队员一年级新生
* *
[例] 所有的灰狼都是狼。
这一断定显然是真的。
因此，所有的疑似SARS病例都是SARS病例，这一断定也是真的。
以下哪项最为恰当地指出了题干论证的漏洞？
A．题干的论证忽略了：一个命题是真的，不等于具有该命题形式的任一命题都是真的。
B．题干的论证忽略了：灰狼与狼的关系，不同于疑似SARS病例和SARS病例的关系。
C．题干的论证忽略了：在疑似SARS病例中，大部分不是SARS病例。
D．题干的论证忽略了：许多狼不是灰色的。
E．题干的论证忽略了：此种论证方式会得出其它许多明显违反事实的结论。
答案是B。
“灰狼”和“狼”是种属关系：
“疑似SARS病例”和“SARS病例”是交叉关系
1-2基于以下题干：
所有安徽来京打工人员，都办理了暂住证；所有办理了暂住证的人员，都获得了就业许可证；有些安徽来京打工人员当上了门卫；有些业余武术学校的学员也当上了门卫；所有的业余武术学校的学员都未获得就业许可证。
1．如果上述断定都是真的，则除了以下哪项，其余的断定也必定是真的？
A．所有安徽来京打工人员都获得了就业许可证。
B．没有一个业余武术学校的学员办理了暂住证。
C．有些安徽来京打工人员是业余武术学校的学员。
D．有些门卫没有就业许可证。
（答案是C）
2．以下哪个人的身份，不可能符合上述题干所作的断定？
A．一个获得了就业许可证的人，但并非是业余武术学校的学员。
B．一个获得了就业许可证的人，但没有办理暂住证。
C．一个办理了暂住证的人，但并非是安徽来京打工人员。
D．一个办理了暂住证的业余武术学校的学员。
（答案是D）
1的答案是C。
2的答案是D。
题干的条件可由下面的欧拉图刻画。
参照下图可清晰准确地解答该题。
就业证
暂住证
门卫安徽人
武校学员
■
[例] 宏达超市的所有商品都是合格产品。
有些贴有蓝箭商标的商品不是合格产品。
如果以上两个命题为真，则以下哪个命题能确定真假？
（1）贴有蓝箭商标的商品都是宏达超市的商品。
（2）贴有蓝箭商标的商品都不是宏达超市的商品。
（3）有些贴有蓝箭商标的商品是合格产品。
A．只有（1）B．只有（2）
C．只有（3）D．只有（1）和（3）
答案：A
由题干，上图表示“贴有蓝箭商标的商品”外延的圆形中，只有阴影部分确定为非空；非阴影部分是否非空未作确定，即可能空也可能非空。
因为阴影部分非空，所以（1）假。
因为非阴影部分可能空，也可能非空，因此，（2）和（3）不能确定真假。
■
[例] “男女”和“阴阳”似乎指的是同一种区分标准，但实际上，“男人和女人”区分人的性别特征，“阴柔和阳刚”区分人的行为特征。
按照“男女”的性别特征，正常人分为两个不重叠的部分；按照“阴阳”的行为特征，正常人分为两个重叠的部分。
以下哪项不可能符合题干？
A．人的性别特征不能决定人的行为特征。
B．女人的行为，不一定具有阴柔的特征。
C．男人的行为，不一定具有阳刚的特征。
D．同一个人的行为，可以既有阴柔又有阳刚的特征。
E．一个人的同一个行为，可以既有阴柔又有阳刚的特征。
答案是E。
条件1：“男女”区分人的性别。
条件2：“阴阳”区分人的行为。
人人的行为
男女阴阳
条件3：按照“阴阳”的行为特征，正常人分为两个重叠的部分。
阴柔阳刚
的人的人
题干断定，“阴柔和阳刚”区分人的行为特征，即任何一种行为，如果阴柔，就不阳刚；如果阳刚，就不阴柔。
E项显然不符合题干的上述含义。
其余各项都符合题干的含义。
例如，D项符合题干的含义。
因为题干断定，按照“阴阳”的行为特征，正常人分为两个重叠的部分。
这就是说，同一个人的行为，可以既有阴柔又有阳刚的特征。
[例]某单位组织职工游览上海世博园。
所有参观沙特馆的职工都未能参观德国馆。
凡参观沙特馆的职工也未能参观日本馆。
有些参观丹麦馆的职工参观了德国馆，有些参观丹麦馆的职工参观了日本馆，有些参观丹麦馆的职工参观了沙特馆。
如果以上陈述为真，下面哪项关于该单位职工的陈述必然为真？
A．有些参观了日本馆的职工未能参观德国馆。
B．有些参观了德国馆的职工既没有参观日本馆，也没有参观丹麦馆。
C．有些参观了丹麦馆的职工既没有参观德国馆，也没有参观日本馆。
D．所有参观丹麦馆的职工或参观了德国馆，或参观了日本馆，或参观了沙特馆。
丹注：日本和德国
沙德关系不确定
日
A．有些参观了日本馆的职工未能参观德国馆。
(不必然真)
丹日
沙德
B．有些参观了德国馆的职工既没有参观日本馆，也没有参观丹麦馆。
(不必然真)
丹日
沙德答案是C。
