离散2笔记

\(\mathcal{Author:gpf}\)

考前要看的几点

判断题

连通无向图：欧拉图 \(\Leftrightarrow\) 有欧拉闭路；非连通无向图：欧拉图 \(\Leftrightarrow\) 每个分支都有欧拉闭路

字典序不一定保证有极小元（ab,aab,aaab,...）

n阶二叉树有(n+1)/2个叶节点，(n-1)/2个分支节点

任何图都有偶数个奇结点

三个集合间的交、并关系仔细看！

证明题

最优叶加权路径

n阶非循环无向图有n-1条边，求证连通

n阶连通无向图有n-1条边，求证非循环

n阶连通无向图G非循环，求证有n-1条边

\(t(R)=R^{+}\)

基础图是完全无向图的n阶有向图必有哈密顿路径

集合

罗素悖论：\(T=\{x|x\notin x\}\)，则推理 \(T\in T\) 与 \(T\notin T\) 过程中均产生矛盾

幂集：集合A的全部子集构成的集合，即 \(\mathcal{P}(A)=\{X|X\subseteq A\}\)

A有穷，则 \(\#\mathcal{P}(A)=2^{\#A}\)

集合的运算

\(A-B=A\cap \sim B\)

\(A\oplus B=(A-B)\cup(B-A)\)

证明某式成立：元素分析法、集合运算

广义交、广义并

集类：某集合的所有元素都是集合

广义并：设 \(\mathcal{B}\) 是任意集类，称集合 \(\{x|\exists X(X\in\mathcal{B}\land x\in X)\}\) 为 \(\mathcal{B}\) 的广义并，记为 \(\cup\mathcal{B}\)

广义交：设 \(\mathcal{B}\) 是任意集类，且 \(\mathcal{B}\ne\emptyset\)，称集合 \(\{x|\forall X(X\in\mathcal{B}\rightarrow x\in X)\}\) 为 \(\mathcal{B}\) 的广义交，记为 \(\cap\mathcal{B}\)

有穷集的计数原理：\(\#(A\cup B)=\#A+\#B-\#(A\cap B)\)

集合的归纳定义、字符串集合

归纳定义法

1. 基本项：非空集 \(S_0\subseteq A\)
2. 归纳项：一组规则，使得从A中元素出发，按照规则所获得的元素仍然是A中元素
3. 极小化：A中每个元素都是通过有限次使用1或2获得的，如果集合 \(S\subseteq A\) 也满足1和2，则 \(S=A\)

字符串集合

字母表 \(\Sigma\)：字母或符号的非空有限集合

字符串：由 \(\Sigma\) 中字母组成的有穷序列

字符串长度：字符串 \(x\) 所含字母的个数，记作 \(|x|\)

空串：若 \(|x|=0\)，称 \(x\) 为空串，记作 \(\varepsilon\)

字符串连接：设 \(\Sigma\) 是一字母表，\(x,y\) 是 \(\Sigma\) 上字符串，\(x=a_1a_2...a_n,y=b_1b_2...b_m\) ，则 \(x\) 和 \(y\) 的连接记作 \(xy\)，\(xy=a_1a_2...a_nb_1b_2...b_m\)。另外规定：

• \(x\varepsilon=\varepsilon x=x\)
• n个 \(x\) 的连接记作 \(x^n,x^0=\varepsilon,x^{n+1}=x^nx\)
• \(|x+y|=|x|+|y|\)

字符串集合 \(\Sigma^*\)：\(\Sigma\) 上的所有字符串构成的集合，其中非空字符串的集合记为 \(\Sigma^+\)，\(\Sigma^*\) 归纳定义如下

1. \(\{\varepsilon\}\cup\Sigma\subseteq\Sigma^*\)
2. 若 \(x\in\Sigma^*\) 且 \(a\in\Sigma\)，则 \(xa\in\Sigma^*\)
3. \(\Sigma^*\) 中的每一个元素都可以通过有限次应用上述1、2规则得到

语言

\(\Sigma^*\) 的子集称 \(\Sigma\) 上的语言

语言的乘积：设A、B是 \(\Sigma\) 上的语言，则A与B的乘积记作 \(AB=\{xy|x\in A\land y\in B\}\)

语言的幂运算：\(A^0=\{\varepsilon\},A^{n+1}=A^nA\)

语言的闭包：\(A^*={\varepsilon\cup A\cup A^2\cup......}\)，正闭包 \(A^+\) 没有 \(\varepsilon\)

有序偶与笛卡尔积

有序偶：\(<x,y>=\{\{x\},\{x,y\}\}\)

笛卡尔积：\(A\times B=\{<x,y>|x\in A\land y\in B\}\)

笛卡尔积无交换律，但是对交、并、差满足分配律

关系

定义与性质

设 \(n\in I^+\)，且 \(A_1,A_2,...A_n\) 为n个任意的集合，\(R\subseteq A_1\times A_2\times...\times A_n\)，称R为 \(A_1,A_2,...A_n\) 间的n元关系。\(<x,y>\in R\)，则可表示成 \(xRy\) ；\(<x,y>\notin R\)，则可表示成 \(x\bar{R}y\)

全关系：\(R= A_1\times A_2\times...\times A_n\)

A上的关系：\(A_1=A_2=...=A_n=A\)

恒等关系（X上的二元关系）：\(I_X=\{<x,x>|x\in X\}\)

从有限集到有限集的二元关系可用关系图、关系矩阵表示

设R是集合X上的二元关系：

• 自反性：\(\forall x(x\in X\rightarrow<x,x>\in R)\Leftrightarrow I_X\subseteq R\) ，对角线元素为1、所有节点有自环
• 反自反：\(\forall x(x\in X\rightarrow<x,x>\notin R)\Leftrightarrow I_X\cap R=\emptyset\) ，对角线元素为0、所有节点无自环
• 对称性：\(\forall x\forall y(x\in X\land y\in X\land<x,y>\in R\rightarrow<y,x>\in R)\Leftrightarrow R=R^{-1}\)， 对称矩阵、边成对出现
• 反对称：\(\forall x\forall y(x\in X\land y\in X\land<x,y>\in R\land<y,x>\in R\rightarrow x=y)\Leftrightarrow R\cap R^{-1}\subseteq I_X\)
• 传递性：\(\forall x\forall y \forall z(x\in X\land y\in X\land z\in X\land<x,y>\in R\land<y,z>\in R\rightarrow<x,z>\in R)\Leftrightarrow R\circ R\subseteq R\)， x到y有路径，则x到y有边

非空集上的空关系没有自反性，空集上的空关系具有全部性质

含有3个元素的集合A上的反对称关系共有216个（用矩阵考虑，且三角阵里是 \(3^3\)）

关系的运算

交并补、异或、差

定义域与值域：

• \(dom(R)=\{x\in A|\exists y\in B使得<x,y>\in R\}\)
• \(ran(R)=\{y\in B|\exists x\in A使得<x,y>\in R\}\)
• \(dom(R_1\cup R_2)=dom(R_1)\cup dom(R_2)\)
• \(ran(R_1\cap R_2)\subseteq ran(R_1)\cap ran(R_2)\) （注意交集的情况下不会相等）

R,S	\(R\cap S\)	\(R\cup S\)	\(R-S\)	\(R\oplus S\)	\(\sim R\)
自反	\(\checkmark\)	\(\checkmark\)
反自反	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
对称	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
反对称	\(\checkmark\)		\(\checkmark\)
传递	\(\checkmark\)

逆关系相当于矩阵转置，保持原有关系的5个性质

复合运算

\(R\circ S=\{<x,z>|\exists y\in Y使得xRy\land ySz\}\)

若R是A上的关系，则 \(R^0=I_A\) ， \(R^{n+1}=R^n\circ R\)

有时也记 \(R^{+}=\cup_{i=1}^{\infty}R^i\)

无交换律，有结合律

设 \(R_1\subseteq A\times B,\ R_2,R_3\subseteq B\times C，R_4\subseteq C\times D\)，则

• \(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_1\circ R_2)^{-1}=R_2^{-1}\circ R_1^{-1}\)

复合运算仅能保持5个性质中的自反性

闭包

定义：设R是集合A上的关系，称R‘是R的自反（对称、传递）闭包，当且仅当

1. R'是自反（对称、传递）的
2. \(R\subseteq R'\)
3. 对于A上的任何自反（对称、传递）关系R''，如果 \(R\subseteq R''\) ，则 \(R'\subseteq R''\)

R的自反（对称、传递）闭包即包含R的最小自反（对称、传递）关系

• R自反：\(r(R)=R=R\cup I_A\)
• R对称：\(s(R)=R=R\cup R^{-1}\)
• R传递：\(t(R)=R=\cup_{n=1}^{\infty}R^n\)
• \(t(R)=\cup_{i=1}^{\#A}R^i\)

闭包运算保持集合上的包含关系，但传递闭包不保持关系的并

• \(r(R_1\cup R_2)=r(R_1)\cup r(R_2)\)
• \(s(R_1\cup R_2)=s(R_1)\cup s(R_2)\)
• \(t(R_1)\cup t(R_2)\subseteq t(R_1\cup R_2)\)

R	r(R)	s(R)	t(R)
自反性	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
对称性	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
传递性	\(\checkmark\)		\(\checkmark\)

次序

各种序

• 偏序关系：A上二元关系R，且R自反、反对称、传递。用 \(<A,\le>\) 表示偏序结构

• 全序关系：\(<A,\le>\) 是一个偏序结构，若 \((\forall xy)(x\in A\land y\in A\rightarrow x\le y\lor y\le x)\)，则称 \(\le\) 为A上的全序（线序），并称 \(<A,\le>\) 为全序结构（链）

• 严格偏序关系：A上二元关系R，且R反自反、传递

• 覆盖：y是x的覆盖 \(\Leftrightarrow x<y\land\neg\exists z(z\in A\land x<z\land z<y)\)

• 良序：偏序结构 \(<A,\le>\)，若A的每一个非空子集都有一个最小元，则称 \(\le\) 为良序关系，\(<A,\le>\) 为良序结构

良序的充要条件：全序+非空子集有极小元；全序+不存在A中元素的无穷递降序列

特殊元素

\(<A,\le>\) 是偏序结构，并且 \(S\subseteq A,S\ne\emptyset\)

• S的最大元：\(b\in S\land\forall x(x\in S\rightarrow x\le b)\)
• S的最小元：\(b\in S\land\forall x(x\in S\rightarrow b\le x)\)
• S的极大元：\(b\in S\land\forall x(x\in S\land b\le x\rightarrow x=b)\)
• S的极小元：\(b\in S\land\forall x(x\in S\land x\le b\rightarrow x=b)\)
• S的上界：\(b\in A\land\forall x(x\in S\rightarrow x\le b)\)
• S的下界：\(b\in A\land\forall x(x\in S\rightarrow b\le x)\)

注意S的上下界可能不在S中

等价关系

• 相容关系：A上关系R自反、对称

• 等价关系：A上关系R自反、对称、传递\(\Leftrightarrow r(R)=s(R)=t(R)=R\)

R是A上二元关系，则 \(tsr(R)、trs(R)、rts(R)\) 都是A上的等价关系（t在s之后）

设R是A上等价关系

• 等价类：\([x]_R=\{y|y\in A\land xRy\}\)

• 商集：\(A/R=\{[x]_R|x\in A\}\) ，称 \(n(A/R)\) 为R的秩

划分

定义：设 \(\Pi\subseteq\mathcal{P}(A)\) ，且有

1. 若 \(S\in\Pi\) ，则 \(S\ne\emptyset\)
2. \(\cup\Pi=A\)
3. 若\(S_1,S_2\in\Pi\) ，且 \(S_1\cap S_2\ne\emptyset\)，则 \(S_1=S_2\)

若R为A上的等价关系，则商集 \(A/R=\{[x]_R|x\in A\}\) 为A的一个划分

若 \(\Pi\) 为A的一个划分，则 \(R_{\Pi}=\{<x,y>|\exists S\in\Pi,使x,y\in S\}\) 为A上的等价关系，且 \(A/R_{\Pi}=\Pi\)

函数

部分函数相关概念

部分函数：从X到Y的二元关系f满足 \(<x,y_1>\in f\land<x,y_2>\in f\rightarrow y_1=y_2\) ，记作 \(y=f(x)\)

定义域：\(dom(f)=\{x\in X|\exists y\in Y使y=f(x)\}\) 。\(x\in dom(f)\) 称f在x处有定义，记为 \(f(x)\uparrow\) ，反之记为 \(f(x)\downarrow\)

值域：\(ran(f)=\{y\in Y|\exists x\in X使y=f(x)\}\)

\(dom(g\circ f)=f^{-1}[dom\ g],ran(g\circ f)=g[ran\ f]\)

严格部分函数：\(dom f\subset X\)

从X到Y上的部分函数：\(ran f=Y\)

从X到Y内的部分函数：\(ran f\subset Y\)

1-1部分函数：\(\forall x_1,x_2\in dom f,当x_1\ne x_2时,均有f(x_1)\ne f(x_2)\)

\(A\subseteq X,B\subseteq Y\) 像：\(f[A]=\{y\in Y|\exists x\in A使y=f(x)\}\) 源像：\(f^{-1}[B]=\{x\in X|\exists y\in B使y=f(x)\}\)

函数相关概念

• 函数（全函数）：\(dom f=X\)，记为 \(f:X\rightarrow Y\)
• 限制：\(f:X\rightarrow Y,A\subseteq X\)，称 \(f\cap(A\times Y)\) 是从A到Y的函数，f在A上的限制，记作 \(f|_A\)。f为 \(f|_A\) 到X的延拓
• 记A到B的函数的集合为 \(B^A=\{f|f:A\rightarrow B\}\) ，则有 \(n(B^A)=(n(B))^{n(A)}\)
• 单射（内射）：\(\forall x_1\forall x_2(x_1\in X\land x_2\in X\land f(x_1)=f(x_2)\rightarrow x_1=x_2)\)
• 满射：\(ranf=Y\)
• 双射：单射+满射
• *自然映射/正则映射：设R是集合A上的等价关系，\(\varphi=\{<x,[x]_R>|x\in A\}\)

注意空关系！

设X是任意集合、f和g都是X到R的函数

\(f\leqslant g:\forall x\in X\rightarrow f(x)\leqslant g(x)\)

\(f+g:\forall x\in X\rightarrow (f+g)(x)=f(x)+g(x)\) ，称 \(f+g\) 为 \(f\) 和 \(g\) 的和

\(f-g:\forall x\in X\rightarrow (f-g)(x)=f(x)-g(x)\) ，称 \(f-g\) 为 \(f\) 和 \(g\) 的差

\(f*g:\forall x\in X\rightarrow (f*g)(x)=f(x)*g(x)\) ，称 \(f*g\) 为 \(f\) 和 \(g\) 的积

函数的复合

设f是从X到Y的（部分）函数，g为从Y到Z的（部分）函数，则复合关系 \(f\circ g\) 是从X到Y的（部分）函数，记为 \(g\circ f=\{<x,z>|x\in X\land z\in Z\land \exists y(y\in Y\land y=f(x)\land z=g(y))\}\)

\(f:X\rightarrow X\)，则f的n次幂记为 \(f^n=f\circ f^{n-1}\) ……

\(g\circ f\) 可以传递满射、单射、双射的性质（f与g均满足时）

逆向推导“左满右单”（\(f:X\rightarrow Y,g:Y\rightarrow Z\)）：

• 若 \(g\circ f\) 是满射，则 \(g\) 是满射
• 若 \(g\circ f\) 是单射，则 \(f\) 是单射
• 若 \(g\circ f\) 是双射，则 \(g\) 是满射且 \(f\) 是单射

逆函数

定义

\(f:X\rightarrow Y\)

若有 \(g:Y\rightarrow X\) 使 \(g\circ f=I_X\) ，称f为左可逆，g为f的一个左逆函数（左逆）

若有 \(g:Y\rightarrow X\) 使 \(f\circ g=I_Y\) ，称f为右可逆，g为f的一个右逆函数（右逆）

若有 \(g:Y\rightarrow X\) 使 \(g\circ f=I_X\) 且 \(f\circ g=I_Y\) ，称f可逆，g为f的一个逆函数（逆）

充要条件

设 \(X\ne \emptyset\) ，若 \(f:X\rightarrow Y\) ，则以下条件等价

• f为单射
• f左可逆
• f可左消去，即对任意Z、任意 \(g:Z\rightarrow X\) 和 \(h:Z\rightarrow X\)，当 \(f\circ g=f\circ h\) 时，都有 \(g=h\)

设 \(f:X\rightarrow Y\) ，则以下条件等价

• f为满射
• f右可逆
• f可右消去，即对任意Z、任意 \(g:Y\rightarrow Z\) 和 \(h:Y\rightarrow Z\)，当 \(g\circ f=h\circ f\) 时，都有 \(g=h\)

\(f:X\rightarrow Y\)，则 \(f\) 是双射 \(\Leftrightarrow f\) 可逆

\(f:X\rightarrow Y,g:Y\rightarrow Z\) 都可逆，则 \(g\circ f\) 可逆，且 \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)

特征函数

定义

设 \(U\) 是全集，\(A\) 是 \(U\) 的子集，\(A\) 的特征函数为 \(\chi_A(x):U\rightarrow R\) \[ \chi_A(x)=\begin{cases} 1,x\in A\\0,x\notin A \end{cases} \]

性质

\(\forall x(\chi_A(x)=0)\Leftrightarrow A=\emptyset\)

\(\forall x(\chi_A(x)=1)\Leftrightarrow A=U\)

\(\forall x(\chi_A(x)\leqslant\chi_B(x))\Leftrightarrow A\subseteq B\)

\(\forall x(\chi_A(x)=\chi_B(x))\Leftrightarrow A=B\)

运算

\(\chi_A*\chi_A=\chi_A\)

\(\chi_A*\chi_B=\chi_A\Leftrightarrow A\subseteq B\)

交：\(\chi_{A\cap B}=\chi_A*\chi_B\)

并：\(\chi_{A\cup B}=\chi_A+\chi_B-\chi_A*\chi_B\)

补：\(\chi_{\sim A}=1-\chi_A\)

差：\(\chi_{A-B}=\chi_A-\chi_A*\chi_B\)

自然数、基数与归纳法

自然数与归纳法

后继：A的后继 \(A^{+}=A\cup\{A\}\) ，每个集合的后继唯一

自然数的归纳定义：

1. \(0\in N\) ，此处 \(0=\emptyset\)

2. 若 \(n\in N\)，则 \(n^{+}\in N\)

3. 若 \(S\subseteq N\)，且满足

   a.\(0\in S\)

   b.如果 \(n\in S\) ，则 \(n^{+}\in S\)

   则 \(S=N\)

自然数的运算

对于每个自然数n，都有 \(n\in n^{+}\) 且 \(n\subseteq n^{+}\) ，\(\cup n^{+}=n\)

\(m<n\)：\(m,n\in N,m\in n\)

+：\(m+0=m,m+n^{+}=(m+n)^{+}\)

\(\cdot\)：\(m\cdot0=0,m\cdot n^{+}=m\cdot n+m\)

自然数系统与皮亚诺公理

定义加法与乘法后，得到自然数系统 \(<N,+,\cdot>\)

这样构造的自然数系统满足以下皮亚诺公理：

1. \(0\in N\)
2. 若 \(n\in N\) ，则有唯一后继 \(n^{+}\in N\)
3. 若 \(n\in N\) ，则有 \(n^{+}\ne0\)
4. 若 \(n,m\in N\) 且 \(n^{+}=m^{+}\) ，则 \(n=m\)
5. 若 \(S\subseteq N\) 满足 \(0\in S\)、如果 \(n\in S\) 则 \(n^{+}\in S\) ，则 \(S=N\)

作为集合的自然数满足

• 传递性：若 \(n_1\in n_2\) 且 \(n_2\in n_3\) ，则 \(n_1\in n_3\)
• 三歧性：对于任意两个自然数 \(n_1,n_2\) ，下式恰有一个成立：\(n_1\in n_2,n_1=n_2,n_2\in n_1\)
• 良基性：不存在一个自然数的无穷递降序列

数学归纳法

第一种

设 \(N_n=\{0,1,...,n-1\}\) ，\(\bar{N}_n=N-N_n={n,n+1,...}\) ， \(n_0\in N\)

若对每个 \(n\in \bar{N}_{n0}\) ，命题 \(P(n)\) 满足：

1. \(P(n_0)\) 真
2. 对任意 \(n\in \bar{N}_{n0}\) ，若 \(P(n)\) 为真，则 \(P(n^{+})\) 也为真

则对所有 \(n\in\bar{N}_{n0}\) ，\(P(n)\) 都为真

第二种

设 \(n_0\in N\) ，若对每个 \(n\in \bar{N}_{n0}\) ，\(P(n)\) 满足：

1. \(P(n_0)\) 为真
2. 对任何自然数 \(n>n_0\) ，若当 \(k\in N\) ，且 \(n_0\leqslant k<n\) 时 \(P(k)\) 为真，则 \(P(n)\) 也为真

则对所有 \(n\in\bar{N}_{n0}\) ，\(P(n)\) 都为真

二重归纳

设 \(i_0,j_0\in N\) ，对任意自然数 \(i\geqslant i_0,j\geqslant j_0\) ，都有命题 \(P(i,j)\) 满足

1. \(P(i_0,j_0)\) 为真
2. 对任意自然数 \(k\geqslant i_0,l\geqslant j_0\) ，若 \(P(k,l)\) 为真，则 \(P(k+1,l)\) 和 \(P(k,l+1)\) 都为真

则对任意自然数 \(i\geqslant i_0,j\geqslant j_0\) ，\(P(i,j)\) 都为真

基数

概念

等势：若存在从集合A到集合B的双射，则称A、B等势，记为 \(A\sim B\)

有穷与无穷：设 \(n={0,1,...n-1}\) ，若存在 \(n\in N\) 使 \(A\sim N\) ，称A为有穷集，否则为无穷集

有穷集的基数：即元素个数，表示为 \(\#(A),card(A),n(A)或|A|\) ，且若 \(A\sim n\)，则 \(\#(A)=n\)

无穷集的基数：\(\#(N)=\aleph_0\)

可数集：可数无穷集合+有穷集

可数无穷集合：任何与自然数集等势的集合

不可数集：无穷且不可数

基数的大小

\(A\sim B\) ，则基数相等，记为 \(\#(A)=\#(B)\)

存在从A到B的单射，则 \(\#(A)\leqslant\#(B)\)

若 \(\#(A)\leqslant\#(B)\) 且 \(\#(A)\ne\#(B)\) ，则 \(\#(A)<\#(B)\)

对每个集合A，\(\#A<\#\mathcal{P}(A)\) ，且 \(\#(R)=\#\mathcal{P}(N)=\aleph\) （二进制+特征函数证明）

定义 \(f:\mathcal{P}(N)\rightarrow[0,1]\) \[ f(A)= \begin{cases} 0,A=\emptyset\\ 1,A=N\\ \sum\limits_{i=0}^{\infty}\dfrac{\chi_A(i)}{2^{i+1}} \end{cases} \] 可证

图论

基础概念

定义

设V、E是有限集合且V非空

无向图：如果 \(\Psi:E\rightarrow\{\{v_1,v_2\}|v_1\in V且v_2\in V\}\) ，则称 \(G=<V,E,\Psi>\) 为无向图

有向图：\(\Psi:E\rightarrow V\times V\) ，则G为有向图

称V为结点集，E为边集，结点数目称阶

若有 \(\Psi(e)=\{v_1,v_2\}\) 或 \(\Psi(e)=<v_1,v_2>\) ，称e与 \(v_1\) 互相关联，\(v_1\) 与 \(v_2\) 临接，无向图中 \(v_1,v_2\) 既是起点又是终点，有向图中 \(v_1\) 为起点，\(v_2\) 为终点

若 \(e\) 关联的两个结点相同，则e为自圈（自环）。若 \(\Psi(e_1)=\Psi(e_2)\) ，称 \(e_1\) 与 \(e_2\) 平行（重边）

简单图：G无自圈，无平行边

无向图中与v关联的边的数目之和称度，记为 \(d_G(v)\)

有向图中以v为起点的边的数目为v的出度，记为 \(d_G^{+}(v)\)；以v为终点的边的数目为v的入度，记为 \(d_G^{-}(v)\) ；出度+入度=度，记为 \(d_G(v)\)

度为奇数称奇结点，偶数为偶结点，0为孤立点，1为端点。

定理

握手定理：设图G中有m条边，则 \(\sum_{v\in V}d_G(v)=2m\)

任何图中都有偶数个奇结点

特殊的图

零图：结点都是孤立点的图

平凡图：一阶零图

d度正则图：所有结点的度均为自然数d的无向图

完全无向图：n阶简单无向图G是n-1度正则图，则是完全无向图，记为 \(K_n\)

完全有向图：每个结点的出度与入度均为n-1的n阶简单有向图

零图也是正则图，正则图不一定是完全图

圈图：结点恰形成一圈的n阶简单无向图（\(n\geqslant3\)）

轮图：n-1个结点形成一个圈图，且第n个结点与圈图上的每个结点邻接的n阶简单无向图（\(n\geqslant3\)）

立方图：

图的运算

同构

设图 \(G=<V,E,\Psi>,G'=<V',E',\Psi'>\) ，如果存在双射 \(f:V\rightarrow V',g:E\rightarrow E'\) 使得任意 \(e\in E\) 及 \(v_1,v_2\in V\) 都有 \(\Psi'(g(e))=\{f(v_1),f(v_2)\}\) 或 \(<f(v_1),f(v_2)>\) ，则称G与G‘同构，记作 \(G\cong G'\)，称f与g为G与G’间的同构映射。

必要条件：结点个数、边数、结点度数相同

相互同构的图的补图仍相互同构

当不要求f、g是双射时，称同态

子图

设图 \(G=<V,E,\Psi>,G'=<V',E',\Psi'>\)

子图：\(V'\subseteq V,E'\subseteq E,\Psi\subseteq\Psi\) ，记为 \(G'\subseteq G\)

真子图：\(V'\subseteq V,E'\subset E,\Psi\subset\Psi\) ，记为 \(G'\subset G\)

生成子图：\(V'=V,E'\subseteq E,\Psi\subseteq\Psi\)

结点导出子图： \(V'\subseteq V,V'\ne\emptyset\) ，以V'为结点集合，以所有起点和终点均在V'中的边的全体为边集的G的子图，记为 \(G[V']\) 。当 \(V'\subset V\) 时，导出子图 \(G[V-V']\) 记为 \(G-V'\)

边导出子图：\(E'\subseteq E,E'\ne\emptyset,V'=\{v|v\in V且\exists e\in E'使v与e关联\}\) ，记为 \(G[E']\)

一些运算

可运算

设图 \(G=<V,E,\Psi>,G'=<V',E',\Psi'>\) 同为无向图或有向图

若对任意 \(e\in E\cap E'\) 均有 \(\Psi(e)=\Psi'(e)\) ，则称G和G‘可运算

若 \(V\cap V'=E\cap E'=\emptyset\) ，则称G和G’不相交

若 \(E\cap E'=\emptyset\) ，则称G和G’边不相交

交、并、环和

设图 \(G_1=<V_1,E_1,\Psi_1>,G_2=<V_2,E_2,\Psi_2>\) 可运算

交：\(G_1\cap G_2=<V_1\cap V_2,E_1\cap E_2,\Psi_1\cap\Psi_2>\) 。以 \(V_1\cap V_2\) 为节点集合、\(E_1\cap E_2\) 为边集合的 \(G_1,G_2\) 的公共子图。

并：\(G_1\cup G_2=<V_1\cup V_2,E_1\cup E_2,\Psi_1\cup\Psi_2>\) 。以 \(V_1\cup V_2\) 为节点集合、\(E_1\cup E_2\) 为边集合的 \(G_1,G_2\) 的公共母图。

环和：\(G_1\oplus G_2=<V_1\cup V_2,E_1\oplus E_2,\Psi_1\cup\Psi_{2E_1\oplus E_2}>\) 。以 \(V_1\cup V_2\) 为节点集合、\(E_1\oplus E_2\) 为边集合的 \(G_1\cup G_2\) 的子图。

边的增删

删边：设图 \(G=<V,E,\Psi>,E'\subseteq E\) ，记 \(<V,E-E',\Psi|_{(E-E')}>\) 为 \(G-E'\)

增边：设图 \(G=<V,E,\Psi>,G'=<V,E',\Psi'>\) 同为无向图或有向图，若两图边不想交，且G‘无孤立点，则记 \(G\cup G'\) 为 \(G+E'_{\Psi'}\)

补图

设n阶无向图 \(G=<V,E,\Psi>\) 是n阶完全无向图 \(K_n\) 的生成子图，则称 \(K_n-E\) 为G的补图，记为 \(\bar{G}\)

自补图：与其补图同构的简单无向图图

路径

基本概念

设 \(n\in N；v_0,v_1,...,v_n；e_1,e_2,...,e_n\) 是图G的结点、边，并且 \(v_{i-1}\) 和 \(v_i\) 分别是 \(e_i\) 的起点和终点，则称序列 \(v_0e_1v_1e_2...v_{n-1}e_nv_n\) 为图G中从 \(v_0\) 至 \(v_n\) 的路径（链）， \(n\) 称该路径的长度

\(v_0=v_n\) ，称该路径为闭的，否则是开的

边互不相同称简单路径（迹），结点互不相同称基本路径（路径）

图中存在从 \(v\) 至 \(v'\) 的路径，则存在从 \(v\) 至 \(v'\) 的基本路径

n阶图中的基本路径长度小于n

若图G中存在从 \(v_1\) 至 \(v_2\) 的路径，则称在G中从 \(v_1\) 可达 \(v_2\) ，用 \(R(v)\) 表示从v可达的全体结点的集合

若从 \(v_1\) 可达 \(v_2\) ，则称从 \(v_1\) 至 \(v_2\) 的路径中长度最短者为从 \(v_1\) 至 \(v_2\) 的测地线，该测地线的长度为从 \(v_1\) 至 \(v_2\) 的距离，记作 \(d(v_1,v_2)\) 。不可达则 \(d(v_1,v_2)=\infty\)

图 \(G<V,E,\Psi>\) 的直径定义为 \(\max_{v,v'\in V}d(v,v')\)

加权图：设图 \(G<V,E,\Psi>\) ，若 \(W:E\rightarrow R_{+}\) ，则称 \(<G,W>\) 为加权图。

边 \(e\in E\) ，称 \(W(e)\) 为e的加权长度，路径中所有边的加权长度之和为该路径的加权长度，类似有最短路径、加权距离

连通性

无向图

若图G的任意两个结点都相互可达，则称G是连通的

连通的充分条件：n阶简单无向图任意两个结点的度数之和大于等于n-1

极大子图：设G‘是图G的具有某性质P的子图，并且对于G的具有该性质的任意子图G’‘，只要有 \(G'\subseteq G''\) ，就有 \(G'=G''\) ，则称G'相对于该性质是G的极大子图

无向图G的极大连通子图称G的连通分支，简称分支

有向图

基础图：设有向图 \(G=<V,E,\Psi>\) ，定义 \(\Psi':E\rightarrow\{\{v_1,v_2\}|v_1\in V\land v_2\in V\}\) 使得对任意 \(e\in E\) 和 \(v_1,v_2\in V\) ，若 \(\Psi(e)=<v_1,v_2>\) ，则 \(\Psi'(e)=\{v_1,v_2\}\) 。称 \(G'=<V,E,\Psi'>\) 为有向图G的基础图

若有向图G中任意两个结点都相互可达，则称G是强连通的

若对于G任意两结点，必有一结点可达另一结点，则称G是单向连通的

若G的基础图是连通的，则称G是弱连通的

G的极大强/单向/弱连通子图称G的强/单向/弱分支

回路

设G’是有向图G的基础图，则G‘中的路径称G中的半路径

设 \(v_0e_1v_1...v_{m-1}e_mv_m\) 是G中的半路径，对每个 \(i(1\leqslant i\leqslant m)\) ，若 \(\Psi(e_i)=<v_{i-1},v_i>\) 则称 \(e_i\) 是该半路径中的正向边，若 \(\Psi(e_i)=<v_i,v_{i-1}>\) 则称 \(e_i\) 是该半路径中的反向边

回路：连通2度正则图

半回路：基础图是回路的有向图

有向回路：每个结点的出度和入度均为1的弱连通有向图

回路中边的数目称为回路的长度

若回路（有向回路，半回路）C是图G的子图，则称G有回路C

有向图G有有向回路的充分条件：图G有子图G’使得对G‘的任意结点v，都有 \(d_{G'}^{+}>0\) 或都有 \(d_{G'}^{+}<0\)

非循环图：没有回路的无向图和没有半回路的有向图

图G不是非循环图 \(\Leftrightarrow\) G有子图G‘使得对于G'的任意结点v，都有 \(d_{G'}(v)>1\)

割集与连通度

设无向图 \(G<V,E,\Psi>\) 为连通图，若有点集 \(V_1\subset V\) 使得

1. 图G删除了 \(V_1\) 的所有结点后，所得子图是不连通图
2. 图G删除了 \(V_1\) 的任意真子集后，所得子图仍是连通图

则称 \(V_1\) 是G的一个点割集 ，某点构成一个点割集则称该点为割点

\(k(G)=\min\{|V_1|V_1是G的点割集\}\) 是G的（点）连通度

设无向图 \(G<V,E,\Psi>\) 为连通图，若有边集 \(E_1\subset E\) 使得

1. 图G删除了 \(E_1\) 的所有边后，所得子图是不连通图
2. 图G删除了 \(E_1\) 的任意真子集后，所得子图仍是连通图

则称 \(E_1\) 是G的一个边割集 ，某边构成一个边割集则称该点为割边（桥）

\(\lambda(G)=\min\{|E_1|E_1是G的边割集\}\) 是G的边连通度

欧拉图

图G中包含其所有边的简单开路径成为G的欧拉路径，简单闭路径为欧拉闭路

欧拉图：每个结点都是偶节点的无向图

欧拉有向图：每个结点的出度与入度都相等的有向图

若G是连通无向图，则G是欧拉图当且仅当G有欧拉闭路；若G不连通，则G是欧拉图当且仅当G的每个分支都有欧拉闭路。

连通无向图有一条从 \(v_1\) 至 \(v_2\) 的欧拉路径当且仅当G恰有两个奇结点 \(v_1\) 和 \(v_2\)

若 \(G_1\) 和 \(G_2\) 是可运算欧拉图，则 \(G_1\oplus G_2\) 是欧拉图。但有向欧拉图的环和不一定是欧拉图

哈密顿图

图G中包含它的所有结点的基本路径成为G的哈密顿路径 ，若回路（有向回路）C是图G的生成子图，则称C为G的哈密顿回路

哈密顿图（哈密顿有向图）：有哈密顿回路的图

有哈密顿回路的必要条件：

1. 用黑白两种颜色给图中点着色，使相邻点颜色不同，若能染色且黑白结点个数不同，则无哈密顿回路。数目相差大于1，则无哈密顿路径
2. 设 \(G<V,E,\Psi>\) 是哈密顿图，则对V的任意非空真子集 \(v_1\) 有 \(W(G-V_1)\leqslant|V_1|\) 。其中 \(W(G-V_1)\) 为 \(G-V_1\) 的分支个数。即删掉的点的个数应当大于等于剩下部分的分支数。
3. 哈密顿图不存在悬挂边或孤立点

哈密顿图的充分条件：

1. 欧尔定理：设G是一个n阶简单图(n>1)，若G中任意一对顶点u和v，都满足 \(d_G(u)+d_G(v)\geqslant n-1\) ，则G中存在哈密顿路径
2. 设G是一个n阶简单图(n>2)，若G中任意一对顶点u和v，都满足 \(d_G(u)+d_G(v)\geqslant n\) ，则是哈密顿图

中国邮递员问题：给定一个连通图G，每边有非负权，求一条回路经过每条边至少一次且总权最小

图的表示

邻接矩阵

设n阶图G的结点集为 \(\{v_1,v_2,...,v_n\}\) ，定义G的邻接矩阵 \(X(G)\) 为 \(n\times n\) 矩阵 \((x_{ij})\) ，其中 \(x_{ij}\) 为分别以 \(v_i\) 和 \(v_j\) 为起点和终点的边的数目。

若两图同构，则边边互换、对应列再互换后，邻接矩阵相同

• 无向图的邻接矩阵对称
• 简单图元素均为0或1，对角线元素为0
• 零图即零矩阵
• 无向图有k个分支则可矩阵分块后对角线有k个1矩阵？
• 记图G的邻接矩阵X的m次幂后的元素为 \(x_{ij}^{(m)}\) ，则它表示 \(v_i\) 到 \(v_j\) 的长度为m的路径数

路径矩阵

设n阶图G的结点集为 \(\{v_1,v_2,...,v_n\}\) ，定义G的路径矩阵（可达性矩阵） \(X(G)\) 为 \(n\times n\) 矩阵 \(P=(p_{ij})\) ，其中 \(p_{ij}=\begin{cases}1\ \ 从v_i可达v_j\\0\ \ 从v_i不可达v_j\end{cases}\)

距离矩阵

设n阶图G的结点集为 \(\{v_1,v_2,...,v_n\}\) ，定义G的邻接矩阵为 \(n\times n\) 矩阵 \(D=(d_{ij})\) ，其中 \(d_{ij}\) 为分别从 \(v_i\) 至 \(v_j\) 的距离。

关联矩阵

设无自圈的n阶无向图G的结点集和边集分别为为 \(\{v_1,v_2,...,v_n\}\) 和 \(\{e_1,e_2,...,e_m\}\) ，定义G的关联矩阵 \(A(G)\) 为 \(n\times m\) 矩阵 \((a_{ij})\) ，其中 \(a_{ij}=\begin{cases}1,\ e_j与v_i关联\\0,\ e_j与v_i不关联\end{cases}\)

设无自圈的n阶有向图G的结点集和边集分别为为 \(\{v_1,v_2,...,v_n\}\) 和 \(\{e_1,e_2,...,e_m\}\) ，定义G的关联矩阵 \(A(G)\) 为 \(n\times m\) 矩阵 \((a_{ij})\) ，其中 \(a_{ij}=\begin{cases}1,\ v_i是e_j的起点\\-1,\ v_i是e_j的终点\\0,\ e_j与v_i不关联\end{cases}\)

树

无向树

树：非循环连通无向图

平凡树：只有一个顶点的平凡图

树T中，度数为1的结点称叶子结点，度数大于1的结点称分支结点

树定义的等价条件（设图 \(G=<V,E,\Psi>\) 是n阶无向图）：

1. G连通且非循环
2. G连通且 \(G-e\) 非连通
3. G连通且 \(|E|=n-1\)
4. G非循环且 \(|E|=n-1\)

森林：每个分支都是树的无向图

若森林F有n个结点，m条边，k个分支，则 \(m=n-k\)

若树T是无向图G的生成子图，则称T为G的生成树。若森林F是无向图G的生成子图，则称F为G的生成森林

每个无向图均有生成森林，若连通才有生成树

生成树构造方法：破圈法、

最小生成树：连通无向加权图的加权长度最小的生成树

设T是连通无向图G的生成树，称T的边为枝，G的不属于T的边称弦

对n阶无向图G，有m条边，任何生成树T，都有 \(n-1\) 条枝，\(m-n+1\) 条弦

若n阶无向图G有m条边和k个分支，则G的余圈秩 \(r=n-k\) ，圈秩 \(\mu=m-n+k\)

G的只包含一条弦的回路称基本回路

设T是连通无向图G的任意生成树，则

1. 基本回路的数目等于G的圈秩
2. 对G的任意回路C，总可以找到若干个基本回路 \(C_1,C_2,...C_k\) ，使C与 \(C_1\oplus C_2\oplus...\oplus C_k\) 的差别仅在于孤立点

有向树

有向树：一个结点的入度为0，其余结点的入度为1的弱连通有向图

有向树中入度为0的结点称为根，出度为0的结点称叶，出度大于0为分支结点。从根至任意结点的距离称为该结点的级，所有结点的级的最大值称有向树的高度

设 \(v_0\) 是有向图G的结点，则D是以 \(v_0\) 为根的有向树当且仅当从 \(v_0\) 到D的任意结点恰有一条路径

有向森林：每个弱分支都是有向树的有向图

若有向树的结点出度的最大值m，则称D为m元有向树。每个结点出度均为m或0，则称D为完全m有向树。

二叉树

二叉树：完全二元有向树

叶加权二叉树：设V是二叉树D的叶的集合， \(W:V\rightarrow R_{+}\) ，则称 \(<D,W>\)

对于D的任意v，称W(v)为v的权， \(\sum_{v\in V}(W(v)L(v))\) 称叶加权二叉树的叶加全路径长度，其中 L(v)为v的级

最优二叉树：设 \(<D,W>\) 是叶加权二叉树，如果对任一叶加权二叉树 \(<D',W’>\) ，只要对于任意正实数r，D和D‘中权等于r的叶的数目相同，就有 \(<D,W>\) 的叶加权路径长度不大于 \(<D',W’>\) 的叶加权路径长度，则称 \(<D,W>\) 为最优的

哈夫曼的最优二叉树的求解

有序树

有序树：每一级上的结点规定了次序的有向树

有序森林：有向森林中每个弱分支都规定了次序

定位有序树：为每个分支结点的儿子规定了位置的有序树

若用空字符串表示根，a0表示分支节点a的左儿子，a1表示a的右儿子，则每个结点都有了唯一的编码表示，并且不同结点的编码表示不同。

定位二元有序树的全体叶的编码表示集合称为它的前缀编码