《离散数学》补充练习题（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.Awolf,agoatandacabbageareononebankofariver.Aferrymanwantstotakethemacross,butsincehisboatissmall,hecantakeonlyoneofthematatime.Forobviousreasons,neitherthewolfandthegoatnorthegoatandthecabbagecanbeleftunguarded.Howistheferrymangoingtogetthemacrosstheriver?

　　在一河岸有狼、羊和卷心菜,农夫要将它们渡过河去,但由于他的船太小,每次只能载一样葡萄东西,并且,狼和羊,羊和卷心菜都不能在无人照看的情况下留在一起.问农夫有无办法将它们渡过河去?若有,给出其实施办法.

　　人、狼、羊、菜四种东西的任意组合,共有24=16种情况,其中狼羊菜、羊菜、狼羊三种情况不允许,因而这三种情况的余：人、人狼、人菜三种情况也不会出现.这样,岸上只能有如下10种情况：

　　人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、

　　空、菜、羊、狼、狼菜.

　　将这10种状态各用一个点表示,且两种状态的两个点有边相连当且仅当该两种状态可用载人（或加一物）的渡船互相转换.于是可得下图：

　　我们的问题就转化为求一条从“人狼羊菜”到“空”的路.从而可求得渡河办法.