离散数学及其应用 (Discrete Mathematics)

第一章：基础：逻辑和证明

1. 命题逻辑基础 (1.1 - 1.2)

考点： 什么是命题、连接词、优先级、翻译（符号化）。

• 命题 (Proposition)：
  • 定义：能判断真假的陈述句。
  • 避坑：感叹句、疑问句、祈使句、含变量未赋值的句子（如 $x+1=2$）都不是命题。
• 逻辑连接词 (Connectives)：
  1. 否定 (Negation, $\neg p$)：非 $p$。
  2. 合取 (Conjunction, $p \wedge q$)：$p$ 且 $q$。（全真才真）
  3. 析取 (Disjunction, $p \vee q$)：$p$ 或 $q$。（全假才假，注意包含“两者都”的情况）。
  4. 条件语句 (Implication, $p \rightarrow q$)：如果 $p$，则 $q$。
     • 死记硬背：只有当 $p$ 真且 $q$ 假 时，结果为 假 (F)。其他情况全为真。
     • 术语：$p$ 是前件（假设），$q$ 是后件（结论）。
  5. 双向条件 (Biconditional, $p \leftrightarrow q$)：当且仅当。
     • 同真同假时为 真 (T)，异值为 假 (F)。
• 优先级 (Priority)：
  • $\neg$ (最高) $\to$ $\wedge$ $\to$ $\vee$ $\to$ $\rightarrow$ $\to$ $\leftrightarrow$ (最低)。
  • 考试技巧：看到复杂式子，先标括号再做。

2. 命题等价式 (1.3)

考点： 判断重言式/矛盾式、熟记关键等价公式。

• 分类：
  • 重言式 (Tautology)：永真式（无论变量取什么，结果永远是 T）。
  • 矛盾式 (Contradiction)：永假式（永远是 F）。
  • 或然式 (Contingency)：既非永真也非永假。
• 必背等价公式 (用于化简和证明)：
  1. 德摩根定律 (De Morgan’s Laws)：
     • $\neg(p \wedge q) \equiv \neg p \vee \neg q$
     • $\neg(p \vee q) \equiv \neg p \wedge \neg q$
     • 口诀：否定号进括号，且变或，或变且。
  2. 蕴含消除 (最重要的公式)：
     • $p \rightarrow q \equiv \neg p \vee q$
     • 用途：几乎所有的化简题，第一步都是把 $\rightarrow$ 变成 $\vee$。
  3. 逆否命题：
     • $p \rightarrow q \equiv \neg q \rightarrow \neg p$ (原命题与逆否命题同真同假)。

3. 谓词与量词 (1.4)

考点： 全称与存在、量词的否定。

• 谓词：$P(x)$，如 “$x > 3$”。只有赋予具体值或加量词后才变成命题。
• 量词：
  • $\forall x$ (全称)：对所有 $x$。
  • $\exists x$ (存在)：存在至少一个 $x$。
• 德摩根定律（量词版）—— 必考：
  • $\neg \forall x P(x) \equiv \exists x \neg P(x)$
  • $\neg \exists x P(x) \equiv \forall x \neg P(x)$
  • 操作：否定号穿过量词，量词翻转（$\forall$ 变 $\exists$），否定号停在谓词前。

4. 嵌套量词 (1.5)

考点： 顺序的重要性、翻译句子。

• 顺序不能乱：
  • $\forall x \exists y P(x, y)$：对每个人 $x$，都有一个对应的 $y$ 爱他。（每个人都有爱人，爱人可以不同）。
  • $\exists y \forall x P(x, y)$：存在一个特定的人 $y$，所有 $x$ 都爱他。（全班有一个万人迷）。
• 否定操作：
  • $\neg \forall x \exists y P(x, y) \equiv \exists x \forall y \neg P(x, y)$。
  • 技巧：像剥洋葱一样，把 $\neg$ 一层层往里送，每过一层量词就变号。

5. 推理规则 (1.6) —— 第一章最难点/大题考点

考点： 提纲强调“熟练书写规范的推理步骤”，这通常对应 10 分的证明题。

核心推理规则 (必须能默写)：

1. 假言推理 (Modus Ponens): $p \rightarrow q, p \Rightarrow q$
2. 拒取式 (Modus Tollens): $p \rightarrow q, \neg q \Rightarrow \neg p$
3. 假言三段论 (Hypothetical Syllogism): $p \rightarrow q, q \rightarrow r \Rightarrow p \rightarrow r$
4. 析取三段论 (Disjunctive Syllogism): $p \vee q, \neg p \Rightarrow q$ (如果不是A，那肯定是B)
5. 化简 (Simplification): $p \wedge q \Rightarrow p$
6. 附加 (Addition): $p \Rightarrow p \vee q$

解题格式规范 (自然演绎推理)：
题目通常是：给定前提 $A, B, C…$，证明结论 $D$。

示例写法：

已知前提：
(1) $p \rightarrow q$
(2) $\neg q$
求证：$\neg p$

证明步骤 (Proof Sequence)：

注意：提纲里说“重点掌握自然演绎系统中的直接证明方法”，这意味着你不需要用反证法去凑，而是顺着前提一步步推到结论。

第一章复习自测题 (脑补一下)

1. 选择题考法：$p \rightarrow q$ 的逆否命题是什么？(答案：$\neg q \rightarrow \neg p$)
2. 填空题考法：$\neg \forall x (P(x) \rightarrow Q(x))$ 的等价式是？
   • 解析：
     1. 变量词：$\exists x \neg (P(x) \rightarrow Q(x))$
     2. 变蕴含：$\exists x \neg (\neg P(x) \vee Q(x))$
     3. 进括号：$\exists x (P(x) \wedge \neg Q(x))$
3. 大题考法：构造推理证明。
   • 前提：如果今天下雨，我就不打篮球。如果我不打篮球，我就去学习。今天没去学习。
   • 结论：今天没下雨。
   • 技巧：先符号化，再列表证明。

第二章：基本结构 (集合与矩阵)

1. 集合 (Sets) (2.1)

考点： 集合运算、幂集、笛卡尔积、集合相等的证明。

• 基本概念：

  • 子集 ($\subseteq$)：$A \subseteq B$ 意味着 $A$ 中所有元素都在 $B$ 中。
  • 真子集 ($\subset$)：$A \subseteq B$ 且 $A \neq B$。
  • 空集 ($\emptyset$)：不包含任何元素的集合。注意：$\emptyset \subseteq A$ 对任何集合成立。
  • 基数 ($|A|$)：集合中不同元素的个数。

• 幂集 (Power Set, $P(A)$)：

  • 定义：集合 $A$ 的所有子集组成的集合。
  • 核心考点：如果 $|A| = n$，则 $|P(A)| = 2^n$。
  • 易错点：$\emptyset$ 的幂集是 ${\emptyset}$，大小为 $2^0=1$。

• 笛卡尔积 (Cartesian Product, $A \times B$)：

  • 定义：所有有序对 $(a, b)$ 的集合，其中 $a \in A, b \in B$。
  • 基数：$|A \times B| = |A| \cdot |B|$。

• 集合运算 (Operations)：

  • 并 ($\cup$) $\leftrightarrow$ 逻辑或 ($\vee$)
  • 交 ($\cap$) $\leftrightarrow$ 逻辑且 ($\wedge$)
  • 补 ($\bar{A}$) $\leftrightarrow$ 逻辑非 ($\neg$)
  • 差 ($A - B$)：${x \mid x \in A \wedge x \notin B}$。等价公式：$A - B = A \cap \bar{B}$ (常用)。

• 【重点题型】集合相等的证明 ($A=B$)：

  • 提纲明确提到了“集合相等的证明”，这通常是一道 证明题 (5-10分)。
  • 万能证明法 (双向包含法)：
    要证 $A = B$，分两步走：
    1. 先证 $A \subseteq B$：任取 $x \in A$，利用定义和逻辑推导，证明 $x \in B$。
    2. 再证 $B \subseteq A$：任取 $x \in B$，同理证明 $x \in A$。
  • 或者利用集合恒等式 (Set Identities)：
    类似逻辑等价变形，如分配律、德摩根定律。
    • $\overline{A \cap B} = \bar{A} \cup \bar{B}$
    • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

2. 矩阵 (Matrices) (2.6)

考点： 加减乘、转置、对称矩阵。（注：不涉及求逆、行列式等线性代数深层内容）

• 基本运算：

  • 加/减：维度必须相同，对应位置相加减。
  • 乘法 ($AB$)：
    • 条件：$A$ 的列数 = $B$ 的行数。
    • 结果：$A (m \times k)$ 乘 $B (k \times n)$ 得到 $C (m \times n)$。
    • 算法：$C_{ij}$ = ($A$ 的第 $i$ 行) 点积 ($B$ 的第 $j$ 列)。
    • 注意：矩阵乘法不满足交换律 ($AB \neq BA$)。

• 转置 (Transpose, $A^T$ 或 $A^t$)：

  • 把行变成列。$A_{ij}$ 变成 $A^T_{ji}$。

• 对称矩阵 (Symmetric Matrix)：

  • 定义：$A = A^T$。
  • 特征：必须是方阵，且关于主对角线对称 ($a_{ij} = a_{ji}$)。

第二章复习自测与技巧

1. 易错点检测：
   • 问：集合 ${1, 2}$ 的幂集是什么？
   • 答：${\emptyset, {1}, {2}, {1, 2}}$ (共4个元素)。漏掉 $\emptyset$ 或自身是最常见的错误。
2. 计算题技巧：
   • 如果考到矩阵乘法，通常维度不会很大（如 $2 \times 2$ 或 $3 \times 3$）。
   • 一定要列出计算过程，不要直接写答案，防止算错一个数字全扣分。
3. 证明题套路：
   • 题目：证明 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
   • 解法开头：
     • “$\Rightarrow$ (包含于): 任取 $x \in A \cap (B \cup C)$…”
     • “…由定义知 $x \in A$ 且 $x \in (B \cup C)$…”
     • “…即 $x \in A \wedge (x \in B \vee x \in C)$…”
     • “…利用逻辑分配律…”

第三章：计数 (Counting)

1. 基础计数法则 (3.1)

考点： 什么时候用加，什么时候用乘？

• 加法原理 (Sum Rule)：
  • 关键词：“分类”。完成一件事有几类办法，每类互不相容。
  • 计算：类A方法数 + 类B方法数。
• 乘法原理 (Product Rule)：
  • 关键词：“分步”。完成一件事需要连续做几个步骤。
  • 计算：步1方法数 $\times$ 步2方法数。
• 减法原理 (Inclusion-Exclusion for 2 sets)：
  • $|A \cup B| = |A| + |B| - |A \cap B|$。
  • 应用：直接算很难，算出总数减去“不满足条件”的情况。

2. 鸽巢原理 (Pigeonhole Principle) (3.2)

考点： 识别谁是鸽子，谁是笼子。

• 原理 (基础版)：
  • $k+1$ 个物体放入 $k$ 个盒子，至少有一个盒子包含 $\ge 2$ 个物体。
• 广义鸽巢原理 (Generalized) —— 必考计算/证明：
  • $N$ 个物体放入 $k$ 个盒子，至少有一个盒子包含 $\lceil N/k \rceil$ 个物体。
  • 注：$\lceil x \rceil$ 表示向上取整（Ceiling function），例如 $\lceil 3.1 \rceil = 4$。
• 解题套路：
  • 找 $N$ (物体)：通常是“人”、“分数”、“苹果”。
  • 找 $k$ (盒子)：通常是“星座”、“星期”、“成绩等级”、“余数”。
  • 例题：某班多少人才能保证至少有2人生日是同一个月？
    • $k=12$ (月份)，要求结果 $\ge 2$，即 $\lceil N/12 \rceil = 2$。
    • $N > 1 \times 12$，最小 $N = 13$。

3. 排列与组合 (Permutations & Combinations) (3.3)

考点： 有序 vs 无序。

• 排列 $P(n, r)$：有序。从 $n$ 个里选 $r$ 个排队。
  • 公式：$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times \dots$ (乘r项)。
  • 场景：选主席副主席、排队照相、数字排列。
• 组合 $C(n, r)$：无序。从 $n$ 个里选 $r$ 个组队。
  • 公式：$C(n, r) = \frac{n!}{r!(n-r)!} = \binom{n}{r}$。
  • 性质：$C(n, r) = C(n, n-r)$。
  • 场景：选委员会、买彩票、发牌。

4. 排列组合的推广 (3.5) —— 难点

考点： 可重复选择、物体放入盒子。

• 有重复元素的排列：

  • 问题：单词 “MISSISSIPPI” 有多少种排列？
  • 公式：$\frac{n!}{n_1! n_2! \dots n_k!}$。
  • 解释：总字母数阶乘除以重复字母个数的阶乘。

• 有重复元素的组合 (Stars and Bars / 隔板法)：

  • 问题：$n$ 个相同元素放入 $k$ 个不同盒子（允许盒子为空）。
    • 或者：方程 $x_1 + x_2 + \dots + x_k = n$ 的非负整数解个数。
  • 公式（死记）：$C(n+k-1, n)$ 或 $C(n+k-1, k-1)$。
  • 记忆法：想象有 $n$ 个球和 $k-1$ 个隔板，混在一起全排列。

• 物体放入盒子 (Distributing Objects into Boxes)：
  提纲特别指出“主要是前两种情形”：

  1. 不同物体 $\to$ 不同盒子：
     • 每个物体有 $k$ 种选择，共 $n$ 个物体。
     • 公式：$k^n$。
  2. 相同物体 $\to$ 不同盒子：
     • 这就是上面的“隔板法”/重复组合。
     • 公式：$C(n+k-1, n)$。

第三章复习自测与避坑指南

1. 区分 $P$ 和 $C$：
   • 密码锁 (有序) $\to$ $P$ (或 $n^r$)。
   • 水果拼盘 (无序) $\to$ $C$。
2. 区分 $n$ 和 $k$ (鸽巢)：
   • 如果题目问“至少多少人…”，那我们在求 $N$。
   • 如果题目问“至少有几人…”，那我们在求 $\lceil N/k \rceil$。
3. 隔板法典型题：
   • “买10个面包，有3种口味，每种至少买一个”怎么算？
   • 解法：先每种口味拿1个（剩7个要买），转化为“7个相同面包放进3个不同口味篮子”。
   • $n=7, k=3 \Rightarrow C(7+3-1, 7) = C(9, 7) = C(9, 2)$。

第四章：高级计数技术

1. 递推关系的构造 (Modeling with Recurrence Relations) (4.1)

考点： 读懂应用题，写出 $a_n$ 和前几项 ($a_{n-1}, a_{n-2}$) 的关系。

• 定义：一个序列的第 $n$ 项 $a_n$ 等于前面几项的函数。记得要写初始条件（如 $a_0$ 或 $a_1$）。
• 经典模型（背下来，考试直接套）：
  1. 复利问题 (Compound Interest)：
     • 存钱 $P$，利息 $r$。
     • 递推式：$a_n = (1+r) a_{n-1}$。
  2. 兔子繁殖 / 斐波那契 (Fibonacci)：
     • 每对兔子一个月后成年，成年后每月生一对。
     • 递推式：$a_n = a_{n-1} + a_{n-2}$。
     • 逻辑：第 $n$ 个月的兔子 = 上个月原本有的 ($a_{n-1}$) + 新出生的 (等于两个月前的兔子数 $a_{n-2}$)。
  3. 汉诺塔 (Tower of Hanoi)：
     • $n$ 个盘子从柱子1移到柱子3。
     • 递推式：$H_n = 2H_{n-1} + 1$。
     • 逻辑：先把 $n-1$ 个移到中间 ($H_{n-1}$)，把最大的移到目标 (+1)，再把 $n-1$ 个移到目标 ($H_{n-1}$)。
  4. 不含连续0的位串 (Bit strings without consecutive 0s)：
     • 长度为 $n$ 的二进制串，不能有 “00”。
     • 递推式：$a_n = a_{n-1} + a_{n-2}$ (形式同斐波那契)。
     • 推导技巧：
       • 若第 $n$ 位是 1，则前 $n-1$ 位任意合法 ($a_{n-1}$)。
       • 若第 $n$ 位是 0，则第 $n-1$ 位必须是 1，前 $n-2$ 位任意合法 ($a_{n-2}$)。

2. 容斥原理 (Inclusion-Exclusion Principle) (4.5)

考点： 求并集大小，或者求“都不满足”的数量。

• 基本公式：
  • 两集合：$|A \cup B| = |A| + |B| - |A \cap B|$
  • 三集合（必背）：
    $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$
  • 口诀：奇加偶减。（单个加，两两减，三三加…）

3. 容斥原理的应用 (Applications) (4.6)

考点： 错排问题、筛选法。

• 应用场景1：求补集（None of the properties）

  • 问题：求 $1$ 到 $100$ 之间不能被 2 或 3 整除的数。
  • 解法：$N - |P_1 \cup P_2|$。先用容斥原理算能被整除的，再用总数减去它。

• 应用场景2：错排问题 (Derangements)

  • 经典题目：帽子问题（所有人拿错帽子）、信封问题（所有信装错信封）。
  • 定义：$D_n$ 表示 $n$ 个元素都不在原来位置上的排列数。
  • 公式（由于不考递推求解，建议记一下前几个数）：
    • $D_1 = 0$
    • $D_2 = 1$ (21)
    • $D_3 = 2$ (231, 312)
    • $D_4 = 9$
    • 通用公式：$D_n = n! [1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} ] \approx \frac{n!}{e}$

• 应用场景3：满射函数的个数 (Onto Functions)

  • 从 $m$ 个元素到 $n$ 个元素的满射个数。
  • 解法：利用容斥原理排除掉“不是满射”（即值域漏掉1个、漏掉2个…）的情况。

第四章复习自测

1. 构造题：
   • 题目：某人上楼梯，一步可以跨1阶或2阶，上 $n$ 阶楼梯有多少种走法？
   • 答案：$a_n = a_{n-1} + a_{n-2}$。
   • 分析：最后一步要么是跨1阶上来的（前 $n-1$ 阶的方法数），要么是跨2阶上来的（前 $n-2$ 阶的方法数）。
2. 容斥计算：
   • 题目：求不超过 100 的素数个数？或者求不能被 2, 3, 5 整除的数。
   • 注意：画三个圈的图（Venn图），先把中间填好，再填周围。
3. 避坑：
   • 千万不要在考试时去尝试解 $r^2 - r - 1 = 0$ 这种方程求通项，提纲说了不考！只要求列出关系式即可。

第五章：关系 (Relations)

1. 关系的性质 (Properties) (5.1)

考点： 给你一个矩阵或关系图，判断它是否满足以下性质（必考选择或填空）。

• 自反性 (Reflexive)：
  • 定义：$\forall a \in A, (a, a) \in R$。
  • 矩阵特征：主对角线全为 1。
  • 图特征：每个点都有自环。
• 对称性 (Symmetric)：
  • 定义：若 $(a, b) \in R$，则 $(b, a) \in R$。
  • 矩阵特征：关于主对角线对称 ($M = M^T$)。
  • 图特征：如果是单向边，必须成对出现（有去必有回）。
• 反对称性 (Antisymmetric) —— 易错点：
  • 定义：若 $(a, b) \in R$ 且 $(b, a) \in R$，则 $a = b$。
  • 通俗理解：两个不同的点之间，不能同时有双向边（要么没边，要么只有单向边）。
  • 矩阵特征：对于 $i \neq j$，如果 $m_{ij}=1$，则必须 $m_{ji}=0$。
• 传递性 (Transitive)：
  • 定义：若 $(a, b) \in R$ 且 $(b, c) \in R$，则 $(a, c) \in R$。
  • 检测方法：如果在图中能走两步到达某点，那么必须能一步直接到达。

2. 关系的合成 (Composition) (5.1)

考点： 计算 $S \circ R$。

• 定义：$S \circ R = {(a, c) \mid \exists b, (a, b) \in R \wedge (b, c) \in S}$。
• 注意顺序：$S \circ R$ 意味着先走 $R$，再走 $S$（就像函数 $f(g(x))$ 是先算 $g$）。
• 矩阵算法：$M_{S \circ R} = M_R \times M_S$（逻辑矩阵乘法，加法变逻辑或，乘法变逻辑且）。

3. 闭包 (Closures) (5.4)

考点： 缺什么补什么。

• 定义：包含关系 $R$ 且满足特定性质（自反/对称/传递）的最小关系。
• 求法：
  • 自反闭包：在对角线补 1（加自环）。
  • 对称闭包：如果 $a \to b$，就补上 $b \to a$。
  • 传递闭包 ($R^*$)：如果 $a \to \dots \to z$（有一条路径），就补上 $a \to z$（直达边）。注：提纲说不考Warshall算法，所以大概率考小规模图的手推。

4. 等价关系 (Equivalence Relations) (5.5)

考点： 判定与等价类。

• 定义：同时满足 自反 + 对称 + 传递 的关系。（口诀：RST）
• 典型例子：
  • “$=$” (相等)。
  • “$\equiv \pmod m$” (同余)。
  • “朋友的朋友是朋友”（假设这也是传递的）。
• 等价类 (Equivalence Class, $[a]$)：
  • 所有与 $a$ 有关系元素的集合。
• 划分 (Partition)：
  • 等价关系会将集合切分成若干个不相交的块（等价类）。

5. 偏序关系 (Partial Orderings) (5.6) —— 难点

考点： 哈塞图、极大/极小元、上界/下界。

• 定义：同时满足 自反 + 反对称 + 传递 的关系。（口诀：RAT）

  • 例子：$\le$ (小于等于)，$\subseteq$ (包含于)，$a \mid b$ (整除)。

• 哈塞图 (Hasse Diagram) —— 必会画：

  • 画法步骤：
    1. 去掉所有自环（因为默认自反）。
    2. 去掉所有传递边（因为默认传递，如 $a \to b \to c$，去掉 $a \to c$）。
    3. 箭头全都不画，默认方向是从下往上。
  • 整除关系题：画出 ${1, 2, 3, 4, 6, 12}$ 的整除哈塞图。1在最底，12在最顶。

• 极值概念辨析 (The Most Confusing Part)：
  假设给定一个子集 $A$：

  1. 极大元 (Maximal)：在它上面没有点了。（可以有多个，比如图顶端的几个分叉）。
  2. 最大元 (Greatest)：它是唯一的最高点，所有其他点都在它下面。（可能不存在）。
  3. 上界 (Upper Bound)：一个元素 $u$，使得 $A$ 中所有元素都在 $u$ 下面。
  4. 最小上界 (Least Upper Bound, LUB / Supremum)：所有上界里最小的那个。

第五章复习自测与技巧

1. 反对称的陷阱：
   • 问：矩阵全为 0 是反对称的吗？
   • 答：是！因为不存在“$m_{ij}=1$ 且 $m_{ji}=1$”的情况，条件自然满足（空真）。
2. 哈塞图看图技巧：
   • 找最大元：看最上面是不是只有一个点，且这个点连着下面所有线。如果是两个分叉的头，那就没有最大元，只有两个极大元。
   • 找最小上界 (LUB)：
     • 题目：在 ${2, 3, 4, 6, 12}$ 整除关系中，找 ${2, 3}$ 的 LUB。
     • 步骤：
       1. 找 ${2, 3}$ 的公共倍数（上界）：6, 12。
       2. 找最小的：6。
3. 合成运算顺序：
   • $f: A \to B, g: B \to C$。合成是 $g \circ f$。
   • 关系矩阵也是 $M_S \times M_R$ 表示先 $R$ 后 $S$。

第六章：图 (Graphs)

1. 图的基本术语 (6.1 - 6.2)

考点： 握手定理、特殊图的符号与边数。

• 握手定理 (Handshaking Theorem) —— 必考计算：
  • 公式：$\sum_{v \in V} \deg(v) = 2|E|$。
  • 含义：所有顶点的度数之和 = 边数的 2 倍。
  • 推论：度数为奇数的顶点个数必为偶数。
  • 题型：已知一个图有 3 个度为 4 的点，4 个度为 3 的点…求边数。
• 常见特殊图 (记符号和边数)：
  1. 完全图 ($K_n$)：任意两点都相连。边数 $= C(n, 2) = \frac{n(n-1)}{2}$。
  2. 圈图 ($C_n$)：$n$ 个点围成一圈。$n \ge 3$。度数全是 2。
  3. 轮图 ($W_n$)：中间加一个点连向 $C_n$ 的所有点。总点数 $n+1$。
  4. 立方体图 ($Q_n$)：点数 $2^n$，它是 $n$-正则图（每个点度数都是 $n$）。
  5. 二分图 (Bipartite Graph)：
     • 点集能分成 $V_1, V_2$，边只在两个集合之间，集合内部没边。
     • 判定技巧：只要能用 2 种颜色给顶点着色且相邻不同色，就是二分图。或者：图中没有长度为奇数的回路。
  6. 完全二分图 ($K_{m,n}$)：$V_1$ 有 $m$ 个，$V_2$ 有 $n$ 个，两组之间全连满。边数 $= m \times n$。

2. 图的同构 (Isomorphism) (6.3)

考点： 判断两个图是不是同一个图（只是画法不同）。

• 判定方法 (必要条件检查)：
  两个图 $G_1, G_2$ 同构，必须满足：
  1. 顶点数相同。
  2. 边数相同。
  3. 度数列 (Degree Sequence) 相同（比如都有 2 个 3 度点，4 个 2 度点）。
  • 进阶检查：如果上面都一样，检查“特定度数顶点的邻居”。（例如：在 $G_1$ 中，唯一的 5 度点连接了一个 1 度点；但在 $G_2$ 中，5 度点只连 2 度点 $\to$ 不同构）。

3. 连通性与回路 (6.4 - 6.5) —— 核心考点

考点： 欧拉 vs 哈密顿（一个走边，一个走点）。

• 欧拉回路 (Euler Circuit)：

  • 定义：包含所有边且仅一次，回到起点。（笔不离纸一笔画，画完所有边回到原点）。
  • 判定 (充要条件) —— 必背：
    1. 图是连通的。
    2. 所有顶点的度数都是偶数。

• 欧拉通路 (Euler Path)：

  • 定义：包含所有边，但不一定回到起点。
  • 判定：恰好有 0 个或 2 个奇度数顶点。（如果有 2 个，必须从一个奇度点出发，另一个结束）。

• 哈密顿回路 (Hamilton Circuit)：

  • 定义：经过所有顶点且仅一次，回到起点。
  • 判定：没有简单的充要条件（这是 NPC 难题）。
  • 必要条件：如果删去 $k$ 个点，图分裂成超过 $k$ 个连通分量，则不存在哈密顿回路。
  • 充分条件 (Dirac定理)：$n \ge 3$，且每个点度数 $\ge n/2$ $\to$ 必有哈密顿回路。

4. 最短路径 (Shortest Path) (6.6)

考点： Dijkstra 算法（手动模拟）。

• Dijkstra 算法步骤：
  1. 设起点 $a$ 距离为 0，其他为 $\infty$。标记所有点为“未访问”。
  2. 选出当前“未访问”中距离最小的点 $u$。
  3. 把 $u$ 标记为“已访问”。
  4. 更新 $u$ 的所有邻居 $v$：如果 $dist(u) + w(u,v) < dist(v)$，则更新 $dist(v)$。
  5. 重复直到终点被访问。
  • 技巧：考试时列表格！列出每一步各顶点的距离更新情况。

5. 平面图 (Planar Graphs) (6.7)

考点： 欧拉公式。

• 定义：能画在平面上且边不交叉的图。
• 欧拉公式 —— 必考计算：
  • 对于连通平面图：$r = e - v + 2$。
  • 其中 $r$ (Region/Face) 是面数（包含外部无限面），$e$ 是边数，$v$ 是点数。
• 推论 (用于证明非平面图)：
  • $e \le 3v - 6$ (当 $v \ge 3$)。
  • 如果由该不等式推出矛盾，则不是平面图。
  • 典型非平面图：$K_5$ (五角星连满), $K_{3,3}$ (房子连三口井)。

6. 图着色 (Graph Coloring) (6.8)

考点： 色数 $\chi(G)$。

• 定义：相邻顶点不同色，最少需要几种颜色。
• 常见结论：
  • 偶环/二分图：2 色。
  • 奇环 ($C_3, C_5…$)：3 色。
  • 完全图 $K_n$：$n$ 色。
  • 平面图：最多 4 色 (四色定理)。

第六章复习自测与技巧

1. 欧拉 vs 哈密顿记忆法：
   • 欧拉 (Euler) = Edge (边)：走遍所有边。看度数奇偶。
   • 哈密顿 (Hamilton) = Home (家/点)：走遍所有人家(点)。很难判断。
2. 握手定理陷阱：
   • 题目：10个顶点的图，每个点度数都是6，有多少条边？
   • 计算：总度数 $= 10 \times 6 = 60$。边数 $e = 60 / 2 = 30$。
3. 平面图面数：
   • 不要忘了外部那个无限大的面也算一个面！

第七章：树 (Trees)

1. 树的性质 (7.1)

考点： 边与点的关系、$m$ 叉树计算。

• 定义：
  • 树 (Tree)：连通且无环的无向图。
  • 森林 (Forest)：无环图（由多棵树组成）。
• 核心公式（必考填空/选择）：
  1. 边数公式：一棵树有 $n$ 个顶点，则它恰好有 $n-1$ 条边。
  2. $m$ 叉树公式：
     • 若一棵满 $m$ 叉树（每个内部节点都有 $m$ 个孩子）有 $i$ 个内部节点。
     • 则顶点总数 $n = m \cdot i + 1$。
     • 叶子节点数 $l = (m-1)i + 1$。
     • 考法：已知某比赛是“单败淘汰制”（类似二叉树），有 100 人参赛，要进行多少场比赛？
     • 秒杀：比赛场数 = 淘汰人数 = $100 - 1 = 99$ 场。（对应边数 = 点数 - 1）。

2. 树的遍历 (Tree Traversal) (7.3)

考点： 给一棵树（通常是二叉树或算术表达式树），写出三种遍历序列。

• 三种顺序（口诀：根在哪，叫什么）：

  1. 前序 (Preorder)：根 $\to$ 左 $\to$ 右。
     • 对应：波兰表达式 (Prefix)。
  2. 中序 (Inorder)：左 $\to$ 根 $\to$ 右。
     • 对应：我们平时用的算术表达式（需要加括号）。
  3. 后序 (Postorder)：左 $\to$ 右 $\to$ 根。
     • 对应：逆波兰表达式 (Postfix)。

• 做题技巧（围墙法）：

  • 拿起笔，从树根左边开始，沿着树的轮廓画一圈（像描边一样）。
  • 前序：第一次经过节点左边时记录。
  • 中序：经过节点底部时记录（仅限二叉树）。
  • 后序：经过节点右边（离开时）记录。

3. 生成树 (Spanning Trees) (7.4)

考点： DFS/BFS 构造生成树、最小生成树 (MST) 算法。

• 生成树定义：包含图中所有顶点的一个子图，且该子图是一棵树（边数最少，保持连通）。

• 搜索算法：

  • 深度优先 (DFS)：一条路走到黑，撞墙回溯。生成的树长得比较“高瘦”。
  • 宽度优先 (BFS)：一层层向外扩（像水波纹）。生成的树长得比较“矮胖”。

• 最小生成树 (MST) —— 必考大题 (画图或计算权值和)
  给一个带权图，找一棵生成树，使得边权之和最小。

  • 算法 1：Prim 算法 (普里姆算法) —— “加点法”

    • 逻辑：从任意一个点开始，把这个点放入集合 $S$。
    • 步骤：每次寻找连接“集合 $S$ 内的点”和“集合 $S$ 外的点”的最短边，把对应的外点拉入 $S$。
    • 特点：树是一点点长大的，始终保持连通。

  • 算法 2：Kruskal 算法 (克鲁斯卡尔算法) —— “加边法”

    • 逻辑：只看边，不看点。
    • 步骤：
      1. 把所有边按权值从小到大排序。
      2. 按顺序选边。如果这条边加入后不构成回路，就要；否则扔掉。
      3. 直到选够 $n-1$ 条边。
    • 特点：开始是散落的森林，最后连成一棵树。

第七章复习自测与避坑

1. 算术表达式树：
   • 题目：画出 $((a+b)*c) + (d/e)$ 的表达式树。
   • 方法：最后算的运算符是“根”。这里最中间的 $+$ 是根，左孩子是 $*$，右孩子是 $/$。
2. Prim vs Kruskal：
   • Prim 必须找与当前树相连的边。
   • Kruskal 全局找最小边，只要不通过程环即可（可能跳着选）。
   • 结果：两者求出的总权值一定相同，但选的边可能不同（如果有等权边）。

📚 全书复习总结与考试策略

恭喜你！所有考试范围内的知识点（第1-7章）都已经过了一遍。最后送你几条考场救命锦囊：

1. 证明题写不出来怎么办？
   • 不要空着！ 把题目中涉及的定义（如“偶数”、“子集”、“满射”）用数学符号写出来，这通常能拿 2-3 分的步骤分。
   • 尝试写出第一步（假设…）和最后一步（所以…），中间如果卡住，尝试“倒推”。
2. 计算题检查技巧：
   • 逻辑题：代入简单的真值（比如全T或全F）看看等不等。
   • 图论题：算完握手定理看一眼奇度数点是不是偶数个。
   • 计数题：如果 $n$ 很小，直接枚举数一下验证公式。
3. 时间管理：
   • 选择/填空：遇到卡住的图论概念题，画个小图试错。
   • 大题：推理证明和归纳法通常分值高且步骤固定，优先保证书写规范。

祝你离散数学期末考试高分通过！加油！ 🎉