0513上午

1、子图

导出子图（Induced subgraph）

• $G=(V,E)$，$G$ 在 $v_1$ 上的导出子图 $G_1=(V_1,E_1),E_1=\{e\in E\mid u,v\in v_1\}$
• 相当于在图中去掉一些点。$n$ 阶导出子图有 $2^n$ 个。

生成子图（Spanning subgraph）

• $G=(V,E)$，$G_1$ 为 $G$ 生成子图是指 $V(G_1)=V(G),E(G_1)\subseteq E(G)$
• 相当于在图中去掉一些边。生成子图有 $2^{|E|}$ 个。

$\color{red}{\texttt{Note: }}$

• 导出子图和生成子图都不限定是否为简单图。
• 既是导出子图又是生成子图为原图。

2、Mantel 定理、托兰定理

Mantel's thm

• 如果图 $G=(V,E)$ 中没有三角形，则 $|E|\leq [\frac{n^2}4]$ 。
• 等号成立条件 $\Longleftrightarrow$ $G=K_{\lfloor \frac n2\rfloor\lceil \frac n2\rceil}$。

Turan's thm

• 若 $G$ 无 $K_k$ 子图，$G$ 的边数取最大值的图唯一，为$G=K_{x_1,x_2,...,x_{k-1}}$，其中$\sum_{i=1}^{k-1} x_i=n$，同时 $|x_i-x_j|\leq 1$。
• 形式化的，$G=K_{[\frac n{k-1}][\frac {n+1}{k-1}]...[\frac{n+k-2}{k-1}]}$，$\sum_{i=0}^{r-1} [\frac{x+i}r]=[x]$。

3、二分图

二分图（Bipartite Graph） 定义

• $G=(V,E),V=A\cup B$。
• $\forall u,v\in A,(u,v)\notin E$ 且 $\forall u,v\in B,(u,v)\notin E$。
• 则称 $G$ 为二分图。

二分图判定定理

• 一个图 $G$ 是二分图，当且仅当图 $G$ 无奇环。
• 命题①：$G$ 是二分图
• 命题②：$G$ 无奇环
• 命题③：$G$ 无奇数长的回路
• 通过 ①$\Rightarrow$②$\Rightarrow$③$\Rightarrow$① 可证得三个命题相互等价，在此略去。

4、完美匹配、Hall定理、Tutte定理

匹配（Matching）

• $G=(V,E)$，$E$ 的子集 $E_1$ 的顶点两两不重合。则 $E_1$ 为 $G$ 的匹配。

完美匹配（Perfect Matching,PM）

• 匹配 $E_1$ 的顶点覆盖 $V$，$G$有PM $\Rightarrow$ $|G|\equiv 0(\operatorname{mod} 2)$

二分图完美匹配

• $G$ 为二分图 $(x,y,E)$。
• $G$ 有 PM ，则 $|X|=|Y|$ 且 $X$ 到 $Y$ 有双射。
• $f$ 称为由 PM $E$ 诱导（induce） 的双射。
• 满足 $f(x_i)=y_i,(x_i,y_i)\in E(E_1=\{(x_i,y_i)\mid 1\leq i\leq |X|\})$。

Hall 定理

• 二分图有完美匹配的充要条件为：$\forall S\subseteq X，|N(S)|\geq |S|$（有匹配覆盖 $X$ 的所有顶点），$\forall S\subseteq Y,|N(S)|\geq |S|$（有匹配覆盖 $Y$ 的所有顶点）。

Tutte 定理

• 对于图 $G$ ，$G$ 有PM的充要条件为 $\forall S\subseteq V$ ，$G$ 在 $V-S$ 上的导出子图 $M$ 的有奇数个顶点的连通分支的个数 $\leq |S|$。

5、正则图的定义

正则图

• 一个图为 $k-\texttt{正则}$ 的，定义为 $\forall v\in V,d(v)=K$ 。

0513下午

1、欧拉图的定义

欧拉图 Euler Graph

• 存在一条回路，经过图 $G$ 的全部的边恰好一次。（欧拉回路）

2、一笔画的算法，欧拉图的充要条件

• 若一个图 $G$ 存在 $0$ 个或 $2$ 个奇点，则这个图可以一笔画。
• 欧拉图充要条件：$\forall v\in V,2\mid d(v)$。

3、哈密顿（Hamilton）图、哈密顿链的定义

哈密顿图

• 一个图 $G$ 为哈密顿图 $\Longleftrightarrow$ 存在一条回路包含图 $G$ 的全部顶点，这个回路被称为 Hamilton 圈。

哈密顿链

• 若一条链 $P$ 遍历了图 $G$ 的全部顶点，则称 $P$ 为哈密顿链。

4、Hamilton 性质、必要条件

必要条件

• 设 $S$ 为 $G$ 的一个顶点子集，若 $G$ 在 $V-S$ 上导出子图的连通分量个数大于 $|S|$ $(|S|+1)$ ，则 $G$ 无哈密顿图（链）。
• 二分图有哈密顿圈（链），必要条件为 $||X|-|Y||\leqslant 0$（$1$）。

5、哈密顿图（链）的一些充分条件：Ore条件、Dirac条件

Ore 条件

• 若 $G$ 为哈密顿图，设 $|G|=n$，则 $\forall v,d(v)\geqslant \frac{n}{2}$。

Dirac 条件

• 若 $G$ 为哈密顿图，设 $|G|=n$，则 $\forall u,v$，若 $(u,v)\notin E$ ，$d(u)+d(v)\geqslant n$。
• 若 $G$ 存在哈密顿链，则 $d(u)+d(v)\geqslant n-1$。

6、图的笛卡尔积的定义

• 集合的笛卡尔积： $A\times B=\{(a,b)\mid a\in A,b\in B\}$。
• 图的笛卡尔积： $G=(V,E)\space ,\space H=(U,F)$。
• 定义 $G\times H=(V\times U,E')$。$E'=\{(v_1,u)(v_2,u)\mid v_1,v_2\in E,u\in U\}\cup\{(v,u_1)(v,u_2)\mid u_1,u_2\in F,v\in V\}$。

0514上午

1、图的顶点染色

染色的定义

• 一般染色：$f:x\rightarrow \{1,2,3,\cdots,k\}$。其中，$1\cdots k$ 是颜色集合。（高联一般不考虑无穷染色）
• 图的顶点染色：$G=(V,E)$
  • 无限制的染色：$f:V\rightarrow \{1,2,3,\cdots,k\}$
  • 一般意义上的图染色：$f:V\rightarrow \{1,2,3,\cdots,k\}$，且对于 $\forall(a,b)\in E,a\neq b,f(a)\neq f(b)$

染色数的定义

• 最小使得染色映射 $f$ 存在的 $k$ 称为图 $G$ 的色数，记为 $\chi(G)$。（chromatic number）

$\color{red}{\texttt{Note: }}$

• $n$ 阶图一定可以用 $n$ 种颜色染色。随机图算色数较为困难。
• 答题方法：考试时将颜色标在图上，再证明不存在更少的色数。
• 常用结论：
• $\chi(K_n)=n$（ $n$ 阶完全图 ）
• $\chi (C_n)=\begin{cases} 2, &2\mid n \\ 3, &2\nmid n \end{cases}$（ $n$ 个点的环）
• $\chi (T)=2\ (n\geqslant 2)$ （ $n(n\geqslant 2)$个点的树）

2、色数的简单估计

估计色数上下界

下界

• 团数（clique number）：设团数 $\omega(G)$ 为 $G$ 中最大完全子图的阶数。

• 明显的下界：$\chi (G)\geqslant \omega(G)$。

• 最大独立集：一个图的最大独立集 $S\subseteq V$，是指点数最大的两两不连的顶点集合。

• 独立数（independence number）：设独立数 $\alpha(G)$ 为图 $G$ 的最大独立集顶点数。
• 另一个下界：$\chi(G)\geqslant \frac{n}{\alpha(G)}$。

上界

• 上界：$\chi(G)\leqslant 1+\Delta(G)$。

3、Brooks 定理简介

Brook's Thm

• 设 $G$ 为连通图且不是完全图或奇圈。则必有 $\chi(G)\leqslant \Delta(G)$。
• 前提的等价表述：$\Delta\geqslant 3$，且$\exists\ u,v\in V,(u,v)\notin E$。

4、色多项式（chromatic polynomial）

• 我们考虑一张一般的图 $G$ ，将它 $k$ 染色的方案数。
• 我们在图 $G$ 上任取一条边 $e=(u,v)$，把 $e$ 去掉。
• 然后我们对 $G\setminus e$（从 $G$ 中删去边 $e$）的任一种染色 $f$。
  1. 对于 $f(u)\neq f(v)$ 的 $f$，则 $f$ 也是 $G$ 的染色。
  2. 对于 $f(u)=f(v)$ 的 $f$，则$f$ 是图 $G\cdot e$ 的染色（把 $G$ 中 $e$ 的端点合并，去掉重边）
• 反之，$G$ 的染色均是 $G\setminus e$ 的使 $f(u)\neq f(v)$ 的染色，$G\cdot e$ 的染色均是 $G\setminus e$ 的使 $f(u)=f(v)$ 的染色。

• 于是，我们定义 $F_G(k)$ 为 $k$ 种颜色对 $G$ 染色的方案数。
• 此时，$F_{G\setminus e}(k)=F_G(k)+F_{G\cdot e}(k)$，即 $F_G(k)=F_{G\setminus E}-F_{G\cdot E}(k)$。
• 对边数归纳可证对于任意的 $G$，$F_G$ 为关于 $k$ 的 $n$ 次多项式。$F_\texttt{n个点，没边}=k^n$ 。
• $F$ 首项系数$=1$，次高项系数$=-|E|$。
• 当 $k<\chi(G)$ 时，$F_G(k)=0$，$(x-k)|F_G(k)$。

5、平面图的定义

• 可以画在平面上，使边与边只在顶点处相交（边可以为曲线或折线）。

6、库拉托夫斯基定理

Kuratowski's Thm

• 一个图是平面图当且仅当 $G$ 无同胚与 $K_5$ 或 $K_{3,3}$ 的子图。
• 同胚：如果两个图 $G_1$ 和 $G_2$ 同构，或经过反复插入（将 $e=(u,v)$ 拆成 $e_1=(u,w),e_2=(w,v)$）或消去 $2$ 度顶点后同构，则称 $G_1$ 与 $G_2$ 同胚。

7、欧拉公式（多面体/平面图）

• 连通图 $G$ 为平面图，$|G|=n,||G||=e,$面数$=f$，则 $n-e+f=2$。

0514下午

1、Ramsey 问题

前置知识

• 图 $G=(V,E)$ ，图的一个边染色指映射 $f:E\rightarrow \{1,2,3,\cdots\}$。
• 对 $\forall e_i,e_j$ ，若 $e_i\cap e_j\neq \varnothing$，则 $f(e_i)\neq f(e_j)$。
• 所需最小色数 $k$ 称为图 $G$ 的边染色数 $\chi'(G)$，显然 $\chi'(G)\geqslant \Delta(G)$。

Viking Thm

• $\chi'(G)\leqslant 1+\Delta(G)$。

Ramsey's Thm

• $\forall s,t\in \mathbb{N}^+$，对 $K_n$ 的边 $2$ 染色，当 $n$ 足够大时，存在红色 $K_s$ 或 蓝色 $K_t$ 子图。
• 最小满足上述条件的 $n$ 称为 Ramsey 数 $r(s,t)$。

$\color{red}{\texttt{Note: }}$

• 常用结论：
  1. $r(s,t)=r(t,s)$，显然。
  2. $\forall x\quad r(x,1)=r(1,x)=1$，证明显然。
  3. $\forall x\quad r(x,2)=r(2,x)=x$，证明显然。
  4. $r(s,t)\leqslant r(s,t-1)+r(s-1,t)$，证明可以对 $s+t$ 归纳，在此略去。
  5. ④的推论：$r(s,t)\leqslant \binom{s+t-2}{s-1}$，显然。

2、简单的 Ramsey 数

$r(3,3)=6$

1. 根据结论⑤，有$r(3,3)\leqslant \binom{4}{2}=6$
2. 证明 $5$ 不可以，请读者自行证明。

$r(3,4)=9$

• 请读者自行证明。

$r(3,5)=14$

1. $r(3,5)\leqslant r(3,4)+r(2,5)=9+5=14$
2. 证明 $13$ 不可以，给出简要思路：循环构造，将 $i-j\equiv \pm 1 \operatorname{or} \pm 5$ 连红边，否则连蓝边。

3、范德瓦尔登定理

Vander Waerden's Thm

• $\forall m\in \mathbb{N}^+,\exists N$，使集合 $\{1,2,3,4,\cdots,N\}$ 的任意 $2$ 染色必定存在同色，长度为 $m$ 的等差数列。
• 上面的表述等价于 $\exists N_1,\{1,\cdots ,N_1\}$ $2$ 染色存在长为 $N$ 的同色等差数列。

4、同色角，异色角方法

• 我们将角的两条边颜色相同的角称为 同色角 ，将角的两条边颜色不同的角称为 异色角 。

• 显然，有同色 $\Delta$ 数 $+$ 异色 $\Delta$ 数 $=\binom n3$。

• 我们考虑顶点在 $v$ 处的 $\Delta$ 。同色角数$=\binom{d_\texttt{红}(v)}2+\binom{d_\texttt{蓝}(v)}2$。异色角数$=d_\texttt{红}(v)\times d_\texttt{蓝}(v)$。所有角数$=\binom{d_\texttt{红}(v)+ d_\texttt{蓝}(v)}2$。

• 整个图 $\sum_{v\in V} \binom{d_\texttt{红}(v)}2+\sum_{v\in V} \binom{d_\texttt{蓝}(v)}2+\sum_{v\in V}d_\texttt{红}(v)\times d_\texttt{蓝}(v)$。

• 即我们可以将 同/异色$\Delta$ 与 顶点的红蓝度 相互转化。