Discrete Mathematics¶

Section1¶

Chap1 数学语言与证明方法 ¶

集合 ¶

基数 (cardinality) 相对补集对称差集

证明 ¶

间接证明法 ( 逆否命题 ) 归谬法(反证法) 数学归纳法构造证明法

Chap2 命题逻辑 ¶

与非

$\uparrow$

或非

$\downarrow$

范式（normal form）¶

优先级 $(),\neg,\wedge,\vee,\rightarrow,\leftrightarrow$ 全析取范式 full disjunctive normal form 极小项简单合取式极大项命题变元或其否定均恰出现一次的简单析取式主析取范式简单合取式均为极小项主合取范式简单析取式均为极大项

推理 ¶

构造证明法重要的推理定律结论转化为前提条件，如附加前提法和归谬法归结规则
归结证明法基本规则

重言蕴含式 ¶

附加律化简律假言推理拒取式析取三段论假言三段论构造性二难(及特殊形式) 破坏性二难等价三段论

Chap3 一阶逻辑 ¶

概念 ¶

谓词逻辑命题函数=n元谓词量词域（domain）

量化推理 ¶

全称实例全称引入存在实例存在引入全称假言推理全称取拒式

量词辖域扩张与收缩 ¶

参考这篇文章

Section2¶

Chap4 关系 ¶

集合 ¶

基数 (cardinality) 幂集(power set) 序偶/有序二元组(ordered pair )

概念 ¶

$E_A,I_A$ 全域关系与恒等关系基于笛卡尔乘积构造关系自反(reflexive)/反自反对称(symmetric)/反对称（两者并不对立）传递(transive) 关系的幂运算

表示 ¶

关系矩阵与关系图

矩阵 ¶

自反对角线均为 1 对称矩阵对称

有向图 ¶

自反有环对称双重路径

闭包 ¶

自反闭包 $M_r=M+E$ 注意逻辑加对称闭包 $M_s=M+M^T$ 传递闭包 $M_t=M_1+M_2+M_3+...$传递闭包等于连通性关系 tsr 同时具有三种性质的闭包 warshell 算法参考这篇文章

等价关系 ¶

自反、对称、传递等价类与代表元划分商集加细

偏序 ¶

自反、反对称、传递元素不一定可比每对都可比的称为全序/线序(totally/linear ordering relation) 全序集（线序集、链）

反链

拟序反自反、反对称、传递

偏序集变成全序集称为拓扑排序

哈斯图 ¶

去环、传递边、箭头极大元（maximal）、极小元（minimal）最大元（greatest）、最小元（least）上界（upper bounds）、下界（lower bounds）最小上界（LUB）、最大下界（GLB）格

Chap5 函数 ¶

定义域陪域值域像原像

单射（injection） $\forall a,b\in A ,f(a)=f(b)\rightarrow a=b$
满射（surjection/onto） $\forall b\in B,\exists a \in A,f(a)=b$
双射（bijective）一一映射，即既满足单射又满足满射上取整(ceiling) >=x的最小整数下取整(floor) <=x的最大整数

Section3¶

图 ¶

概念 ¶

邻接到邻接于度 deg 环为顶点的度有双倍贡献孤立点 $deg=0$ 悬挂点 $deg=1$ 握手定理无向图有偶数个度为奇数的顶点入度 $deg^{-}(v)$ 出度 $deg^{+}(v)$ 环对入度和出度的贡献均为1

特殊简单图 ¶

完全图 $K_n$ 圈图 $C_n$ 轮图 $W_n$ $n$立方体图 $Q_n$ 完全二分图 $K_{m,n}$ 二部图判定当且仅当G中无奇数长度的回路完全匹配霍尔婚姻定理

构图 ¶

生成子图导出子图

表示 ¶

邻接表邻接矩阵关联矩阵

连通性 ¶

连通分支割点割边/桥点连通度 $\kappa (G)$ 边连通度 $\lambda(G)$ $\kappa(G)<\lambda(G)<min\ deg(v)$ 有向图连通性弱连通无向图连通单向连通单向可达强连通 a->b,b->a

匹配 ¶

Hall 定理：v1 任意 k 个顶点与 v2 至少 k 个顶点相连

通路 ¶

欧拉通路恰有两个度为奇数的顶点
欧拉回路每个顶点的度都为偶数（有向图基图为连通图，且所有顶点出入度都相等）
哈密顿通路 >=n-1
p(G-v1)<=|v1|+1)
哈密顿回路 >=n
必要条件 p(G-V1)<=|v1|)p 为连通分支数量
有桥非哈密顿图欧尔定理 deg(u)+deg(v)>=n 狄拉克定理 deg(v)>=n/2

最短通路问题 ¶

迪克斯特拉算法（Dijkstra's algorithm）旅行商问题

平面图 ¶

面与次数关系：平面图各面次数之和等于边数的两倍欧拉公式 r=e-v+2 r为面数，G为连通平面简单图推论 v>=3 则 $e\le3v-6$ 推论有度数不超过5的顶点推论 v>=3 且没有长度为 3 的回路，则$e\le2v-4$ 库拉图斯基定理初等细分得到的图为同胚的非平面图当且仅当包含一个同胚于$K_{3,3}$和$K_5$的子图平面图无子图可同胚或收缩为$K_{3,3}$和$K_5$的子图

图着色 ¶

着色数 $\chi$

树及其应用 ¶

概念 ¶

不包含简单回路的连通无向图根是内部节点,除非其是唯一顶点,此时它是树叶满m叉树每个内点(internal vertices)都有m个孩子带有i个内点的满m叉树含有n=mi+1个内点推导:除根节点外每个节点都是内点的孩子根树平衡树生成树深度优先搜索/回溯(depth-first search,DFS) 广度优先搜索(breadth-first search,BFS) 最小生成树(minimun spanning tree) 普林算法中序左根右前序根左右后序左右根

Section4¶

组合计数基础 ¶

二项式系数帕斯卡恒等式 $ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} $ 范德蒙德恒等式 $ \binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} $ 扩展二项式系数 $ \binom{-n}{k} =(-1)^n\binom{n+k-1}{k} $

模型 ¶

排列组合模型

非降路径模型栈问题不定方程解的个数模型棋盘模型正整数拆解模型

容斥原理 ¶

公式 ¶

应用 ¶

计数问题具有约束条件的方程的整数解个数埃拉托色尼筛（对称筛）求素数个数求m元素集合到n元素集合的映上函数个数错位排列

性质

Section5¶

递推方程与生成函数 ¶

复习一下常微分方程和微积分吧

递推方程 ¶

常系数线性齐次 ¶

特征方程与特征根解的线性性质无重根有重根

非齐次 ¶

$\overline{H(n)}$ 齐次方程通解 $H^{*}(n)$ 特解非齐次通解=齐次通解+特解

Discrete Mathematics¶

Section1¶

Chap1 数学语言与证明方法 ¶

集合 ¶

证明 ¶

Chap2 命题逻辑 ¶

范式（normal form）¶

推理 ¶

重言蕴含式 ¶

Chap3 一阶逻辑 ¶

概念 ¶

量化推理 ¶

量词辖域扩张与收缩 ¶

Section2¶

Chap4 关系 ¶

集合 ¶

概念 ¶

表示 ¶

矩阵 ¶

有向图 ¶

闭包 ¶

等价关系 ¶

偏序 ¶

哈斯图 ¶

Chap5 函数 ¶

Section3¶

图 ¶

概念 ¶

特殊简单图 ¶

构图 ¶

表示 ¶

连通性 ¶

匹配 ¶

通路 ¶

最短通路问题 ¶

平面图 ¶

图着色 ¶

树及其应用 ¶

概念 ¶

Section4¶

组合计数基础 ¶

模型 ¶

容斥原理 ¶

公式 ¶

应用 ¶

Section5¶

递推方程与生成函数 ¶

递推方程 ¶

常系数线性齐次 ¶

非齐次 ¶

多项式 ¶

指数 ¶

组合形式 ¶

其他解法 ¶

生成函数 ¶

初等数论 ¶

Section6¶

离散概率 ¶

初等数论和离散概率的应用 ¶

代数系统 ¶