离散数学09 图
第九章 图
9.1设},,,,{y x w v u V =，画出图),(E V G =，其中：
（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =
（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =
再求各个顶点的度数。
解
（1）见图9.1(a )。其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。
图9.1 习题1图
（2）见图9.1(b )。其中顶点u 的度数是1，顶点v 的度数是2，顶点x 的度数是2，顶点y
的度数是2，顶点w 的度数是3。
9.2 设G 是具有4个顶点的完全图。
（1）画出图G 。
（2）画出G 的所有互不同构的生成子图？
解
（1）如图9.2(1)所示。
图9.2(1) 习题2图
（2） 如图9.6(2)所示
﹒ ﹒ ﹒ ﹒ ﹒ ﹒
图9.2(2) 习题2图
9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。
（1）试画出五个顶点的自互补图。
（2）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。
解
（1）
(a) (b)
图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(4
1-n n 条边，因此，k n 4=或14+k 。
9.4 画出两个不同构的简单无向图。每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。
解
图9.4 习题9.4图
9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。顶点度序列是一组按大小排列的正整数。每一个数对应某一个顶点的度数。
证明
两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对
应关系，进而建立起边的对应关系。所以，任意二个同构的无向图，一定有一个同样的顶点度序列。
9.6图9.6中所给的图(a )与图(b )是否同构？为什么？
(a )
(b ) 图9.6 习题6图 解
左图9.2（a ）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b ）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。因此两图之间不存在同构映射，从而不同构。
9.7有207个人在一起欢聚。若已知每个人至少和5个人握了手，则至少有一个人不止和5个人握手。
证明
设20721,...,,v v v 代表这207个人，建立顶点集},...,,{20721v v v V =,对于其中的任意两个人)(,j i v v j i ≠，若j i v v 和握了手，则E v v j i ∈},{，得到边集E ，则有一个无向图)(E V G ，=。若每一个人仅和其余5个人握过手，则5)(=i v d ，而此时图G 的奇数度的顶点是207个，即是奇数个，产生矛盾。因此至少有一个人i v ，6)(≥i v d 。
9.8证明一个无向图的奇数度的顶点一定有偶数个。
证明
设)(E V G ，=是一个无向图。})(|{1是奇数v d V v V ∈=，})(|{2是偶数v d V v V ∈=，显然},{21V V 是V 的一个划分。所以∑∑∑∈∈∈+=21)()()(V v V v V v v d v d v d ，而2
()v V d v ∈∑是一个偶数，
所以
1()v V d v ∈∑=()v V d v ∈∑－2()v V d v ∈∑，其中||2)(E v d V
v =∑∈也是一个偶数，偶数减去偶数仍然是偶数，故
1()v V d v ∈∑是偶数。
9.9 设 δ，?分别是图)(E V G ，=中顶点的最小度数和最大度数。n |V |=，m |E |=，证明δ≤2m n
≤?。 证明
因为
∑∈=V v i i m v 2)d e g (，对任意的V v i ∈，有?≤≤)d e g (
i v δ，于是??≤≤?∑n v n i v i )deg(δ，即??≤≤?n m n 2δ，所以?≤≤
n
m 2δ。 9.10证明由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。
证明
设n v v v ,...,,21代表这)2(≥n n 个人，建立顶点集},...,,{21n v v v V =，对于其中的任意两个人)(,j i v v j i ≠，若j i v v 和是朋友，则E v v j i ∈},{，得到边集E ，则有一个无向图)(E V G ，=。由于每个顶点仅仅能够与另外的1-n 个顶点邻接，所以每个顶点的度数1-≤n 。因此，在G 中顶点可能出现的度数是0，1，2，…, 1-n 。由于度数是0的顶点是孤立顶点，而度数为1-n 的顶点一定邻接其它1-n 个顶点的，所以在G 中度数为0和度数为1-n 的顶点不可能同时出现。因此，在G 中可以出现的顶点的度数应该分成以下两种情况：
(1) 0,1,2,…, 2-n
(2) 1,2,3,…, 1-n
上述两种情况最多有1-n 种不同的度数。根据鸽巢原理，至少有两个顶点具有相同的度数。故由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。
9.11 )(E V G ，=是一个简单无向图，若2)|)(|1|(|2
1-->
V V |E |，则G 是连通图。 证明
反证法。假设G 不连通，不妨设G 可分成两个不相连通的子图1G 和2G ，并假设它们中的顶点个数分别为1n 和2n ，当然21||n n V +=，因为1≥i n ，所以0)1)(1(21≥--n n ，从而有012121≤--+n n n n 。 )(212)1(2)1(||2122212211n n n n n n n n E --+=-+-≤ ))(2)((2
12121221n n n n n n +--+= ))22)(22||3|(|2
121212--+++-=n n n n V V ))1(22||3|(|2
121212--+++-=n n n n V V )2|)(|1|(|2
1)2||3|(|212--=+-≤V V V V 这与假设相矛盾，因此G 是连通的。
9.12 )(E V G ，=是一个简单图，试证明若G 不连通，则G 的补图G 一定连通。
证明
若>= （a ）v u ,分别属于两个不同顶点子集i V 与j V 。由上可知，G 包含边),(v u ，故u 和v 在G 中是连通的。 （b ）v u ,属于同一个顶点子集i V 。可在另一个顶点子集j V 中取一个顶点w ，由上可知，边),(w u 及边),(w v 均在G 中，故邻接边),(w u 和),(v w 组成的路连接顶点u 和v ，即u 和v 在G 中也是连通的。因此，当图G 不连通时，G 一定连通。 9.13已知关于人员a ，b ，c ，d ，e ，f 和g 的下述事实： (a ) 说英语； (b ) 说英语和西班牙语； (c ) 说英语，意大利语和俄语； (d ) 说日语和西班牙语； (e ) 说德语和意大利语； (f ) 说法语，日语和俄语； (g ) 说法语和德语。 试问：上述七个人中是否任意两人都能交谈（如果必要，可由其余五人所组成的译员链帮忙），为什么？ 解 以a ，b ，c ，d ，e ，f 和g 为顶点，如能讲同一语言则作一边，得图9.7，图9.7是连通的，所以这7个人中，任意两个都能交谈。 图9.7 习题13图 9.14（1d ，2d ，…n d ）是一个非负整数的n 元数组，若存在一个n 个顶点的简单无向图，使得其顶点的度数分别是1d ，2d ，…n d ，则称这个n 元数组是可图的。证明 （1）(4，3，2，2，1)是可图的。 （2）（3，3，3，1）是不可图的。 （3）不失一般性设n d d d ， ≥≥21证明：（1d ，2d ，…n d ）是可图的当且仅当（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的。 证明 （1）其构成图如图9.8所示。 图9.8 习题14(1)图 （2）（3，3，3，1）说明4阶无自回路的图中有3个顶点的度数为3，一个顶点的度数为1，而当有3个顶点的度数为3时，说明这3个顶点与其余各个顶点相邻接，这是，另一个顶点度数也应为3。与题设相矛盾，所以（3，3，3，1）是不可图的。 （3）先证明必要性。若 （1d ，2d ，…n d ）是可图的，则（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的。 设（1d ，2d ，…n d ）构成图G 的顶点为n v v v ,...,,21，且i i d v d =)(，可有以下两种情况： (a )若1v 关联的边正好是,,...,,1131211+d v v v v v v 则去掉这些边所得之图，即为所要求的图。 (b )若1v 关联的边中，有},...,,{11312111+?d j v v v v v v v v ，即,11+>d j 令 1)}(|min{1 )}(|max{110110+≤?=+>∈=d G E v v i i d G E v v j j j j 则有)(01G E v v j ∈，当0j j >时，)(1G E v v j ?； )(01G E v v i ?，当0i i <时，)(1G E v v i ∈。 其线图如图9.9所示。考察与顶点0i v 相邻接的0i d 个顶点，其中必有一个顶点k v 与0j v 不相邻接，否则就会产生100+≥i j d d 的矛盾。 图9.9 习题14(3)图 图9.10 习题14(3)图 作图},{},{'001001j k i k i j v v v v v v v v G G +-=,即得图9.10。于是'G 仍是无向无自回路的线图，且有与G 相同的度序列，只是'G 的0j 减少了，0i 增大了。这个过程重复地做下去，总可得到与（a ）相同的情况。因此，必要性得证。 再证充分性。若（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的，则（1d ，2d ，…n d ）也是可构成图的。 设前者所构成的图为G ，顶点为n v v v ,,,32 ，且顶点的次数为n i d d v d d i d v d i i i i ≤<+=+≤≤-=1,)(;12,1)(11时，G 中增加一个新顶点1v ，使1v 与 121,...,+d v v 相邻接，所得新图的顶点度序列为（1d ，2d ，…n d ） 。因此，充分性得证。 9.15 一个简单连通的无向图的中心，定义为具有这样性质的一个顶点，即这个顶点到其余顶点之间的最大距离是最小的。（两点间的距离为两点间最少边的一条通路的边的数目）。 （1）举出仅有一个中心的图的例子。 （2）举出一个不止一个中心的图的例子。 （3）若T 是一棵树，且T 有两个中心，则这两个中心一定邻接。 解 （1 ）如图9.11(a ) （2）如图9.11(b ) （a ） （b ） 图9.11 习题15的图 （3）设顶点v 的偏心数记为),(max )(u v d V u v D ∈= 。显然，具有最小偏心数的顶点v 是G 的中心。下面考察T 的中心v 。 在树),(E V T =中，V v ∈，不妨设),()(*v v d v D =，则容易说明*v 一定是树叶。在树中删去全部树叶仍是一棵树，记为),(111E V T =，由于在1T 中，1V v ∈，1)()()1(-=v D v D ，可见树T 的中心仍在1T 中。继续上述工作，直到只剩下一个顶点或剩下二个有一条边的相继顶点。这些顶点就是中心。 故若T 是一棵树，且T 有两个中心，则这两个中心一定邻接。 9.16 G 是一个简单图，)(E V G ，=，G 中顶点度数的最少值2||)(-≥V G δ，证明欲使此图不连通至少擦去)(G δ这么多顶点。（即点连通度)(G k =)(G δ）。 证明 因为G 是简单图，所以每个顶点的度数最多为1||-V ，现2||)(-≥V G δ，所以可以分两种情况讨论： （a ）若1||)(-=V G δ，则||v K G =，因此)(1||)(G V G k δ=-=。 （b ）若2||)(-=V G δ，则必有两个顶点不相邻接，设V v v ∈21,，且1v 与2v 不相邻接。于是，对于任意的V v ∈3,都有E v v v v ∈3231,。因此，对于V 中任意的3||-V 个顶点的集合1V ,1V G -一定是连通的，故必有)(2||)(G V G k δ=-≥。大家知道对于任何一个图G 都有)()()(G G G k δλ≤≤（)(G λ是边连通度）。因此)(G k =)(G δ。 9.17 设G 为n )2(≥n 阶无向欧拉图，证明G 中无桥。 证明 假设G 中存在桥),(v u e =，由于G 为欧拉图，所以e 的两个端点在G 中的度数均为偶数。因为e 为G 中桥， 所以e G G -='，由两个连通分支'1G 和'2G 组成。不妨设)'(),'(21G V v G V u ∈∈，由于删除了e ，因而在'1G 和'2G 中，)(),('2'1v d u d G G 为奇数度顶点，而对于任意的)'(1G V w ∈，u w ≠，)('1w d G 为偶数，即'1G 中只有一个奇度顶点u ；类似地，'2G 中也只有一个奇度顶点v 。这与握手定理的推论矛盾，故G 中不可能含桥。 9.18 一个连通的简单无向图，若每一个顶点的度数均是偶数，则此图不存在仅有一条边的割集。 证明 因为图中每一个顶点的度数均是偶数，所以该图为欧拉图，从而存在欧拉回路。又因为该 图为简单无向图，则该欧拉回路至少有3条边。根据欧拉回路的性质知，删除图中任何一条边后，图仍然连通。因此，此图不存在仅有一条边的割集。 9.19 ),(E V G =是一个图， V 是顶点集， E 是边集。若n V =||，则对于任意的)(,j i j i v v V v v ≠∈，i v 到 j v 有一条通路，一定有一条长度不超过1-n 的通路。 证明 对于任意的)(,j i j i v v V v v ≠∈，i v 到 j v 有一条通路，则由定理知，一定存在一条从i v 到 j v 的初等通路。因为图中只有n 个顶点，故任意一条初等通路的长都不超过1-n 。因此，一定存在i v 到 j v 的长度不超过1-n 的初等通路。 9.20 证明在一个连通图中，任意两条最长路必有公共顶点。 证明 设),(E V G =是连通图，且有两条最长的简单路：),...,,(:211n v v v l 和),...,,(:''2'12n v v v l 。 假设1l 和2l 无公共点，取1l 中一点1v ，2l 中一点'1v ，由于G 连通，必然有一条简单路 ),...,,(:213k x x x l ，其中11v x =，'1v x k =。设j x 是3l 中从左向右看第一个2l 中的点'k v ，得一简单路),...,,(:214j x x x l ，设i x 是4l 中从右向左看第一个1l 中的g v ，则又得到一个简单路1||),,...,,(:515≥+l x x x l j i i ，且5l 中除了i x 和j x 外，没有1l ，2l 中的点，不妨设 ),...,,(),...,,(121n g i i v v x x v v +≥，|),...,,(|),...,,(''1'2'1m k j j v x x x v v +≥，则可以取到简单路 ),...,,...,,,...,,(:'1'11216v v x x v v l k i i -+，因为1||5≥l ，所以|}||,min{|216l l l >，这样就可以得 到一条更长的路，矛盾。因此，任意两条最长的简单路必有公共点。 9.21证明若一个连通简单无向图有且仅有两个顶点不是割点，（即除这2个不是割点顶点外，任何另外的一点若擦去图就不连通了），则此图是一条直线。 证明 设图),(E V G =，由于该图为连通简单无向图，则该图没有多重边。因此该图若有回路至少应有3个顶点。因为该连通简单无向图有且仅有两个顶点不是割点，所以该图没有回路。否则该图至少存在3个不是割点的顶点。一个没有回路的连通简单无向图至少存在两个1度顶点，设此两顶点为1v 和2v ，此两顶点不是割点。 假设该图不是一条直线，则图G 中至少存在一个顶点V v ∈，其度数3)(≥v d 。因为图为连通且无回路，所以从顶点v 出发至少存在3条通路，从v 到1v 的通路，从v 到2v 的通路和从 v 到3v 的通路（其中3v 为该通路的终点） 。由此可见3v 不是割点，也即图G 存在3个不是割 点的顶点321,,v v v ，与已知矛盾。故该图是一条直线。 9.22 证明若一个无向图G 没有孤立点，没有奇数度顶点，则它必包含有圈。 证明 如果图G 有自环，则结论自然成立。 假设图G 没有自环，由于图G 没有孤立点，没有奇数度顶点，则每个顶点的度数至少是 2。设L 是图G 中最长路中的一条，设其长度为m ，这条路的一个端点设为a ，考察G 中与a 关联的那些边，这些边中任何一条边的另一端必在L 中，否则，将这个顶点加进L 中就可得到一条更长的路。 如果G 中每个顶点的度数至少为2，那么a 也要关联于一条不在L 上的边e 。若e 是环，则e 本身就是回路。否则，e 的另一个端点b 在L 上，而连通L 中a 到b 的子路与边e 就形成一个回路。如图9.12所示。 图9.12 习题22、23图 9.23 )(E V G ，=是一个简单连通图。若G 中每个顶点的度数都大于1，则G 中有圈。 证明 设L 是图G 中最长路中的一条，设其长度为m ，这条路的一个端点设为a ，考察G 中与a 关联的那些边，这些边中任何一条边的另一端必在L 中，否则，将这个顶点加进L 中就可得到一条更长的路。 因为G 中每个顶点的度数都大于1，则G 中每个顶点的度数至少为2，那么a 也要关联于一条不在L 上的边e 。e 的另一个端点b 在L 上，而连通L 中a 到b 的子路与边e 就形成一个回路。如图9.12所示。 9.24 ),(E V G =是一个简单无向图。若G 是一个二部图（偶图），且每一个顶点的度数都是3度，},{21V V 是G 作为二部图顶点集一个划分。证明||||21V V =。 证明 因为每一个顶点的度数都是3度，所以由二分图的定义知，图共有||31V 条边，每条边对应2个度数，故图的总度数为||61V 。由握手定理知，||6||3||3121V V V =+，从而有||||21V V =。 9.25 ),(E V G =是简单图，证明以下三条等价： （1）G 是一个顶点2着色的图； （2）G 是一个二部图（偶图）； （3）G 是所有回路都是由偶数条边组成。 证明 （1）?（2）： G 能够顶点2着色，则把顶点划分成两个分类1V 和2V ，其中1V 、2V 分别是着色相同的顶点，则},{21V V 就作为二部图顶点集的一个划分。因此，G 是一个二部图。 （2）?（3）：如果G 是二部图，},{21V V 是它的二分类。令),,,,(01i ik i io v v v v 是G 中的一条长度为1+k 的回路。不失一般性，设10V v i ∈，则由二部图的定义知，1042,,,V v v v i i i ∈ ，231,,V v V v ik i i ∈ 。因此，k 是奇数，从而1+k 是偶数。 故G 是所有回路都是由偶数条边组成。 （3）?（1）： 先假设G 是连通的，取定V v ∈0，定义V 的二个子集如下： }|{01的距离是偶数到v v v V i i =，}|{02的距离是奇数到v v v V i i = 任取E v v e j i ∈=),{，若1,V v v j i ∈，由1V 的定义知，从i v 到0v 有一条初等通路，其长为偶数，从j v 到0v 也有一条长为偶数的初等通路，再加上边e 得到一条回路，此回路的长度是偶数+偶数+1，即为奇数，与题设矛盾。矛盾说明i v 与j v 不可能同时属于1V 。同样可以证明i v 与j v 不可能同时属于2V ，即},{21V V 是G 的一个二分类。这样图G 中每一条边，它所关联的两个顶点一个在1V 中，一个在2V 中，将1V 中所有顶点着上1c 色，2V 中所有顶点着上2c 色，就得到图G 的一种正常着色。 故G 是一个顶点2着色的图。 如果图G 不是连通的，则可以对G 的诸连通分支的顶点2着色，从而得到对图G 的顶点2着色。 9.26已知：a ，b ，c ，d ，e ，f ，g 的下述事实： (a )说汉语、日语； (b )说日语、法语； (c )说德语、法语、西班牙语； (d )说汉语、德语、俄语、葡萄牙语； (e )说俄语、朝语； (f )说朝语、西班牙语； (g )说葡萄牙语。 试问：能否将七个人分成二组，使同一组中没有二个人能互相交谈？并用图论方法，说明你的结论。 解 把每个人对应成相应的顶点，两个能够交谈当且仅当相应的顶点相邻，得图9.13显然该图是一个二部图。因此能将七个人分成二组},,,{g e c a 和},,{f d b ，使同一组中没有二个人能互相交谈。 图9.13 习题26图 9.27图9.14中哪个图是欧拉图？哪个图是哈密尔顿图？哪个图有欧拉通路？哪个图有哈密尔顿通路？ (a ) (b ) (c ) 图9.14 习题27图 解 图9.14（a ）中有两个奇数度顶点，如图中“黑点”所示。其余的全是偶数度顶点，根据定理，该图存在欧拉通路，但不存在欧拉回路，因此该图不是欧拉图。该图同样存在哈密尔顿通路，沿着边走就可。但是不存在哈密尔顿回路，因此不是哈密尔顿图。 图9.14（b ）中有六个奇数度顶点，因此它不存在欧拉通路，也不是欧拉图。 图9.14（c ）中两个奇数度顶点，如图中“黑点”所示。其余的全是偶数度顶点，根据定理，该图存在欧拉通路，但不存在欧拉回路，因此该图不是欧拉图。该图存在哈密尔顿通路，不是哈密尔顿图。 图9.18（d ）中全都是奇数度的顶点，因此不是欧拉图。图中存在哈密尔顿回路，因此 是哈密尔顿图。 9.28当 n 是什么数时，完全图n k 是欧拉图？请说明理由。 证明 n k 有n 个顶点，每个顶点的度数为1-n ，故当)3(≥n 为奇数时，图n k 有一条欧拉回路。 9.29 （1）画一个欧拉图，但不是哈密尔顿图。 （2）画一个哈密尔顿图，但不是欧拉图。 （3）画一个有哈密尔顿路的非哈密尔顿图 （4）画一个有哈密尔顿通路但无哈密尔顿图的欧拉图。 解 （1）如图9.15（a ）所示。 （2）如图9.15（b ）所示。 （3）如图9.15（c ）所示。 （4）如图9.15（d ）所示。 （a ） （b ） （c ） （d ） 图9.15 习题29图 9.30 一个连通图中有一个顶点，称为桥。若擦去这个顶点后，图就不连通了，请画一个欧拉图，但不是哈密尔顿图且没有桥。 解：如图9.16所示 图9.16 习题30图 图9.17 习题31图 9.31画一个有7个顶点的简单无向图，满足 （1）它有哈密尔顿通路。 （2）它不是哈密尔顿图。 （3）它不是欧拉图。 （4）它能一笔画。 解 如图9.17。 9.32 证明一个无向图若有m 2个奇数顶点，则此图至少要m 笔才能画，且能用m 笔画。 证明 根据欧拉通路的性质可知，在图中存在一个奇数度顶点到另一个奇数度顶点欧拉通路，该通路可以一笔画出，且在画图过程中其余经过的顶点均为偶数度，删除通路中的边，所得图中 有)1(2-m 个奇数度顶点。重复上述过程m 次后，图中没有任何边。因此此图至少要m 笔才能画，且能用m 笔画。 9.33 如果可能，请画一个顶点是偶数，边是奇数的欧拉图。否则说明理由。 解 图9.18 习题33图 9.34 画一个欧拉图，它是简单无向图，有偶数条边，但有奇数个顶点。 图9.19 习题34图 9.35 证明一个欧拉图不存在割边，即不存在一条边，拿去此边后，原图变成不连通的两部分。 证明 因为图G 是欧拉图，所以G 存在一条经过每条边一次且仅一次的回路，删除G 中的任何一条边，图仍然连通，故一个欧拉图不存在割边。 9.36 )(E V G ，=是一个简单连通图。且G 是一个二部图（偶图），相应地顶点分类为},{21V V ，且||||21V V ≠。证明G 不是哈密尔顿图。 证明 因为||||21V V ≠，不妨设||||21V V <，从图中去掉1V 中的顶点后, 得到||2V 个连通分枝。因为所得到的连通分枝数目||2V 大于所去掉的顶点数目||1V ，即||||)(121V V V G W >=-，所以由哈密尔顿图的必要条件知，G 不是哈密尔顿图。 9.37如果一个无向图中每一条边给它定一个方向，使所得有向图是强连通的，那么称这个图为可定向的。证明任何一个哈密尔顿图是可定向的。 证明 设G 是哈密尔顿图，则在图中一定存在一条经过所有顶点一次且仅一次的回路C ，对C 上的每一条边沿回路按顺时针方向加上方向，不在回路上的边任意加方向所得之图是一个有向图，该有向图中存在一条经过G 中每个顶点一次且仅一次的回路，所以此有向图是强连通的。因此，任何一个哈密尔顿图是可定向的。 9.38 ),(E V G =是一个简单连通图。E e ∈是G 中一条边，若从图G 中擦去边e ，则G 不连通，说e 是G 中的桥。证明若G 是哈密尔顿图，则G 中没有一条边是桥。 证明 因为G 是哈密尔顿图，所以一定存在哈密尔顿圈，它包括图G 中的任意一个顶点，删去 其中的任意一条边，若删除的不是圈中的边，则哈密尔顿圈仍然存在，图仍然连通；若删除的是圈中的边，则图中存在一条哈密尔顿路，图仍然连通。 因此G 中无任何一条边是桥。 9.39 )(E V G ，=是一个简单连通图。E v ∈是G 中一个顶点，若从图G 中擦去顶点v ，其余不动，则G 不连通，说v 是G 中的桥。证明若G 是哈密尔顿图，则G 中没有一个顶点是桥。 证明 因为G 是哈密尔顿图，所以一定存在哈密尔顿圈，它包括图G 中的任意一个顶点，删去其中的任意一个顶点，则图中存在一条哈密尔顿路，图仍然连通。因此G 中无任何一个顶点是桥。 9.40 有12个人围坐一圆桌，边会餐边交流乒乓球技术。已知这12个人中，每个人至少和其余的6人打过球，试问是否有一种坐法，使每个人左、右俩人都和他打过球？请说明原因。 证明 设>= 9.41 有12个人，围坐一个圆桌的四周开会。已知这12个人中的任意的二个人能认识其余的10个人，则这12个人围坐一圈能使每一个人都认识各自的左、右邻人。 解 设>= 若u 和v 相邻，则121)(1)()()(1010≥+++=+v d u d v d u d 。 若u 和v 不相邻，则},{v u V -中恰有10个顶点。如果10)()(1010=+v d u d ，且其余10个顶点必与u 或v 相邻接，则至少有一个顶点只能与u 和v 中的一个顶点相邻（否则，1020102≠=?，矛盾）。设w 与u 相邻， w 与v 不相邻。此时，对于顶点w u ,来说，都不与v 相邻，即w u ,合起来不能认识v ，故不能认识所留下的10个人，这与假设相矛盾。故11)()()()(1010≥+=+v d u d v d u d 。如果11)()(1010=+v d u d ，且其余10个顶点必与u 或v 相邻接，则至少有一个顶点只能与u 和v 中的一个顶点相邻（否则2*10=2011≠，矛盾）。设w 与u 相邻， w 与v 不相邻。此时，对于顶点w u ,来说，都不与v 相邻，即w u ,合起来不能认识v ，故不能认识所留下的10个人，这与假设矛盾。故12)()()()(1010≥+=+v d u d v d u d ，由哈密尔顿的充分条件知，图中存在一条哈密尔顿圈，因此，这12个人沿哈密尔顿圈就坐，能使每一个人都认识各自的左、右的邻人。 9.42 ),(E V G =是一个连通无向图。我们做一个新图),(E V G ''='，使 }|{V v v V ∈='， 在新图G '中， E v v '∈},{'2'1，当且仅当在原图G 中有一条从1v 到2v 的哈密尔顿通路。一个 图G 叫自哈密尔顿路图，若G 与G '同构。请画出两个不同构的自哈密尔顿路图，他们都各有4个顶点。 解 图9.20 习题42图 9.43 画两个最简单的不同构的非平面图 解 图9.21（a ）是具有6个顶点的3,3K ，它是非平面图。 图9.21（b ）也具有5个顶点的5k ，它是非平面图。显然两个图不同构。 (a) (b) 图9.21 习题42图 9.44 画二个六个顶点的图，它们都是非平面图，但互不同构。 解 图9.22（a ）是具有6个顶点的3,3K ,它是非平面图。图9.22（b ）也具有6个顶点， 13=e ，每个区域至少由3条边围成，1266313=-?>，因此它不是平面图。而且图（a ）每个顶点的度数都是3，图（b ）两个顶点的度数是5，其余的顶点度数均为4，因此这两个图不同构。 (a) 图9.22 习题43图 9.45试画一个有8个顶点的简单连通图，让它和它的补图都是平面图。 解 图9.23 习题45图 9.46 ),(E V G =是一个无向图。若11||≥V ，则G 或者G 的补图G 是非平面图。 证明 设G 和G 都是平面图，设图G 的顶点数为v ，边数为e ，图G 的顶点数为'v ，边数为'e ，显然'v v =，)1(2 1'-=+v v e e 。由不等式636'3',63-=-≤-≤v v e v e ，相加得126')1(2 1-≤+=-v e e v v ，从而有02)11)(2(24132≤+--=+-v v v v ，显然应有11|| 9.47 证明小于30条边的简单平面图至少有一个顶点的度数小于或等于4。 证明 假设每个顶点的度数>4,即5)deg(≥i v ，设图G 的顶点数为v ，边数为e 。因为v v e v i i 5)deg(21≥=∑=，即e v 52≤ 。由于63-≤v e ，代入后得到65 6-≤e e ，即有30≥e ，与边数小于30相矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于或等于4。 9.48 设G 是每一个面至少由)3(≥K K 条边围成，则≤e (2)2K v K --。这是e ，v 分别是G 的边数和顶点数。 证明 设图G 的顶点数为v ，边数为e ，平面数为r 。因为每一个面至少由)3(≥K K 条边围成。所以Kr e ≥2，即K e r 2≤，而2=+-r e v ，故22≥+-K e e v ，即2 )2(--≤K v K e 。 9.49 证明具有6个顶点12条边的连通平面简单图，它的每一个面都是由3条边组成。 证明 设图G 的顶点数为v ，边数为e ，平面数为r 。由题意知，12,6==e v ，由欧拉公式 82=-+=v e r ，设至少有一个区域由4条边围成，则有2432=>r e ，从而有12>e 。与12=e 矛盾。故每一个面都是由3条边组成。 9.50一个连通的简单平面图有8个顶点18条边。此图嵌入平面后，会把平面分成几个小区域？ 解 设图G 的顶点数为v ，边数为e ，平面数为r ，则题意知，18,8==e v ，由欧拉公式122=-+=v e r ，因此，此图嵌入平面后，会把平面分成12个小区域。 离散数学形成性考核作业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={ 2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标： 第1次作业 一、单项选择题（本大题共30分，共 15 小题，每小题 2 分） 1. 图G所示平面图deg(R3)为 A. 4 B. 5 C. 6 D. 3 2. 在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。 A. (m-1)i C. (m-1)i=t-1 D. (m-1)i≤t-1 3. 命题a）：如果天下雨，我不去。写出命题a）的逆换式。 A. 如果我不去，天下雨。 B. 如果我去，天下雨。 C. 如果天下雨，我去。 D. 如果天不下雨，我去。 4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（） A. 5 B. 4 C. 2 D. 6 5. 假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。 A. S是A的覆盖 B. S是A的划分 C. S既不是划分也不是覆盖 D. 以上选项都不正确 6. 没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。 A. (?x)(M(x)→F(x) B. (?x)(M(x)?F(x) C. （?x）(M(x)?F(x)) D. (?x)(M(x)→F(x) 7. 命题逻辑演绎的CP规则为（） A. 在推演过程中可随便使用前提 B. 在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C. 如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出C D. 设?(A)是含公式A的命题公式，B<=>A，则可以用B替换?(A)中的A 8. 设G是有6个结点的完全图，从G中删去（）条边，则得到树。 A. 6 B. 9 C. 10 D. 2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（ A ）． 选择一项： ， A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 . 答案已保存 满分 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（ D ）． ) 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 < 题目3 答案已保存 满分 标记题目 题干 ； 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 ， D. 17 题目4 答案已保存 满分 标记题目 … 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 ~ C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分 " 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 … B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 ^ 满分 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： % A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 《 答案已保存 满分 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第（ A ）个版块． 、 选择一项： A. 6 B. 7 C. 8 D. 9 @ 题目8 答案已保存 满分 标记题目 题干 ( 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项： 《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44 一、单项选择题（共 10 道试题，共 100 分。） 1. 设集合A = {1, a }，则P(A) = ( D )． A. {{1}, {a}} B. { ,{1}, {a}} C. {{1}, {a}, {1, a }} D. { ,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（C ）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( C )． A. {a，{a}} A B. {1，2} A C. {a} A D. A 4. 设集合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 ）． A. f?g C. f?f D. g?g 5. 设集合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. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系￡是A上的整除关系，则偏序集上的元素5是集合A的（ C ）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（ A ）． 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G= 8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图． 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} A B ==，P(A)-P(B )={{3},{1,3},{2,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的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} x∈ y y > <那么R－1＝{<6,3>,<8,4>}． x = ∈ 2 , , x , {B A y 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 国家开发教育本科离散数学形考+答案 形考任务一 题目1：本课程的教学内容分为三个单元，其中第三单元的名称是（）． A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2：本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其 中第2章关系与函数中的第3个知识点的名称是（）． A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3：本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（）讲． A. 18 B. 20 C. 19 D. 17 题目4：本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（）． A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5：课程学习平台左侧第1个版块名称是：（）． A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6：课程学习平台右侧第5个版块名称是：（）． A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7：“教学活动资料”版块是课程学习平台右侧的第（）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8：课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（）． A. 复习指导 B. 视频 C. 课件 D. 自测 形考任务二 题目1：若集合 $$ A＝\{a,\{a\},\{1,2\}\}$$，则下列表述正确的是( )． A. $$\{a,\{a\} \in A$$ B. $$\{1，2\}\notin A$$ C. $$\{a\}\subseteq A $$ D. $$\emptyset \in A $$ 题目2：设集合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} 题目3：设集合A = {1,$$ a$$ }，则P(A) = ( )． A. {{1}, {$$a$$}} B. {?,{1}, {$$a$$}} C. $$\{\{1\}, \{a\}, \{1, a \}\}$$ D. $$?,\{1\}, \{a\}, \{1, a \}\}$$ 题目4：集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={ 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={ 5. 设集合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. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} A B ==，P(A)-P(B )={{3},{1,3},{2,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的二元关系， ∈ x y R? < 且 =且 > ∈ ∈ {B , , x A y A y B x } 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y y x∈ = <那么R－1＝{<6,3>,<8,4>}． > ∈ A 2 , x , , x y {B 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( D )． A. {{1}, {a}} B. { ,{1}, {a}} C. {{1}, {a}, {1, a }} D. { ,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（C ）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( C )． A. {a，{a}} A B. {1，2} A C. {a} A D. A 4. 设集合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 ）． A. f?g B. g?f C. f?f D. g?g 5. 设集合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. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系￡是A上的整除关系，则偏序集上的元素5是集合A的（ C ）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（A ）． A. 1024 B. 10 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ? ? ? ? ? c a b e d ? f 图四 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word 文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 { f }，{ e,c} ． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G= 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word 文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 { f }，{ e,c} ． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结 点 ． 5．设G=离散数学形成性考核作业4题目与答案
离散数学形考任务1-7试题及答案完整版
离散数学 ( 第1次 )
离散数学形考任务1-7试题及答案完整版
《离散数学》及答案
204电大离散数学,形考任务2
离散数学作业答案
2018国家开放大学离散数学本形考任务答案
离散数学课后答案
电大离散数学本形考任务完整版
国家开发教育本科离散数学形考+答案
离散数学及答案
离散数学答案
电大离散数学(本)形考任务2知识讲解
2014电大离散数学-形考任务2
离散数学试题及答案(1)
离散数学图论部分经典试题及答案
2018国家开放大学离散数学(本)形考任务4答案
2018国家开放大学离散数学(本)形考任务答案