《离散数学》总复习

《离散数学》总复习黄玉yuhua2k@163.com南航计算机学院A12-1161.主范式、集合、布尔格(有补分配格)运算2.命题符号化+命题/谓词逻辑推理3.前束范式4.元素与集合、集合与集合的关系(判断,证明)5.排列组合、容斥原理、递推方程6.关系合成、函数复合、置换乘法7.等价关系(等价类、商集、划分、自然映射)8.偏序集(偏序关系、覆盖、哈斯图)、格9.同构=同态∩双射10.代数系统及其性质(判断)11.域=整环∩除环0.重要概念:幂集,笛卡积,闭包,积代数,循环群;0.重要概念:生成子图,自补图,自对偶图,割集12.握手定理13.邻接矩阵14.最短路径(标号法)与关键路径(最长路径)15.图的类型(二部,欧拉,哈密顿,平面,树)判别16.平面图欧拉公式：n

m+r=217.树的重要性质：m=n-118.最小生成树(避圈法)、基本回路/割集系统19.Huffman算法(最优二元树/最佳前缀码)20.二/多项式定理与组合恒等式21.分治算法的常用递推公式第1章命题逻辑1.1命题符号化及联结词（联结词是基础）1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式（主范式演算是重点）1.6推理理论（重点）联结词与复合命题(小结)联结词优先级:(),

,

,

,

,

同级按从左到右的顺序进行

pq

pp∧qp∨qp

qp

q0010011011011010001001101111基本复合命题的真值1.3命题逻辑等值演算等值式定义：(A

B1)(A

B)（重点）基本等值式(重点) 双重否定律

:

A

A等幂律：

A

A

A,A

A

A交换律:A

B

B

A,A

B

B

A结合律:(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律:A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律:

(A

B)

A

B

(A

B)

A

B基本等值式（续）吸收律:A

(A

B)

A,A

(A

B)

A零律:A

1

1,A

0

0同一律:A

0

A,

A

1

A排中律:A

A

1矛盾律:A

A

0蕴涵等值式:A

B

A

B等价等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等价否定等值式:A

B

A

B归谬论:(A

B)

(A

B)

A1.4复合联结词（重要的非重点）与非式:p

q(p

q)；或非式:p

q(p

q)习题1.14，1.10(4)(5)异或：p

q

p

q

(p

q)

p

q

p

qA

p1

p2

…

pn,偶数个命题变项赋值为1Þ(A0),奇数个命题变项赋值为1Þ(A1);B

q1

q2

…

qn,偶数个命题变项赋值为0Þ(A1),奇数个命题变项赋值为0Þ(A0).习题1.221.5主范式（重点）成真赋值i对应主析取范式的极小项mi；成假赋值j对应主合取范式的极大项Mj。命题公式有几个成真赋值，主析取范式就是几个极小项相或(

)；命题公式有几个成假赋值，主合取范式就是几个极大项相与(

)。例1.31，1.32分配律Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)习题1.12(1),1.13(1)。五71.6

命题逻辑推理（重点）“推理正确”定义：(A®B1)(AÞB)（重点）A

Þ(AÚB) 附加律(AÙB)Þ

A

化简律(A®B)ÙA

Þ

B

假言推理(A®B)ÙØB

Þ

ØA

拒取式(AÚB)ÙØB

Þ

A

析取三段论(A®B)Ù(B®C)Þ(A®C) 假言三段论(A«B)Ù(B«C)Þ(A«C) 等价三段论(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD) 构造性二难(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难(特殊形式)(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难习题1.18,1.21,1.17(2)。六1注意事项1：命题只有能确定真假(但不能可真可假)的陈述句才是命题.不管是正确的观点,还是错误的观点,都是命题.猜想和预言是命题,如哥德巴赫猜想.感叹句,祈使句,疑问句都不是命题.陈述句中的悖论以及判断结果不惟一确定的也不是命题.有些简单命题貌似复合命题,要注意区分.题1(15)注意事项2：蕴涵联结词“

”p

q的逻辑关系:p为q的充分条件，q为p的必要条件.“如果p,则q”的多种表述方式：(1)若p,就q.(2)只要p,就q.(3)p仅当q.(4)只有q

才p.(5)除非q,才p.(6)除非q,否则非p.p

q为假当且仅当p为真q为假，即当p为假时，p

q为真(不管q为真,还是为假);当q为真时，p

q为真(不管p为真,还是为假).习题1.5(6)(7)了解概念、掌握方法真值表、命题公式类型所有等值的含n个命题变项的公式对应同一个n元真值函数F:{0,1}n

{0,1}；哑元最小联结词组对偶式与对偶原理简单析取式、简单合取式析取范式与合取范式附加前提证明法、反证法第2章一阶逻辑2.1 一阶逻辑基本概念（量词是关键）2.2 一阶逻辑公式、解释及分类2.3 一阶逻辑等值式、前束范式（重点）2.4 一阶逻辑推理理论（重点）一阶逻辑与命题逻辑关系一阶逻辑将命题(公式)拆分为个体词、谓词、量词(

、)。谓词是核心，没有谓词，不构成命题；量词是关键。个体词（元素）分为个体常项和个体变项.个体域（集合）:个体变项的取值范围.

全总个体域:宇宙间一切事物组成一阶逻辑≈命题逻辑+量词

xF(x)

x

F(x),

xF(x)

x

F(x);

xF(x)

x

F(x),

xF(x)

x

F(x)2.3一阶逻辑等值式基本等值式（重点）

:命题逻辑中16组基本等值式的代换实例消去量词等值式设D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)量词辖域收缩与扩张等值式

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)量词分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)注意事项1：前束范式（重点）设A为一个一阶逻辑公式,若A具有如下形式

Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1

i

k)为

或

，B为不含量词的公式.1）对

无分配律，

对

无分配律

xA(x)

xB(x)

x

y(A(x)

B(y))

x

y(A(x)

B(y))

xA(x)

xB(x)2）变量冲突，有一个要换名.3）x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B习题2.21,2.15(1),2.14(1)。四102.4一阶逻辑推理理论（重点）重要的推理定律第一组命题逻辑推理定律代换实例第二组由基本等值式生成（置换规则）第三组

xA(x)

xB(x)

x(A(x)

B(x))

x(A(x)

B(x))

xA(x)

xB(x)(12)

全称量词消去规则（简记为UI规则或UI）(13)

全称量词引入规则（简记为UG规则或UG）(14)存在量词引入规则（简记为EG规则或EG）(15)存在量词消去规则（简记为EI规则或EI）注:必须先消去存在量词,后消去全称量词.七1第三版:习题2.22,2.16,2.19,2.17(1),2.23；例2.18注意事项2：一阶逻辑中命题符号化无特别要求，用全总个体域量词顺序一般不要随便颠倒

x

yA(x,y)

y

xA(x,y)全称量词一般对应“”存在量词一般对应“”习题2.3(2)(5)(6)了解有限个体域,无限个体域;谓词常项,谓词变项,一元谓词,多元谓词(n元谓词,n

2),0元谓词,原子公式;项字母表包含：1)个体常项,2)个体变项,3)函数符号,4)谓词符号,5)量词符号(

,),6)联结词符号(

,

,

,

,),7)括号与逗号.指导变元，辖域，约束出现，自由出现闭式:不含自由出现的个体变项的公式.解释I包含：(a)非空个体域DI,(b)DI中一些特定元素集,(c)DI上特定函数集,(d)DI上特定谓词集.闭式在任何解释下都是命题，不是闭式的公式在某些解释下也可能是命题.公式类型.换名规则与代替规则第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算（重点）3.3集合中元素的计数（容斥原理是重点）3.1集合的基本概念元素x与集合A的关系：属于x

A，不属于x

A集合A与集合B的关系：习题3.2,3.8,3.12,3.16

包含(子集)A

B,不包含A⊈B

相等A=B,不相等A

B

真包含A

B,

不真包含A

B重要概念：集合A的幂集P(A)={x|x

A}。如果|A|=n，则|P(A)|=2n.习题3.14(4),3.18习题3.3,3.9,3.113.2集合的基本运算（重点）集合运算符，，，分别对应 联结词∧,∨，，A

B=A

B=A

(A

B)A

B=(A

B)

(B

A)=(A

B)(A

B)

A

B

A

A

BA

B

A

B=B

A

B=A

A

B=

A

B=

A

B=A习题3.17,3.16；例3.17，3.18。四3，4；六4集合运算的文氏图表示习题3.4,3.15(2)集合运算的算律（重点）

交换A

B=B

AA

B=B

AA

B=B

A结合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)幂等A

A=AA

A=A

与

与

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A吸收律的前提：、可交换集合运算的算律（续）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C双重否定

A=A

E补元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=3.3集合中元素的计数容斥原理及其推论（重点）习题3.6,3.18,3.19。五10注意1）0是自然数.2）对于任何集合A和元素x(可以是集合)，

x

A和x

A两者成立其一，且仅成立其一.3）和

是不同层次的问题.4）空集是任何集合的子集.5）在给定问题中，全集E包含任何集合，即

A(A

E)了解概念、掌握方法1）集合的表示法：列元素法A={a,b,c,d}谓词表示法B={x|P(x)}.习题3.10(4)2）文氏图与文氏图法.习题3.63）集合A的基数cardA=|A|=n4）证明

X

Y命题演算法包含传递法等价条件法反证法并交运算法5）证明X=Y命题演算法等式代入法反证法运算法第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算（重点）4.3关系的性质（基础）4.4关系的闭包4.5等价关系和偏序关系（重点）4.6函数的定义和性质4.7函数的复合和反函数4.1集合的笛卡儿积和二元关系1）重要概念：集合A与B的笛卡儿积A

B={<x,y>|x

A

y

B}.若|A|=m,|B|=n,则|A

B|=mn分配律A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)A

=

B=

(A

C=B

D)(A,B,C,D非空)(A=B)

(C=D)2）从A到B的二元关系R

A

B.A×B的子集有2mn个，所以A到B有2mn个不同的二元关系.注：笛卡儿积不适合交换律和结合律.如<x,y>∈R,可记作xRy.A上重要关系从A到A的二元关系叫做A上的二元关系.空关系

是A上的关系全域关系EA={<x,y>|x∈A∧y∈A}=A×A

恒等关系IA={<x,x>|x∈A}小于等于关系LA={<x,y>|x,y∈A∧x≤y},A

R整除关系DA={<x,y>|x,y∈A∧x整除y},A

Z包含关系R

={<x,y>|x,y∈A∧x

y},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.4.2关系的运算逆R

1={<y,x>|<x,y>

R}合成R∘S={<x,z>|

y(<x,y>

S

<y,z>

R)}(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)

1=G

1∘F

1.幂运算(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn∘R习题4.13。五14.3关系的性质（基础，重中之重）(1)若

x∈A,<x,x>

R,则称R在A上是自反的.(2)若

x∈A,<x,x>

R,称R在A上是反自反的.(3)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.(4)若

x,y∈A,<x,y>∈R∧<y,x>∈R→x=y,则称R为A上的反对称关系.(5)若

x,y,z∈A,<x,y>∈R∧<y,z>∈R→<x,z>∈R,则称R是A上的传递关系.习题4.4关系性质判别

自反反自反对称反对称传递表达式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk,则从xi到xk有边

恒等关系IA既是等价关系,又是篇序关系。运算与性质的关系（了解）自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××4.5等价关系和偏序关系（重点）(1)等价关系、等价类、商集、划分、自然映射等价关系:同时满足自反、对称和传递的关系.若<x,y>∈等价关系R,称x等价于y,记做x～y.x(x∈A)关于集合A上等价关系R的等价类

[x]R

={y|y∈A∧xRy}.以集合A上的等价关系R的所有等价类为元素的集合称为A关于R的商集,记做A/R.商集A/R就是A的一个划分;等价关系与商集、划分一一对应.习题4.5，4.15，4.24。五2；六14(2)偏序关系,覆盖,偏序集与哈斯图偏序关系：同时满足自反、反对称和传递的关系,记作≼.如果<x,y>∈偏序关系≼,则记作x≼y.x≺y且不存在z

A使得x≺z≺y,则称y覆盖x.集合A和A上的偏序关系≼一起叫做偏序集,记作<A,≼>.习题4.6，4.16。五3哈斯图：简化关系图。特点（注意）：每个结点没有环，位置低的元素的顺序在前，具有覆盖关系的两个结点之间才连边.特定元素：区分最小(大)元与极小(大)元；下界、上界、下确界、上确界注意事项：特定元素对于有穷集，极小元和极大元必存在，可能存在多个.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是极小元;最大元一定是极大元.反之不对.

孤立结点既是极小元，也是极大元.下界、上界、下确界、上确界不一定存在.下界、上界存在不一定惟一.下确界、上确界如果存在，则惟一.集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.4.6函数

x∈domF都存在唯一的y∈ranF使xFy成立,则称二元关系F为函数.对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的值.所有从A到B的函数的集合记作BA,读作“B上A”，符号化表示为BA

={f|f：A→B}函数f：A→B，domF=A，|f|=|A|，ranF

B.计数：|A|=m,|B|=n,且m,n>0,|BA|=nm.B

={

}.A≠

,则

A=

.恒等函数IA(x)=x习题4.22了解有序对<x,y>，有序n元组<x1,x2,…,xn>.关系矩阵、关系图;关系的定义域、值域和域.习题4.2关系F在集合A上的限制F↾A={<x,y>|xFy

x

A}

F.A在F下的像F[A]=ran(F↾A)ranF.习题4.3R的自反闭包r(R)=R∪R0,对称闭包s(R)=R∪R

1,传递闭包t(R)=R∪R2∪R3∪…。习题4.14Mr

=M+E，Ms

=M+M’，Mt

=M+M2+M3+…(不)可比。全序(线序)关系：所有元素可比；良序集单射,满射,双射；常函数、单调函数；特征函数.g(a)=[a]是从A到商集A/R的自然映射.习题4.10,4.18函数复合与反函数良序集：任意非空子集都有最小元素的全序集第5章代数系统的一般性质5.1二元运算及其性质（基础）5.2代数系统及其子代数和积代数（重要概念积代数）5.3代数系统的同态与同构（重点）5.1一、二元运算,代数系统,封闭性函数f：S×S→S称为集合S上的二元运算,也称S对f

封闭;即

x,y∈S,f(x,y)∈S.函数f：S→S称为集合S上的一元运算;即

x∈S,f(x)∈S.函数的性质：运算结果唯一性.非空集合S和S上k个一元或二元运算f1,f2,…,fk

组成的系统称为一个代数系统,简称代数，记做

V=<S,f1,f2,…,fk>.习题5.8，5.7二元运算可能的性质

x,y,z∈S

(1)交换律：

x∘

y=y∘x.(2)结合律：(x∘

y)∘

z=x∘

(y∘z).

(3)幂等律：

x∘

x=x.(4)消去律：若x∘

y=x∘

z,且x不是零元,则y=z;

若y∘

x=z∘

x,且x不是零元，则y=z.

无零因子：(x∘y=

x=

∨y=)

消去律.

(1)∘

运算对∗运算满足分配律：

z∘(x∗y)=(z∘

x)∗(z∘

y).(2)∘

和∗运算满足吸收律(前提∘

和∗都可交换)：

x∘

(x∗y)=x；x∗(x∘

y)=x.一些二元运算的性质集合运算交换律结合律幂等律消去律Z,Q,R,C普通加法+有有无有普通乘法

有有无有Mn(R)矩阵加法+有有无有矩阵乘法

无有无无P(B){0,1}并

(或∨)有有有无交

(与∧)有有有无对称差

(

,

)有有无有AA函数复合

无有无无Zn模乘

有有无无Z+lcm,gcd有有有无{0,1}与非

,或非有无无无一些二元运算的性质

集合运算分配律吸收律Z,Q,R,CMn(R)普通加法+与乘法

矩阵加法+与乘法

对+可分配无+对

不分配P(B){0,1}并

与交(或∨和与∧)

对

可分配有

对

可分配交

与对称差(与∧和排斥或)

对

可分配无

对

不分配Zn模加

与模乘

对

可分配无

对

不分配全集E并

与笛卡儿积

对可分配无交

与笛卡儿积

对可分配Z+lcm与gcd有有二元运算可能的特异元素

x∈S,(e∘x=x)

(x∘e=x),称e为单位元(幺元)(惟一性).

x∈S,(θ∘x=θ)

(x∘θ=θ),称θ是零元(惟一性).注:只有左或右单位元(零元),不称为有单位元(零元).(y∘x=e)

(x∘y=e),称y为x的逆元,并称x是可逆元素.注:逆元的存在以幺元的存在为前提.e-1=e.对于可结合的二元运算,可逆元素x只有惟一的逆元,记作x

1.

习题5.14，5.15，5.3，5.12，5.2一些二元运算的特异元素集合运算幺元e零元θ逆元x-1(e-1=e)Z,Q,R,C普通加法+0无

x普通乘法

101/x(x≠0)Mn(R)矩阵加法+0阵无

x矩阵乘法

单位阵In0阵x

1(逆阵,x可逆)P(B){0,1}并

(或∨)

(0)B(1)

-1=(0-1=0)交

(与∧)B(1)

(0)B-1=B(1-1=1)

(

)

(0)无xAA函数复合

IA无双射逆元=反函数Zn模乘

10x,n互质,x有逆元模加

0无n

x(0-1=0)Z+lcm1无1-1=1gcd无1无{0,1}等价

1无x由运算表判别算律的一般方法交换律：运算表关于主对角线对称幂等律：主对角线元素排列与表头顺序一致消去律：所在的行与列中没有重复元素单位元:所在行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成A的可逆元：a所在的行中某列(比如第j列)元素为e，且第j行

i列的元素也是e，那么a

与第j个元素互逆结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立习题5.1，5.95.2代数系统及其子代数和积代数重要概念：<S1,o>和<S2,>是代数系统，积代数<S1

S2,∙>有：<x1,y1>∙<x2,y2>=<x1ox2,y1

y2>.题5.10(1)若o

和

运算是可交换的，那么∙运算也是可交换的

(2)若o

和

运算是可结合的，那么∙运算也是可结合的

(3)若o

和

运算是幂等的，那么∙运算也是幂等的

(4)若

o

和

运算分别具有单位元

e1

和e2，那么∙运算也具有单位元<e1,e2>(5)若o

和

运算分别具有零元1和2，那么∙运算也具有零元<

1,

2>(6)若x关于

o

的逆元为x

1,y关于

的逆元为y1，那么<x,y>关于∙运算也具有逆元<x1,y1>5.3代数系统的同态与同构(重点)V1=<S1,∘>和V2=<S2,>是代数系统,f:S1

S2,x,y∈S1,

f(x∘y)=f(x)f(y),则称f为V1到V2的同态(映射).如果同态f是满射，则称为满同态，这时称V2是V1的同态像，记作V1

V2；如果同态f是双射，则称为同构，记作V1

V2.习题5.6，5.5。六13，15满同态保持运算的算律及特异元素V1=<S1,∘,∗>和V2=<S2,o’,∗’

>是代数系统，f：V1

V2是满同态，那么(1)若o运算是可交换的（可结合、幂等的），则o’运算也是可交换的（可结合、幂等的）.(2)若o运算对∗运算是可分配的，则o’运算对∗’运算也是可分配的；若o

和∗运算是可吸收的，则o’和∗’运算也是可吸收的。(3)若e为o

运算的单位元，则f(e)为o’运算的单位元.(4)若

为o

运算的零元，则f(

)为o’运算的零元.(5)设u

V1，若u1是

u

关于o运算的逆元，则f(u

1)

是

f(u)关于o’运算的逆元。注意事项1）集合S上的二元运算就是S×S→S的二元函数.集合S上的一元运算就是S→S的一元函数.2）e-1=e.当|S|

2，单位元与零元是不同的，零元无逆元；当|S|=1时，这个元素既是单位元也是零元.3）子代数B和原代数S含有相同的代数常数4）同态映射保持运算的算律及特异元素仅在满同态时成立，如果不是满同态，那么相关性质在同态像中成立.

同态映射不一定能保持消去律成立.了解运算表代数系统的载体，成分，代数常数同类型与同种代数系统子代数和原代数是同种的代数系统最大的子代数就是V本身.代数常数(对运算封闭)构成最小的子代数.最大和最小子代数称为平凡的子代数.真子代数.习题5.4零同态、单(自)同态、(满)自同态和自同构.第6章几个典型的代数系统6.1半群与群6.2环与域（“域”是重点）6.3格与布尔代数（“布尔代数”是重点）6.1 (半)群|S|≥2<S,o>封闭性结合律含幺所有元有逆元交换律<a>={az}消去律含零代数系统√半群√√交换半群独异点√√√群√√√√√×Abel群√√√√√√×循环群√√√√√√√×重要概念：循环群，n元置换群。(半)群实例(1)<Z+,+>,交换半群,不含幺;<N,+,0>,交换半群,含幺半群,非群;<Z,+,0>,<Q,+,0>,<R,+,0>,<C,+,0>都是交换群;<Z+,*,1>,<N,*,1,0>,<Z,*,1,0>都是交换半群,含幺半群,非群;<Q*,*,1>,<R*,*,1>,<C*,*,1>都是交换群。+是普通加法,*是普通乘法.(2)<Mn(R),+,0n>是交换群;<Mn(R),·,In,0n>是含幺半群,非交换。+和·分别表示矩阵加法和乘法.(3)<P(B),

,,B>,<P(B),

,B,>为交换半群,含幺半群,非群;<P(B),,>为交换群。并

,交

,对称差.(4)<Zn,,0>为交换群;<Zn,

,1,0>为交换半群,含幺半群,非群;<Zn*,

,1>(n为素数)为交换群。模加,模乘(5)<AA,,IA>为含幺半群,非交换,

为函数复合. n元对称群及其子群n元置换群为(非交换)群.注：Q*,R*,C*,Zn*不含0；Zn={0,1,…,n

1}.习题6.2，6.4，6.8掌握重要概念，了解性质设G为群，a∈G，令H={ak|k∈Z}，则H是G的子群，称为由a生成的子群，记作<a>.设G是群，若存在a∈G使得G={ak

|k∈Z}，则称G是循环群，记作G=<a>，称a为G的生成元.习题6.5，6.9(1)若G=<a>是无限循环群，则G只有a和a

1两个生成元.

(2)若G=<a>是n阶循环群，则ar是G的生成元当且仅当r是小于等于n且与n互质的正整数.(1)设G=<a>是循环群，则G的子群仍是循环群.(2)若G=<a>是无限循环群，则G的子群除{e}以外都是无限循环群.(3)若G=<a>是n阶循环群，则对n的每个正因子d，G恰好含有一个d阶子群.6.2环与域<S,+,*>含幺所有元素有逆元交换律分配律消去律|S|≥2环*是半群√+是Abel群√√√√域整环交换环*是交换半群√含幺环*是独异点√除环无零因子环*√*√(θ除外)√n为素数

<Zn,

,

>是域环与域的实例(1)整数集、有理数集、实数集和复数集关于普通加法和乘法构成环，分别称为整数环Z(整环)、有理数环Q(域)、实数环R(域)和复数环C(域).(2)n(n≥2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构成环，称为n阶实矩阵环(含幺环).(3)幂集P(B)关于对称差和交运算构成环(交换环,含幺环).(4)Zn＝{0,1,...,n－1}，

和

分别表示模n加法和乘法，<Zn,

,

>构成环，称为模n的整数环(交换环,含幺环)；n为素数

<Zn,

,

>是域.习题6.6。六56.3格与布尔代数(“布尔代数”是重点)<L,∧,∨>结合律交换律幂等律吸收律封闭性幺元e零元

格∧√√√√√10∨√√√√01布尔格=有补分配格幂集格(|P|=2n)有界格钻石格和五角格是有补格，非分配格。<Z,≤>是链;链是分配格,中间元素无补。6.3格与布尔代数1）设<S,≼>是偏序集，如果

x,y≼S，{x,y}都有最小上界和最大下界，则称S关于偏序≼作成一个格.Sn是n的正因子的集合.D为整除关系,则偏序集<Sn,D>构成分配格.n分解为素数的单次幂相乘时,Sn是布尔格.<P(B),>为B的幂集格

布尔格.<Z,≤>是链；任何一条链(中间元素无补元)都是分配格.2）定理设L是格,则L是分配格当且仅当L不含有与钻石格或五角格同构的子格.小于五元的格都是分配格.3）格L若存在全下界0或全上界1,一定是惟一的.a∧b=0和a∨b=1成立,则称b是a的补元.0,1互补.有界分配格L中元素a若存在补元,则存在惟一的补元.4）有限布尔代数(布尔格=有补分配格)L含有2n个元素.习题6.13，6.12，6.3，6.14，6.7；例6.13。七2；四8注意事项1）两个n元置换的乘法就是函数的复合运算n

元置换的求逆就是求反函数.题6.10。五9.所有的n元置换构成集合Sn，Sn关于置换乘法构成n元对称群.恒等置换(1)是单位元，逆置换σ

1是σ的逆元.n元对称群的子群称为n元置换群.2）x的加法逆元为负元，记作

x.3）全下界0与全上界1互补.了解幂运算子半群与子独异点;子群,真子群,平凡子群;子格积半群与积独异点半群和独异点的同态，格同态.习题6.11Klein四元群有限群，无限群.群G的基数称为群G的阶|G|.元素x的阶(或周期)|x|=k，称x为k阶元.无限阶元.子群判定定理；群G的中心C.k阶轮换与对换格的对偶命题与对偶原理第四部分 图论图论基本定理——握手定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.推论

在任何无向图和有向图中，奇度顶点的个数必为偶数.不存在具有奇数个面且每个面都具有奇数条棱的多面体.习题7.1,7.14,7.19,7.5,7.6;例7.8(六3)。五6第7章图的基本概念7.1无向图及有向图(握手定理、自补图是重点)7.2通路、回路、图的连通性(割集是重点)7.3图的矩阵表示(由有向图的邻接矩阵求通路数和回路数是重点)7.4最短路径(Dijkstra标号法)与关键(最长)路径7.1无向图及有向图重要概念：1）设G1=<V1,E1>,G2=<V2,E2>为两个无向图(有向图),若存在双射函数f:V1

V2,使得对于任意的vi,vj

V1,(vi,vj)

E1（<vi,vj>

E1）当且仅当(f(vi),f(vj))

E2（<f(vi),f(vj)>

E2），并且,(vi,vj)（<vi,vj>）与(f(vi),f(vj))（<f(vi),f(vj)>）的重数相同，则称G1与G2是同构的，记作G1

G2.同构的必要条件,但它们都不是充分条件:①边数相同，顶点数相同②度数列相同(不计度数的顺序)③对应顶点的关联集及邻域的元素个数相同.2）既无平行边也无环的图称为简单图.题7.13n阶无向完全图Kn:边数m=n(n-1)/2,

=

=n-1.题7.7n阶有向完全图:边数m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-1.习题7.93）若G

G且V

=V，则称G

为G的生成子图.4）设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.习题7.8若G

,则称G是自补图.习题7.20，7.12习题7.12，7.10；例7.107.1无向图及有向图(自补图是重点)7.2通路、回路、图的连通性(了解)1）区分初级通路(路径)与简单通路,初级回路(圈)与简单回路.2）u

v(连通,不一定直通).规定u与自身总连通.四6，11，12连通关系R={<u,v>|u,v

V且u

v}是V上的等价关系连通图:平凡图,任意两点都连通的图.G是连通图

p(G)=1连通分支:V关于R的等价类的导出子图.设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.3）D弱连通(连通):基图为无向连通图.D单向连通:

u,v

V，u可达v

或v可达u.D强连通:

u,v

V，u与v相互可达强连通

单向连通

弱连通.习题7.21，7.16(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次的回路.(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次的通路割集（重点）记G

v:从G中删除顶点v及关联的边.G

V

:从G中删除V

中所有顶点及关联的边.G

e:从G中删除边e.G

E

:从G中删除E

中所有边.设无向图G=<V,E>,V

V,若p(G

V

)>p(G)且

V

V

,p(G

V

)=p(G),称V

为G的点割集.若{v}为点割集,称v为割点.V

为点割集且V

⊈V

V

∪V

非点割集.设无向图G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),称E

为G的边割集.若{e}为边割集,称e为割边或桥.E

为边割集且E

⊈E

E

∪E

非边割集.Kn无点割集.n阶零图既无点割集，也无边割集.若G连通，E

为边割集，则p(G

E

)=2.例7.11若G连通，V

为点割集，则p(G

V

)

2.习题7.177.3图的矩阵表示有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令aij(1)为顶点vi邻接到顶点vj边的条数,称(aij(1))m

n为D的邻接矩阵,记作A(D),简记为A.有向图的邻接矩阵（重点）定理设A为n阶有向图D的邻接矩阵,则Al(l

1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.习题7.18推论设Bl=A+A2+…+Al(l

1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.7.4最短路径与关键(最长)路径带权图；最短路径与Dijkstra标号法.习题7.22。五4PERT图(计划评审技术图)与关键路径.关键路径:PETR图中从始点到终点的最长路径vi的最早完成时间TE(vi):从始点v1沿最长路径到vi所需的时间.TE(v1)=0 TE(vi)=max{TE(vj)+wji|vj

-(vi)},i=2,3,,nvi的最晚完成时间TL(vi):在保证终点vn的最早完成时间不增加的条件下,从始点v1最迟到达vi的时间

TL(vn)=TE(vn) TL(vi)=min{TL(vj)-wij|vj

+(vi)},i=n-1,n-2,,1vi的缓冲时间TS(vi)=TL(vi)-TE(vi),i=1,2,,nvi在关键路径上

TS(vi)=0.习题7.23了解n阶图:n个顶点的图.有限图:V,E都是有穷集的图.零图:E=.平凡图:1阶零图.空图:V=.端点(始点,终点),关联次数,环,孤立点,相邻,邻接.邻域(先驱元集∪后继元集),闭邻域,关联集.v的度数d(v)=出度d+(v)+入度d

(v);悬挂顶点,悬挂边;G的最大度

(G),最小度

(G);D的最大出度

+(D),最小出度

+(D),最大入度

(D),最小入度

(D);度数列,出度列,入度列;平行边,重数,多重图;n阶k正则图;子图,母图,真子图,导出子图;连通度.可达矩阵P(D)主对角线上的元素全为1.关联矩阵.D强连通当且仅当可达矩阵P(D)的元素全为1.第8章一些特殊的图图的类型(二部图,欧拉图,哈密顿图,平面图,树)判别是重点.习题8.18,8.21;例8.2~8.5.四148.1二部图（了解匹配）8.2欧拉图（前提连通）8.3哈密顿图（前提连通）8.4平面图（欧拉公式是重点，了解自对偶图）8.1二部图设无向图G=<V,E>,若能将V分成V1和V2(V1

V2=V,V1

V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点均与V2中每个顶点都相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注:n阶零图为二部图.题8.2,8.3定理无向图G=<V,E>是二部图当且仅当G中无奇圈.二部图无环；平行边不影响图的二部性.匹配(边独立集):任2条边均不相邻的边子集.习题8.4极大匹配,最大匹配,匹配数

1,(非)饱和点,完美匹配.注：匹配不限于二部图；完备匹配专门针对二部图而言.满足t条件

满足相异性条件

存在完备匹配(Hall定理).8.2欧拉图欧拉通路:图中恰好经过每条边一次的通路.欧拉回路:图中恰好经过每条边一次的回路.欧拉图:有欧拉回路的图.半欧拉图:有欧拉通路而无欧拉回路的图.定理有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度.习题8.10有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点,其中一个入度比出度大1,另一个出度比入度大1,其余顶点的入度等于出度.欧拉通路是简单通路,欧拉回路是简单回路.规定平凡图为欧拉图.环不影响图的欧拉性.哥尼斯堡七桥问题无欧拉通路也无欧拉回路.8.3哈密顿图哈密顿通路:经过图中所有顶点恰好一次的通路.哈密顿回路:经过图中所有顶点恰好一次的回路.哈密顿图:具有哈密顿回路的图.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.哈密顿通路是初级通路，哈密顿回路是初级回路.平凡图是哈密顿图.环与平行边不影响图的哈密顿性.定理(必要条件)设无向图G=<V,E>是哈密顿图,则对于任意V1

V且V1,均有p(G

V1)

|V1|.Kr,s当s

r+1时不是哈密顿图.设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.习题8.12无向哈密顿图的一个充分条件定理

G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n

1,则G中存在哈密顿通路.当n

3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路,从而G为哈密顿图.当n

3时,Kn均为哈密顿图.习题8.11(四7),8.14,8.19当r

2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.哈密顿周游世界问题中存在哈密顿回路,故它是哈密顿图.注意,并不满足充分条件.8.4平面图（欧拉公式是重点）如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.平行边与环不影响图的平面性.设G

G,若G为平面图,则G

也是平面图;若G

为非平面图,则G也是非平面图.Kn(n

5),Km,n(m,n

3)都是非平面图.定理平面图各面的次数之和等于边数的2倍.欧拉公式的推广：n

m+r=p+1.习题8.16定理设G为简单平面图，则

(G)

5.六8库拉图斯基定理：G是平面图

G中不含与K5,K3,3同胚收缩的子图.习题8.23了解无限面(外部面)R0,有限面(内部面),边界,面Ri的次数deg(Ri)极大平面图(习题8.20).若简单平面图中已无不相邻顶点,则是极大平面图.K1,K2,K3,K4都是极大平面图.极大平面图必连通.n(n3)阶极大平面图中不可能有割点和桥.设G为n(n3)阶极大平面图,则G每个面的次数均为3.任何n(n

4)阶极大平面图G均有δ(G)

3.极小非平面图：K5,K3,3都是极小非平面图极小非平面图必为简单图同胚与收缩平面图G的对偶图G*是平面图,而且是平面嵌入.G*是连通图.若边e为G中的环,则G*与e对应的边e*为桥;若e为桥,则G*中与e对应的边e*为环.在多数情况下,G*含有平行边.同构的平面图的对偶图不一定同构.题17(1)n*=r;(2)m*=m;(3)r*=n-p+1;(4)d(vi*)=deg(Ri).题22第9章树9.1无向树及生成树(利用Kruskal避圈法求最小生成树是重点，并求对应的基本回路系统和基本割集系统)9.2根树及其应用(利用Huffman算法求最优r元树或最佳前缀码是重点,了解波兰符号法与逆波兰符号法)9.1无向树及生成树无向树:连通无回路的无向图.例9.5.平凡树:平凡图.森林:每个连通分支都是树的非连通的无向图.题9.3树叶:树中度数为1的顶点.分支点:度数

2的顶点.n阶无向树的性质:1)(重要)边数m=n

1;习题9.2,9.52)G中任意两个顶点之间存在惟一的路径;例9.113)G是连通的且G中任何边均为桥;四1(2)，六64)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.定理

n阶非平凡的无向树T中