《离散数学》补充练习题（2011.05.30）
1、将下列命题符号化.
（1）小李边读书边听音乐.
（2）现在没下雨,可也没出太阳,是阴天.
2、证明等价关系： .
3、概述求解主合取范式的主要方法和步骤,并求公式 的主合取范式.
4、将下列论证用命题符号表示,然后求证逻辑推论是否成立.
如果天热则蝉鸣叫,如果蝉鸣叫则小王不睡觉,小王游泳或睡觉,所以如果天热则小王游泳.
5、将下列语句用谓词公式表示.
（1）不劳动者不得食.
（2）每个人的祖父都是他父亲的父亲.
6、给定集合 , 均是 上的二元关系, , .
（1）画出 的关系图；
（2）写出 的关系矩阵；
（3）写出 所具有的性质；
（4）求 .
7、设 是集合 上的二元关系.证明 .
8、简述传递闭包的定义,并求 上关系 的传递闭包.
9、列出色数 为的三个图： .
10、 阶完全图的色数为： .
11、 阶树的色多项式为： .
12、 阶完全图的色接多项式为： .
13、如下图所示的图的邻接矩阵为 ,关联矩阵为 .
14、设 阶图的各顶点的度分别为 ,则称 为该图的度序列.度序列为 的简单图是 .
15、是否存在度序列为 , 的简单图?若存在,给出一个图；若不存在,请说明理由.
16、画出如下图的所有生成子图.
17、设图 如下图所示,求该图的生成树个数 .
18、已知图G（V、E）,画出G－V5,G－v3v4,G[{v2,v3,v5}],G[{v3v4,v4,v6,v7v8}]
G：
19、已知图G的邻接矩阵 ,画出G,并求出度序列.
20、证明：偶图G的任意子图H仍为偶图.
21、证明：设图G（V、E）的度序列为（ ）,边数为q,则
22、证明：整数序列（6,6,5,4,3,3,1）不可能为一个简单图的图序列.
23、证明顶点度数均为 的简单连通图是圈.
23、若图G是 不连通的,则其补图GC是连通的.
24、证明：设 是由 和 两个连通分支组成的图,则其色多项式 .
25、证明：设 是由 和 两个连通分支组成的图,则其色数 .
26、设图G（V、E）且|V|＝p,|E|＝q,则G为树当且仅当G为连通的且p＝q＋1.
27、证明：图G为树当且仅当G的任意两个不同顶点之间存在唯一的一条路.
28、画出全部非同构的6阶树.
29、利用Cayley公式计算图G的生成树数目（写出演算过程）.
G：
30、下列图是否为Enler图?
G1： G2：
31、证明：设 为 条边的 阶连通简单图且 ,则 包含圈.
32、证明：非平凡树的最长路的起点和终点均为悬挂点.
33、证明：恰好有两个悬挂点的树是一条路.
34、证明：图G为非平面图.
G：
35、给出下图G的一个最大匹配（最大对集）.
G：
36、设图G有完美匹配,则G为偶数阶图.
37、证明：路至多有一个完美匹配.
38、写出p（≥1）阶树T的色多项式,并确定T的色数.
39、写出5个阶轮图W5的色多项式,并求χ（w5）
W5：
40、设G为任一偶图,则χ（G）≤2.
41、证明：非平凡连通偶图 的色数为 .
42、证明圈 的色数为 或 .
43、证明：设 为具有 条边的 阶极大平面图,则 .
44.证明：在空间中,不可能有这样的多面体存在,它们有奇数个面,而它们的每个面又都有奇数条边.
证明：假设存在这样的多面体,将这多面体的面用顶点表示,当且仅当两个面有公共棱时,在相应的顶点间连一边,得图G.按题意,G有奇数个奇顶点.显然,这样的图不存在,故这样的多面体是不存在的.
45. A wolf, a goat and a cabbage are on one bank of a river. A ferryman wants to take them across, but since his boat is small, he can take only one of them at a time. For obvious reasons, neither the wolf and the goat nor the goat and the cabbage can be left unguarded. How is the ferryman going to get them across the river?
在一河岸有狼、羊和卷心菜,农夫要将它们渡过河去,但由于他的船太小,每次只能载一样葡萄东西,并且,狼和羊,羊和卷心菜都不能在无人照看的情况下留在一起.问农夫有无办法将它们渡过河去?若有,给出其实施办法.
人、狼、羊、菜四种东西的任意组合,共有24=16种情况,其中狼羊菜、羊菜、狼羊三种情况不允许,因而这三种情况的余：人、人狼、人菜三种情况也不会出现.这样,岸上只能有如下10种情况：
人狼羊菜、 人狼羊、 人狼菜、 人羊菜、 人羊、
空、 菜、 羊、 狼、 狼菜.
将这10种状态各用一个点表示,且两种状态的两个点有边相连当且仅当该两种状态可用载人（或加一物）的渡船互相转换.于是可得下图：
我们的问题就转化为求一条从“人狼羊菜”到“空”的路.从而可求得渡河办法.
