离散数学知识总结

参考: 两本课本，kumiko的笔记以及其中参考资料。

数理逻辑

命题逻辑

关注命题和命题之间的结构与关系。

• 命题：非真即假的陈述句，可决定是真 or 假，并且不是真的就是假的，不能不真又不假，也不能又真又假。
  • $T/1$ --True
  • $F/0$ --False
• 简单命题/原子命题
  • 不包含任何与/或/非联接词
  • 不可再分割
  • 简单命题中的主语/谓语不可分割，在谓词逻辑里才进行深入分析
• 复合命题
  • 把一个 or 几个简单命题用联结词联结所构成的新命题
  • 真值依赖于各个简单命题的真值
  • 讨论多个命题联结而成的复合命题的规律性
• （原子）命题变元：代表那些未被定义的命题，用 $P, Q,R$ 表示，这些变元与逻辑符号共同构成了复合命题公式。
• 逻辑联接词：
  • $\lnot$ ：否定词，当且仅当 $P$ 是假时， $\lnot P$ 为真。
  • $\land$ ：合取词，当且仅当 $P$ 和 $Q$ 都为真时， $P\land Q$ 为真。
  • $\lor$ ：析取词，当且仅当 $P$ 和 $Q$ 都为假时， $P \lor Q$ 为假。
    • 注意，日常语言中的“或”与析取词的意义并不一致，有时这里的或代表“异或” $\bar{\lor}$ ，表示“不可兼或”。
  • $\to$ ：蕴涵词，当且仅当 $P$ 为真而 $Q$ 为 $F$ 时， $P\to Q=F$ 。
    • $P$ 是 $Q$ 的充分条件 / $Q$ 是 $P$ 的必要条件 / $Q$ 每当 $P$ / 只有 $Q$ ，才 $P$ / 除非 $Q$ ，否则非 $P$ 。
    • 已知 $P\to Q$ ，把 $Q\to P$ 称为逆命题， $\lnot P\to \lnot Q$ 称为否命题， $\lnot Q \to \lnot P$ 称为逆否命题
  • $\leftrightarrow$ ：双条件词： $P\leftrightarrow Q=(P\to Q)\land (Q\to P)$
• 合式公式：
  • 定义书写复合命题的语法
  • 定义：
    • 每个命题变量都是合式公式
    • 如果 $\alpha$ 是合式公式，那么 $\lnot \alpha$ 也是合式公式
    • 如果 $\alpha$ 和 $\beta$ 是合式公式， $\cdot$ 是二元逻辑联接词，那么 $(\alpha\cdot\beta)$ 是合式公式。
  • 约定
    • 优先级 $\lnot$ ， $\land$ ， $\lor$ ，$\to$ ， $\leftrightarrow$ ，在前面的优先运算。
    • 先左后右
• 对于任何解释都为真的公式称为重言式
  • 由 $\lor$ ， $\lor$ ，$\to$ ， $\leftrightarrow$ 联结的重言式仍然是重言式
• 在某个解释下为真的公式是可满足的
  • 重言式是可满足的
  • $A$ 可满足，$\lnot A$ 非永真。
• 在任意解释下都是假的的公式是矛盾式 / 永假式 / 不可满足式
  • 不是可满足的公式必然永假
  • 非永假的公式必然可以满足
• 代入规则
  • $A$ 是一个公式，对 $A$ 使用代入规则得到公式 $B$ ，若 $A$ 是重言式， $B$ 也是重言式
  • 只能代换命题变元（原子命题）而非复合命题
  • 必须对所有命题变元代换以同一公式
• 中缀后缀前缀表达式
  • 波兰式 / 前缀式：运算符在运算数前面
  • 逆波兰式 / 后缀式：运算数在运算数后面
  • 方法：按照运算优先级顺序逐步写成前缀式
• 等值：$\alpha$ 和 $\beta$ 是两个命题公式，如果对于任何情况，二者的真值表都相等，那它们是逻辑相等 / 等价的，用 $\alpha \Leftrightarrow \beta$ / $\alpha=\beta$ 表示。
  • 两个公式等值并不一定要有相同的命题变项。
• 等值定理： $A=B$ 的充分必要条件是 $A\leftrightarrow B$ 是重言式。
  • $A\leftrightarrow B$ 和 $A \Leftrightarrow B$ 并不是等同的，前者表示一种语法关系，不暗示任何联系，后者则表示语义上的相等。
• $=$ ：在逻辑关系上指一种等价关系，而非联结词，具有自反性，传递性与对称性。
• 基本等值公式（容易错的）
  • 结合律： $(P\leftrightarrow Q)\leftrightarrow R=P\leftrightarrow(Q\leftrightarrow R)$
  • 分配律：$P\to(Q\to R)=(P\to Q)\to(P\to R)$
  • 吸收律（悄悄用数电的手法写一遍，然后换过来）
  • 摩根律：$\lnot(P\leftrightarrow Q)=\lnot P \leftrightarrow Q=P\leftrightarrow \lnot Q=(\lnot P \land Q)\lor(P \land \lnot Q)$
  • 同一律
    • $P\to F=\lnot P$
    • $F\leftrightarrow P=\lnot P$
    • $P\to \lnot P=\lnot P$
    • $\lnot P\to P=P$
• 常见等值式
  • $P\to Q=\lnot P \lor Q$
  • 前提合并 $P\to(Q\to R)=(P \land Q)\to R$
  • 描述双条件
    • 取真：$P\leftrightarrow Q=(P \land Q)\lor(\lnot P \land \lnot Q)$
    • 取假：$P\leftrightarrow Q=(P\lor \lnot Q) \land(\lnot P \lor Q)$
  • 前提交换 $P\to (Q\to R)=Q\to(P\to R)$
  • $(P\to R)\land(Q\to R)=(P\lor Q)\to R$
  • 归谬： $(P\to Q)\land(P\to \lnot Q)=\lnot P$
• 置换规则
  • 对公式 $A$ 的子公式，用与之等值的公式来代换，代换为 $B$
  • $A=B$
  • $A$ 是重言式时，置换后的公式 $B$ 也是重言式
  • 与代入公式不同，不必对所有同一的子公式做代换
• 从真值表写命题公式
  • 从 $T$ 来列写：项间用 $\lor$ ，每项内用 $\land$
  • 从 $F$ 来列写：项间用 $\land$ ，每项内用 $\lor$ ，同时 $T$ 的项用 $\lnot$ 表示
• 联接词的个数 / 真值函项
  • 一个命题变项有 $2$ 种值，共有 $2^2$ 种可能，所以可以定义 $4$ 种真值函项
    • 永假 $F$ ，永真 $T$ ，$P$ 自身，$\lnot P$ 否定词
    • 于是定义 $\lnot P$ 为否定词
  • 两个变项共有 $4$ 种取值情形，共有 $2^4$ 种可能，可以定义 $16$ 种真值函项
    • 在前面所述的几个联结词之外，定义
      • 异或 $P \bar{\lor} Q=(\lnot P \land Q) \lor(P \land \lnot Q)$
      • 与非 $P \uparrow Q=\lnot(P\land Q)$
      • 或非 $P \downarrow Q= \lnot(P \lor Q)$
  • $n$ 个命题变元对应的取值情形为 $2^n$ 种，对应的真值函项有 $2^{2^n}$ 个。
• 联接词的完备集
  • 全体联结词的无限集合是完备集
  • 比较重要且容易忘的完备集
    • $\{\lnot,\to\}$
    • $\{\uparrow\}$
    • $\{\downarrow\}$
    • 其他：否定词+析取 / 合取任一
  • 不完备集
    • 缺少 $\lnot$
    • $\{\lnot,\leftrightarrow\}$ 这个十分重要
  • 基底
    • 一个联接词： $\uparrow$ ，$\downarrow$
• 对偶式与对偶性
  • $\alpha$ 是一个只包含 $\lnot$ ， $\lor$ 和 $\land$ 的公式
    • $\alpha^*$ （对偶式）
      • 析取 / 合取， $F$ 和 $T$ 交换
      • $(A^*)^*=A$
      • 结合律
    • $\alpha^-$
      • 将 $P_{i}$ 替换为 $\lnot P_{i}$
      • $(A^-)^-=A$
      • 结合律
• 德摩根律的新表示（证明：用归纳法，首先证一个命题变元，再假设含 $k$ 个运算符满足，分别用 $\lnot$ 和 $\lor$ 和 $\land$ 推含 $k+1$ 个运算符的情况）：

$${\neg\alpha=( \alpha^{*} )^{-} }$$

• 相关定理
  • $A$ 和 $A^-$ / $\lnot A$ 与 $A^*$ 同永真，同可满足（前者用代入规则，后者德摩根+代入规则）
  • $A=B$ ，则有 $A^*=B^*$ （先推 $\lnot A=\lnot B$ ，之后用德摩根和代入）
  • $A\to B$ 和 $B^*\to A^*$ 同永真（用逆否命题和德摩根）
• 范式：将等值的公式化为某个统一的标准形式
  • 文字： $P$ 和 $\lnot P$
  • 文字的合取称为合取式
  • 文字的析取称为析取式
  • 计算
    • 消去 $\to$ 和 $\leftrightarrow$
    • 否定深入到命题变项
    • 用分配律（已知一种范式，用分配律求另一种）
  • 功能：判断重言式，矛盾式，两公式是否等值
• 主析取范式
  • 极小项： $m_{j}$ 用合取词联结所有的命题变项 ，其中 $m_{0}$ 是全部取反的。按照题给字母顺序排列，如 $P \land Q\land \lnot R=m_{6}$
  • 主析取范式是仅有极小项构成的析取式
  • 极小项的个数 $2^n$
  • 每个解释与极小项一一对应，且解释为真的时候极小项为真
  • 极小项互不相等
  • 恰有 $2^n$ 个极小项的析取构成的公式必为重言式。
  • $m_{i} \land m_{j}=F\ (i\neq j)$
• 主合取范式
  • 极大项： $M_{j}$ 用析取词联结所有的命题变项，其中 $M_{0}$ 是全部取反的。
  • 主合取范式是仅有极大项构成的合取式
  • 每个解释与极大项一一对应，且解释为假的时候极小项为假
  • 个数同极小项
  • 恰有 $2^n$ 个极大项的合取构成的公式必为矛盾式。
  • $M_{i}\lor M_{j}=T \ (i\neq j)$
• 二者转换：找析取/合取范式的补，之后再用总数减补，就得到另一个范式。
• 推理形式
  • 重言蕴含：如果 $A$ 为真时， $B$ 必然为真，则称 $A$ 重言蕴含 $B$ （ $B$ 是 $A$ 的逻辑推论），也即 $A \Rightarrow B$ （ $\Rightarrow$ 是真值关系，而非逻辑联结词）
  • $A\Rightarrow B$ 是 “ $A\to B$ 是正确的推理形式” 的充要条件
• 推理公式
  • $(P \land Q)\Rightarrow P$
  • $P \Rightarrow (P \lor Q)$
  • $\lnot P\land(P \lor Q)\Rightarrow Q$
  • $P \land(P \to Q) \Rightarrow Q$
  • $(P\to Q) \land \lnot Q \Rightarrow \lnot P$
  • $(P →Q)∧(Q→R)⇒P →R$
  • $(P ↔Q)∧(Q↔R)⇒P ↔R$
  • $(P →R)∧(Q→S)∧(P ∨Q)⇒R∨S$
• 推理规则
  • 前提引用
  • 结论引用
  • 代入
  • 置换
  • 分离 （ $A\to B$ + $A$ ，可以分离出 $B$）
  • 条件证明 / 附加前提：结论方的条件可以作为条件使用
  • 三段论
• 归结证明
  • $A\Rightarrow B$ 等价于 $A \land \lnot B$ 是矛盾式，假设其为真，导出矛盾
  • 化为合取范式，建立子句集，归结，直到出现矛盾

谓词逻辑

• 对“命题逻辑”中的简单命题做进一步剖析，引入谓词，变量以及量词。
• 小写命题，大写谓词
• 仅限于一阶谓词逻辑 or 狭称谓词逻辑
• 个体词和谓词
  • 主词/个体词：一般用变量 $x$ 表示，也称为个体变元。确定了个体具体指向的成为个体常元。
  • 谓词：一个个体的性质和个体之间的关系，给定个体域到集合 $\{T,F\}$ 上的映射。
  • 一元谓词：主词只有一个时，表示主词性质和属性的词称为谓词 $P(x)$ ，确定了含义的是常项，没确定的是变项（一般指一切关系 / 性质的结合） 。
  • 多元谓词： $P(x,y,z)$
  • 个体域 / 论域： $D$ （一般认为是最广的集合）
    • 同一谓词在不同论域下的描述形式可能不同，所取的真假值也不同
  • 注意
    • 谓词 $P(x)$ 和 $Q(x,y)$ 是命题形式而非命题，因为没有指定它们的含义，不知道其值的真假
    • 当谓词变项为某个谓词常项，个体词确定为个体常项或者量词+确定个体词的论域时 命题形式才变为命题
• 谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻辑的特殊情形
• 函数
  • 某个体域向另一个体域的映射
  • 并不单独使用而是嵌入到谓词中
• 量词：表示个体数量，运算优先级高于逻辑连接词
  • 全称： $\forall x$
  • 存在： $\exists x$
  • $(\forall x)(P(x)\lor Q(x))\neq(\forall x)P(x)\lor Q(x)$
  • 被量词约束的变元称为约束变元，不受量词约束的变元叫自由变元
  • 量词约束的范围称为量词的辖域
• 变元易名规则
  • $(\forall x)P(x)=(\forall y)P(y)$
  • $(\forall x)(P(x)\to Q(x,y))\neq(\forall y)(P(y)\to Q(y,y))$
• 合式公式
  • 限定命题形式的范围
  • 关注一阶谓词逻辑
    • 量词仅作用于个体变元
    • 量词不作为命题变项和谓词变项
    • 不讨论谓词的谓词
  • 定义
    • 命题常项，变项，原子谓词公式
    • $A$ 如果是合式公式， $\lnot A$ 也是
    • $A$ ， $B$ 是合式公式，没有出现同一变元 $x$ 在 $A$，$B$ 中一个是约束一个是自由的，则 $A \land B$ ， $A \lor B$ ， $A\to B$ ，$A\leftrightarrow B$ 也是合式公式
    • $A$ 是合式公式，$x$ 在 $A$ 中是自由变元， $(\forall x)A$ ， $(\exists x) A$ 也是合式公式
• 形式化
  • 所有的……都是……只能使用 $\to$ ，而不能使用 $\land$ （使用 $\land$ 时，真值与论域有关，而使用 $\to$ 时，真值与论域无关，当论域中有的个体不满足 $P(x)$ 时，$(\forall x)(P(x)\land Q(x))$ 为假，而 $(\forall x)(P(x)\to Q(x))$ 为真，但显然后者是符合实际的）
  • 存在……是……只能使用 $\land$ ，而不能使用 $\to$ （原因同上，论域中的所有个体都不满足 $P(x)$ 时， $(\exists x)(P(x)\land Q(x))$ 为假，而 $(\exists x)(P(x)\to Q(x))$ 却为真，不符合实际）
• 谓词变元多次量化
  • 相同的量词可以交换，但不同的量词不能交换
• 论域为有限域时
  • $(\forall x)P(x)$ 可视作一系列 $\land$
  • $\exists P(x)$ 可视作一系列 $\lor$
• 一般谓词逻辑的公式不能转换为命题逻辑公式
• 解释 $I$ 的给出
  • 可知的论域
  • 命题变项，自由个体变项，谓词变项，函数
• 在论域 $D$ 上，一个谓词公式解释的个数是无限的
• 判定问题
  • 在任意解释下真值为真，称为普遍有效
  • 某个解释下为真，可满足
  • 任意解释下真值为假，不可满足
  • 依赖且仅依赖于个体域个体的数目
  • 某公式在 $k$ 个体域上可满足，在 $k-1$ 个体域上也可满足，但其他不能保证
  • 结论
    • 谓词逻辑是不可判定的，困难在于个体域是无穷集以及谓词设定具有任意性，但其子类是可判定的
    • 只含一元谓词变项的公式可判定
    • $(\forall x_{1})\dots(\forall x_{n})P(x_{1},\dots,x_{n})$ 以及对应的存在公式，若 $P$ 中无量词和其他自由变项时也可判定
    • 个体域有穷时可判定
• 谓词公式代入命题公式中的谓词变项，可以得到谓词等值式
• 德摩根律的推广
  • $\lnot (\forall x)P(x)=(\exists x) \lnot P(x)$
  • $\lnot(\exists x)P(x)=(\forall x)\lnot P(x)$
• 量词分配等值式
  • $(\forall x)(P(x)\lor q)=(\forall x)P(x) \lor q$ ，其中 $q$ 是命题变项，与 $x$ 无关
  • 对 $\to$ 的分配律
    • $(\forall x)(P(x)\to q)=(\exists x)P(x)\to q$
    • $(\exists x)(P(x)\to q)=(\forall x)P(x)\to q$
    • $(\forall x)(p\to Q(x))=p\to(\forall x)Q(x)$ ，用 $\exists$ 代替 $\forall$ 时，亦然
  • 分配律： $\forall$ 对 $\lor$ ， $\exists$ 对 $\land$ 的分配律一般不成立，但是
    • $(\exists x)(P(x)\to Q(x))=(\forall x)P(x)\to (\exists x)Q(x)$
    • $(\forall x)P(x) \lor (\forall x)Q(x)\Rightarrow(\forall x)(P(x) \lor Q(x))$ 蕴含关系成立
    • $(\exists x)(P(x) \land Q(x)) \Rightarrow (\exists x) P(x) \land (\exists x) Q(x)$ 蕴含关系也成立
  • 变元易名分配律
    • $(\forall x)(\forall y)(P(x) \lor Q(y))=(\forall x)P(x) \lor (\forall x)Q(x)$
    • $(\exists x)(\exists y)(P(x) \land Q(y))=(\exists x)P(x) \land (\exists x)Q(x)$
• 范式：研究公式的特点
  • 前束范式和 $\mathrm{Skolem}$ 标准形不要搞混！
  • 前束范式与原公式等值（前束范式：一切量词都在公式的最左边）
    • 一般形式 $(Q_{1}x_{1})\dots(Q_{n}x_{n})M(x_{1},\dots,x_{n})$ ， $M$ 称为公式的母式，其中没有量词
    • 谓词逻辑的任意公式都可化为等值的前束范式，但前束范式不唯一，且前束范式对前束量词没有次序要求
    • 操作
      • 消去联接词（注意量词的优先级高于逻辑联接词）
      • 德摩根律进行 $\lnot$ 内移
      • 量词左移，变元易名
  • $\rm{Skolem}$ 标准形
    • 保留全称量词消去存在量词
    • 只保持在某种意义下的等值关系
    • 公式 $A$ 不可满足当且仅当其 $\rm{Skolem}$ 标准形是不可满足（永假）的（对不可满足的公式，二者等值）
    • 操作
      • 化为前束范式
      • 从左到右依次消去存在量词，若存在量词在某几个全称量词的右侧，则需要以函数的方式写入，如 $f(x,y)$ ，若存在量词出现在最左边，直接将相关变元以论域中没在 $P$ 中出现的某个常项 $a$ 代入
    • 从操作中也可以得到不等值性：因为存在量词所辖变元不一定必然是其左侧全称量词所辖变元的函数。
• 推理公式
  • 命题逻辑中有关推理形式的术语都可以引入到谓词逻辑中
• 推理演算
  • 全称量词消去规则 $(\forall x)P(x)\Rightarrow P(y)$ ， $y$ 是论域中一个个体
    • $P(x)$ 中有量词和变项时， $y$ 须不在 $P(x)$ 约束中出现
  • 全称量词引入规则 $P(y)\Rightarrow (\forall x)P(x)$ ， $y$ 是论域中任意个体
    • $x$ 不在 $P(y)$ 中约束出现
  • 存在量词消去规则 $(\exists x)P(x)\Rightarrow P(c)$ ，$c$ 是论域中的一个个体常项
    • $(\exists x)P(x)$ 中没有自由个体出现
    • $P(x)$ 中不含有 $c$
  • 存在量词引入规则 $P(c)\Rightarrow(\exists x)P(x)$ ， $c$ 是论域中的个体常项
    • $x$ 不能出现在 $P(c)$ 中
  • $(\forall x)(\exists y)P(x,y)\Rightarrow (\exists y)P(x,y)\Rightarrow P(x,a)$ ，但无法推出 $(\forall x)P(x,a)$ 和 $(\exists y)(\forall x)P(x,y)$ ，因为 $P(x,y)$ 的成立是有条件的
• 过程
  • 谓词形式化 $\to$ 消去量词 $\to$ 推理 $\to$ 引入量词
• 归结推理
  • 建立子句集
    • 化为 $\rm{skolem}$ 标准形，省略全称量词，将 $\land$ 用 $,$ 表示，获得子句集 $S$
  • 对 $S$ 做归结，消去互补对
    • 譬如 $P(x) \lor Q(x)$ 和 $\lnot P(a) \lor R(y)$ 可以归结为 $Q(a) \lor R(y)$

集合论

集合

• 集合
  • 不能出现相同的元素
  • 集合是无次序的
  • 事物是否属于集合是确定的
  • “无限多的集合”
• 约定俗成
  • $\mathrm{Q}$ 有理数集
  • $\mathrm{C}$ 复数集
• 集合论不能研究“所有集合组成的集合”
• 两集合相等
  • 当且仅当它们拥有相同的元素（也即外延公理：一个集合是由它的元素完全决定）
  • 充要条件：两集合互为子集
• $A \in B$ ： $A$ 是 $B$ 的一个元素， $A\subseteq B$ ： $A$ 的每个元素都是 $B$ 的元素
• 关系 $\subseteq$ 具有自反，反对称，传递性，但 $\in$ 没有这三个性质
• 真子集 $\subset$ ，可以写成 $(\forall x)(x\in A \to x \in B) \land(\exists x)\lnot(x\in A\leftrightarrow x \in B)$
• 不是子集 $\nsupseteq$
• 相交：有公共元素
• 空集 $\emptyset$ ，可以表示为 $\{ x\mid x\neq x \}$ ，空集是唯一的
• 全集 $E$ ，表示为 $\{x\mid x=x \}$
• 余集 $-A$ ，也称 $A$ 的绝对补集 $\{ x\mid \lnot(x\in A) \}$ ，或者称为 $A$ 对 $E$ （全集）的相对补集
• 对称差 $A\oplus B$ ，$\{ x\mid x\in A \bar{\lor} x \in B \}$
• 对集合的集合 $A$ 的运算
  • 广义并 / 广义交
  • $\cup \emptyset=\emptyset$
• 幂集：集合所有的子集组成的集合
  • 记作 $P(A)$
  • $2^n$ 个元素，都是集合
  • $x \subseteq A \Leftrightarrow x \in P(A)$
• 笛卡尔积（元素有序）
  • 有序对
    • 两个元素按给定次序排成的二元组合
    • $<x,y>\neq<y,x>$
    • 用集合定义有序对： $<x,y> = \{ \{ x \},\{ x,y \} \}$
  • $n$ 元组 / 多重有序对（递归方法定义）
    • $<x_{1},\dots,x_{n}>= <<x_{1},\dots,x_{n-1}>,x_{n}>$
  • 笛卡尔积：$A\times B=\{ <x,y>\mid x\in A \land y\in B \}$
    • $A=B$ 时，可以写成 $A^2$
    • $n$ 阶笛卡尔积 $A_{1}\times A_{2}\times \dots \times A_{n}=\{ <x_{1},\dots,x_{n}>\mid x_{1}\in A_{1}\land \dots \land x_{n}\in A_{n} \}$
• 优先级
  • 一元运算符 $>$ 二元运算符 $>$ 集合关系符 $>$ 一元联结词 $>$ 二元联接词 $>$ 逻辑关系符
• 幂集图示法（连线表示包含关系）
• 笛卡尔积图示法： $x$ ， $y$ 轴上的线段表示集合
• 运算
  • 广义交 / 广义并和集合的二元运算不是一回事儿
  • 摩根律
    • $A-(B\cup C)=(A-B)\cap(A-C)$
    • $A-(B \cap C)=(A-B)\cup(A-C)$
    • $-(B \cup C)=-B\cap-C$
    • $-(B \cap C)=-B \cup-C$
  • 证明
    • 谓词法：将集合转变为谓词
    • 集合法：直接使用集合的计算规律
• 差集的性质
  • $A-B=A \cap -B$ （将差集转化为交并补）
  • $A-B=A-(A \cap B)$
  • $A \cup(B-A)=A\cup B$
  • $A \cap(B-C)=(A \cap B)-C$
• 对称差的性质
  • $A \cap(B\oplus C)=(A\cap B)\oplus(A\cap C)$ （证明补项：$\cup(A\cap B\cap-A)$ ）
  • $A \oplus(A\oplus B)=B$
  • $(A-B)\oplus(A-C)=\emptyset$ 的充要条件是 $A-B=A-C$
• $\subseteq$ 的性质
  • $(A\subseteq B)\land(C\subseteq D)\Rightarrow(A-D)\subseteq(B-C)$
• 幂集的性质
  • $P(A)\cap P(B)=P(A\cap B)$
  • $P(A) \cup P(B)\subseteq P(A\cup B)$ （注意不是等式！因为涉及到 $\forall$ 和 $\lor$ 的混用）
  • $P(A-B) \subseteq(P(A)-P(B)) \cup \{ \emptyset \}$
• 传递集合
  • 集合的集合 $A$ 的任一元素的元素都是 $A$ 的元素，称 $A$ 为传递集合
  • 等价： $(\forall x)(\forall y)((x \in y \land y \in A)\to x \in A)$
    • 推论 $x \subseteq A$ ， $y \subseteq A$
  • 若 $A$ 是传递集合 $\Leftrightarrow A\subseteq P(A)$
  • $A$ 是传递集合 $\Leftrightarrow P(A)$ 也是传递集合
• 广义并与广义交
  • $A \subseteq B\Rightarrow \cup A \subseteq \cup B$
  • $A\subseteq B \implies \cap B \subseteq \cap A$
  • $\cap(A \cup B)=(\cap A)\cap(\cap B)$
  • $\cup(P(A))=A$
  • $A$ / $A$ 中的元素是传递集合 $\Rightarrow \cup A$ 是传递集合
  • 非空集合 $A$ 是传递集合， $\cap A$ 是传递集合，且 $\cap A=\emptyset$
    • 元素是传递集合亦然
• 笛卡尔积
  • $A \times \emptyset=B\times \emptyset=\emptyset$
  • 不满足交换律和结合律
  • $x \in A$ ， $y \in A$ ，故而 $<x,y>\in P(P(A))$
  • $A \subseteq B \Leftrightarrow A\times C \subseteq B \times C \Leftrightarrow C\times A \subseteq C \times B$
  • $A \times B \subseteq C\times D$ 当且仅当 $A\subseteq C$ 且 $B \subseteq D$
• 基数：集合中元素的个数
  • $\mid P(A)\mid=2^{\mid A\mid}$
  • $\mid A\times B\mid=\mid A\mid \cdot \mid B\mid$
  • $\mid A_{1}-A_{2}\mid\geq\mid A_{1}\mid-\mid A_{2}\mid$
  • $\mid A_{1} \oplus A_{2}\mid=\mid A_{1}\mid+\mid A_{2}\mid-2\mid A_{1} \cap A_{2}\mid$
  • 容斥原理： $\mid A_{1} \cup A_{2}\mid=\mid A_{1}\mid+\mid A_{2}\mid-\mid A_{1} \cap A_{2}\mid$
    • $n$ 个 $\mid A_{1} \cup A_{2} \cup\dots \cup A_{n}\mid=\sum_{1\leq i\leq n}\mid A_{i}\mid-\sum_{1\leq i< j\leq n}\mid A_{i}\cap A_{j}\mid+\sum_{1\leq i<j<k\leq n}\mid A_{i} \cap A_{j} \cap A_{k}\mid+\dots+(-1)^{n-1}\mid A_{1}\cap A_{2}\cap \dots \cap A_{n}\mid$

关系

• 运算优先级：关系合成符优先于集合运算符
• 集合 $A$ 和 $B$ ， $A\times B$ 的任一子集称为 $A$ 到 $B$ 的一个二元关系，称为 $R$ ，若 $<x,y> \in R$ ，可以记作 $xRy$ ，反之则记作 $x\not\operatorname{R}y$
• 特殊关系（对任意集合 $A$ ）
  • 恒等 $I_{A}=\{ <x,x>\mid x \in A \}$
  • 全关系 $E_{A}=\{ <x,y>\mid x \in A \land y \in A \}$
  • 空关系 $\emptyset$
• 关系 $R$ ，定义域+值域， $R$ 的域 $fld(R)=dom(R) \cup ran(R)$
• 若 $<x,y> \in R$ ，则 $x,y \in \cup \cup R$ （注意 $R$ 是集合，$<x,y>$ 在 $R$ 中表现为 $\{ \{ x \},\{ x,y \} \}$
• $fld(R)=\cup \cup R$
• 关系矩阵： $A$ ，$B$ 两集合，分别有 $m$ ， $n$ 元素，画出一个 $m\times n$ 的矩阵 $M(R)$ ，当 $<a_{i},b_{j}>\in R$ 时， $r_{ij}=1$
• 关系图：集合中的每个元素画成一个点，关系 $<x_{i},y_{j}>$ 是有向图的边，从 $x_{i}$ 指向 $y_{j}$
• 逆 $R^{-1}$ $<x,y> 变为 <y,x>$ ，关系矩阵求转置
• 合成 $S\circ R$ $<x,z> \in R \land<z,y> \in S 变为<x,y>$ ，注意 $S$ 和 $R$ 书写的顺序 ，关系矩阵求乘法（矩阵相乘中的加变为 $\lor$ ，乘变为 $\land$ ）
  • $(S \circ R)^{-1}=R^{-1}\circ S^{-1}$
  • 关系合成满足结合律，不满足交换律
  • $R_{1}\circ(R_{2} \cup R_{3})=R_{1}\circ R_{2} \cup R_{1} \circ R_{3}$
  • $R_{1} \circ(R_{2} \cap R_{3})\subseteq R_{1} \circ R_{2}\cap R_{1} \circ R_{3}$
• 限制 $R\upharpoonright A$ ： $<x,y>\in R \land x \in A$
• 象 $R[A]$ / $[a]_{R}$ ：当 $<x,y> \in R$ 且 $x \in A$ 时， $y$ 的取值组成的集合（注意，这里都是 $\in$ ，而不是子集关系）
  • $R[A \cup B]=R[A]\cup R[B]$
  • $R[\cup A]=\cup \{ R[B]\mid B \in A \}$
  • $R[A\cap B]\subseteq R[A]\cap R[B]$
  • $R[\cap A]\subseteq \cap \{ R[B]\mid B \in A \},A\neq \emptyset$
  • $R[A]-R[B]\subseteq R[A-B]$
• 性质
  • 自反 $xRx$ ，非自反 $x\not\operatorname{R}x$
    • 在非空集合上的空关系是非自反的
    • 自反和非自反关系不能同时满足
    • 自反：关系矩阵的主对角线元素都是 $1$ ，关系图的每个角都有自圈
    • $R_{1},R_{2}$ 是 $A$ 上的自反关系，则 $R_{1}^{-1}$ ， $R_{1} \cap R_{2}$ ， $R_{1}\cup R_{2}$ 也是 $A$ 上自反的关系
  • 对称 $xRy\to yRx$ ，反对称 $(xRy\land yRx)\to x=y$
    • 对称性和反对称可性以同时满足，也可以同时不满足
    • 对称：关系矩阵是对称矩阵，关系图的任意两个顶点之间或者没有有向边，或者互有有向边
    • 反对称：关系矩阵是反对称矩阵（对任意的 $i\neq j$ ，若 $r_{ij}=1$ ，则 $r_{ji}=0$ ， 关系图任意两定点之间或者没有有向边，或者仅有一条有向边
    • $R_{1},R_{2}$ 是 $A$ 上的对称关系，则 $R_{1}^{-1}$ ， $R_{1} \cap R_{2}$ ， $R_{1}\cup R_{2}$ 也是 $A$ 上对称的关系
    • $R_{1},R_{2}$ 是 $A$ 上的反对称关系，则 $R_{1}^{-1}$ ， $R_{1} \cap R_{2}$ 也是 $A$ 上反对称的关系 ，如 $A=\{ 1,2 \}$ 上的关系 $R_{1}=\{ <1,2> \}$ 和 $R_{2}=\{ <2,1> \}$ 是 $A$ 上反对称的，但 $R_{1} \cup R_{2}$ 不是反对称的
    • $R$ 是对称的 $\Leftrightarrow$ $R=R^{-1}$
    • $R$ 是反对称的 $\Leftrightarrow R\cap R^{-1}\subseteq I_{A}$
  • 传递：$R$ 为 $A$ 上的关系，对任意 $x,y,z\in A$ $(xRy\land yRz)\to xRz$
    • 空关系是传递关系
    • $R_{1},R_{2}$ 是 $A$ 上的传递关系，则 $R_{1}^{-1}$ ， $R_{1} \cap R_{2}$ 也是 $A$ 上传递的关系，但 $R_{1} \cup R_{2}$ 不一定传递，如 $A=\{ 1,2,3 \}$ 上的关系 $R_{1}=\{ <1,2> \}$ ，$R_{2}=\{ <2,3> \}$ 均是传递的，但 $R_{1} \cup R_{2}$ 不是传递的 ^07e11c
• 关系的合成：
  • $R^0=I_{A}$
  • $R^{n+1}=R^n \circ R(n\geq 0)$
  • $A$ 是有限集合， $\mid A\mid=n$ ， $R$ 是 $A$ 上的关系，则存在自然数 $s$ 和 $t$ ，$s\neq t$ ，使得 $R^s=R^t$ 。（因为 $\mid A\times A\mid=n^2$ ，而 $\mid P(A\times A)\mid =2^{n^2}$ ，而 $R^i$ 都是 $P(A\times A)$ 中的元素。由鸽巢原理，可以得出至少有两个幂是相等的）
    • 于是 $A$ 的幂具有了一定的“周期性”。设 $s<t$ ，则 $t-s$ 可以看作是其的一个“周期”，且 $B=\{ R^0,R^1,\dots,R^{t-1} \}$ ， $R$ 的各次幂均为 $B$ 的元素（ $R^q\in B$ ）。
  • $R^m \circ R^n=R^{m+n}$
  • $(R^m)^n=R^{mn}$
• 闭包
  • 在已有关系 $R$ 上增加一些新的有序对，构成新关系 $R'$ （ $R\subseteq R'$ ），使得 $R'$ 具有某些性质，且希望这些有序对尽量少
  • 自反 $r(R)$ ，对称 $s(R)$ ，传递 $t(R)$ 闭包
  • 若 $R_{1} \subseteq R_{2}$ ，则它们的闭包也满足这样的关系
  • $t(R_{1})\cup t(R_{2})\subseteq t(R_{1} \cup R_{2})$ ，其他两个闭包都是相等关系
• 构造方法：（非空集合）
  • $r(R)=R \cup R^0$
  • $s(R)=R \cup R^{-1}$
  • $t(R)=R \cup R^2 \cup R^3 \cup \dots$
    • $R^+=\cup_{k=1\sim \infty}R^k=R \cup R^2 \cup R^3 \cup \dots$
    • $R^*=\cup_{k=1\sim \infty}R^k=R^0 \cup R \cup R^2 \cup R^3 \cup \dots$
    • 若 $A$ 为非空有限集合， $\mid A\mid=n$ ，存在一个正整数 $k\leq n$ ，使得 $t(R)=R \cup R^2 \cup R^3 \cup \dots \cup R^k$
    • $\rm{Warshall}$ 算法：【考试向】Warshall 算法速记 - 知乎 (zhihu.com)
  • $R$ 自反，剩下俩都自反； $R$ 对称，剩下俩都对称；$R$ 传递，仅自反闭包传递。
  • 三者之中，任取其中两个， $r(s(R))=s(r(R))$ ，都满足，前提是非空。
• 等价：具有自反，对称，传递性质的关系
  • 所有谓词公式集合上的等值关系也是等价关系
  • 一个关系中，每组任两个元素都有关系，而不同组元素之间没有关系，称为等价类。 $R$ 是非空集合中的等价关系，在非空集合中，对任意的 $x \in A$ ， $[x]_{R}=\{ y\mid y \in A \land xRy \}$，则称该集合为 $x$ 关于 $R$ 的等价类。
    • 集合中的每个元素各有一个等价类，各等价类之间或者相等或者不相交，等价类的并集是 $A$
      • 等价类不是空集。
      • 若 $xRy$ 则 $x$ 和 $y$ 的等价类相等
      • 若 $x\not\operatorname{R}y$ ，则二者等价类的并集为空集。
    • 以 $R$ 的不相交的等价类为元素的集合称为 $A$ 的商集，记作 $A / R$
  • 等价关系在平面坐标系的矩形表示法中，表示为正方形的一条对角线和若干正方形 ，而下图中由于不满足传递性，所以不是等价关系。
  • $A$ 的划分 $\pi$ ，是 $A$ 非空子集的集合，它们互不相交，且并集为 $A$
    • 集合本身也可看作一个划分。
    • $A / R$ 是 $A$ 的划分，称为从等价关系 $R$ 诱导出的 $A$ 的划分，记作 $\pi R$ 。
    • 划分 $\pi$ 也可诱导出等价关系， $R\pi=\{ <x,y>\mid(\exists z)(z \in\pi \land x \in z \land y \in z) \}$
    • 对一个划分 $\pi$ 和 $A$ 上的等价关系 $R$ ， $\pi$ 诱导 $R$ 当且仅当 $R$ 诱导 $\pi$ 。
• 相容关系
  • 自反且对称
  • 对 $A$ 上的相容关系 $R$ ，若 $C \subseteq A$ ，且其中任意两个元素 $x,y$ 有 $xRy$ ，则 $C$ 为相容类。
    • 相容类不是其他相容类的真子集，称为最大相容类
    • 在简化图中寻找最大相容类
      • 简化图：不画自圈，用无向边代替一对来回的有向边
      • 最大完全多边形（每个顶点与其他所有顶点相连）的顶点集合 / 一个孤立点的集合/两点连线不是最大完全多边形的边
  • 覆盖：基本同划分，覆盖中各元素可能相交。
  • 一个覆盖也可以确定一个相容关系
  • 最大相容类的集合是 $A$ 的一个覆盖，称为 $A$ 的完全覆盖，记作 $C_{R}(A)$
• 偏序关系
  • 自反，反对称性，传递性
  • 记作 $\leq$
  • 又称弱偏序关系，半序关系
  • 拟序关系：非自反，传递，记作 $<$
  • $R-R^0$ 是 $A$ 上的拟序关系
  • $A$ 与 $A$ 上的偏序关系 $R$ 称为偏序结构 / 偏序集，记作 $<A,R>$
  • 盖住关系：
    • 偏序集中 $x\leq y$ ，且中间不存在 $z$ ，则称之为盖住关系 $cov A$ ，写成 $<x,y>$ 的集合
    • 偏序集中盖住关系是唯一的，可以用它画偏序集的哈斯图
      • 每个顶点代表 $A$ 的一个元素
      • 若 $x\leq y$ 且 $x\neq y$ ，则 $y$ 在顶点 $x$ 上方
      • 若 $<x,y> \in cov A$ ，则 $x,y$ 间连无向边
  • 最小元，最大元（跟每一个元素都有关系），极小元，极大元（看图）
  • 上界（要跟每一个元素都有关系），下界，上确界 / 最小上界，下确界 / 最大下界（看图）
    • 某个偏序集 $A$ 中的子集 $B$ 的上下界和上下确界可能在 $B$ 中，也可能不在 $B$ 中但一定在 $A$ 中
    • 上界 / 下界不一定存在，不一定唯一
    • 上确界 / 下确界不一定存在，若存在必唯一
  • 可比：对偏序集 $<A,\leq>$ 中的 $x,y$ ， $x\leq y$ 或者 $y\leq x$ ，则 $x$ 和 $y$ 是可比的
  • 对偏序集 $<A,\leq>$ ，对任意的 $x,y \in A$ ， $x,y$ 都可比，则称之为 $A$ 上的全序关系，称为线序关系，则称这个偏序集为全序集。
  • 偏序集 $<A,\leq>$ 对任意的 $x,y \in B$ ，都可比，称 $B$ 为 $A$ 上的链， $B$ 中元素个数称为链的长度
  • 对任意的 $x,y \in B$ ， $x,y$ 不是可比的，则称 $B$ 为 $A$ 上的反链， $B$ 中元素个数称为反链的长度。
  • 对全序集， $A$ 和 $A$ 的任何子集都是链。
  • $A$ 中最长链的长度是 $n$ ，将 $A$ 中元素分成不相交的反链，反链个数至少 $n$ 。
  • 偏序集中 $A$ 的任何非空子集都有最小元，则称之为良序关系，称这个偏序集为良序集。
  • 一个良序集一定是全序集。
  • 一个有限的全序集一定是良序集。
  • 非良序的集合可以定义集合上的全序关系，使其称为良序集。任意集合都可以良序化。
• 拟序关系
  • 非自反，反对称，传递，记作 $<$
  • 强偏序关系
  • $R \cup R^0$ 是 $A$ 上的偏序关系

函数

• 函数：对任意 $x \in dom(f)$ ，存在唯一 $y$ 值使$xfy$ 成立 / 定义域中所有值都要满足关系（定义域所有，来自函数的定义本身）
• 从集合 $A$ 到集合 $B$ 的所有函数的集合记为 $A_{B}$ ，若 $A$ 和 $B$ 是有限集合，且$\mid A\mid=m$ ， $\mid B\mid=n$ ，则 $\mid AB\mid=n^m$
  • 从 $\emptyset$ 到 $\emptyset$ 的函数只有 $f=\emptyset$
  • 从 $\emptyset$ 到 $B$ 的函数只有 $f=\emptyset$
  • 若 $A$ 为非空集合，从 $A$ 到 $\emptyset$ 的函数不存在（ $A_{\emptyset}=\emptyset$ ，当 $A\neq \emptyset$）
  • $\emptyset_{\emptyset}=\emptyset_{B}=\{ \emptyset \}$
• 象 $f[A_{1}]$ ，完全原象 $f^{-1}[B_{1}]$ ，注意 $f^{-1}$ 表示逆关系，但不一定是逆函数
  • $f[\emptyset]=f^{-1}[\emptyset]=\emptyset$
• 满射 $ran(f)=B$
• 单射：对任意 $x_{1}$ ， $x_{2}$ 都有 $f(x_{1})\neq f(x_{2})$
• 满射+单射=双射
• 构造从 $N\times N$ 到 $N$ 的双射函数
  • 思路
  • $f(<m,n>)=\frac{(m+n)(m+n+1)}{2}+m$
• 常用函数
  • 常函数，对所有的 $x \in A$ ，有 $f(x)=y$
  • 恒等函数
  • 单调函数
  • $A^n\to A$ ， $A$ 上的 $n$ 元运算
  • $B_{C}$ 是从 $B$ 到 $C$ 所有函数的集合， $A\to B_{C}$ 称为一个泛函
  • 特征函数：若 $a \in A$ ，则特征函数取 $1$ ，反之取 $0$
• 典型映射 / 自然映射： $A\to A/R$ ， $g(a)=[a]_{R}$ ，称 $g$ 为典型映射或自然映射。
• 选择公理：对任意关系 $R$ ，存在函数 $f$ ，使得 $f \subseteq R$ ，且 $dom(f)=dom(R)$
  • 给每个关系 $R$ 都构造一个函数 $f$。
  • 同一 $x$ ，若有多个 $y$ ，挑一个放入 $f$ 中，构造的 $f$ 也可以有多个
• 函数的合成：
  • $g:A\to B$ ， $f:B\to C$ ，$f\circ g:A\to C$
  • $(f \circ g)(x)=f(g(x))$
  • 若 $f,g$ 是满 / 单 / 双射的，则 $f \circ g$ 是满 / 单 / 双射的
  • 若 $f \circ g$ 是满射的，则 $f$ 是满射的
  • 若 $f \circ g$ 是单射的，则 $g$ 是单射的
  • 双射的就是把前面俩结论加起来（考虑这几个定理的时候，可以考虑 $B$ 比 $A,C$ 都大的集合
  • $f=f \circ I_{A}=I_{B} \circ f$
• 函数的逆不一定是函数，双射的逆是函数，称为反函数，双射的反函数也是双射的
  • 对于双射 $f^{-1}(f(x))=x$ ， $f(f^{-1}(y))=y$
• 左逆与右逆
  • 若 $f:A\to B$ ， $g:B\to A$ ， $g \circ f=I_{A}$ ， $g$ 为 $f$ 的左逆
  • 若 $f \circ g=I_{B}$ ，则 $g$ 为 $f$ 的右逆
  • $f$ 存在左逆，当且仅当 $f$ 是单射的
  • $f$ 存在右逆，当且仅当 $f$ 是满射的
  • 存在左逆又存在右逆，当且仅当 $f$ 是双射的
  • 若 $f$ 是双射的，当且仅当 $f$ 是满射的
• 函数的性质
  • 对 $f:A\to B$ ， $g:C\to D$ ，对任意的 $x \in A \cap C$ ，都有 $f(x)=g(x)$ ，两函数相容
    • $C$ 是一堆函数组成的集合，若其中任意两个函数都相容，那么 $C$ 是相容的
  • 两函数相容，当且仅当 $f \cup g$ 是函数
  • 由一个相容的函数集合 $C$ ，可以构造函数 $F$ ，它开拓了 $C$ 中所有的函数
  • 若 $R$ 是 $A$ 上的等价关系，且 $f:A\to A$ ，对任意的 $x,y \in A$ ，有 $<x,y> \in R$ ，$<f(x),f(y)> \in R$ ，则称关系 $R$ 与函数 $f$ 是相容的
    • 存在唯一的函数 $F: A/R \to A / R$ ，使得 $F([x]_{R})=[f(x)]_{R}$
      • $A=\{ 1,2,3,4,5,6,7 \}$ ，商集 $A / R=\{ \{ 1,2,3 \},\{ 4,5 \},\{ 6,7 \} \}$ ， $f=\{ <1,4>,<2,5>,<3,5>,<4,3>,<5,2>,<6,1>,<7,3> \}$ ， $R$ 和 $f$ 相容，构造 $F=\{ <\{ 1,2,3 \},\{ 4,5 \}>,<\{ 4,5 \},\{ 1,2,3 \}>,<\{ 6,7 \},\{ 1,2,3 \}> \}$
• 开集与闭集（实数集合上开区间和闭区间概念的推广）
  • 距离： $p(x,y)=\mid x-y\mid$
  • $n$ 阶笛卡尔积 $R^n$ ，距离函数 $p(<x_{1},x_{2},\dots ,x_{n}>,<y_{1},\dots，y_{n}>>)=((x_{1}-y_{1})^2+\dots+(x_{n}-y_{n})^2)^{1/2}$
  • 在 $R_{2}$ 和 $R_{3}$ 上定义的距离就是在二维平面和三维空间中两点间的直线距离。
  • 邻域，与极限点（ $x_{0}$ 是 $A$ 的极限点，在 $x_{0}$ 附近， $A$ 的点是稠密的，且 $x_{0}$ 不一定在 $A$ 中）
    • 对于一个开区间 $A$ ，其中的元素和两端的端点都是 $A$ 的极限点，一个闭区间极限点的集合是它本身。
    • 空集没有极限点，有理数集 $Q$ 的极限点集合是实数集 $R$ （在任意实数附近，有理数和无理数都是稠密的。
    • 若 $A \subseteq R$ 是有界无限集，则 $A$ 具有极限点。
    • 若 $x_{0}$ 不是某集合中的极限点，则称其为 $A$ 的孤立点
    • 对实数集，其所有极限点的集合为 $A$ 的导集，记作 $A'$ ，若 $A' \subseteq A$ ，则称 $A$ 为闭集（ $A$ 的极限点都在 $A$ 中）
      • $R$ 是闭集，有理数集 $Q$ 不是闭集
      • $\emptyset$ 是闭集
      • 任意个闭集的交 / 并集也是闭集
  • 对实数集 $R$ ， $A \subseteq R$ ， $x_{0} \in R$ ，若存在 $x_{0}$ 的 $\epsilon$ 邻域，其中全是 $A$ 的元素，则称 $x_{0}$ 是 $A$ 的一个内点。
    • 对实数集 $R$ ， $A \subseteq R$，若 $A$ 的元素都是 $A$ 的内点，则称 $A$ 为开集
      • $R$ 是开集，有理数集 $Q$ 没有内点（元素的任一个 $\epsilon$ 邻域内都有无理数），所以 $Q$ 不是开集
    • 任意个开集的并集是开集，有限个开集的交集是开集
  • 若 $A$ 是开集，则 $R-A$ 是闭集
  • 若 $A$ 是闭集，则 $R-A$ 是开集

图论

图

• 结点表示事物，边表示它们之间的联系
• $(V(G),E(G))$ 称为图， $V(G)$ 是结点集， $E(G)$ 是边集，$\mid V\mid=n$，$\mid E\mid=m$
  • 自环：只与一个结点相关联的边
  • 重边：同一对结点之间存在多条边
  • 度：与某节点关联的边数称为度，用 $d(v)$ 表示，自环对度的贡献为 $2$
    • 出度 $d^+(v)$ ，入度 $d^-(v)$
    • $d(v)=d^+(v)+d^-(v)$
• 简单图：不存在重边、自环
  • 非空简单图中一定存在度相同的结点（ $n$ 个结点的简单图， $d(V)$ 的取值范围是 $1\sim n-1$ ，由鸽巢原理，一定存在）
• 没有任何边的简单图 $(V,\emptyset)$ ，称为空图 $N_{n}$
• 平凡图：$\mid V\mid=1$
• 任意两个结点间都有边的简单图称为完全图 $K_{n}$ ，每个结点的度都是 $n-1$ ，边数为 $\frac{n(n-1)}{2}$
• $\sum_{v \in V(G)} d(v)=2m$
• $G$ 中度数为为奇数的结点必为偶数个
• 有向图 $G$ 中正度之和等于负度之和
• 子图：
  • 生成子图 / 支撑子图：给定 $G=(V,E)$ ，若存在 $G'=(V',E')$ ，满足 $V'=V$ ，$E'\subseteq E$
    • 空图是 $G'$ 的支撑子图
  • 导出子图： $V'\subseteq V$ ，且 $E'$ 包含了结点子集之间的所有边
  • $G$ 自身既是支撑子图，也是导出子图
• 交（边和点集分别取交），并（边和点集分别取并），对称差（点取并，边 $E=E_{1}\oplus E_{2}$
• 删去子图也即删去子图的边 / 删去结点，也即删去结点和其关联的边
• 邻点集 $\Gamma(v)=\{ u\mid(v,u)\in E \}$
  • 后继集 $\Gamma^+(v)$
  • 前趋集 $\Gamma^-(v)$
• 同构的图（两图的各点 / 边存在双射）
  • 必要条件
    • 边 / 点的个数相等
    • 结点度的非递增序列相同
    • 存在同构的导出子图
• 强连通分量：使用 Tarjan 算法 Tarjan’s Algorithm | Baeldung on Computer Science
• 表示
  • 邻接矩阵
    • $v_{i}$ 出度：第 $i$ 行之和
    • $v_{j}$ 入度：第 $j$ 列之和
    • 无权值的无向图的邻接矩阵是对称矩阵
    • 不能表示重边
  • 关联矩阵
    • 表示结点与边之间的关联关系
    • $n\times m$ 的矩阵
    • $M[i,j]=1$ 若 $v_{i}$ 是边 $e_{j}$ 的始点，若是终点，就是 $-1$ ，其他点为 $0$
    • 每列只有两个非零元： $1$ 和 $-1$
    • 可以表示重边，但不能表示自环
    • 无向图：是端点的为 $1$ ，不是端点的为 $0$
  • 若能用上述两种矩阵表示，则表示是唯一的。
  • 邻接表
    • 每个 Node ：邻接点的编号，边权值，下一个结点的地址指针
    • 便于增加和删除边，可以表示重边和自环，可以唯一表示任何一个图
• 道路与回路
  • 道路：需要边首尾相连，只要终点和始点重合，就是回路
  • 若 $P$ 中的边没有重复出现，则称为简单有向道路和简单有向回路
  • 简单有向道路 + 结点不重复出现：初级有向道路和初级有向回路（头尾可以重复）
  • 长度为边数
• 无向图任意两结点之间都存在道路，称 $G$ 为连通图，否则为非连通图
  • 对于一个简单图，当 $m> \frac{(n-1)(n-2)}{2}$ ， $G$ 是连通图（证明方法：假设含有 $2$ 个连通分支，之后证明相反的结论）
  • $n$ 个结点的连通图的边数一定 $\geq n-1$
  • 两点间距离：连通的两点之间的最短道路长度称为 $u$ 与 $v$ 的距离。
  • 割点：去掉该点后，图的连通分支数上升
  • 割边：去掉该边后，图的连通分支数上升
• 有向图不考虑边的方向，若连通也是连通图
• 连通子图不是 $G$ 的任何连通子图的真子图，称为极大连通子图或者连通支
• $C$ 是简单图 $G$ 中含结点数大于 $3$ 的初级回路，若其中有两结点不相邻，而两点所连边 $\in E(G)$ ，则称 $(v_{i},v_{j})$ 是 $C$ 的一条弦
• 极长初级道路：路径的两个端点不与初级道路本身之外的任何结点相邻，称为极长初级道路。
• 图 $G$ 的顶点集 $V(G)$ 可以分成两个不相交的非空子集 $V_{1}$ 和 $V_{2}$ ，使得 $G$ 的每条边的两个端点分别在 $V_{1}$ 和 $V_{2}$ ，称为二分图
  • 可能不唯一
  • 若二分图中的每个顶点与 $V_{2}$ 的每个顶点都邻接，则称 $G$ 为完全二分图，记为 $K_{m,n}$ ， $\mid V_{1}\mid=m$ ， $\mid V_{2}\mid=n$
  • 含有 $K_{3}$ 子图的图一定不是二分图
  • $K_{n}$ 不是二分图
  • 若二分图中存在回路，则它们都是由偶数条边构成的
• 补图：顶点集相等，边互补
• 欧拉道路与回路
  • 欧拉回路： $G=(V,E)$ 中一条经过所有边的简单回路称为欧拉回路
  • 无向连通图 $G$ 存在欧拉回路的充要条件是 $G$ 中各结点的度都是偶数。
  • 若无向连通图 $G$ 中只有 $2$ 个度为奇的结点，则 $G$ 存在欧拉道路（在这两个度为奇的结点上加一条边，正好构成欧拉回路）
  • 有向连通图：所有顶点的出度与入度都相等；或者除两个顶点外，之差为 $1$ ，另一个顶点的出度与入度之差为 $-1$
  • 由偶点组成的连通图，一定可以一笔画成（任意一点开始，任意一点为终点）；只有两个奇点的连通图一定可以一笔画成（一个奇点为起点，一个奇点为终点）；其他图可以用奇点除二计算出需要几笔画成
• 寻找欧拉回路的方法
  • 判断是否存在欧拉回路
  • 首先找到一条回路，之后从它的补图中继续寻找回路
  • 最终可以找到包含了 $G$ 的所有边的简单回路，它便是欧拉回路
• 连通图 $G=(V,E)$ 有 $k$ 个度为奇数的结点（ $k$ 为偶数），那么可以划分成 $\frac{k}{2}$ 条简单道路（证明：在这 $k$ 个结点间增加 $\frac{k}{2}$ 条边，每个结点与其中一条边关联，增加边之后，新图包含一个欧拉回路 $C$）
• 哈密顿道路与回路
  • 无向图的过全部结点的初级回路称为 $G$ 的哈密顿回路（ $H$ 回路）
  • 判定 $H$ 回路存在性问题一般是针对简单图的（因为含有重边和自环的图删去上述两者， $H$ 道路的存在性是等价的
  • 设 $P$ 是图 $G$ 中一条极长的初级道路（有 $l$ 个点），且 $d(v_{1})+d(v_{l})\geq l$ ，则 $G$ 中一定存在经过这些结点的初级回路。
  • 充分性定理（通过这些定理一定能判断）
    • 若简单图 $G$ 的任意两结点 $v_{i},v_{j}$ 之间恒有 $d(v_{i})+d(v_{j})\geq n-1$ ，则可判断存在哈密顿道路
    • 若任意两结点恒有 $d(v_{i})+d(v_{j})\geq n$ ，则存在哈密顿回路。
    • 若简单图 $G$ 中每个结点的度都大于等于 $\frac{n}{2}$ ，则有 $H$ 回路
  • 必要性定理（逆否命题可以判断一个图不是哈密顿图）
    • 若 $G$ 是哈密尔顿图，则对于 $V(G)$ 的每个非空真子集 $S$ ，均有 $W(G-S)\leq\mid S\mid$ ，其中 $W(G-S)$ 是 $G-S$ 中连通分支数。
    • 有奇数个顶点的二部图
  • 彼得森图不是哈密尔顿图，与之同构的图也一定不是哈密尔顿图，但其中存在哈密顿道路
  • 有奇数个顶点的二分图必不是哈密顿图
• 仅有哈密顿通路而无哈密顿回路的图不是哈密顿图
• $G$ 的闭合图 $C(G)$
  • 不断连接相加后度大于等于 $n$ 的两不相邻结点对，直至没有
  • 简单图 $G$ 的闭合图是唯一的
• 简单图 $G$ 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路
• 对一个哈密顿图，可以用 $A$ ， $B$ 交替标记所有的顶点（某顶点标记为 $A$ ，其邻接点标记 $B$ ），则有 $\mid A\mid=\mid B\mid$
• 若无法用 $A,B$ 交替标记顶点，也无法判断是否是哈密顿图

树

• 不含任何回路的图称为“林”，若这个图还是连通的（只有一个连通支），就称为树，边称为树枝，度为 $1$ 的结点称为树叶
• 度相关
  • 孤立点：度为 $0$
  • 悬点：度为 $1$ ；悬边：与悬点关联的边
  • 奇点：度为奇数的顶点
  • 偶点：度为偶数的顶点
  • 正则图：各顶点度相同（eg： $K_{n}$ 是 $n-1$ 正则图）
  • 含 $n$ 个点的树，度数为 $2n-2$ ，也即 $2(n-1)$
• 树的每条边都不属于任何回路，叫做割边
  • 删去割边之后，割边的两结点属于不同的分支
  • 一条割边不属于 $G$ 的任何回路
• 树（ $n\geq 2$ ）具有如下性质
  • 连通且无回路
  • 连通，且每条边都是割边
  • 连通且有 $n-1$ 条边
  • 有 $n-1$ 条边且无回路
  • 任意两结点间有唯一道路
  • 无回路，在任两结点间加上一条边后恰有一个回路
  • 树是极小的连通图
  • 树是极大的不含回路的连通图
• 对于一个图：支撑子图+树=支撑树 / 生成树 / 图的树
• 求完全图不同构的生成树：也即将 $2(n-1)$ 个度分配给 $n$ 个结点
• 任何无向连通图 $G$ 都具有生成树，一个连通图的生成树可能不唯一
  • $G-T$ 删去 $T$ 中各边后的子树为 $T$ 的余树，不一定连通，也不一定无回路，所以它不一定是树，更不一定是生成树
• 二叉树
  • 二叉树的第 $i$ 层至多有 $2^{i-1}$ 个结点
  • 满二叉树：高度为 $k$ 并且有 $2^k-1$ 个结点的二叉树，任意一层的结点个数都达到了最大值
  • 完全二叉树：满二叉树最后一层自右至左依次删去若干个结点的二叉树
    • 叶子结点个数的范围为 $2^{k-2},2^{k-1}$
    • 所有的叶结点都出现在最低的两层上
    • 右子树为 $k$ ，左子树高度为 $k$ 或者 $k+1$
  • 满二叉树一定是完全二叉树，但反之不是
• 路径：从根到树叶 $v_{i}$ 包含的边数
  • 带权路径长度：$WPL=\sum_{i}l_{i}w_{i}$
• 带权路径长最小的二叉树称为最优二叉树
  • 也即哈夫曼树，算法略。
  • “二进制字符串不允许带空格”的意思是空格不是特殊代码表示，而是作为普通字母被使用
• 最短树（最小生成树）
  • 在赋权连通图中，计算该图总长最小的支撑树（最小生成树）
  • $\rm{Kruskal}$ 算法
    • 不断往 $T$ 中加入当前的最短边 $e$ ，若此时构成回路，则一定是回路中的最长边，删之，直至达到 $n-1$ 条边为止
    • 复杂性 $O(m+p*\log m)$
  • $\mathrm{Prim}$ 算法
    • 任选一节点，之后不断在剩下的边中选一条到这个点集中最短的边，直到 $n-1$ 条边为止