离散数学小记

Posted on 繁/简： set

我有时会向往去到离散的世界，因为在那里一切命题只有真假两种取值。

COMP2121 Discrete Math 笔记。

教授是我很喜欢的 Ravi，但周一/四的九点半开课真的很折磨。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


数理逻辑 Logic and Proofs

Lecture 1

引入问题：证明 \(\sqrt{2}\) 是无理数。方法是反证法 (proof by contradiction) 与平方数的奇偶性。附：

  • 有理数的定义：A real number \(r\) is rational if there exist integers \(p,q \ (q\neq 0)\) with no common factors, such that \(r=\frac{p}{q}\). 见 这个回答，使用同样的方法可推广到证明任意素数开根是无理数。
  • 有理数根定理 (Rational Root Theorem)：If \(p(x)\) is a monic polynomial with integer coefficient, then the roots of \(p(x)\) are either integers or irrational numbers. 构造 \(p(x)=x^2-2\) 后应用该定理。

命题逻辑 (Propositional Logic)：aka Propositional Calculus。

  • A Proposition is a statement that is either True (T) or False (F), but not both.
  • Negation (NOT), \(\lnot{p}\)
  • Conjunction (AND), \(p\land q\). Disjunction (OR), \(p\lor q\). Exclusive Or (XOR), \(p\oplus q\)
  • Implication, \(p\to q\). Bi-Conditionals, \(p \longleftrightarrow q\)
  • Converse (逆命题), \(q\to p\). Contrapositive (逆否命题), \(\lnot q\to \lnot p\). Inverse (否命题), \(\lnot p \to \lnot q\)

这里特别讲一下 Implication (\(p\to q\)) 复合命题，它和我们熟悉的 NOT，OR，AND 是平级的。

  • \(p\) 为 hypothesis 或 premise，\(q\) 为 conclusion 或 consequence.
  • \(p\) is sufficient for \(q\), \(q\) is necessary for \(p\). 初中死记硬背的充分必要到现在才完全理解。
  • false when \(p\) is true and \(q\) is false, and true otherwise. 也就是说，当前提 \(p\) 为假时，implication 一定为真。

关于 Theorem，Proposition，Lemma 与 Corollary：见这篇回答。


Lecture 2

关于逻辑等价 (Logical Equivalences)：两个有相同 truth value 的 propositions 是逻辑等价的。

  • Tautology：无论 propositional variables 的值怎么取，值总为真的命题。
  • Contradiction：......值总为假的命题。

三个最常用的 non-trivial 公式！

  • Conditional-Disjunction Equivalence: \((p\to q)\equiv (\lnot{p}\lor q)\)
  • Distributive Laws: \(p\lor (q\land r)\equiv (p\lor q)\land (p \lor r)\) 与 \(p\land (q\lor r)\equiv (p\land q)\lor(p\land r)\)
  • De Morgan's Laws: \(\lnot (p\land q)\equiv \lnot{p}\lor \lnot{q}\) 与 \(\lnot(p\lor q)\equiv \lnot{p}\land \lnot{q}\)​

还有关于 implication 和 bi-implication 的常用公式：

  • Contrapositive. \((p\to q)\equiv (\lnot p\to \lnot q)\)
  • Bi-Implication. \((p\leftrightarrow q)\equiv (\lnot p\leftrightarrow \lnot q)\equiv (p\land q)\lor (\lnot p\land \lnot q)\)
  • Distributive Laws. \(p\to (q\land r)\equiv (p\to q)\land (p\to r)\) 与 \((p\to r)\land (q\to r)\equiv (p\lor q)\to r\)

布尔可满足性问题 (Satisfiability)：一个复合命题是 satisfiable 的当存在一种 truth values 对 propositional variables 的分配方式，使得该复合命题为真。


Lecture 3

前两节课重点在 Propositional Logic，这一节开始进入 Predicate Logic。

Predicate Logic 引入了 Quantification 来构造更为复杂的命题。

  • The Universal Quantifier \(\forall\)
  • The Existential Quantifier \(\exists\)
  • The Uniqueness Quantifier \(\exists!\) or \(\exists_1\)

使用 Quantifier 时，注意 propositional variables 所属的论域 Domain (aka Domain of Discourse, or Universe of Discourse)。

  • 论域需要事先指出：例如，命题函数 (propositional function) \(P(x)\) 表示 \(x\) 很有高扬感。\(x\) 的论域是北宇治高校吹奏乐部的成员。在此基础上 \(\forall x P(x)\) 才有意义：对于所有吹奏乐部的成员，他们是很有高扬感的。
  • 试试再添加一个命题函数 \(Q(x)\)：\(x\) 吹上低音号。那么 \(\forall{x} (Q(x)\to P(x))\) 就表示：对于所有吹奏乐部的成员，如果他们吹上低音号，那么他们就很有高扬感。

Quantifier 的 De Morgan's Laws: \(\lnot \forall{x}\equiv \exists{x}\), \(\lnot \exists{x}=\forall{x}\)。如果是 Nested Quantifiers，全部取反即可。


Lecture 4

先说 argument: argument 是一系列 propositions，分为最后的 conclusion 和之前的所有 premises。为了证明 conclusion 的正确性，我们需要说明 the truth of premises logically implies the truth of conclusion。

Logically Implication: \(p\) logically implies \(q\) (\(p \implies q\)) if \(p\to q\) is a tautology.

对 argument 进行推理时的几个重要的 Rules of Inference：

  • Modus Ponens (Affirming the Antecedent). tautology \((p\land (p\to q))\to q\). 肯定前件。
  • Modus Tollens (Denying the Consequent). tautology \((\lnot{q} \land (p\to q))\to \lnot{p}\). 否定后件。
  • Hypothetical Syllogism (Chain Rule). tautology \(((p\to q)\land (q\to r))\to (p\to r)\). 直言三段论。
  • Disjunctive Syllogism (Disjunction Elimination). tautology \(((p\lor q)\land \lnot p)\to q\). 选言三段论。
  • Addition. tautology \(p\to (p\lor q)\).
  • Simplification. tautology \((p\land q)\to p\). (前提为假一定为真。前提为真 \(p\), \(q\) 必全为真)
  • Resolution. tautology \(((p\lor q)\land (\lnot{p}\lor r))\to (q\lor r)\). (分别对应 \(p\) 与 \(\lnot p\) 两种情况)
  • Universal Instantiation and Universal Generalization. \(\forall\) Domain 的特殊化与一般化。
  • Existential Instantiation and Existential Generalization. 关于 \(\exists\).

关于应用 Rules of Inference 的一个实例：找犯人 - Lecture 4 Slides 3。

谬误 (Fallacies)：

  • Affirming the Conclusion: false proposition \(((p\to q)\land q)\to q\).
  • Denying the Hypothesis: false proposition \(((p\to q)\land \lnot{p})\to \lnot{q}\).


Lecture 5

这一节主要讲命题的证明方法 (Methods of Proof)。对于命题 \(p\to q\)，

  • Direct Proof. assume \(p\) is True, use the Rules of Inference to establish subsequent propositions, in the final step show that \(q\) is True. 总而言之就是证明 \(p\) 为真但 \(q\) 为假的 case 不存在。
  • Proof by Contraposition. assume \(\lnot{q}\) is True, use the Rules of Inference to establish subsequent propositions, in the final step show that \(\lnot{p}\) is True. 总而言之就是利用逆否等价 \((p\to q)\equiv (\lnot{q}\to\lnot{p})\).
  • Proof by Contradiction. assume \(\lnot(p\to q)\equiv (p\land\lnot q)\) is True, i.e. \(p\) is True, \(q\) is false and show \(r\land \lnot{r}\) for some proposition \(r\). 总而言之就是假设 \(p\) 为真且 \(q\) 为假，在此基础上找到一个矛盾 \(r\land \lnot{r}\).
  • Proof by Cases. 对于命题 \((p_1\lor p_2 \lor...\lor p_n)\to q\)，若难以把 \(p_1\lor...\lor p_n\) 作为一个整体考虑，使用 tautology 转化后 case by case 证明 \([(p_1\lor p_2\lor...\lor p_n)\to q]\leftrightarrow [(p_1\to q)\land (p_2\to q)\land...\land (p_n\to q)]\).
  • Proofs of Equivalence. 使用 tautology \((p_1 \leftrightarrow ...\leftrightarrow p_n)\leftrightarrow ((p_1\to p_2)\land (p_2\to p_3)\land ...\land (p_n \to p_1))\) 证明命题 \(p_1...p_n\)​ 等价。
  • Vacuous Proof. Proving a statement \(p\to q\) is True when we know that \(p\) is False. 无需看结论。
  • Trivial Proof. Proving a statement \(p\to q\) is True when we know that \(q\) is True. 无需看前提。

Existence Proof. 证明存在性命题 \(\exists x P(x)\) (e.g., 证明存在无理数 \(x,y\) 使得 \(x^y\) 有理。Lec 4 pp.24)

  • Constructive Existence Proof. 找到论域中的某元素 \(a\) 使得 \(P(a)\) 为真。该 \(a\) 被称为 witness。
  • Non-Constructive Existence Proof. 不依靠确定的 \(a\) 进行证明。

Proof by Induction. 证明 propositional function \(P(n)\) 对所有正整数 \(n\) 为真，使用数学归纳法。

  • Basis Step: verify that \(P(1)\) is True.
  • Inductive Step: show that \(\forall k(P(k)\to P(k+1))\) is True. 在进行这一步时我们会假设 \(P(k)\) 为真来证明 \(P(k+1)\) 为真。\(P(k)\) 为真这一假设被称为 inductive hypothesis.
  • 一个著名的 wrong proof: all girls have eyes of the same color.


集合论 Set and Relations

Lecture 6

Set Notation. 一些表记和对应的术语。

  • Roster Method. 直接列出集合的元素表示法。
  • Set Builder Method. 通过表示集合内元素必须具有的属性来表示集合。

特殊集。\(\mathbb{N}\) (Natural numbers), \(\mathbb{Z}\) (Integers), \(\mathbb{Q}\) (Rational numbers), \(\mathbb{R}\) (Real numbers), \(\mathbb{C}\) (Complex numbers).

空集。\(\emptyset\) or \(\{\}\) (Empty set aka Null set)；单元集。Singleton set.

集 \(S\) 的基数 \(|S|\) (cardinality of a set) 是 \(S\) 中 distinct elements 的个数。有限与无限集 (finite/infinite set)。

自指集 (set containing themselves)。导致悖论 (paradox)，they are NOT well-formed sets.

集合运算。

  • 幂集 (Power set) \(\mathscr{P}(S)\) aka \(2^{S}\)。集合 \(S\) 的所有子集形成的集合。
  • 笛卡尔积 (Cartesian Product of Sets)。\(A_1\times A_2=\{(a_1,a_2)|a_1\in A_1\land a_2\in A_2\}\)。笛卡尔积不满足交换律，结合律 \(A_1\times A_2\times A_3\neq (A_1\times A_2)\times A_3\) (triple \(\neq\) tuple)。任何集合与空集的笛卡尔积为它本身。
  • 真理集 (Truth Set)。命题 \(P\) 和论域 \(D\)，\(P(x)\) 的真理集 \(\{x\in D |P(x)\}\)。
  • 并集 (Union of Sets) \(A\cup{B}\)，交集 (Intersection of Sets) \(A\cap{B}\)，差集 (Difference of Sets) \(A-B\) 或者 \(A\setminus B=\{x|x\in A\land x\notin B\}\)，补集 (Complement of Sets) \(\overline{A}=U-A\)，这里 \(U\) 是全集 (Universal Set)。

集合恒等式 (Set Identities)。与逻辑恒等式对应。集合恒等式的证明：

  • 证明 \(A\subseteq B\) 且 \(B\subseteq A\)，取某个元素 \(x\) 后转为逻辑证明，例 Lecture 6 pp.25 证明 De Morgan's Law。
  • 使用 Existing Identities 证明。

Membership Tables。即集合层面的 Truth Tables。


Lecture 7

这一节主要讲集合间的关系 (Set Relations)。

集合间的关系是一种规则，用于筛选集合笛卡尔积形成的二元组。

  • Binary Relation \(R\) from \(A\) to \(B\), \(R\subseteq A\times B\).
  • Relation \(R\) on a Set \(A\), \(R\subseteq A\times A\). Proposition. 大小为 \(n\) 的集合 \(A\) 共有 \(2^{n^2}\) 种 relations。

关系的性质 (Properties of Relations)。

  • 自反关系 (Reflexive Relations)：\(R\) on a set \(A\) is Reflexive if \((a,a)\in R\) for every \(a\in A\).
  • 对称关系 (Symmetric Relations)：\(\forall a \forall b ((a,b)\in R \to (b,a)\in R)\).
  • 反对称关系 (Anti-Symmetric Relations)：\(\forall a \forall b (((a,b)\in R\land (b,a)\in R)\to (a=b))\).
  • 传递关系 (Transitive Relations)：\(\forall a\forall b\forall c (((a,b)\in R\land(b,c)\in R))\to(a,c)\in R)\).

Note that 对称关系与反对称关系并非 opposite！A relation is antisymmetric if and only there are no pairs of distinct elements \((a,b)\) with \(aRb\) and \(bRa\). e.g., \(R=\{(1,1),(2,2),(3,3)\}\), 该关系既是对称的又是反对称的。

关系的组合 (Combining Relations)。由于集合 \(A,B\) 的关系本质上是 \(A\times B\) 的子集，不同关系间能够进行组合，就像集合间能够进行组合一样。

  • 交集，并集，差集，补集。
  • Composition: \(R\) 是 \(A\) 到 \(B\) 的关系，\(S\) 是 \(B\) 到 \(C\) 的关系，\(R\) 与 \(S\) 的复合 (Composite)，表示为 \(S\circ R\)，包含所有二元组 \((a,c)\)，满足存在 \(a\in A,c\in C,b\in B\)，使得 \((a,b)\in R\land {(b,c)\in S}\)。
  • 若 \(R\) 是一个在 \(A\) 上的关系，\(R^{n+1}=R^n\circ R\)​。

关系的表示 (Representing Relations)。

  • 有向图 (Digraphs) 表示。\(aRb\) 表示一条由点 \(a\) 连向点 \(b\)​ 的有向边。
  • 01 矩阵表示。\(m_{ij}\) 为 \(1\) 当且仅当 \((a_i,b_j)\in R\)。

通过观察关系的矩阵表示发现关系的性质。

  • \(M_R\) 主对角线 (main diagonal) 的元素全为 \(1\) 当且仅当 \(R\) 是自反的。
  • \(M_R=(M_R)^T\) (对称矩阵) 当且仅当 \(R\) 是对称的。
  • Either \(m_{ij}=0\) or \(m_{ji}=0\) when \(i\neq j\) 当且仅当 \(R\)​ 是反对称的。

等价关系 (Equivalence Relations)。关系 \(R\) 是一个等价关系当它是 reflexive，symmetric 与 transitive 的。被等价关系所关联的元素 \(a,b\) 是等价的，记作 \(a\sim b\)。

等价类 (Equivalence Classes)。所有与 \(a\) 等价的元素形成的集合被称为 \(a\) 的等价类 (Equivalence Class of \(a\))，记作 \([a]_R\)，即 \([a]_R=\{b|(a,b)\in R\}\)。任意 \(c\in [a]_R\) 为该等价类的代表元 (representative)。


函数 Functions

Lecture 8

一些名词的英文记法。对于函数 \(f:A\to B\)，存在 \(a\in A, b\in B\)，使得 \(f(a)=b\)。则：

  • \(A\): Domain (定义域) of \(f\).
  • \(B\): Codomain (陪域) of \(f\)​.
  • \(b\) is the Image (像) of \(a\), \(a\) is the Preimage (原像) of \(b\).
  • \(\{f(a)|\forall a\in A\}\): Range (值域) of \(f\). Range is a subset of Codomain.

函数的性质。

  • One-to-One Functions, or an Injection (单射).
  • Onto Functions, or a Surjection (满射), Range = Codomain.
  • One-to-One Correspondence, or a Bijection (双射/对射), if both one-to-one and onto.
  • Inverse Functions, exist only if \(f\)​ is a one-to-one correspondence.


Lecture 9

更多的英文记法和一些特殊函数。

  • Ceiling function \(\lceil x \rceil\). Floor function \(\lfloor x \rfloor\) (Greatest integer function \([x]\)​)
    • 性质 \(\lfloor-x \rfloor=\lceil x \rceil\), \(\lceil -x \rceil=-\lfloor x \rfloor\)
  • Exponential function \(f_b(n)=b^n\)
  • Logarithmic function \(\log_b x\). Note that Base \(b>1\)
  • Factorial function \(f:\mathbb{N}\to \mathbb{Z}^+, f(n)=n!\)​
    • Stirling's Formula. \(n!\sim \sqrt{2\pi n}(n/e)^n\).
    • Inequality. \(\sqrt{2\pi n}(n/e)^n\leq n!\leq e\sqrt{n} (n/e)^n\) for all \(n\in\mathbb{Z}^+\)​.
  • Graphs of Functions 与 Vertical Line test.

Partial functions 与 Total functions.

  • Domain 与 Domain of Definition (定义域)；关系类似于 Codomain 与 Range。e.g., \(f:\mathbb{Z}\to \mathbb{R}\) where \(f(n)=\sqrt{n}\), Domain 为 \(\mathbb{Z}\)，Domain of Definition 为 \(\mathbb{N}\)。
  • Total function: Domain \(=\) Domain of Definition. 反之为 Partial function。

经典的 asymptotic order of growth. 符合条件的 \(C,k\) 被称为 witnesses。

  • Big-O notation. \(f(x)=O(g(x))\to\exists C,k \ \ s.t. \ \ \forall x>k, |f(x)|\leq C|g(x)|\).
  • Big-Omega notation. \(f(x)=\Omega(g(x))\to \exists C,k, \ \ s.t. \ \ \forall x>k,|f(x)|\geq C|g(x)|\).
  • Big-Theta notation. \(f(x)=\Theta(g(x))\to f(x)=O(g(x))\land f(x)=\Omega(g(x))\)​.


Lecture 10

更多的 Big-O notation 与 Recurrence Relations。

  • Sum of Functions。对于 \(f_1(x)=O(g_1(x))\) 与 \(f_2(x)=O(g_2(x))\)，有 \((f_1+f_2)(x)=O(g(x))\)，其中 \(g(x)\) 为 \(\max(|g_1(x)|, |g_2(x)|)\)​。
  • Product of Functions。对于 \(f_1(x)=O(g_1(x))\) 与 \(f_2(x)=O(g_2(x))\)，有 \((f_1f_2)(x)=O(g_1(x)g_2(x))\)。

Recurrence Relations 与 Recursively Defined Function。没什么好讲的。


计数原理 Basic Counting Principles

Lecture 11

大多数都是比较 trivial 的高中知识。

  • The Product Rule (乘法原理)。分步处理思想。
  • The Sum Rule (加法原理)。组合思想。
  • Inclusion-Exclusion Principle (容斥原理)。集合数为 \(2\)​ 时的特化是 Subtraction Rule (减法原理)。
  • The Division Rule (除法原理)。\(f:A\to B\) 且 \(f\) 是 \(d\)-to-\(1\) 函数，\(|A|/d=|B|\)。圆桌座位安排。
  • Generalized Pigeonhole Principle (鸽巢原理/抽屉原理)。\(N\) objects \(k\) boxes, at least one box containing at least \(\lceil N/k \rceil\) objects.

一些值得研究的例题。

  • [Lecure 11 pp.13] 容斥原理。先取两个相连的点构成一条边，容斥原理证明这两个点延伸出去的点集的交集不为空，这就形成了一个三角形。
  • [Lecture 11 pp.19] 鸽巢原理。大小为 \(n+1\) 的集合中至少有两个元素模 \(n\) 同余。这个方法理论上能够在 \(O(n)\) 的时间内构造出符合条件的解，并且可以证明这个解一定满足 \(11..100...0\)​ 的形式。
  • [Lecture 11 pp.21] 广义鸽巢原理。把朋友/敌人视为鸽巢后分类讨论即可。
  • [Lecture 11 pp.22] 鸽巢原理。分别构造两段前缀和 \(\{a_1,...,a_{30}\}\) 与 \(\{a_1+14,...,a_{30}+14\}\)，且这两段前缀和中的所有元素都满足 \(\leq 45+14=59\)。\(60\) 个元素 \(59\) 个坑，至少有一对元素相等。又因为前缀和单调递增，这一对相等的元素一定分布在两段前缀和中。有 \(a_j=a_i+14\) 进而证明 \(n_{i+1}+...+n_j=a_j-a_i=14\)。


Lecture 12

基础的排列 (permutation) 与组合 (combination) 计数。也是老朋友了。

  • # of \(r\)-permutation of a set with \(n\) elements \(P(n,r)=\frac{n!}{(n-r)!}\)
  • # of \(r\)-combination of a set with \(n\) elements \(C(n,r)=\frac{n!}{r!(n-r)!}\)​
  • # of \(r\)-permutation of a set with \(n\) elements, repetition allowed \(n^{r}\)
  • # of \(r\)-combination of a set with \(n\) elements, repetition allowed \(C(n+r-1,r)\)。经典的插板法。对于 \(n+r\) 个小球，有 \(n+r-1\) 个间隔；在这些间隔中选出 \(n-1\) 个把 \(n+r\) 个小球分为 \(n\) 块。其中第 \(i\) 块小球的数量为 \(x_i \ (x_i>1)\)，那么元素 \(i\) 在 \(r\)- combination 中出现的次数是 \(x_i-1\)。证：\(\sum_{i=1}^n (x_i-1)=r\)。
  • # of permutations with indistinguishable objects. \(k\) 个 types \((n!)/(n_1!n_2!...n_k!)\)。


概率论基础 Probability Theory

Lecture 13

很基础的概率论知识。一些英文名词还是有必要稍微记录一下的。

  • Experiment (实验)。指的是产生 one of a set of possible outcomes 的 procedure。
  • Sample space of the experiment (样本空间)。所有 possible outcomes 的集合。
  • Event (事件)。样本空间的子集。
  • Discrete Probability (离散概率) 研究的是发生在 countable/finite 样本空间内的事件。
  • Assigning Probabilities。向 outcome \(s\) 分配概率 \(p(s)\)；这里用 assigning 是因为 probability distribution (概率分布) \(p\)​ 本质上是一个函数。

Conditional probability (条件概率)。

(Generalized) Bayes' Theorem. \(p(F_j|E)=(p(E|F_j)p(F_j))/(\sum_{i=1}^n p(E|F_i)p(F_i))\).

  • 条件概率的定义 \(p(E|F)=p(E\cap F)/p(F)\) 得到 \(p(E\cap F)=p(E|F)p(F)\)。
  • 列出 \(p(F|E)\) 的条件概率式，把分子 \(p(E\cap F)\) 替换为 \(p(E|F)p(F)\)。
  • 把分母 \(p(E)\) 按照全概率公式 (Law of Total Probability) 展开就能得到广义贝叶斯公式。
  • 若只展开两项 \(p(E)=p(E\cap F)+p(E\cap \bar{F})=P(E|F)p(F)+p(E|\bar{F})p(\bar{F})\) 得到普通贝叶斯公式。

Independence. \(p(E\cap F)=p(E)p(F)\).

  • Mutually independent 指 \(p(\cap_{i=1}^n E_i)=\prod_{i=1}^n p(E_i)\)。
  • Mutual independence 是 pairwise independence 的充分不必要条件。


Lecture 14

伯努利试验，二项分布与二项式定理。

  • Bernoulli Trials - outcomes 只有成功 \(p\) /失败 \(q\)。
  • Binomial Distribution - \(b(k;n,p)=C(n,k)p^k q^{n-k}\), \(p+q=1\)，\(n\) 次中获胜 \(k\) 次的概率。
  • Binomial Theorem - \(\sum_{k=0}^n C(n,k)p^{k}q^{n-k}=(p+q)^n=1\)​。

关于随机变量。

  • Random Variables 本质上是一个函数，它把实验的 outcome 映射为一个实数。例如实验为进行 \(10\) 次检定，定义随机变量 \(X\) 为投出大成功的次数；那么对于一个实验的 outcome \(t\)，\(X=3\) 其实是 \(X(t)=3\)。
  • 随机变量 \(X\) 在样本空间 \(S\) 上的分布 (Distribution) 指的是一系列 \((r,p(X=r))\) 对，其中 \(r\in X(S)\)​。
  • Expected Value - 随机变量的期望 \(E(X)=\sum_{s\in S}p(s)X(s)\)​。期望的线性性 (Linearity of Expectations)。
  • Variance - 随机变量 \(X\) 的方差 \(V(X)=\sum_{s\in S}(X(s)-E(X))^2p(s)\)，标准差 \(\sqrt{V(X)}\)。方差与期望间的关系 \(V(X)=E(X^2)-E(X)^2\)。
  • 独立随机变量 - 样本空间 \(S\) 上的独立随机变量 \(X,Y\) 满足 \(p(X=r_1,Y=r_2)=p(X=r_1)\cdot p(Y=r_2)\)。
    • \(E(XY)=E(X)\cdot E(Y)\)
    • \(V(X+Y)=V(X)+V(Y)\)
  • 生日问题，逆序对期望数问题 \(n(n-1)/4\)，\([x/y]\) 为偶数的概率 [Lecture 14 pp.38]。


图论 Graph Theory

Lecture 15

也是老熟人了。记录一下 terminology。

自环 (loops, aka self loops) 与重边 (multiple edges connecting same vertices)。

  • Simple Graph (简单图)。不含自环和重边的图。
  • Multigraphs (多重图)。含重边的图。
  • Pseudographs (伪图)。含自环与重边的图。
  • 对于 vertices pair \((u,v)\)，重边的数量被定义为重数 (multiplicity)。

无向图 (Undirected Graph) 相关。

  • 度数 (degree) \(deg\)。无向图自环为同一个 vertex 贡献两个度数。
  • Isolated vertex - 度数为 0。Pendant vertex - 度数为 1。
  • The Handshaking Theorem - \(2|E|=\sum_{v\in V} deg(v)\)​。
  • 一个性质：无向图中有偶数个 vertices 的度数是奇数。可根据 Handshaking Theorem 的奇偶性质得出。

有向图 (Directed Graph, aka Digraph) 相关。

  • 有向边 \((u,v)\)，其中 \(u\) is adjacent to \(v\), \(v\) is adjacent from \(u\).
  • 入度 (in-degree) \(deg^{+}\) 与出度 (out-degree) \(deg^{-}\)​。有向图自环为同一个 vertex 贡献一个入度，一个出度。
  • \(\sum_{v\in V}deg^{-}(v)=\sum_{v\in V}deg^{+}(v)=|E|\)。

一些特殊图。

  • Complete Graphs (完全图)。\(n\) 个 vertices，\(n(n-1)/2\) 条边。
  • Cycles (环图)。\(v_i\) 与 \(v_{i-1},v_{i+1}\) 相连。
  • Wheels (轮图)。向 Cycles \(C_n\) 中添加一个与所有环节点相连的节点，获得 Wheels \(W_n\)。
  • Bipartite Graph (二分图)。
    • 点集 \(V_1,V_2\)，若 \(|V_1|=n, |V_2|=m\)，完全二分图 (Complete Bipartite Graphs) 有 \(nm\)​ 条边。
    • 二分图检查 - 节点黑白染色，相邻节点颜色不同。
    • 奇环检查 - 不含奇环的图 \(\iff\) 二分图。


Lecture 16

一些杂七杂八的概念，包括图的匹配 (matching) 与衍生出的霍尔婚配定理 (Hall's Marriage Theorem)，图的连通性和强连通分量 (Strong Connected Components)。

简单图的匹配 (Matching \(M\) in a simple graph) 是一个边集，其中任意两条边都不共点 (no two edges are incident with the same vertex)。

  • Maximal Matching \(M\)。极大匹配，无法再加入新边。
  • Maximum Matching \(M_m\)。最大匹配，cardinality \(|M_m|\) 是所有匹配中最大的。最大匹配一定是极大匹配，极大匹配不一定是最大匹配。

二分图完美匹配 (匈牙利算法，网络流 - 过去的记忆袭击了我)。二分图 \((V_1,V_2)\) 从 \(V_1\) 到 \(V_2\) 的完美匹配 (Complete Matching aka Perfect Matching from \(V_1\) to \(V_2\)) 指的是包含所有 \(V_1\) 的匹配；因此有性质 \(|M|=|V_1|\)​。

霍尔婚配定理 (Hall's Marriage Theorem)。二分图 \((V_1,V_2)\) 有从 \(V_1\) 到 \(V_2\) 的完美匹配当且仅当对于所有 \(A\subseteq V_1\)，都有 \(|N(A)|\geq |A|\)，其中 \(N(A)\) 定义为 \(A\) 的邻接点 (二分图中显然有 \(N(A)\subseteq V_2\)​)。

  • (If prove) Strong Induction - 两个完美匹配合成一个更大的完美匹配。(Only if prove) - 鸽巢原理反证。
  • [Lecture.16 pp.11] Denomination 作为 \(V_1\)，牌堆作为 \(V_2\)。对于任何 \(A\subseteq V_1\)，\(\min(N(A))=4/4=1\)。根据霍尔定理，一定存在完美匹配。

关于子图。

  • 子图 (Subgraph) 与真子图 (Proper Subgraph)。\(G\) 删边形成的图 \(G'\) 均为子图。
  • 导出子图 (Induced Subgraph)。\(G\) 删点形成的图 \(G'\) 均为导出子图。导出子图一定是子图，子图不一定是导出子图。
  • 边缩 (Edge Contractions)。删掉某条边并把该边的两个顶点缩成一个。

关于路径 (Path) 与回路 (circuit or cycle)。简单路径/回路指的是相同边最多出现一次。

无向图的连通性。

  • 无向图的连通性。对于任意 \(u,v\in V\)，存在一条 \(u-v\)​ 路径。
  • 无向图 \(G\) 的极大连通子图 (maximal connected subgraph) \(H\) 称为连通块/连通分量 (connected component)。若 \(G\) 有两个以上的连通块，它一定是不连通的。
  • 割点 (Cut vertex, aka articulation point) 与桥 (Cut edge aka bridge)。删去后使图不连通。类似的，有点割集 (vertex cut/separating set) 与边割集 (edge cut)。

有向图的连通性。

  • 有向图是强连通 (strongly connected) 的，当对于任意 \(u,v\in V\)，存在 \(u\to v\) 与 \(v\to u\) 路径。
  • 有向图是弱连通 (weakly connected) 的，当它的 underlying 无向图是连通的。
  • 有向图 \(G\) 的极大强连通子图 (maximal strongly connected subgraph) \(H\) 被称为强连通块/强连通分量 (strongly connected components)。若 \(G\) 有两个以上的强连通分量，它一定不是强连通的。

关于图的连通度。

  • 点连通度 (Vertex Connectivity)。非完全图 \(G\) 的点联通度 \(\kappa(G)\) 定义为其最小点割集的 cardinality。当 \(\kappa(G)\geq k\) 时，我们说 \(G\) 是 \(k\)-连通 (\(k\)​​-connected) 的。
  • 完全图 \(K_n\) 是没有点割集的，定义 \(\kappa(K_n)=n-1\)。定义单点图 \(K_1\) 与非连通图的 \(\kappa(G)=0\)。
  • 边连通度 (Edge Connectivity)。图 \(G\) (这里没有完全/非完全的限制) 的边连通度 \(\lambda(G)\) 定义为其最小边割集的 cardinality。
  • 完全图 \(K_n\) 有边割集且 \(\lambda(K_n)=n-1\)。特殊定义单点图 \(K_1\) 与非连通图的 \(\lambda(G)=0\)​。

连通度关系 \(\kappa(G)\leq \lambda(G)\leq \min_{v\in V}\text{deg}(v)\)。

  • 第二个 \(\leq\)：总可以删掉度数最小的点的所有邻边。
  • 第一个 \(\leq\)：一定能保证至多删去 \(\lambda(G)\)​ 个点就能使得图不连通 - 删去边割集中每座桥的一个顶点。


Lecture 17

欧拉图。图 \(G\) 的：

  • Euler Circuit：包含了 \(G\) 中所有边的简单回路 (注意简单的定义：相同边最多出现一次)。
  • Euler Path：包含了 \(G\) 中所有边的简单路径。
  • 欧拉回路充要条件：\(n\geq 2\) 的连通多重图有一个欧拉回路 \(\iff\) 该图所有顶点的度数为偶数。
  • 欧拉路径 \(-\) 欧拉回路：\(n\geq 2\) 的连通多重图有一条欧拉路径，但没有欧拉回路 \(\iff\) 该图所有顶点中有且仅有两个顶点度数为奇数。

哈密顿图。图 \(G\) 的：

  • Hamiltonian Circuit：经过了 \(G\) 中所有顶点恰好一次的简单回路。
  • Hamiltonian Path：经过了 \(G\) 中所有顶点恰好一次的简单路径。
  • 哈密顿路径/回路判断 (Hamiltonian Path Problem) 是著名的 NP-complete 问题。
  • 两个观察：
    • 存在度数为 \(1\) 顶点的图没有哈密顿回路 (进入就出不来了)。
    • 若图有哈密顿回路，图中所有度数为 \(2\) 的顶点所连接的两条边一定是哈密顿回路的一部分 (有进必有出)。
  • 完全图与哈密顿回路：完全图 \(K_n \ (n\geq 3)\) 有 \((n-1)!/2\) 个不同的哈密顿回路 [\(n!/2n\)​，起始点，顺/逆时针]。
  • 两个充分条件：
    • Dirac's Theorem。\(n\geq 3\) 的简单图 \(G\)，若 \(G\) 中所有顶点的度数 \(\geq n/2\)，存在哈密顿回路。
    • Ore's Theorem。\(n\geq 3\) 的简单图 \(G\)，若对于任意对不相邻的顶点 \(u,v\) 都满足 \(\text{deg}(u)+\text{deg}(v)\geq n\)，存在哈密顿回路。[证明很巧妙，逆否后考虑 \(G\) 的极大不含哈密顿回路的生成图 \(H\)​ Lecture 17 pp.24-27]
    • 答案 \(K_{n, n + 1}\) [Lecture 17 pp.28 q.2]


Lecture 18

图的着色问题与色数。

简单图的着色问题 (Coloring of a simple Graph) - 任意两个相邻顶点不同色。定义 \(\chi(G)\) 为图 \(G\)​ 的色数 (Chromatic Number)，即对该图进行着色所需的最少颜色数。

著名的四色问题 (Four Color Theorem) - 任意平面图 (planar graph) [stay tuned] \(G\) 的 \(\chi(G)\leq 4\)。

几个显然的结论。

  • 完全图 \(K_n\) 的 \(\chi(K_n)=4\)。
  • 二分图 \(G\) 的 \(\chi(G)=2\)。
  • 偶环 \(C_{2k}\) 的 \(\chi(C_{2k})=2\)。
  • 奇环 \(C_{2k+1}\) 的 \(\chi(C_{2k+1})=3\)​。
  • 对于任意 \(G\) 都有 \(1\leq \chi(G)\leq n\)，只有无边图 \(G\) 满足 \(\chi(G)=1\)。
  • \(\chi(G)(\chi(G)-1)\leq 2m\)。这是因为任意两个 color class 间至少有一条边连接。
  • Clique - 完全子图。\(\chi(G)\geq \omega(G)\), where \(\omega(G)\) 代表 \(G\)​ 中最大 clique 的大小。
  • \(\chi(G)\leq \Delta(G)+1\), where \(\Delta(G)=\max \deg(v)\)。

Zykov Relations - \(\chi(G)=\min\{\chi(G+uv),\chi(G/uv)\}\)。其中 \(G+uv\) 是加边 \(\{u,v\}\) 后形成的新图，\(G/uv\) 是 contract 边 \(uv\) 后形成的新图。

  • 前者 - \(G\) 中 \(u,v\) 异色。
  • 后者 - \(G\) 中 \(u,v\) 同色。


Lecture 19

关于平面图 (planar graph)。这个概念倒是第一次听说。

如果图 \(G\) 能画在平面 \(S\) 上，且除顶点外无边相交 (without any edges crossing)，我们说该图 \(G\) 是能嵌入 \(S\) 的平面图。这种「画」的方式被称为平面表示 (planar representation)。

有 planar representation \(\iff\) planar graph。有 non-planar representation \(\not\Rightarrow\) non-planar graph。

欧拉公式 (Euler's Formula) - 若 \(G\) 是连通的简单平面图，\(e=|E|, v=|V|, r\) 是 \(G\) 的平面表示中划分出的区域数，有 \(r=e-v+2\)。

证明：平面图中的区域一定是一个 cycle。不断删环，每删一条边 (\(e:=e-1\))，就有一个环被打开 \((r:=r-1)\)；直到图 \(G\) 变为一棵树。此时有 \(r=1,e-v=-1\) 满足 \(r=e-v+2\)。

欧拉公式的推论 - 若 \(G\) 是连通的简单平面图 with \(v\geq 3\)，有 \(e\leq 3v-6\)。且 \(G\) 存在一个顶点 \(\deg(v)\leq 5\)。

证明：简单平面图中的一个区域至少被三条边包围，因此有 \(3r\leq\sum \deg(v)\)。根据握手定则，有 \(2e=\sum \deg(v)\)。所以有 \(3r\leq 2e\)，又 \(r=e-v+2\) ，所以有 \(e=3v-6\)。

  • 多重平面图 (multigraph) 又如何？由于重边的存在，一个区域至少被两条边包围，因此有 \(2r\leq 2e\)。
  • 伪平面图 (pseudo graph) 又如何？由于自环的存在，一个区域至少被一条边包围，因此有 \(r\leq 2e\)。
  • [Lecture 18 pp.43 q1] 假设 \(K_{3,3}\) 又如何？由于奇环不存在，一个区域至少被四条边包围，因此有 \(4r\leq 2e\)。

库拉托夫斯基定理 (Kuratowski's Theorem) - \(G\) 为非平面图当且仅当它含有与 \(K_5\) 或 \(K_{3,3}\) 同胚 (homeomorphic) 的子图。当然 \(K_5\) 与完全二分图 \(K_{3,3}\) 一定是非平面的。


Lecture 20

最后一节课！关于边染色问题 (Edge Colorings) 与一些图论题的讲解。

边染色 (Edge Colorings)。即图染色的边版本。定义 edge-chromatic number \(\chi'(G)\) 为使得 loopless graph (无自环图) \(G\) 是 \(k\)-edge-colorable 的最小 \(k\)。显然有 \(\chi'(G)\geq \Delta(G)\)，其中 \(\Delta(G)\) 是 \(G\) 中的最大度数。

一些题目。

[Lecture 20 pp.9 Q3] 简单连通图 \(G\)，若 \(|E|>(|V|/2)^2\)，它不可能是二分图。

设两个 partition 中的点个数为 \(m\) 与 \(v-m\)，显然有 \(\max e=m(v-m)=-[m-(v/2)]^2+(v/2)^2\)。可见当 \(m=v/2\) 时有 \(e_{max}=(v/2)^2\)。又有题目限制 \(G\) 满足 \(e>(v/2)^2\)，所以 \(G\)​ 一定不是二分图。

[Lecture 20 pp.10 Q4] 简单无向图 \(G\)，点集大小为 \(n\)，边集大小为 \(m\)。

  • [\(b\)] 顶点度数相同，至少向 \(G\) 中加多少边使得欧拉路径存在？若 \(2m/n\) 为偶数，不用加。
  • [\(c\)] 最小连通块数量 \(\max\{n-m,1\}\)。
  • [\(d\)] 最大连通块数量：构造一个能容纳所有边的超大 \(r\) 连通块 (完全子图)，剩下的 \(n-r\) 个顶点自成一派。取最小 \(r\) 使得 \({n\choose r}\geq m\) 满足，答案为 \(n-r+1\)。
  • [\(e\)] 使得 \(G\) 不存在哈密顿回路的最大 \(m\)。这个有一个固定的构造方法，取 \(n-1\) 个顶点构造一个完全图，最后一个顶点单独伸出去作为 trap。此时边数为 \({n-1\choose 2}+1\)​。
  • [\(f\)] \(G\) 无 cycle，求 \(\chi(G)\)。无 cycle \(\Rightarrow\) 森林。当 \(m=0\) 时，\(\chi(G)=1\)，否则 \(\chi(G)=2\)。
  • [\(g\)] \(G\) 无 cycle，使用 \(\chi(G)\) 种颜色有多少种染色方法？\((n,m)\) 森林中的连通块数量为 \(n-m\)，每个连通块有两种染色方式 (根为黑或根为白)。因此有 \(m=0\) 时，\(\chi(G)=1\)，否则 \(\chi(G)=2^{n-m}\)。

[Lecture 20 pp.12 Q5] 简单无向图 \(G\) 的关联矩阵 (Incidence Matrix) 与其转置的乘积有什么意义？

注意，关联矩阵 (Incidence Matrix) 是 \(n\times m\) 的，与 \(n\times n\) 邻接矩阵 (Adjacency Matrix) 的概念不同！答案：得到矩阵的主对角线表示顶点的度数，第 \(i,j\) 个 entry 象征着顶点 \(i,j\) 的连接性。

[Lecture 20 pp.15 Q6] \(m\leq n\). Under what conditions on \(m,n\) will every edge in \(K_{m,n}\) be in exactly one of two isomorphic subgraphs of \(K_{m,n}\)​.

这题主要的难度在于理解题意。isomorphism 指同构，即两个图完全等价。那么两个同构子图指的就是这两个子图 (去掉顶点标签后) 完全一致。那么这道题的意思是 \(m,n\) 应当满足什么条件，使得我们能够将 \(K_{m,n}\) 拆成不相交的，完全一样的子图？答案呼之欲出了：\(mn\)​ 为偶数即可。

[Lecture 20 pp.17 Q7] \(G\) 为简单连通平面图，点集大小 \(|V|=v\)。若 \(G\) 与其对偶图 (dual) 同构，求边集大小 \(|E|\)。

又是一个新的概念：对偶图 (dual)。这是与平面图有关的概念。把平面图中的每个 region 抽成一个顶点，相邻 (即 share 共同边界) 的 region 对应的顶点连边，形成的图即为原平面图的对偶图。

平面图，先想到欧拉定理：\(r=e-v+2\)。由于对偶图与原图同构，有 \(r=v\)。因此 \(e=2v-2\)。

[Lecture 20 pp.18 Q8] \(G_1,G_2\) 为简单连通无向图。若 \(G_1,G_2\) 为同胚图 (homeomorphic)，证明若 \(G_1\) 有欧拉路径 (或回路) 当且仅当 \(G_2\) 有欧拉路径 (或回路)。

同胚图 (homeomorphic) 的概念：如果 \(G_1\) 能通过 subdivision/smoothing 得到 \(G_2\)，我们说 \(G_1,G_2\) 是同胚的。subdivision (expansion) 往边中间加顶点，smoothing 将顶点融进边中。见 Homeomorphism。

可以发现，subdivision 的操作实际上就是添加若干度数为 2 的顶点：因此在不考虑度数为 2 的顶点的情况下，同胚图是同构的 - 也就是说，同胚图含有相同数量的，度数为奇数的顶点。

这个性质与欧拉路径/回路完美契合。

  • \(G_1\) 有欧拉路径 \(\Rightarrow\) \(G_1\) 恰有两个奇数度数顶点 \(\Rightarrow\) \(G_2\) 恰有两个偶数度数顶点 \(\Rightarrow\) \(G_2\) 有欧拉路径。
  • \(G_1\) 有欧拉回路 \(\Rightarrow\) \(G_1\) 无奇数度数顶点 \(\Rightarrow\) \(G_2\) 无奇数度数顶点 \(\Rightarrow\) \(G_2\) 有欧拉回路。

[Lecture 29 pp.20 Q9] Wheel graph \(W_n\) for \(n\geq 3\)​ 有多少哈密顿回路？

顺逆时针同构，环同构：唯一的非同构点在于在第 \(i\) 个结点进入轴心。因此共有 \(n\) 个哈密顿回路。


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info: COMP2121 Discrete Mathematics 2C, Lecturer: Prof. Ramanathan Ravishankar

Course textbook: Kenneth H. Rosen (2019) Discrete Mathematics and Its Application (8th Edition)

-----------------------------------そして、次の曲が始まるのです。-----------------------------------