离散下-习题课

11/23/11第十一章，格和布尔代数例：设S110={1,2,5,10,11,22,55,110}是110的所有因数的集合,令glb,lub是最大公约数和最小公倍数运算。下面简记为glb—*,lub—证明<S110,*,>是一个布尔代数。证明:110=1×2×5×11质因子分解式中因子是不重复的。记(x)为x分解的质因数的集合,例(55)={1,5,11}。而12=1×2×2×3,质因子分解中,因子是重复的。<S110,D>的哈斯图与<S30,D>,<P(A),>,A={a,b,c}是完全相同的。容易验证,交换律显然成立。

11/23/11第十一章，格和布尔代数x,y,z∈S110,x*(yz)=(x)∩((y)∪(z))=((x)∩(y))∪((x)∩(z))=(x*y)(x*z)同理x(y*z)＝(xy)*(xz)分配律成立。显然1是S110的最小元,110是S110的最大元。x*110=x,x1=x,同一律成立。11/23/11第十一章，格和布尔代数记﹁x=110/x,因110中质因数分解中质因数不重复。故﹁x与x的质因数没有重复的。∴﹁x*x=1,﹁xx=(﹁x)∪(x)=110互补律是成立,∴<S110,*,,﹁,1,110>是布尔代数。第十一章，格和布尔代数本章的主要知识点有：格的代数性质；基于格的布尔代数定义方法；布尔代数的同态、同构；几种特殊的布尔代数.本章的学习需要注意如下几点：格是一种非常重要的代数结构,

它与集合论中介绍的偏序关系紧密相关,

本章中仅仅介绍了格的基本概念以及为讨论布尔代数而介绍了两种特殊的格,

但这也是以后根据需要进一步学习格论的基础.

学习格,

重点应在于理解格的概念,

以及讨论格是一种代数结构的思路.

此外,

理解相关证明的基本思路也是非常重要的.本章习题类型主要有概念题、判断题,

如布尔代数的概念及其判断,

以及证明题,

如证明等式、某代数结构是布尔代数或格等.

这些都需要抓住基本概念,

以及基本性质进行直接证明.

此外,

由于对布尔代数的讨论中指出了其元素的原子表达式以及基集的基数性质,

在习题中主要反映为解答题的形式来深化这些知识点.练习1下面那些构成格，那些不能？练习2设L是模12加群<Z12,>的子群格，给出L的所有4元子格。书上187书上习题218,第3题练习3设R为实数集，其中K0=K2=0,K1=K3=-1,K4=-2。令S={At|t=0,1,2,3,4}。画出偏序集的哈斯图并求其极大，极小，最大，最小元。说明该偏序集构成什么格？练习4设B是布尔代数，证明：在格<L；≤>中,

如果a≤b≤c,

则有

1)aÚb=bÙc

2)(aÙb)Ú(bÙc)=b=(aÚb)Ù(aÚc)证明：格<L；≤>中,

对任意a,b,c,d∈L,

有

1)(aÙb)Ú(cÙd)≤(aÚc)Ù(bÚd).

2)(aÙb)Ú(bÙc)Ú(cÙa)≤(aÚb)Ù(bÚc)Ù(cÚa).9第十四章图的基本概念主要内容无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构通路与回路及其分类无向图的连通性与连通度有向图的连通性及其分类图的矩阵表示10基本要求深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系记住通路与回路的定义、分类及表示法深刻理解与无向图连通性、连通度有关的诸多概念会判别有向图连通性的类型熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵9阶无向图G中，每个顶点的度数不是5就是6.证明G中至少有5个6度顶点或至少有6个5度顶点.练习5证关键是利用握手定理的推论.方法一：穷举法设G中有x个5度顶点，则必有(9x)个6度顶点，由握手定理推论可知，(x,9x)只有5种可能：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求.方法二：反证法否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是9阶图矛盾.数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的非同构的图来.练习6只要能画出6阶无向简单图，就说明它可简单图化.下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图.P293,习题17,23练习7用扩大路径法证明.情况一：

+.证明D中存在长度

+1的圈.设

=v0v1…vl为极大路径，则l

(为什么?).由于d(v0)

，所以在

上存在PLAY邻接到v0，于是情况二：+

，只需注意d+(vl)

+.设D=<V,E>为有向简单图，已知(D)2，+(D)>0，(D)>0，证明D中存在长度max{+,}+1的圈.为D中长度

+1的有向圈练习8(1)D中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？(3)D是哪类连通图?(4)D中v1到v4长度为1,2,3,4的通路各多少条？其中几条是非初级的简单通路？(5)D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型.(6)D中长度为4的通路（不含回路）有多少条？(7)D中长度为4的回路有多少条？(8)D中长度4的通路有多少条？其中有几条是回路？(9)写出D的可达矩阵.4．有向图D如图所示，回答下列诸问：练习916解答(1)D中有3种非同构的圈，长度分别为1,2,3，请画出它们的图形.(2)D中有3种非圈的非同构的简单回路，它们的长度分别为4,5,6.请画出它们的图形来.(3)D是强连通的（为什么？）为解(4)—(8)，只需先求D的邻接矩阵的前4次幂.

17(4)v1到v4长度为1,2,3,4的通路数分别为0,0,2,2.其中只有长度为4的两条是非初级的简单通路（定义意义下），见下图所示.解答18解答(5)v1到v1长度为1,2,3,4的回路数分别为1,1,3,5.其中长度为1的是初级的(环)；长度为2的是复杂的；长度为3的中有1条是复杂的，2条是初级的；长度为4的有1条是复杂的，有4条是非初级的简单回路.请在图中行遍以上各回路.(6)长度为4的通路(不含回路)为33条.(7)长度为4的回路为11条.(8)长度4的通路88条，其中22条为回路.(9)44的全1矩阵.19第十五章欧拉图

主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题基本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.201.设G为n（n2）阶无向欧拉图，证明G中无桥方法二：反证法.利用欧拉图无奇度顶点及握手定理的推论.否则，设e=(u,v)为G中桥，则Ge产生两个连通分支G1,G2，不妨设u在G1中，v在G2中.由于从G中删除e时，只改变u,v的度数(各减1)，因而G1与G2中均只含一个奇度顶点，这与握手定理推论矛盾.练习1方法一：直接证明法.命题(*)：设C为任意简单回路，e为C上任意一条边，则Ce连通.证设C为G中一条欧拉回路，任意的eE(C)，可知Ce是Ge的子图，由()知Ce连通，所以e不为桥.212.

证明下图不是哈密顿图.(破坏必要条件)方法一.利用定理15.6，取V1={a,c,e,h,j,l}，则p(GV1)=7>|V1|=6练习2方法二.G为二部图，互补顶点子集V1={a,c,e,h,j,l},V2={b,d,f,g,i,k,m}，|V1|=67=|V2|.方法三.利用可能出现在哈密顿回路上的边至少有n(n为阶数)条——这也是哈密顿图的一个必要条件，记为（）.此图中，n=13，m=21.由于h,l,j均为4度顶点，a,c,e为3度顶点，且它们关联边互不相同.而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有21(32+31)=12.这达不到（）的要求.223．某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？解图是描述事物之间关系的最好的手段之一.做无向图G=<V,E>,其中

V={v|v为与会者}，E={(u,v)|u,vV且u与v有共同语言，且u

v}.易知G为简单图且vV,d(v)4，于是，u,vV,有d(u)+d(v)8，由定理15.7的推论可知G为哈密顿图.服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.练习3由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.234.距离(公里)如图所示.他如何走行程最短？

练习4最短的路为ABCDA，距离为36公里，其余两条各为多少？24第十六章习题课主要内容无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解基本回路、基本割集的概念，并会计算理解根树及其分类等概念会画n阶（n较小）非同构的无向树及根树（1n6）熟练掌握求最优树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法25（2）（3）从而解出练习11.无向树T有ni个i度顶点，i=2,3,…,k，其余顶点全是树叶，求T的树叶数.解用树的性质：边数m=n1（n为阶数），及握手定理.(1)262．设n阶非平凡的无向树T中，(T)

k，k1.证明T至少有k片树叶.证反证法.否则，T至多有s片树叶，s<k，下面利用握手定理及树的性质m=n1推出矛盾.由于(T)

k，故存在v0，d(v0)

k.于是，由此解出s

k，这与s<k矛盾.证本题的方法有多种，请用分支点都是割点来证明.练习2273．设G为n阶无向简单图，n5，证明G或中必含圈.本题的方法很多，证明中用：G与边数之和为Kn的边数，以及树的性质：m=n1.

方法一.反证法.否则G与的各连通分支都是树.设G与的连通分支分别为G1,G2,…,Gs和G1,G2,…,Gs.令ni,mi与nj,mj

分别为Gi,Gj的顶点数和边数.于是得n25n+40，解出1

n4,矛盾于n5.练习328方法二.在G与中存在一个，比如说G，它的边数用反证法证明G中必含圈.比方法一简单.