Lane
离散数学

离散数学

2025年05月23日 7.2k 字 大概 34 分钟

导航

面向对象

选择竺可桢学院的通识模块课程的同学，主要内容基于jxg老师的ppt。

成绩构成

  1. 作业(10%)+小测(20%)+期末(70%)

chapter1-The Foundations:Logic and Proofs

1.1 Proposition Logic

Logic operators

  • Negation:$\neg$
  • conjunction:$\land$
  • disjunction:$\lor$
  • implication(if p then q):p->q
    • everything implies truth,false implies anything
  • biconditional(p if and only if q)
  • functinally complete
    • 当一套逻辑连接词（或布尔运算符）被称为功能完备时，意味着所有可能的布尔函数都可以仅使用这些连接词来表达。

propositional formula

  • 定义:
    1. Each propositional variable is a formula,and the truth values T and F are formulas.
    2. If A and B are formulas,so are $\neg A,A \land B,A \lor B,A \rightarrow B,A \leftrightarrow B$.
    3. A string of symbols is a formula only as determined by the above three rules.
  • classifaction of propositional formula
    • tautology(永真式)
    • contradiction(永假式)
    • contingence:neither a tautology nor a contradiction

1.2 propositional equivalences

  • 定义：对于两个命题，如果$A \leftrightarrow B$是永真式则这两个命题 logically equivalent,表示为$A \Leftrightarrow B$
  • 重点掌握的逻辑等价的式子
    • 德摩根律:$\neg (p \lor q) \Leftrightarrow \neg p \land \neg q$
    • 分配律:$p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$
    • $\neg p \lor q \Leftrightarrow p \leftrightarrow q$

propositional normal forms

  • disjunctive normal form
    • a formula in disjunctive normal form is $(A_{11} \land A_{12} \land … A_{1n_{1}}) \lor … \lor (A_{k1} \land …)$
    • a minterm is a conjunction of literals in which each variable is represented exactly once.
    • full disjunctive forms:a boolean function is expressed as a disjunction of minterms.
  • conjunctive normal form
  • theorem 1:Any formula A is tautologically equivalent to some formula in disjunctive normal form

methods of proof

  • deductive reasoning:the process of reaching a conclusion q from a sequence of propositions $p_1,p_2…p_n$
    • $p_1,p_2…p_n$:premises or hypothesis
  • 我们说an argument is valid如果我们的假设是真的，则能得到结果为真
  • 本质上推理证明都是基于永真式，即当我的假设为true时，通过$\rightarrow$连接的结果一定为true。所以通过这个性质可以进行推理证明操作。
  • 推理规则
    • 基于$p \rightarrow q$存在两个规则
      • Law of detachment
      • Modus tollens
    • 基于disjunction的add
      • rule of addition
    • 基于conjunction的simplification
      • rule of simplification
    • rule of conjunction
    • 基于$\rightarrow$的传递性
      • rule of hypothetical syllogism
    • rule of disjunctive syllogim
      $p \lor q,\neg p $therefore q
    • 归结规则:resolution
      • 基于下面的永真式:$(p \lor q) \land (\neg p \lor r) \rightarrow (q \lor r)$

1.3 predicates and quantifiers

predicates

  • 定义:A statement of the form $P(x_1,x_2,…,x_n)$ is the value of the propositional function P at the n-tuple$(x_1,x_2,…x_n)$,and P is also called a predicate.

quantifiers

  • universal quantifier:For all x,p(x):$\forall x p(x)$
  • existential quantifier:For some x,p(x):$\exists x p(x)$

some important equivalent predicates formula

  • De Morgan’s laws
    $$
    \neg \forall xp(x) \Leftrightarrow \exists x \neg p(x)
    $$
    $$
    \neg \exists xp(x) \Leftrightarrow \forall x \neg p(x)
    $$
  • 需要注意的是quantifiers，并没有都满足双向
    $$
    \forall x(p(x) \land q(x)) \Leftrightarrow ((\forall xp(x)) \land (\forall xq(x)))
    $$
    $$
    \forall x(p(x) \lor q(x)) \Leftarrow ((\forall xp(x)) \lor (\forall xq(x)))
    $$
    $$
    \exists x(p(x) \lor q(x)) \Leftrightarrow ((\exists xp(x)) \lor (\forall xq(x)))
    $$
    $$
    \exists x(p(x) \land q(x)) \Rightarrow ((\exists xp(x)) \land (\forall xq(x)))
    $$

prenex normal forms

  • 定义:A formula is in prenex normal form if it is of the form:

    $$
    Q_1x_1Q_2X_2…B
    $$

    其中$Q_i$为量词，B是谓词

  • 要将一般的命题转化为prenex normal form的形式：首先是消除$\rightarrow$ and $\leftrightarrow$,其次充分利用之前的逻辑等价的关系，将量词放在命题的最前面

扩展前面的推理证明

  • rules of inference for quantifiers
    • 利用全称量词的性质,$\forall x \in D ,d \in D$ Therefore P(d)
    • 反向构造全称量词,$P(d) for any d \in D$ Therefore $\forall xP(x)$
    • 利用存在量词的性质,$\exists x \in D,P(x)$ Therefore P(d) for some $d \in D$
    • 反向构造存在量词,$P(d) for some d \in D$ Therefore $\exists xP(x)$

chapter2-Basic Structures:Sets,and Functions

2.1 Sets

Sets and subsets

  • Set:The object in a set are called the elements,or members,of the set. A set is said to contain its elements.
  • 描述集合的方式
    • List
    • Predicate(stating the properties)
    • Venn Diagram
  • 集合的性质
    • 无序
    • 元素的重合不影响
    • certainty
  • Subsets

2.2 Set operations

Set operation

  • Union
    • $A \cup B =$ { $x \mid x \in A \lor x \in B $ }
  • Intersection
    • $A \cap B =$ { $x \mid x \in A \land x \in B $ }
  • Difference
    • $A - B$ = { $x \mid x \in A \land x \notin B $ }
  • Complement
  • Syemmetric Difference
    • $A \oplus B =$ $(A - B) \cup (B - A)$

the power set and cartesian products

  • 定义：对于一个集合，它的幂集由他的所有子集组成：$2^{S} = ${ $ T \mid T \subseteq S $ }
  • The ordered n-tuple:$(a_1,a_2,…,a_n)$ is the ordered collection that has a1 as its first element…
  • Cartesian Products:A and B are sets,两者进行cartesian 积的结果 $A \times B = $ { $(a,b) \mid a \in A \land b \in B $ }
    • $A^2 = A \times A$, the cartesian square of A
    • 如果其中一者无限，另外一个为空，则乘积是无限的
    • 和空集的cartesian product均为空集
    • 该操作一般条件下不满足交换律和只存在积的结合律
    • 存在以下等式
      $$
      A \times (B \cup C) = (A \times B) \cup (A \times C)
      $$
      $$
      A \times (B \cap C) = (A \times B) \cap (A \times C)
      $$
  • 同样地，笛卡尔积能够进一步扩展到n个集合进行笛卡尔积

2.3 Cardinality of Finite and Infinite Sets

Counting Finite sets

  • Cardinality(基数): The size of a Set S
  • Principle of inclusion-exclusion:
    $$
    | A \cup B | = |A| + |B| - |A \cap B|
    $$

Cardinality of infinite sets

  • 对于无限集而言:Two sets have the same cardinality if and only if there is an one-to-one correspondence from A to B.

    • example:N1 = {1,3,5…,},then |N1| = |N| and where the one-to-one correspondence is $f(n) = 2n - 1$
    • 如果两个集合满足以上关系那么它们是 equivalence relation. 并且one-to-one correspondence 不是唯一的。

  • 可数（denumerable）的集合:对于无限的集合，如果和自然数集有相同的cardinality,也就是和自然数集建立一对一的映射那么这个无限集是可数的。有限集一定是可数的。

    • 常见可数集

      • 整数集

      • 有理数集

        通过对角线进行证明：
        所有的有理数都可以用两个互质的数表示
        $q = \frac{p}{q}$,consider $|p| + q =k$
        并且我们按照如下计数规则依次计数:
        1. 按照k从小到大的顺序
        2. 在k相同时，按照p从小到大的顺序
        并且在计数过程中，删除掉前面已经出现过的有理数，这样对于任何有理数我们都可以通过这样的方式得到它的$a_i$的表示，也就说明有理数与自然数集建立一一对应的映射

      • The set $N \times N$ is denumerable.

  • 可以试着通过希尔伯特酒店来理解可数无限集。

    • 希尔伯特酒店的设定，想象有一家酒店，它有：
      无限多个房间，并且每个房间都有一个编号：1号房，2号房，3号房，… 以此类推，房间的数量是可数无限的。所有房间都已经住满了客人。
    • 希尔伯特酒店之所以被称为“悖论”，并不是因为它存在真正的逻辑矛盾，而是因为它与我们基于有限经验形成的直觉相悖。它深刻地揭示了无限集合的以下几个重要性质：
      • 无限集可以与其真子集建立一一对应： 在有限世界里，一个集合的真子集（不等于原集合的子集）的元素数量总是少于原集合。但在希尔伯特酒店中，所有房间（无限）的集合与所有奇数房间（无限，是所有房间集合的真子集）的集合具有相同的基数（都是可数无限），它们之间可以建立一一对应。这在有限集合中是不可能的。
      • “满”的定义不同： 对于有限集合，“满”意味着没有空余空间。但对于无限集合，“满”并不意味着不能再容纳新的元素。通过重新安排，总能找到空位。

  • Theorem 1:The cardinality of the power set of an arbitrary set has a greater cardinality than the original arbitrary set.

  • Theorem 2:The set of real numbers is uncountable.(其实我们很多对于集合证明其不可数，最后都可以进行转换分析到实数集的不可数上)

    • 比如(0,1),通过tan能够与实数集建立一对一的映射，这也说明其是不可数的。
    • 我们同样可以利用对角化严格证明(0,1)的不可数

    我们是用反证法进行证明
    假设(0,1)是可数的，那么0到1所有的数都能被按照下面的方式列出来（与自然数构建一一映射）：
    0 $0.a_{00} a_{01} a_{02} …$
    1 $0.a_{10} a_{11} a_{12} …$
    我们现在再构造一个$b = 0.b_0b_1b_2…$（我们的想法是想要说明这个b并不存在于我们前面提及的数组成的集合中）其中如果$a_{ii}$不等于1，那么$b_i = 1$,否则 $b_i = 2$。我们很容易地看到这样构造的b一定不存在于前面的集合中，说明我们的假设是错误的，(0,1)不可数

2.4 Functions

2.4.1 Introduction

  • 定义:A与B均是集合，定义从A到B的函数如下:

$$
f : A \rightarrow B \Leftrightarrow \forall a \in A \exists b \in B \text{ such that } f(a) = b
$$

  • A is the domain of the function,B is the codomain of the function.

one-to-one and onto functions

  • one-to-one function（单射）

$$
\forall a,b \in A \land a \neq b \implies f(a) \neq f(b)
$$

  • onto function（满射）

$$
\forall b \in B \exists a \in A \text{ such that } f(a) = b
$$

  • bijection function（双射）:onto and one-to-one

The growth of functions

  • 定义:Let f and g be functions from the set of integers or the set of real numbers.We say that $f(x)$ is $O(g(x))$ if there exist constants $c$ and $n$ such that $|f(x)| \leq c|g(x)|$ for all $x \geq n$.
  • Theorem 3:Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + … + a_1x + a_0$ be a polynomial of degree $n$ with real coefficients.Then $f(x) = O(x^n)$

证明的思路就是把它转化为定义的表达式：
第一步放缩利用绝对值不等式，再将我们需要的幂次项提出，进一步放缩，最终能得到我们想要的表达式

chapter3-The Fundamentals: Algorithms

3.1 Algorithms

3.1.1 Introduction

  • Algorithm:A finite set of precise instructions for performing a computation or solving problem

chapter4-Induction and Recursion

chapter5-Counting

5.1 The Basics of counting

basic counting principle

  • 加法原理
  • 乘法原理

chapter6-高级计数技术

递推关系的应用

  • 常见的递推关系
    • 斐波那契数
    • 汉诺塔

求解线性递推关系

  • 前面的递推关系的推出，我们需要利用动态规划的思想得到，那么我们应该怎样得到求解呢？
  • 这就涉及到线性递推关系的求解

求解定理1

  • 设c1,c2为实数。假设$r^2-c_1r-c_2=0$有两个不相同的根r1,r2，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}$的解，当且仅当$a_n=a_1r_1^n+a_2r_2^n$

求解定理2（重根）

  • 设c1,c2为实数。假设$r^2-c_1r-c_2=0$有两个相同的根r，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}$的解，当且仅当$a_n=a_1r^n+a_2r^n$

扩展到一般情况

  • 设c1,c2,….ck为实数。假设$r^n-c_1r^{n-1}-c_2r^{n-2}-…-c_kr^0=0$有k个不相等的根，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}+…+cka_{n-k}$的解，当且仅当$a_n=a_1r_1^n+a_2r_2^n+…+a_kr_k^n$

扩展到一般情况(存在重根)

  • 设c1,c2,….ck为实数。假设$r^n-c_1r^{n-1}-c_2r^{n-2}-…-c_kr^0=0$有t个不相等的根r1,r2….rt，其重数分别为m1,m2…mt,满足$\sum_{i=1}^t m_{i}=k$,那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}+…+ck*a_{n-k}$的解，当且仅当$a_n=(\alpha {1,0}+\alpha{1,1}*n…\alpha_{1,m1-1}*n^{m1-1})*r_1^n+(\alpha {2,0}+\alpha{2,1}*n…\alpha_{2,m2-1}*n^{m2-1})*r_2^n+…$

求解常系数线性非齐次递推关系

  • 对于常系数非齐次递推关系$a_{n}=c_1a_{n-1}+c_2a_{n-2}….+F(n)$,其中$a_{n}^{p}$为这个递推关系的一个特解，$a_{n}^{h}$为上述的相伴的齐次递推关系的解，则每一个解的形式是$a_{n}^{p}+a_{n}^{h}$

非齐次递推关系中的特解的求取

  • 对于非齐次线性递推关系，$F(n)=(b_t*n^t+b_{t-1}n^{t-1}+…+b_1n+b_0)*s^n$.当s不是相伴的线性齐次递推关系的特征方程的根时，存在一个下列形
    式的特解$(p_tn^t+p_{t-1}n^{t-1}+…+p_1n+p_0)*s^n$

生成函数

有用的生成函数

  • $(1+x)^n=\sum_{k=0}^{n}C(n,k)x^k$
  • $(1+a*x)^n=\sum_{k=0}^{n}C(n,k)a^kx^k$
  • $\frac{1-x^{n+1}}{1-x}=\sum_{k=0}^{n}x^k$
  • $\frac{1}{1-x}=\sum_{k=0}^{\infty}x^k$
  • $\frac{1}{1-a*x}=\sum_{k=0}^{\infty}a^kx^k$

chapter8-Graphs

8.1 Introductions to Graphs

Types of Graphs

  • 简单图(一般都是指无向的)
  • Multigraph: a graph in which there are multiple edges between two vertices.
  • pseudograph: A pseudograph is a type of graph in graph theory that allows for both multiple edges (also called parallel edges) and loops (also called self-loops).
  • directed graph:有向图
  • directed multigraph:有向图，允许多条边连接两个顶点

8.2 Graph Terminology

basic terminology

  • 无向图
    • degree:the number of edges incident with it,except the a loop at a vertex contribute twice to the degree of the vertex.
    • Theorem 1(握手定理):$\sum_{i=1}^{n}deg(v_i) = 2m$
  • 有向图
    • 和无向图不同的是，有向图分为in-degree(the number of edges with v as their terminal vertex),out-degree(the number of edges with v as their initial vertex).则对于loop而言入度和出度都为1.
    • Theorem 2:$\sum_{i=1}^{n} deg^{-}(v_i) = \sum_{i=1}^{n} deg^{+}(v_i) = |E|$

Some Special simple Graphs

  • 完全图：使用$K_{i}$表示，$|E| = C(n,2)$
  • Cycles：使用$C_{i}$表示
  • Wheels：使用$W_{i}$表示，相对于cycles而言在中间新增了一个节点并增加这个节点和原来节点的边
  • n-Cubes：使用$Q_{i}$表示
  • Bipartite graph：这张图的节点能够划分为两个节点集，并且所有边会被这两个节点集的任意一组节点构成，也就是说同组不会构成边。
  • complete bipartite graph：$K_{m,n}$ 它除了满足二分图的所有条件外，还满足一个更强的条件：每个 V1中的顶点都与每个V2
    中的顶点都有一条边相连。

new graphs from old

8.3 reprensenting graphs and graph isomorphism

reprensenting graphs

  • 邻接矩阵
    • 简单图
    • with loops and multiple edges:$a_{ij} = $the number of edges connecting vertex i to vertex j.
  • 关联矩阵(Incidence Martix)
    • 行对应节点，列对应边。该节点为该边的端点，则为1.

graph isomorphism

  • 定义：如果两个图是同构的，则两个图之间存在一个bijection，使得两个图之间任意两个顶点对应关系互逆。
  • 因为直接寻找映射关系其实是一件很困难的事情，所以一般我们寻找特例来推翻同构：主要是查看度数是否一致

8.4 Connectivity

Paths

  • path
    • 定义: a path is a simple path(a sequence of edges) between two vertices.
    • Circuit: a circuit is a path that starts and ends at the same vertex.（我觉得这个需要和前面的loop进行区分）
    • simple: a path is simple if it does not contain any repeated edge.And we denote the path by its vertex sequence $x_0,x_1,…,x_n$

connectedness in undirected graphs

  • connected:图中的任何不同的两个点都存在一条路径
  • connected components:这个图不是连通的，但是是多个连通的子图的集合，这些连通子图叫作connected components
  • Theorem 3:There are a simple path between every pair of distinct vertices of a connected undirected graph.
  • cut vertices:对于一个连通图 G=(V,E)，如果删除一个顶点 v∈V（及其所有与该顶点相连的边）后，图 G 的连通分量 (Connected Components) 数量增加，那么这个顶点 v 就被称为一个割点。简单来说，割点就是移除它会使图分裂成两个或更多不连通部分的顶点。
  • cut edge or bridge:对于一个连通图 G=(V,E)，如果删除一条边 $e \in E$ 后，图 G 的连通分量 数量增加，那么这条边 e 就被称为一条割边。割边也被称为桥 (Bridge) 或 地峡(Isthmus)。简单来说，割边就是移除它会使图分裂成两个或更多不连通部分的边。

connectedness in directed graphs

  • strongly connected:对于两个节点，a到b，b到a都存在路径
  • weakly connected:退化到无向图的连通

counting paths between vertices

  • Theorem 4:G为一张图，A为这张图对应的邻接矩阵，The number of paths between vertices i and j of length r equals to the(i,j)th entry of $A^r$(利用数学归纳法证明)

Paths and isomorphism

  • 当我们引入了path对于前面的同构问题我们又可以举出一些反例：考虑两个图，一个图有环，一个图没有环或者两张图对应的环的长度和数量不相同，那么两个图不是同构的。

8.5 Euler and Hamilton Paths

Euler paths and circuits

  • 定义:某张图中的欧拉回路就是一个简单图并包含这张图中的所有边,恰好遍历一次。Euler Path is a simple path containing every edge of G。
  • Theorem 5(Necessary and Sufficient Condition):连通的图中如果有欧拉回路当且仅当每一个顶点都有偶数的度数

向后证明：已知存在一个欧拉回路，假设这个欧拉回路访问了某个节点k次，根据欧拉回路的性质，每次访问都会新增访问的两条边，所以每个结点的度数一定为偶数。
向前证明（思路其实就是构造欧拉回路的方法）：此时每个顶点的度数均为偶数，我们考虑一条路径v0->v1..->vk(不等于v0)，则对于vk一定有没有包含在路径中的边，于是我们将这个路径扩展直到路径为:v0->v1->v2->…->vk-1->vk->vm = v0
现在再考虑这个路径,假如vk还有没有被访问的边$v_{m+1}$，那么我们直接让vk=v0,v0->v1…->vm=v0->$v_{m+1}$,我们可以重复上述操作直到所有边都在图中

  • Theorem 6:一张连通图有一条欧拉路径但是没有欧拉回路当且仅当它恰好有两个节点的度数为奇数

向前证明:也是利用构造性证明的方式，因为定理五的充要条件我们可以知道这张连通图一定不存在欧拉回路，所以现在我们主要证明存在欧拉路径。
因为我们有两个顶点的度数恰好为奇数，我们可以构造一张图，相较于原图新增一条边连接这两个度数为奇数的顶点。
此时新图按照我们前面的定理一定存在一个欧拉回路，恰好遍历图的每一条边一次，那么我们将新图中的这条边移走，我们再从这两个顶点出发按照欧拉回路的方式一定能得到一条欧拉路径。

Hamilton paths and circuits

  • 定义:在一个图 G=(V,E) 中，一条哈密尔顿路径是一条简单路径，它包含图 G 中的每一个顶点恰好一次。简单路径 (Simple Path)：路径中不重复任何顶点和任何边。包含每一个顶点恰好一次：这是哈密尔顿路径最核心的特性，它必须“访问”图中的所有顶点，且每个顶点只能被访问一次。
  • 在一个图 G=(V,E) 中，一条哈密尔顿回路是一个简单回路，它包含图 G 中的每一个顶点恰好一次（除了起始和结束顶点，它被访问了两次）
  • Theorem 7:If G is a connected simple graph with n vertices where $n \ge 3$,then G has a hamilton circuit if the degree of each vertex is at least n/2

8.6 Shortest path problems

Introduction

  • Dijkstra’s algorithm（针对不带有负权值的图）

    • 解释
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    初始化：
      创建一个距离数组 dist，用来存储从源顶点到每个顶点的当前最短距离。
      dist[源顶点] 设置为 0。
      dist[所有其他顶点] 设置为无穷大（表示暂时无法到达或距离未知）。
      创建一个布尔数组 visited (或集合 S)，用来记录哪些顶点已经确定了最终的最短路径。
      所有顶点初始时都标记为未访问 (false)。
      创建一个优先队列 (Priority Queue) pq，用于存储 <距离, 顶点> 对。优先队列会根据距离从小到大排序。
      将 <0, 源顶点> 加入到 pq 中。
    迭代过程：
      只要优先队列 pq 不为空，就重复以下步骤：
      a.  从 pq 中取出距离最小的顶点 u（即 pq.pop()）。
      b.  如果顶点 u 已经被访问过（即 visited[u] 为 true），则跳过，因为我们已经找到了它的最短路径。
      c.  将顶点 u 标记为已访问 (visited[u] = true)。这意味着我们已经找到了从源点到 u 的最短路径。
      d.  更新邻居的距离： 遍历顶点 u 的所有邻居 v：
      * 对于每条边 (u, v)，设其权值为 weight(u, v)。
      * 如果 u 已经被访问，并且 dist[u] + weight(u, v) < dist[v]：
      * 这意味着通过 u 到达 v 的路径比目前已知的任何路径都短。
      * 更新 dist[v] = dist[u] + weight(u, v)。
      * 将新的 <dist[v], v> 对加入到优先队列 pq 中。
    结束：
      当优先队列为空时，算法结束。此时，dist 数组中存储的就是从源顶点到所有其他顶点的最短距离。
    • Theorem 8:Diljkstra’s algorithm确实成功找到了最短路径。
    • Theorem 9:Dijkstra’s algorithm use $O(n^2)$

8.7 Plannar Graphs

8.7.1 Introduction

  • 定义:A graph is called planar if it can be drawn in the plane without crossing edges.Such a drawing is called a planar representation of the graph.

euler formula

  • 定义:A planar representation of a graph into regions,including an unbounded region.
  • Theorem 10(欧拉公式):Let G be a connected planar simple graph with e edges and v vertices.Then $v-e+r=2$ where r is the number of regions in the planar representation of G.

欧拉公式的证明也是基于数学归纳法证明：
现在已经假设$r_n = e_n - v_n +2$,相对于满足条件的Gn,我们添加一条边{$a_n+1,b_n+1$}使之成为Gn+1
情况1：这两个点都已经包含在Gn中，那么我们添加边以后，边数多了一个，区域也多了一个，此时欧拉公式仍然成立。
情况2：这两个点中的一个点包含在Gn中，另外一个点在外面。此时我们新增加了一个节点，边数也增加了一个，但是我们现在对于新增的节点并没有一个环经过它，所以区域数是保持不变的，此时欧拉公式仍然成立。

  • Theorem 11（欧拉公式的推论）：If G is a connected planar simple graph with e edges and v vertices where $v \ge 3$,then $e \le 3v-6$，同样利用这个推论可以证明某些图不是平面的
  • 这个推论的证明需要我们了解一些前提条件
    • 面的度数：每个面边界的边数
    • 并且每个面的度数至少为3
  • Theorem 12（加强条件的推论）：If G is a connected planar simple graph with e edges and v vertices where $v \ge 3$ and no circuits of length 3,then $e \le 2v-4$
  • 这个推论的证明类似于上一个推论，只是我们加强了条件，所以最终的结果更精准

Kuratowski’s theorem

8.8 Graph Coloring

8.8.1 Introduction

  • 定义：A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.The chromatic number of a graph is the least number of colors needed for a coloring of this graph.
  • Theorem 13（四色定理）：The chromatic number of a planar graph is no greated than four.

applications of graph colorings

chapter9-Trees

Introductions to Trees

  • 定理1:An undirected graph is a tree iff there is a unique simple path between any two of its vertices.
  • 定理2:A tree with n vertices has n-1 edges.
  • Theorem 3:A full m-ary tree with i internal vertices contains n=mi+1 vertices.
  • Theorem 4:There are at most $m^h$ leaves in m-ary tree of height h.（可以使用数学归纳法证明）
    • corollary(推论)：if an m-ary tree of height h has l leaves,then $h \ge log_m(l)$.If the m-ary trees is full and balanced,then $h = log_m(l)$.

Applications of Trees

二叉搜索树

PREFIX CODES

  • 定义：前缀码的性质就是没有任何一个码是另一个码的前缀
  • 性质：由前缀码的性质，我们可以将它表达为一颗二叉树。霍夫曼编码（根据字符的出现频率进行编码）其实就是前缀码的一种。

desicion trees

  • 定义： decision tree 是一棵树，树中的每个内部节点都表示一个决策，这些内部节点对应的子树的叶子节点对应这个决策的结果。

Tree Traversal

Spanning Trees

  • 定义：图是简单图，那么这个图中的树为生成树需要满足条件：这棵树是这张图的子图；这棵树包含这张图的所有节点
  • Theorem 1:A simple graph is a connected if and only if it has a spanning tree.
  • 当我们计算一张图中有多少颗生成树的时候：我们一般求不同构的树，所以这些树的表示应该是使用每个节点的度数序列来表达

Algorithms for constructing spanning trees

  • depth-first search
    • 深度优先搜索，利用回溯
  • 广度优先搜索

Minimum Spanning Trees

  • 定义:针对加权图，最小生成树是所有边权重之和最小的生成树

Algorithms for constructing minimum spanning trees

  • Kruskal’s algorithm
    • 首先选择整张图中权重最小的边
    • 一直考虑寻找图中的权重最小的边，如果这条边添加后不会形成环，那么就加入到生成树中，否则就忽略这条边。
    • 当边数为n-1时，则停止搜索
  • Prim’s algorithm
    • 还是从图中权重最小的边开始，将它放进生成树中
    • 接下来考虑图中与当前生成树中节点相连的权重最小的边，如果这条边没有在生成树中出现过，那么就加入到生成树中，否则就忽略这条边。
    • 当边数为n-1时，则停止搜索
  • 接下来严格证明Prim算法的合理性

Proof:

  • 图G为连通的带权重的图。假设我们通过普利姆算法成功选择了n-1条边，设为$e_i$。
  • 设S是由上述的边组成的树，$S_k$ 是由$e_1,e_2…e_k$组成的树。
  • 设T是G的最小生成树，包含上面的边$e_1,e_2…e_k$，其中k是使之满足最小生成树性质的最大值。
  • 如果S与T不相等，那么T就不会包含$e_{k+1}$,如果考虑T加上$e_{k+1}$那么一定会存在一个简单的环，并且在简单的环中一定有一条路径没有在$S_{k+1}$中（因为这是一棵树）
  • 并且我们能在T中找到一条边e，并且这条边不在$S_{k+1}$中，将这条边删除，再向T中添加$e_{k+1}$，那么我们就可得到新的一棵树T1。因为$e_{k+1}$是通过普利姆算法得到的，所以它的权重一定比e的权重更小，这就导致矛盾。
本文总阅读量次
本文作者：Lane
本文链接：https://lakerswillwin.github.io/2025/05/23/discremetemath/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
数理课程