武大国软离散数学_习题整理

1、离散数学例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化(1) 只要天冷，小王就穿羽绒服.(2) 因为天冷，所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷.(4) 只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时候.2蕴涵联结词的实例pq注意：注意： pq 与与 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp例6 写出下列公式的真值表, 并求它们的成真赋值和成假 赋值: (1) (pq) r (2) (qp) qp (3) (pq) q3真值表

2、真值表4(1) A = (p q) r成真赋值成真赋值:000,001,010,100,110; 成假赋值成假赋值:011,101,111 p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表15(2) B(qp) qp成真赋成真赋值值:00,01,10,11; 无成假赋值无成假赋值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表真值表26(3) C ( p q) q的真值表的真值表成假赋值成假赋值:00,01,10,11

3、; 无成真赋值无成真赋值p q p p q ( p q) ( p q) q0 00 11 01 11100110100100000真值表真值表3主要内容l命题、真值、简单命题与复合命题、命题符号化l联结词, , , , 及复合命题符号化l命题公式及层次l公式的类型l真值表及应用基本要求l深刻理解各联结词的逻辑关系, 熟练地将命题符号化l会求复合命题的真值l深刻理解合式公式及重言式、矛盾式、可满足式等概念l熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型7第一章 习题课基本概念(1) 文字命题变项及其否定的总称(2) 简单析取式 p, q, pq (3) 简单合取式 p, q

4、, pq, (4) 析取范式 p, pq, pq, (pq) (qr)(5) 合取范式 p, pq, pq, (pq)(pqr)(6) 范式析取范式与合取范式的总称范式不唯一，主唯一主析取范式由极小项(真)构成的析取范式主合取范式由极大项(假)构成的合取范式82.2 析取范式与合取范式 例如，n=3, 命题变项为 p, q, r 时， (pqr)(pqr) m1m3 主析取范式 (pqr)(pqr) M1M7主合取范式定理2.5 (主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取 范式和主合取范式, 并且是惟一的例6 (1) 求公式 A=(pq)r的主析取范式和主合取范式 解 (pq

5、)r (pq)r （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7 （主析取范式）10实例 (pq)r (pr)(qr) （合取范式） pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M0M4 , 代入 并排序，得 (pq)r M0M2M4 （主合取范式）11实例1.求公式的成真成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二

6、进制表示, 其余2n-s 个赋值都是成假赋值 例如 (pq)r m1m3m5 m6m7成真赋值为 001, 011, 101, 110, 111，成假赋值为 000, 010, 100. 类似地，由主合取范式也立即求出成假赋值和成真赋值. 12主范式的应用13主范式的应用2. 判断公式的类型 设A含n个命题变项. A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项, 记为1.A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项, 记为0.A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全部极小项 A的主合取范式中至少含一个、但不是全部极

7、大项.例7 用主析取范式判断公式的类型:(1)A (pq)q (2) B p(pq) (3) C (pq)r解 (1) A ( pq)q ( pq)q 0 矛盾式(2) B p(pq) 1 m0m1m2m3 重言式(3) C (pq)r (pq)r (pqr)(pqr)(pqr)(pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可满足式14主范式的应用3. 判断两个公式是否等值例8 用主析取范式判以下每一组公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (

8、pq)r = m1m3 m4m5 m7显见，中的两公式等值，而的不等值.15主范式的应用4. 解实际问题例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下 述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?解 记 p:派A去, q:派B去, r:派C去(1) pr, (2) qr, (3) (pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq)16主范式的应用求A的主析取范式 A=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr)

9、 (pq)(pq) (pq)(pq)(pr)(pq) (rq)(pq)(pq)(pq) (pr)(pq)(rq)(pq) (pqr)(pqr)成真赋值:101,010结论: 方案1 派A与C去, 方案2 派B去17主范式的应用由主析取范式确定主合取范式例10 设A有3个命题变项, 且已知A= m1m3m7, 求A的主合取范式.解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示, 它们恰好是A的主合取范式的极大项的下角标, 故 A M0M2M4M5M618用成真赋值和成假赋值确定主范式由主合取范式确定主析取范式由主合取范式确

10、定主析取范式用真值表确定主范式用真值表确定主范式 1. A (AB) 附加律 2. (AB) A 化简律3. (AB)A B 假言推理4. (AB)B A 拒取式 5. (AB)B A 析取三段论6. (AB)(BC) (AC) 假言三段论7. (AB)(BC) (AC) 等价三段论8. (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式)9. (AB)(CD)( BD) (AC) 破坏性二难每个等值式可产生两个推理定律如, 由AA可产生 AA 和 AA推理定律-重言蕴涵式20例例1 用用0元谓词将命题符号化元谓词将命题符号化 (1) 墨西哥位于南美洲墨

11、西哥位于南美洲 (2) 是无理数仅当是无理数仅当 是有理数是有理数 (3) 如果如果23，则，则33，q：3y，G(x, y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x) G(y)L(x,y) (2) 令令F(x)：x是无理数，是无理数，G(y)：y是有理数，是有理数，L(x,y)：xy x(F(x)y(G(y) L(x,y)或者或者 x y(F(x) G(y) L(x,y)例4 在一阶逻辑中将下面命题符号化 (1) 没有不呼吸的人 (2) 不是所有的人都喜欢吃糖23实例4解解 (1) F(x): x是人是人, G(x): x呼吸呼吸x(F(x)G(x) x(F(x)

12、G(x)(2) F(x): x是人是人, G(x): x喜欢吃糖喜欢吃糖 x(F(x)G(x)x(F(x)G(x)例5 设个体域为实数域, 将下面命题符号化 (1) 对每一个数x都存在一个数y使得xy (2) 存在一个数x使得对每一个数y都有xy24实例5解解 L(x,y):xy(1) x yL(x,y)注意注意: 与与 不能随意交换不能随意交换显然显然(1)是真命题是真命题, (2)是假命题是假命题(2) x yL(x,y) (4) 没有不爱吃糖的人25练习2 (5) 任何两个不同的人都不一样高任何两个不同的人都不一样高 (6) 不是所有的汽车都比所有的火车快不是所有的汽车都比所有的火车快设

13、设F(x): x是人，是人，G(x): x爱吃糖爱吃糖x(F(x)G(x) 或或 x(F(x)G(x)设设F(x):x是人是人, H(x,y), x与与y相同相同, L(x,y): x与与y一样高一样高 x(F(x)y(F(y)H(x,y)L(x,y) 或或 x y(F(x) F(y)H(x,y)L(x,y)设设F(x):x是汽车是汽车, G(y):y是火车是火车, H(x,y):x比比y快快 x y(F(x) G(y)H(x,y) 或或 x y(F(x) G(y)H(x,y)第二组 (1) 消去量词等值式 设D =a1, a2, , an xA(x) A(a1)A(a2)A(an) xA(x

14、) A(a1)A(a2)A(an)265.1 一阶逻辑等值式与置换规则例3 设个体域D=a,b,c, 消去下述公式中的量词: (1) xy(F(x)G(y)27实例解法一解法一 x y(F(x)G(y) ( y(F(a)G(y) ( y(F(b)G(y) ( y(F(c)G(y) (F(a)G(a) (F(a)G(b) (F(a)G(c) (F(b)G(a) (F(b)G(b) (F(b)G(c) (F(c)G(a) (F(c)G(b) (F(c)G(c) 解法二解法二 x y(F(x)G(y) x(F(x)yG(y) 辖域缩小等值式辖域缩小等值式 x(F(x)G(a) G(b) G(c) (

15、F(a)G(a) G(b) G(c) (F(b)G(a) G(b) G(c) (F(c)G(a) G(b) G(c)28实例(2) x yF(x,y) x yF(x,y) x(F(x,a) F(x,b) F(x,c) (F(a,a) F(a,b) F(a,c) (F(b,a) F(b,b) F(b,c) (F(c,a) F(c,b) F(c,c)设个体域D=a,b,c, 消去下述公式中的量词29求前束范式的实例(3) xF(x)y(G(x,y)H(y)或或 xF(x)y(G(z,y)H(y) 代替规则代替规则 x y(F(x)(G(z,y)H(y) 解解 xF(x)y(G(x,y)H(y) z

16、F(z)y(G(x,y)H(y) 换名规则换名规则 z y(F(z)(G(x,y)H(y) 辖域收缩扩张辖域收缩扩张规则（这个地方注意是规则（这个地方注意是 z ，要与后面的相同要与后面的相同）2. 定义定义6.5 幂集幂集：P(A)= x | x A 实例：实例：P()=, P()=, 计数：如果计数：如果 |A|=n，则，则 |P(A)|=2n.幂集里面的元素都是集合！切记！31文氏图集合运算的表示集合运算的表示ABABABABABA BA BABA BA1. 集合的广义并与广义交 定义6.10 广义并 A = x | z ( zA xz ) 广义交 A= x | z ( zA xz )

17、实例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a运算一次减少一层括号32广义运算2. 广义运算的性质 (1) =，无意义 (2) 单元集x的广义并和广义交都等于x (3) 广义运算减少集合的层次（括弧减少一层） (4) 广义运算的计算：一般情况下可以转变成初级运算 A1, A2, , An=A1A2An A1, A2, , An=A1A2An 例例1 A=a,a,b，计算，计算A (AA). 解：解： A (AA) = a,b ( a,ba) = (a b) (a b) a) = (a b) (b a) = b33关于广义运算的说

18、明 1判断下列命题是否为真 (1) 集合集合 (2) 是集合，不能用这个符号 (3) (4) 元素集合 (5) a, b a, b, c, a, b, c (6) a, b a, b, c, a, b (7) a, b a, b, a, b (8) a, b a, b, a,b a,b有两层，不适合34练习1解解 (1)、(3)、(4)、(5)、(6)、(7)为真，其余为假为真，其余为假.定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，且 AB = | xAyB.35笛卡儿积例例1 A=1,2,3, B=a,b,c A B =, B A =, A=, B= P(A) A = , /这里这

19、里 尖括号尖括号里面的是里面的是属于属于集合的元素集合的元素 所以与空集相乘为空集所以与空集相乘为空集 P(A) B = 证明 A(BC) = (AB)(AC)36性质证明证证 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).例4 A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：37实例 0010000011000011RM例7 设R=, 则 R1 = , R = R2,3 = , R1 = 2,3 R = R3 = 2 38实例定理7.2 设F, G, H是任意的关系, 则(

20、1) (FG)H = F(GH)(2) (FG)1 = G1F139关系运算的性质证证 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)例例 8 设设A = a,b,c,d, R = , 求求R的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示. 0000000010100101000010000101001000001000010100102M40 0000100001010010M解解 R 与与 R2的关系矩阵分别是：的关系

21、矩阵分别是：幂的求法幂的求法R3和R4的矩阵是：因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=， R3=R5=R7=R0的关系矩阵是 41幂的求法 0000000010100101,000000000101101043MM 10000100001000010MR0, R1, R2, R3,的关系图如下图所示. 42关系图R0R1R2=R4=R3=R5=例9 设A=a,b,c,d, R=, R和r(R), s(R), t(R)的关系图如下图所示. 43实例Rr(R)s(R)t(R)等价类 定义7.16 设R为非空集合A上的等价关系, xA，令 xR = y | yAxRy称x

22、R 为x关于R的等价类, 简称为x的等价类, 简记为x或 x44 等价类的性质设R是非空集合A上的等价关系, 则 (1) xA, x是A的非空子集 (2) x,yA, 如果 xRy, 则 x = y (3) x,yA, 如果 x y, 则 x与y不交 (4) x | xA=A定义7.17 设 R 为非空集合A上的等价关系, 以 R 的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA实例 设 A=1,2,8，A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6A关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/

23、EA = 1,2,845商集与划分定义定义7.18 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足满足:(1) (2) x y(x,y xyxy=)(3) = A则称则称是是A的一个的一个划分划分, 称称中的元素为中的元素为A的的划分块划分块. 例10 设 A a, b, c, d , 给定 1, 2, 3, 4, 5, 6如下： 1= a, b, c , d 2= a, b, c , d 3= a , a, b, c, d 4= a, b, c 5=, a, b , c, d 6= a, a , b, c, d 则 1和 2是A的划分, 其他都不是A的划分. 46划分实

24、例47例例11 给出给出 A1,2,3上所有的等价关系上所有的等价关系实例实例1 123 31 1 123 351 123 321 123 341 123 331对应对应 EA, 5 对应对应 IA, 2, 3 和和 4分别对应分别对应 R2, R3和和 R4. R2=,IA R3=,IA R4=,IA解解 先做出先做出A的划分的划分, 从左到右分别记作从左到右分别记作 1, 2, 3, 4, 5.2设A=1,2,3,4，在AA上定义二元关系R： ,R x+y = u+v，求R导出的划分. 48练习2 A A=, , , , , , , , , , , , , , 根据根据 中的中的 x+y

25、= 2, 3, 4, 5, 6, 7, 8 将将A划分成等价类：划分成等价类： A/R=, , , , , , , , , , , , , , 1. 证明证明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理过程推理过程 结论结论2. 证明证明R在在A上对称上对称 任取任取， R . R 前提前提 推理过程推理过程 结论结论49关系性质的证明方法3. 证明R在A上反对称 任取， RR . x = y 前提 推理过程 结论4. 证明R在A上传递 任取,， RR . R 前提 推理过程 结论50关系性质的证明方法例1 设A=1,2,3, B=a,b, 求BA.51实例解解BA= f

26、0, f1, , f7, 其中其中 f0 = , f1 = , f2 = , f3 = , f4 = , f5 = , f6 = , f7 = ,例例2 判断下面函数是否为单射判断下面函数是否为单射, 满射满射, 双射的双射的, 为什么为什么?(1) f:RR, f(x) = x2+2x 1(2) f:Z+R, f(x) = lnx, Z+为正整数集为正整数集(3) f:RZ, f(x) = x (4) f:RR, f(x)=2x+1(5) f:R+R+, f(x)=(x2+1)/x, 其中其中R+为正实数集为正实数集. 解(1) f:RR, f(x)=x2+2x1 在x=1取得极大值0. 既

27、不是单射也不是满射的(2) f:Z+R, f(x)=lnx 是单调上升的, 是单射的. 但不满射, ranf=ln1, ln2, .(3) f:RZ, f(x)= x 是满射的, 但不是单射的, 例如f(1.5)=f(1.2)=1(4) f:RR, f(x)=2x+1 是满射、单射、双射的, 因为它是单调函数并且ranf=R(5) f:R+R+, f(x)=(x2+1)/x 有极小值 f(1)=2. 该函数既不是单射的也不是满射的例3 对于给定的集合A和B构造双射函数 f:AB(1) A=P(1,2,3), B=0,11,2,3(2) A=0,1, B=1/4,1/2(3) A=Z, B=N(

28、4) , B=1,153实例23,2 A(1) A=,1,2,3,1,2,1,3,2,3,1,2,3. B=f0, f1, , f7, 其中 f0=, f1=, f2=, f3=,f4=, f5=,f6=, f7=,. 令 f:AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f754解答155(2) 令令 f:0,11/4,1/2, f(x)=(x+1)/4 01202)(,NZxxxxff：(4) 令令 f: :/2,3/2 1,1 f(x) = sinx 解答解答2(3) 将将

29、Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z： 0 11 2 2 3 3 N： 0 1 2 3 4 5 6 这种对应所表示的函数是：这种对应所表示的函数是：设R是A上的等价关系, 令 g:AA/R g(a)=a, aA称 g 是从 A 到商集 A/R 的自然映射 不同的等价关系确定不同的自然映射, 恒等关系确定的自然映射是双射, 其他自然映射一般来说只是满射. 例如 A=1,2,3, R=,IA g: AA/R, g(1)=g(2)=1,2, g(3)=3解 (1) 由T=B, A, S, E, L知 cardT=5(2) 由B=, 可知 cardB=0.(3

30、) 由|A|=4 可知 cardC=cardP(A)=|P(A)|=24=16.57实例例例9 求下列集合的基数求下列集合的基数(1) T=x | x是单词是单词“BASEBALL”中的字母中的字母(2) B=x | xRx2=92x=8(3) C=P(A), A=1, 3, 7, 11基数就是不重复的元素的个数基数就是不重复的元素的个数1. 证明 f:AB是满射的方法: 任取 yB, 找到 x (即给出x的表示)或者证明存在xA，使得f(x)=y. 2. 证明 f:AB是单射的方法 方法一 x1,x2A, f(x1)=f(x2) x1=x2 推理前提 推理过程 推理结论 方法二 x1,x2A

31、, x1x2 f(x1)f(x2) 推理前提 推理过程 推理结论 3. 证明 f:AB不是满射的方法： 找到 yB, yranf 4. 证明 f:AB不是单射的方法：找到 x1,x2A, x1x2, 且 f(x1)=f(x2)58证明方法59练习练习66已知已知A=n7|nN, B=n109|nN, 求下列各题：求下列各题：(1) Card A(2) Card B(3) card (A B)(4) card (A B)解解 (1) 构造双射函数构造双射函数 f:NA, f(n)=n7 , 因此因此 card A=0(2) 构造双射函数构造双射函数 g:NA, g(n)=n109, 因此因此ca

32、rd B=0(3) 可数集的并仍旧是可数集，因此可数集的并仍旧是可数集，因此card(A B) 0, 但是但是 card(A B) card A=0, 从而得到从而得到 card(A B)= 0. (4) 因为因为7与与109互素，互素，card(A B)=n7 109 | n N，与与(1) 类似得到类似得到 card(A B)= 060运算表：表示有穷集上的一元和二元运算运算表：表示有穷集上的一元和二元运算 运算表运算表 二元运算的运算表二元运算的运算表 一元运算的运算表一元运算的运算表1设 运算为Q上的二元运算， x, yQ, x y = x+y+2xy, (1) 判断 运算是否满足交换

33、律和结合律，并说明理由.(2) 求出 运算的单位元、零元和所有可逆元素的逆元.61练习1(1) 运算可交换，可结合运算可交换，可结合. 任取任取 x, y Q, x y = x+y+2xy = y+x+2yx = y x,任取任取 x, y, z Q, (x y) z = (x+y+2xy)+z+2(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x+(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz62(2) 设设 运算的单位元和零元分别为运算的单位元和零元分别为 e 和和 ，则，则对于任对于任意意 x 有有

34、x e = x 成立，即成立，即 x+e+2xe = x e = 0 由于由于 运算可交换，所以运算可交换，所以 0 是幺元是幺元.对于任意对于任意 x 有有x = 成立，即成立，即 x+ +2x = x+2x = 0 = 1/2 给定给定 x，设，设 x 的逆元为的逆元为 y, 则有则有 x y = 0 成立，即成立，即 x+y+2xy = 0 (x 1/2 )因此当因此当x 1/2时时， 是是x的逆元的逆元. xxy21 xx21 解答解答632下面是三个运算表下面是三个运算表(1) 说明那些运算是可交换的、可结合的、幂等的说明那些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的

35、单位元、零元、所有可逆元素的逆元求出每个运算的单位元、零元、所有可逆元素的逆元练习练习2(1) * 满足交换律，满足结合律，不满足幂等律. 不满足交换律，满足结合律，满足幂等律. 满足交换律，满足结合律，不满足幂等律.(2) * 的单位元为b，没有零元， a1=c, b1=b,c1=a 的单位元和零元都不存在，没有可逆元素. 的单位元为 a，零元为c，a1=a，b, c不是可逆元素. 说明：关于结合律的判断需要针对运算元素的每种选择进行验证，若|A|=n，一般需要验证n3个等式.单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性.64解答65)()()(),()(|)(v

36、vNvNvvuGEvuGVuuvNv 的的闭闭邻邻域域的的邻邻域域)(|)(关关联联与与veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的的闭闭邻邻域域的的邻邻域域的的先先驱驱元元集集的的后后继继元元集集8. 邻域与关联集邻域与关联集 v V(G) (G为无向图为无向图) （领域是相关联的点，关联集是相关联的边）v 的关联集的关联集 v V(D) (D为有向图为有向图)相关概念相关概念66例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余顶点度数均小于

37、度顶点，其余顶点度数均小于3，问问G的阶数的阶数n为几？为几？解解 本题的关键是应用握手定理本题的关键是应用握手定理. 设除设除3度与度与4度顶点外，还有度顶点外，还有x个顶点个顶点v1, v2, , vx， 则则 d(vi) 2，i =1, 2, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 阶数阶数 n 4+4+3=11. 握手定理应用握手定理应用1 . V=v1, v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数列 2. V=v1, v2, , vn为有向图D的顶点集， D的度数列：d(v1), d(v2), , d(vn)

38、D的出度列：d+(v1), d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非负整数列d=(d1, d2, , dn)是可图化的，是可简单图化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简单图化的，特别是后者也不是可图化的67图的度数列定义14.5 设G1=, G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2, 对于vi,vjV1, (vi,vj)E1 当且仅当 (f(vi),f(vj)E2 （E1 当

39、且仅当 E2 )并且, (vi,vj)（）与 (f(vi),f(vj)（）的重数相同，则称G1与G2是同构的，记作G1G2. (即简单说来就是可以让点一一对应即简单说来就是可以让点一一对应)68图的同构l 图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.l 能找到多条同构的必要条件，但它们全不是充分条件：能找到多条同构的必要条件，但它们全不是充分条件： 边数相同，顶点数相同边数相同，顶点数相同; 度数列相同度数列相同; 对应顶点的关联集及邻域的元素个数相同，等等对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构若破坏必要条件，则两图不

40、同构l 判断两个图同构是个难题判断两个图同构是个难题69例例2 画出画出K4的所有非同构的生成子图的所有非同构的生成子图实例实例702. 证明下图不是哈密顿图证明下图不是哈密顿图. (破坏必要条件破坏必要条件)方法一方法一. 利用定理利用定理15.6，取取 V1 = a, c, e, h, j, l，则，则 p(G V1) = 7 |V1| = 6 练习练习 2方法二方法二. G为二部图，互补顶点子集为二部图，互补顶点子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m， |V1| = 6 7 = |V2|. 方法三方法三. 利用可能出现在哈密顿

41、回路上的边至少有利用可能出现在哈密顿回路上的边至少有n(n为阶数为阶数)条条这也是哈密顿图的一个必要条件，记为（这也是哈密顿图的一个必要条件，记为（ ）. 此图中，此图中，n = 13，m = 21. 由于由于h, l, j 均为均为4度顶点，度顶点，a, c, e为为3度顶点，且它们关联边互不相同度顶点，且它们关联边互不相同. 而在哈密顿回路上，而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有每个顶点准确地关联两条边，于是可能用的边至多有21 (3 2+3 1) = 12. 这达不这达不到（到（ ）的要求）的要求. 例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 71例题解 解本题用树的性质m=n1，握手定理. 设有x片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n1) = 2(2+x) = 13+22+x解出x = 3，故T有3片树叶.T 的度数列应为 1, 1, 1, 2, 2, 3，易知3度顶点与1个2度顶点相邻与和2个2度顶点均相