Resources

1. 逻辑和证明

1.1. 命题逻辑

1.1.1. 命题

命题是一个陈述事实的语句, 它或真或假, 但不能既为真又为假. 如果一个命题是真命题, 用T表示, 假命题用F表示.

令 \$p\$ 为一命题, 则 \$p\$ 的否定记作 \$notp\$.

令 \$p\$ 和 \$q\$ 为命题, \$p\$、\$q\$ 的合取记作 \$p^^q\$. 当p和q都是真命题时, \$p^^q\$ 为真, 否则为假.

令 \$p\$ 和 \$q\$ 为命题, \$p\$、\$q\$ 的析取记作 \$pvvq\$. 当p和q都是假命题时, \$pvvq\$ 为假, 否则为真.

令 \$p\$ 和 \$q\$ 为命题, \$p\$、\$q\$ 的异或记作 \$po+q\$. 当p和q中恰好只有1个真命题时为真, 否则为假.

1.1.2. 条件语句

令 \$p\$ 和 \$q\$ 为命题, 条件语句 \$p->q\$ 代表命题 "如果p,则q". 当\$p\$为真且\$q\$为假时, 条件语句 \$p->q\$ 为假, 否则为真.

  • \$q->p\$ 称为 \$p->q\$ 的逆命题.

  • \$notp->notq\$ 称为 \$p->q\$的反命题.

  • \$notq->notp\$ 称为 \$p->q\$的逆否命题.

    逆否命题和原命题有相同的真值.
逆命题和反命题有相同的真值.

令p和q为命题, 双条件语句 \$pharrq\$ 代表命题 "p当且仅当q". 当p和q真值相同时, 双条件语句为真, 否则为假.

1.1.3. 复合命题的真值表

p q \$notq\$ \$pvvnotq\$ \$p^^q\$ \$(pvvnotq)->(p^^q)\$

T

T

F

T

T

T

T

F

T

T

F

F

F

T

F

F

F

T

F

F

T

T

F

F

1.1.4. 逻辑运算符的优先级

运算符 优先级

\$not\$

1

\$^^\$

2

\$vv\$

3

\$->\$

4

\$hArr\$

5

1.1.5. 命题逻辑的应用

  • 系统规范说明

  • 语句翻译

  • 布尔搜索

  • 逻辑电路

  • 逻辑谜题

1.2. 命题等价式

  • 永真式: 命题永远为真.

  • 矛盾式: 命题永远为假.

  • 可能式: 命题可能为真, 可能为假.

如果 \$pharrq\$ 是永真式, 那么 \$p和q\$ 是逻辑等价的, 记为 \$p-=q\$.

德·摩根律

  • \$not(p^^q)-=notpvvnotq\$ 一个析取式的否定是由各个命题的否定合取而成的

  • \$not(pvvq)-=notp^^notq\$ 一个合取式的否定是由各个命题的否定析取而成的

恒等律

  • \$p^^T-=p\$

  • \$pvvF-=p\$

支配律

  • \$pvvT-=T\$

  • \$p^^F-=F\$

幂等律

  • \$p^^p-=p\$

  • \$pvvp-=p\$

双重否定律

  • \$not(notp)-=p\$

交换律

  • \$pvvq-=qvvp\$

  • \$p^^q-=q^^p\$

结合律

  • \$(pvvq)vvr-=pvv(qvvr)\$

  • \$(p^^q)^^r-=p^^(q^^r)\$

分配律

  • \$pvv(q^^r)-=(pvvq)^^(pvvr)\$

  • \$p^^(qvvr)-=(p^^q)vv(p^^r)\$

否定律

  • \$pvv(notp)-=T\$

  • \$p^^(notp)-=F\$

吸收律

  • \$pvv(p^^q)-=p\$

  • \$p^^(pvvq)-=p\$

条件命题的逻辑等价式

  • \$p->q-=notpvvq\$

  • \$p->q-=notq->notp\$

  • \$pvvq-=notp->q\$

  • \$p^^q-=not(p->notq)\$

  • \$not(p->q)-=p^^notq\$

  • \$(p->q)^^(p->r)-=p->(q^^r)\$

  • \$(p->r)^^(q->r)-=(pvvq)->r\$

  • \$(p->q)vv(p->r)-=p->(qvvr)\$

  • \$(p->r)vv(q->r)-=(p^^q)->r\$

双条件命题的逻辑等价式

  • \$pharrq-=(p->q)^^(q->p)\$

  • \$pharrq-=notpharrnotq\$

  • \$pharrq-=(p^^q)vv(notp^^notq)\$

  • \$not(pharrq)-=pharrnotq\$

1.3. 谓词和量词

\$ubrace(AA)_("量词")ubrace(x<0)_("约束论域的量词")ubrace((x^2>0))_("谓词")\$

形式为\$P(x_1,x_2,...,x_n)\$的语句是命题函数P在n元组\$(x_1,x_2,...,x_n)\$的值, P也称为n元谓词.

\$P(x)\$对于x在其论域中的所有值全为真, 即\$P(x)\$的全程量化. \$AAxP(x)\$表示\$P(x)\$的全称量化, 符号\$AA\$称为全称量词.

论域中存在一个\$x\$使得\$P(x)\$为真, 即\$P(x)\$的存在量化. \$EExP(x)\$表示\$P(x)\$的存在量化, 符号\$EE\$称为存在量词. 全称量词的优先级比存在量词的优先级高

论域中存在唯一一个\$x\$使得\$P(x)\$为真, \$EE!xP(x)\$表示\$P(x)\$的唯一量化, 符号\$EE!\$称为唯一量词.

1.4. 极限的定义

\$AAepsilon>0EEdelta>0AAx(0<|x-a|<delta->0<|f(x)-L|<epsilon)\$

2. 离散结构

2.1. 集合

2.1.1. 集合定义

集合是对象的一个无序的聚集, 对象称为集合的元素或成员. 用 \$ainA\$ 表示 a是集合A中的一个元素, 用 \$anotinA\$ 表示 a不是集合A中的一个元素.

2.1.2. 描述集合的两种方式

  • 花名册法: {a,b,c,d}

  • 集合构造器: O={x | x是小于10的所有正整数}

2.1.3. 数集

  • 自然数: \$NN\$={0,1,2,3,…​}

  • 整数集: \$ZZ\$={…​,-1,0,1,2,…​}

  • 正整数集: \$ZZ^+\$={1,2,3,…​}

  • 有理数集合: {\$QQ=p/q|p inZ,qinZ且q!=0\$}

  • 实数集: \$RR\$

  • 正实数集: \$RR^+\$

  • 复数集: \$CC\$

  • 空集: \$O/\$

2.1.4. 子集

集合A是集合B的子集, 当且仅当集合A中的每一个元素都是集合B中的每一个元素. \$AAx(x in A -> x in B)\$. 对于每个非空集合至少有两个子集: 空集和它本身.

真子集: \$AAx(x in A -> x in B) ^^ EEx(x in B -> x !in A)\$

2.1.5. 集合的大小

令S为集合, 如果S中恰有n个不同的元素, 则S是有限集, n为S的基数, 记为 |S|.

2.1.6. 幂集

集合S的所有的子集的集合称为S的幂集. 如果一个集合有n个元素, 那它的幂集的基数为 \$2^n\$

2.1.7. 有序n元组

有序n元组\$(a_1,a_2,...a_n)\$是一个从\$a_1\$到\$a_n\$的n个元素的聚集.

2.1.8. 笛卡尔积

\$AxxB={(a,b)|a in A ^^ b in B}\$

2.1.9. 带量词的集合符号

  • \$AAx in S(P(x))\$ 表示P(x)在集合S上的全称量化.

  • \$EEx in S(P(x))\$ 表示P(x)在集合S上的存在量化.

给定谓词P和论域D, 定义P的真值集为D中使P(x)为真的元素x组成的集合. P(x)的真值集记为 \${x in D | P(x)}\$

2.2. 集合运算

  • 并集: \$AuuB = {x | x in A vv A in B}\$

  • 交集: \$AnnB = {x | x in A ^^ A in B}\$

  • 差集: \$A-B = {x | x in A ^^ A !in B}\$

  • 补集: \$-A={x | x in U ^^ x !in A }\$

2.3. 函数

令A和B都是非空集合, 从A到B的函数f是对函数的一种指派, A中每个元素都能指派到B中的一个元素, 写成 f(a)=b.

2.3.1. 一对一函数(单射函数)

对于函数f的定义域中所有a,b满足 \$a!=b->f(a)!=f(b)\$, 则这个函数是单射的.

2.3.2. 映上函数(满射函数)

对于函数f的值域中所有b都能满足 f(a)=b, 则这个函数是满射的.

2.4. 一些重要的函数

  • \$|__x__|\$ 向下取整: 比自己小的最大整数.

  • \$|~x~|\$ 向上取整: 比自己大的最小整数.

2.5. 序列与求和

2.5.1. 几何级数

\$f(x)=ar^x\$

求和

  • \$sum_(j=0)^nar^j={(a*(r^(n+1)-1)/(r-1),r!=1),((n+1)a,r=1):}\$

  • \$sum_(k=1)^nk=(n*(n+1))/2\$

  • \$sum_(k=1)^nk^2=(n*(n+1)*(2n+1))/6\$

  • \$sum_(k=1)^nk^3=(n^2*(n+1)^2)/4\$

  • \$sum_(k=0)^(oo)x^k=1/(1-x),|x|<1\$

  • \$sum_(k=1)^(oo)kx^(k-1)=1/(1-x)^2,|x|<1\$

2.5.2. 算术级数

\$f(x)=ax+b\$

2.6. 矩阵

矩阵是一个矩形状数组, m行n列的矩阵被称为mxn矩阵. m和n相同时被称为方阵.

2.6.1. 矩阵运算

  • 两个m*n矩阵相加: \$A+B=[a_(ij)+b_(ij)\$]

  • m*k矩阵A和k*n矩阵B相乘: \$A*B=[a_(i1)*b_(1j)a_(i2)*b_(2j)...+a_(ik)*b_(kj)\$]

  • 转置: \$a_(ij)=b_(ji)\$

  • 布尔积: \$Ao.B=[(a_(i1)^^b_(1j))vv(a_(i2)^^b_(2j))vv...vv(a_(ik)^^b_(kj))\$]

  • 对称矩阵: \$a_(ij)=a_(ji)\$

3. 计数

3.1. 计数的用处

  • 确定算法的复杂性.

  • 确定是否存在充分满足需求的样本.

  • 计算离散事件的概率.

3.2. 基本法则

  • 乘积法则: 若一个过程可以被分解为m个任务, 完成第i个任务有\$n_i\$种方式, 那么完成这个过程有\$n_1*n_2*...n_m\$种方式.

    • 有多少不同的7位位串? \$2^7=128\$

  • 求和法则: 若一个过程可以被分解为m个任务,但这些任务不能同时执行, 完成第i个任务有\$n_i\$种方式, 那么完成这个过程有\$n_1+n_2+...n_m\$种方式.

    • 一个学生从三个表里选择课题, 这三个表里的课题数量分别为23/15/19, 一共有多少种可能性? \$23+15+19=57\$

    • 用户密码由6~8位数字或大写字母组成, 但必须至少包含一个数字, 一共有多少种可能性? \$36^6-26^6+36^7-26^7+36^8-26^8\$

    • 所有IPv4地址数量(A类网络号不能全为1,所有主机号不能全为0或全为1): \$(2^7-1)*(2^24-2)+2^14*(2^16-2)+2^21*(2^8-2)\$

  • 减法法则: 如果一个任务可以\$n_1\$种方法执行或者可以通过\$n_2\$种方法执行, 那么执行这个任务可以通过\$n_1+n_2\$种方式减去这两种方式相同的部分.

    • 求以1开始或00结束的8位位串数量: \$2^7+2^6-2^5=160\$

  • 除法法则: 如果一个任务能用n种方式实现, 而对于每种方式, 在所有方式中有d种与之对应, 那么完成这个任务有 \$n/d\$ 种独立的方法.

3.3. 鸽巢原理

如果N个物品放入k个盒子, 那么至少有一个盒子里面物品数量至少有 \$|~N/K~|\$.

example

  • 在100个人里面至少有 \$|~100/12~|=9\$个人出生在同一月.

  • 在52张扑克牌中至少选 \$(3-1)*4+1=9\$ 才能保证至少三张牌有同样的花色.

  • 在52张扑克牌中至少选 \$13*3+3\$ 才能保证至少三张牌是红心.

3.4. 排列

一个n元素的r排列数记为 \$P(n,r)=n(n-1)(n-2)...(n-r+1)=(n!)/((n-r)!)\$

example

  • 100个人中有多少种方法选出一个一等奖, 一个二等奖, 一个三等奖? \$P(100,3)=100*99*98\$

3.5. 组合

一个n元素的r组合数记为 \$C(n,r)=((n),(r))=(n!)/(r!(n-r)!)=C(n,n-r)\$

example

  • 从52张扑克牌中选出5张牌, 一共有多少种选法? \$C(52,5)=52!/(5!*47!)\$

n个元素中允许r个重复元素的组合数为 \$((n+r-1),(r))\$

3.6. 二项式定理

\$(x+y)^n=sum_(j=0)^n((n),(j))x^(n-j)y^j=((n),(0))x^ny^0+((n),(1))x^(n-1)y^1+((n),(2))x^(n-2)y^2+...+((n),(n))x^0y^n\$.

推论

  • \$sum_(k=0)^nx^k((n),(k))=(1+x)^n\$

    • 证明: \$(1+x)^n=sum_(k=0)^n((n),(k))1^(n-k)x^k=sum_(k=0)^nx^k((n),(k))\$

3.7. 帕斯卡恒等式

\$((n+1),(k))=((n),(k-1))+((n),(k))\$

3.8. 生成排列

对于给定数列 \$a_1a_2a_3...a_n\$, 从右向左找到 \$a_(j-1)<a_j\$的两个数, 交换 \$a_(j-1)和min(a_j...a_n) && 大于a_(j-1)\$, 并将 \$a_(j+1)到a_n\$按字典排序.

3.9. 生成组合

对于给定数列 \$a_1a_2a_3...a_n\$的r组合, 找到使得 \$a_i!=n-r+i的a_i\$,将\$a_i\$加1, 对于 \$a_j到a_r (j=i+1)\$, 用 \$a_i+j-i+1\$代替 \$a_j\$

3.10. 线性递推关系

一个常系数的k阶线性齐次递推关系是形如 \$a_n=c_1a_(n-1)c_2a_(n-2)+c_3a_(n-3)...+c_ka_(n-k)\$的关系.

性质

  • 常系数: 序列各项的系数都是常数, 而不是依赖于n的函数.

  • 线性: 序列通项是序列各项的倍数之和.

  • 齐次: 序列各项次数都是1

例子

  • \$P_n=(1.11)P_(n-1)\$是1阶的线性齐次递推关系.

  • \$f_n=f_(n-1)+f_(n-2)\$是2阶的线性齐次递推关系.

  • \$a_n=a_(n-5)\$是5阶的线性齐次递推关系.

  • \$B_n=nB_(n-1)\$不是常系数的, 系数为n, 不是常数.

  • \$f_n=2f_(n-1)+1\$不是齐次的, 第二项次数为0.

  • \$a_n=a_(n-1)+a_(n-2)^2\$不是线性的, 第二项为平方, 不是倍数.

3.11. 求解线性递推关系

3.11.1. 递推关系公式

  1. \$a_n=r^n=c_1a_(n-1) + c_2a_(n-2) + c_3a_(n-3) + ... + c_ka_(n-k)\$.

  2. 等式两边同时除以\$r^(n-k)\$.

  3. 得到特征方程: \$r^k-c_1r^(k-1)-c_2r^(k-2)+...-c_(k-1)r-c_k=0\$

3.11.2. 定理

  • 定理1: 假设 \$r^2-c_1r-c_2=0\$有两个不相等的根 \$r_1和r_2\$, 那么序列 \${a_n|a_n=a_1r_1^n+a_2r_2^n}\$是递推关系 \$a_n=c_1a_(n-1)+c_2a_(n-2)\$的解. 其中 \$a_0=a_1+a_2,a_1=a_1r_1+a_2r_2\$.

定理1证明:

\$a_n=c_1a_(n-1)+c_2a_(n-2)\$

\$=c_1(a_1r_1^(n-1)+a_2r_2^(n-2))+c_2(c_1r_1^(n-2)+a_2r_2^(n-2))\$

\$=a_1r_1^(n-2)(c_1r_1+c_2) + a_2r_2^(n-2)(c_1r_2+c_2)\$

\$=a_1r_1^(n-2)r_1^2+a_2r_2^(n-2)r_2^2\$

\$=a_1r_1^n+a_2r_2^n\$

\$=a_n\$

  • 定理2: 假设 \$r^2-c_1r-c_2=0\$只有一个根 \$r_0\$, 那么序列 \${a_n|a_n=a_1r_0^n+a_2nr_0^n}\$是递推关系 \$a_n=c_1a_(n-1)+c_2a_(n-2)\$的解.

3.11.3. 例子

例1: \$a_n=a_(n-1)+2a_(n-2),a_0=2,a_1=7,求a_n.\$

  1. \$r^2-r-2=0 => r={-1,2} => a_n=a_1*(-1)^n+a_2*2^n\$

  2. \${(a_0=2=a_1+a_2),(a_1=7=-a_1+2a_2):} => a_1=-1,a_2=3\$

  3. \$a_n=(-1)^(n+1) + 3*2^n\$

例2: 求斐波拉契数列递推关系的解

  1. \$a_n=a_(n-1)+a_(n-2),a_0=0,a_1=1\$

  2. \$r^2-r-1=0,r_1=(1+sqrt5)/2,r_2=(1-sqrt5)/2\$

  3. \${(a_0=0=a_1+a_2),(a_1=1=a_1*(1+sqrt5)/2+a_2*(1-sqrt5)/2):} => a_1=1/sqrt5,a_2=-1/sqrt5\$

  4. \$a_n=1/sqrt5*((1+sqrt5)/2)^n-1/sqrt5*((1-sqrt5)/2)^n\$

3.12. 分治递推关系

3.12.1. 分而治之

把一个规模为n的问题分成a个子问题, 每个子问题的规模是\$n/b\$, 把子问题的解组合成原来问题的解需要\$g(n)\$的额外运算, 所以求解问题所需的运算数\$f(n)=af(n/b)+g(n)\$.

复杂度

设\$f\$满足递推关系\$f(n)=af(n/b)+cn^d,n=b^k\$, 那么 \$f(n)={(Theta(n^d),a<b^d),(Theta(n^dlog_bn),a=b^d),(Theta(n^(log_ba)),a<b^d):}\$

3.13. 生成函数

实数序列\$a_0,a_1,a_2,...,a_k\$的生成函数是无穷级数\$G(x)=a_0+a_1x+a_2x^2+...+a_kx^k=sum_(k=0)^ka_kx^k\$.

3.13.1. 例子

  • 序列\${a_k|a_k=3\$的生成函数是\$sum_(k=0)^(oo)3x^k\$.

  • 序列\${a_k|a_k=2^k\$的生成函数是\$sum_(k=0)^(oo)2^kx^k\$.

  • 序列\${1,1,1,1,1,1}\$的生成函数是\$1+x+x^2+x^3+x^4+x^5=(x^5-1)/(x-1)\$.

  • 序列\${a_k|a_k=C(m,k)\$的生成函数是\$G(x)=C(m,0)C(m,1)x+C(m,2)x^2...+C(m,m)x^m=(1+x)^m\$

3.13.2. 定理

  • 令\$f(x)=sum_(k=0)^(oo)a_kx^k,g(x)=sum_(k=0)^(oo)b_kx^k\$, 那么 \$f(x)+g(x)=sum_(k=0)^(oo)(a_k+b_k)x^k,f(x)*g(x)=sum_(k=0)^(oo)(sum_(j=0)^ka_jb_(k-j))x^k\$

  • 广义二项式定理: \$令|x|<1,(1+x)^n=sum_(k=0)^(oo)((u),(k))x^k\$

4. 关系

4.1. 二元关系

\$AAainAAAbinB((a,b)inR)\$,称为a与b有关系R.

  • 设A和B是集合, 一个从A到B的二元关系是AxB的子集.

  • 集合A上的关系是A到A的关系.

  • 若 \$AAainA((a,a)inR)\$,则集合R是集合A上的自反关系.

  • 对于 \$AAaAAbinA,(a,b)inR ^^ (b,a)inR\$,则集合A上的关系R是对称的.

  • 对于 \$AAaAAbAAcinA((a,b)inR ^^ (b,c)inR -> (a,c)inR)\$,集合A上的关系R是传递的.

4.2. n元关系

设 \$A_1,A_2,...A_n\$是集合, 定义在这些集合上的n元关系R是 \$A_1xxA_2xxA_3xx...xxA_n\$的子集, 每一个集合称为R的域, n称为R的阶.

4.2.1. 主键

  • 当n元组的某个域的值能够确定这个n元组时, n元关系的这个域就叫做主键.

  • 当一组域的值确定一个关系中的n元组时, 这些域的笛卡尔积就叫做复合主键.

4.2.2. n元关系的运算

  • 选择(筛选行): 设R是一个n元关系,C是R中元素可能满足的一个条件, 那么选择运算符 \$S_C\$ 将n元关系R映射到R中满足条件C的所有n元组构成的n元关系.

  • 投影(筛选列+删除重复行): 投影 \$P_(i_1i_2...i_m)\$将n元组(\$a_1,a_2,a_3,...,a_n\$)映射到m元组(\$a_(i_1),a_(i_2),...,a_(i_m),m<=n\$).

  • 连接: 设R是m元关系, S是n元关系, 连接运算 \$J_p(R,S)\$是 m+n-p元关系. 将R后p个元组和S前p个元组相同的合并,再将R和S组合起来.

5. 图

图G=(V,E)由定点的非空集V和边的集合E组成, 每条边有一个或两个顶点与它相连.

5.1. 分类

  • 顶点集V或边集E为无限集合的图称为 无限图 ,顶点集和边集为有限集的图称为 有限图 .

  • 图的每条边都连接着两个不同的顶点, 即没有两条不同的边连接一对相同顶点的图称为 简单图 .

  • 有多条边连接同一对顶点的图称为 多重图 .

  • 边的两端顶点是同一个, 这样的边称为 环 ,包含环的多重图称为 伪图 .

  • 一个有向图\$(V,E)\$由一个非空顶点集\$V\$和一个有向边集\$E\$组成, 每条有向边与一个顶点有序对相关联. 与有序对\$(u,v)\$相关联的有向边开始于\$u\$,结束于\$v\$.

  • 既有有向边又包含无向边的图称为 混合图 .

一些特殊的简单图

  • 完全图: 每队不同顶点间恰有一条边的简单图.

  • 圈图: 由\$n\$个顶点\${v_1,v_2,v_3,...,v_n}\$ 以及边\${{v_1,v_2},{v_2,v_3},...,{v_(n-1),v_n},{v_n,v_1}}\$组成的图称为圈图.

  • 轮图: 在圈图的基础上增加一个顶点, 并将这个新顶点于原圈图中的每个顶点相连, 得到轮图.

  • 立方图: 用顶点表示\$2^n\$个长度为\$n\$的位串的图, 且两个顶点表示的位串恰好只有一位不同时相连接.

5.2. 术语

  • 若u和v分别是无向图G中的一条边e的两个端点, 那么称两个顶点u和v在G里 邻接 .

  • 图G=(V,E)中, 顶点v相邻的顶点的集合记作N(v),称为顶点v的 邻居 .

  • 在无向图中, 顶点v的 度(deg(v)) 是与该顶点相连的边的数量, 顶点上有环的度算双份. deg为0的顶点称为 孤立的 , deg为1的点称为 悬挂的 .

  • 当(u,v)表示有向图G的一条边时, u邻接到v, u是起点, v是终点. 环的起点和终点是相同的.

  • 在有向图中, \$deg^(-)(v)\$表示v的 入度 , 表示以v为终点的边数. \$deg^+(v)\$表示v的 出度 , 是以v为起点的边数

5.3. 基本定理

  • 握手定理: 顶点度数之和是边数的两倍: \$sum_(vinA)deg(v)=2m\$.

    • 例子: 一个具有10个顶点且每个顶点的度都为6的图, 有多少条边? \$6*10//2=30\$

  • 无向图中有偶数个度数为奇数的顶点.

    • 证明: 顶点度数之和2m由度数为奇数的顶点和度数为偶数的顶点组成, 度数为偶数的顶点度数之和肯定为偶数, 2m为偶数, 所以必有偶数个度数为奇数的顶点.

  • 因为每条边都有起点和终点, 所以图中所有顶点入度之和=出度之和=边数.

5.4. 二分图

把简单图的顶点分为两个不想交的子集, 使得每条边都连接一个子集中的顶点和另外一个子集的顶点, 且每个子集中的顶点互不相连, 则这样的图称为 二分图 .

5.4.1. 判断是否为二分图

对图中的每个顶点赋予不同的颜色, 如果没有两个相邻的顶点被赋予相同的颜色, 则该图为二分图.

5.5. 图的表示

  • 邻接表 列出每个顶点与它相邻的顶点

  • 邻接矩阵 n个顶点写成nxn的矩阵, 如果两个顶点相连则记下边数, 否则为0

  • 关联矩阵 设图G=(V,E)是无向图, 写成点vx边e的矩阵, 如果v和e关联则记为1, 否则为0

5.6. 图的遍历

5.6.1. 深度优先

  1. 将自己标记位已读, 处理该点.

  2. 遍历与自己相邻的点, 重复步骤1.

5.6.2. 广度优先

5.7. 连通性

通路 是边的序列, 它从图的一个顶点开始沿着图中的边行经图中相邻的顶点.

5.7.1. 无向图的连通性

若无向图中每一对不同的顶点之间都有通路, 则该图是连通的.

5.7.2. 计算顶点之间的通路数

图\$G\$顶点\$v_i到v_j\$长度为\$r\$的不同通路的数目等于图\$G\$的 邻接矩阵 \$A^r\$的第\$i,j\$项.

5.8. 欧拉回路

6. 树

6.1. 术语

  • 不含简单回路的连通图称为树.(每对顶点之间存在唯一简单通路)

  • 指定一棵树的一个特殊顶点为根

  • 假设一棵树的顶点为T,v为非根顶点, 则v的父母是从u到v存在有向边的唯一顶点u.

  • 当u为v的父母时, v称为u的孩子.

  • 具有相同父母的顶点称为兄弟.

  • 若顶点没有孩子, 则该顶点称为树叶, 有孩子的顶点称为内点.

  • 若每棵树的内点都有不超过m个孩子, 则称它为m叉树. 若每个内点正好有m个孩子, 则称它为满m叉树.

  • 若一颗高度为h的m叉树的所有树叶都在h或h-1层, 则这个树是平衡的.

6.2. 性质

  • 带有n个顶点的树含有n-1条边.

  • 带有i个内点的满m叉树含有 \$n=mi+1\$个顶点. (n=m+l)

  • 高度为h的m叉树最多有\$m^h\$个树叶.

    • 一颗高度为h的m叉树带有l个树叶, 则 \$h>=log_ml\$

6.3. 遍历

  • 先序遍历: 先遍历根节点, 再遍历子节点.

  • 后序遍历: 先遍历子节点, 再遍历根节点.

  • 中序遍历: 先遍历左子节点, 再遍历根节点, 最后遍历右子节点.

  • 层序遍历: 遍历完同一高度的兄弟节点, 再遍历下一层的节点.

6.4. 二叉搜索树

6.4.1. 插入

  • 如果插入的key比节点小, 则往左插.

  • 如果插入的key比节点大, 则往右插.

6.4.2. 删除

  • 如果被删除的节点是叶子节点, 则直接删除.

  • 如果有一个子节点, 则用子节点替换被删除的节点.

  • 如果有两个节点, 则找到右节点中最小的节点, 替换被删除的节点, 再把这个最小的节点从右子树中直接删除(最小的节点肯定是树叶).

6.5. AVL树

AVL树是一颗二叉搜索树, 其每个节点的左右子节点高度之差绝对值小于等于1.

设受插入节点影响而失去平衡的节点的父节点为Z.

6.6. 插入方式

  • LL: 插入的节点在Z节点左子树的左子树上.

  • RR: 插入的节点在Z节点右子树的右子树上.

  • LR: 插入的节点在Z节点左子树的右子树上.

  • RL: 插入的节点在Z节点右子树的左子树上.

6.7. 旋转方式

设Z节点的左子节点为X, 右子节点为Y.

  • 右单旋(处理LL): 将Z节点变为X节点的右子节点, X节点原有的右子节点变为Z节点的左子节点.

  • 左单旋(处理RR): 将Z节点变为Y节点的左子节点, Y节点原有的左子节点变为Z节点的右子节点.

  • 左右双旋(处理LR): 以X节点的右子节点为轴进行左单旋(用X节点的右子节点替换X节点), 然后以新的X节点为轴进行右单旋.

  • 右左双旋(处理RL): 以Y节点的左子节点为轴进行右单旋(用Y节点的左子节点替换Y节点), 然后以新的Y节点为轴进行左单旋.

6.7.1. 删除

  1. 先按照普通二叉搜索树的删除方式删除节点.

  2. 如果删除后导致树不平衡, 需要做旋转操作.

6.8. 2-3查找树

一颗2-3查找树由一下节点组成:

  • 2-节点: 含有一个key和两个子树, 左子树的根节点中的key都小于该节点的key, 右子树的根节点中的key都大于该节点的key.

  • 3-节点: 含有两个key和三个子树, 左子树的根节点中的key都小于该节点的key, 中间子树的根节点的key处于该节点的两个key之间, 右子树的根节点中的key都大于该节点的key.

6.8.1. 插入

  • 插入的是2-节点, 则直接将key插入到该节点中.

  • 插入的是3-节点:

    • 父节点是2-节点: 先将key插入到该节点中, 形成4-节点, 然后将中间的key移动到父节点中.

    • 父节点是3-节点: 先将key插入到该节点中, 形成4-节点, 然后递归将中间的key移动到父节点为2-3节点的节点中.

    • 所有节点都是3-节点: 先将key插入到该节点中, 形成4-节点, 然后递归将中间的key移动到根节点中, 最后将根节点分裂, 形成3个2-节点.

6.9. B树

阶为M的B树具有如下性质:

  • 数据项存在树叶上.

  • 非叶节点存储最多\$M-1\$个数据, 其中第\$i\$个数据代表子树中第\$i+1\$个最小的数据.

  • 除了根节点外, 所有非叶子节点的子节点数量在\$|~M/2~|~M\$之间.

  • 所有相同高度的节点拥有\$|~L/2~|~L\$个数据.

6.10. 红黑树

性质

  • 节点不是红色就是黑色.

  • 根节点是黑色的.

  • 每个空的节点都是黑色的.

  • 每个红色节点的叶子节点都是黑色的.

  • 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点.

6.10.1. 插入

uncle节点: X节点的父节点的兄弟节点. grand parent节点: X节点的父节点的父节点.
首先尝试着色

  1. 将新插入的节点X标记位红色.

  2. 如果X是根节点, 则标记为黑色, 结束.

  3. 如果X的父节点为黑色, 结束.

  4. 此时X的父节点是红色, 如果X的uncle节点是红色:

    1. 将X的父节点和uncle节点标记为黑色.

    2. 将X的祖父节点标记为红色.

    3. 将X的祖父节点设为X节点, 重复步骤2, 3, 4.

  5. 如果X的uncle节点是黑色,则先旋转(参考AVL树旋转), 然后父节点设为黑色, 祖父节点设为红色, 重复步骤2, 3, 5:

6.11. 树的应用

  • 二叉搜索树

  • 决策树

  • 前缀码

  • 博弈树

  • 最小生成树

😑卒