本章主要介绍一些基础概念
定义
图与简单图
定义 - 1-1 一个简单图 (simple graph) \(G=\lang V(G),E(G)\rang\) 由一个非空有限集合 \(V(G)\) 和一个有限集合 \(E(G)\) 构成，其中 \(V(G)\) 称为简单图 \(G\) 的顶点集 (vertex-set), 其中的元素被称为顶点 (vertex), \(E(G)\subseteq V^2(G)\) 称为简单图 \(G\) 的边集 (edge-set), 其中的元素被称为边 (edge), 边是无序的二元元素对
边 \(e=\{u,v\}\) 可简写为 \(uv\), 称 \(e\) 连接 (join) 顶点 \(u,v\), 顶点 \(u,v\) 为 \(e\) 的端点 (ends, endpoints)
类似的，我们有
定义 - 1-2 一个一般图 (general graph) (可简称为图 (graph)) \(G=\lang V(G),E(G)\rang\) 由一个非空有限集合 \(V(G)\) 和一个有限集合族 \(E(G)\) 构成，其中 \(V(G)\) 称为图 \(G\) 的顶点集 (vertex-set), 其中的元素被称为顶点 (vertex), \(E(G)\subseteq V^2(G)\) 称为图 \(G\) 的边集 (edge-family), 其中的元素被称为边 (edge), 边是无序的二元元素对
在图 \(G\) 中，若一条边的两个端点相同，则称该边为自环 (loops), 若有多条边的端点分别相同，则称这些边为重边 (multiple edges)
同构
定义 - 1-3 两个图 \(G_1,G_2\) 同构 (isomorphism) 当且仅当
如
和
是同构的
连通
定义 - 1-4 若两图 \(G_1,G_2\) 的点集不交，则称 \(G_1\cup G_2:=\lang V(G_1)\cup V(G_2), E(G_1)\cup E(G_2)\rang\) 为两图的并 (union)
定义 - 1-5 称图 \(G\) 是连通的 (connected), 若 \(G\) 不能表示称两个图的并，否则称其为不连通的 (disconnected), 若 \(G\) 可以表示成若干个连通图的并，则称这些连通图为 \(G\) 的部件 (components)
相邻，度
定义 - 1-6 若图 \(G\) 有边 \(uv\) 此时称，顶点 \(u,v\) 相邻 (adjacent), 顶点 \(u,v\) 均与 \(e\) 相关联 (incident)
与点 \(v\) 相邻的所有点构成点 \(v\) 的邻域 (neighborhood), 记作 \(N(v)\)
点集 \(U\) 的邻域为与 \(U\) 中至少一个点相邻的点构成的集合，记作 \(N(U)\)
定义 - 1-7 顶点 \(v\) 的度 (degree) 为与其相关联的边的条数和自环个数的二倍的和，记为 \(\deg(v)\)
度为 \(0\) 的点称为孤立点 (isolated vertex)
度为 \(1\) 的点称为悬挂点 (pendant vertex, end-vertex)
我们不难证明如下定理:
定理 - 1-1 (握手引理) 任意图的顶点度数和均为偶数
证明
点的度数和为边条数的二倍
由此立得
另外，由抽屉原理，我们可知有至少 \(2\) 个顶点的简单图必有度相等的顶点
子图
定义 - 1-8 若 \(V(G')\subseteq V(G)\) 且 \(E(G')\subset E(G)\), 则称 \(G'\) 为 \(G\) 的子图 (subgraph)
对于图 \(G\), 取其中的顶点 \(v\) 和边 \(e\), 称
- \(G-e\) 为 \(G\) 删去 \(e\) 后的子图
- \(G-v\) 为 \(G\) 删去 \(v\) 和与 \(v\) 关联的边后的子图
- \(G\setminus e\) 为将 \(e\) 的两个端点合并后的图
简单图的补图
定义 - 1-9 简单图 \(G\) 的补图 (complement) \(\bar G\) 满足
- \(V(\bar G)=V(G)\)
- \(e\in E(\bar G)\iff e\notin E(G)\)
若一个图和自身的补图同构，则称其为自补图 (self-complementary)
度矩阵，邻接矩阵与关联矩阵
定义 - 1-10 设图 \(G\) 的顶点标号为 \(1..n\), 边标号为 \(1..m\), 称
- 度矩阵 (degree matrix) \(D\) 为 \(n\times n\) 阶对角矩阵，其中 \(d_{ii}=\deg(i)\)
- 邻接矩阵 (adjacency matrix) \(A\) 为 \(n\times n\) 阶矩阵，其中 \(a_{ij}\) 为连接点 \(i,j\) 的边的总数
- 关联矩阵 (incidence matrix) \(M\) 为 \(n\times m\) 阶矩阵，其中若点 \(i\) 与边 \(j\) 相关联，则 \(m_{ij}=1\), 否则 \(m_{ij}=0\)
度矩阵，邻接矩阵与关联矩阵有很多性质，如
有向图
定义 - 1-11 若图的边是有序的二元元素对，则此时的图即为有向图 (digraph), 此时的边又称为弧 (arc)
无向图的若干概念均可类推到有向图上，比如:
定义 - 1-12 有向图的度分为入度 (inner degree) 和出度 (outer degree), 分别表示从该点出发的边的条数和以该点结束的边的条数，分别记作 \(\operatorname{indeg}\), \(\operatorname{outdeg}\) 或 \(\deg_-\), \(\deg_+\)
类似地，有向图的握手引理如下:
下面的两个概念仅适用于有向图
定义 - 1-13 去掉有向图边的方向后得到的无向图称为底图 (undelying graph)
定义 - 1-14 将有向图边的方向反向后得到的有向图称为反图 (converse, transpose graph)
线图
定义 - 1-15 简单图 \(G\) 的线图 (line graph) \(L(G)\) 是满足如下条件的图:
- \(L(G)\) 的点集和 \(G\) 的边集同构
- \(L(G)\) 中两点相邻当且仅当 \(G\) 中对应的边有公共端点
无限图
定义 - 1-16 无限图 (infinite graph) 是点集为无限集合或边集为无限集合的图
若无限图的点集和边集均可数，则称其为可数无限图 (countable graph)
定义 - 1-17 若无限图所有点的度数均有限，则称该图为局部有限 (locally finite) 的
若无限图所有点的度数均可数，则称该图为局部可数 (locally countable) 的
下面给出一个基本定理
定理 - 1-4 局部可数的连通无限图是可数无限图
证明
在局部可数的连通无限图 \(G\) 中任取一点 \(v\), 设 \(N_0=\{v\}, N_1=N(N_0)\), \(N_2=N(N_1),...\), 则 \(N_1,N_2,...\) 均可数，且由连通性可得
\[ V(G)=\bigcup_{i=0}^{\infty}N_i \]
因此 \(G\) 是可数无限图
例子
零图
完全图
定义 - 1-19 完全图 (complete graph) \(K_n\)
任意两点均相邻的简单图
完全图和零图互为补图
竞赛图
命题 - 1-2 竞赛图的入度平方和等于出度平方和
Hint
考虑 \(\sum_v\operatorname{indeg}^2(v)-\sum_v\operatorname{outdeg}^2(v)\)
命题 - 1-3 \(n\) 个顶点的竞赛图的邻接矩阵的秩为 \(n\) 或 \(n-1\), 且若秩为 \(n\), 则其为 Hamilton 图，否则为半 Hamilton 图
二分图
定义 - 1-21 二分图 (bipartitle graph)
\(G=\lang A,B,E(G)\rang\) 满足
- \(V(G)=A\cup B\)
- \(A\cap B=\varnothing\)
- \(E(G)\cap (A^2\cup B^2)=\varnothing\)
类似地，可以定义
- 完全二分图 \(K_{s,t}\)
- \(k\) 分图
- 完全 \(k\) 分图
圈图
定义 - 1-22 圈图 (cycle graph) \(C_n\)
任意点的度均为 \(2\) 的连通图
链图
定义 - 1-23 链图 (chain graph, path graph)
\(P_n=C_n-e\), \(\exists e\in E(C_n)\)
星图
定义 - 1-24 星图 (star graph) \(S_n\)
\(\exists_1 v\in V(S_n)\) 使得
- \(\deg(v)=n-1\)
- \(\forall v'\in V(S_n)\setminus\{v\},\deg(v')=1\)
轮图
定义 - 1-25 轮图 (wheel graph) \(W_n\)
\(\exists_1 v\in V(W_n)\) 使得
- \(\deg(v)=n-1\)
- \(W_n-v=C_{n-1}\)
正则图
定义 - 1-26 \(k\)- 正则图 (\(k\)-regular graph)
所有顶点的度均为 \(k\) 的图称为 \(k\)- 正则图
显然奇正则图的顶点数为偶数
\(k\)- 正则图的线图是 \(2k-2\)- 正则图
立方图
Petersen 图
From https://www.integral-domain.org/lwilliams/Resources/tikzsnippets.php, 给出的这三个图同构
经常用于构造反例
Platonic 图
又叫正多面体图，一共有五种
From https://www.integral-domain.org/lwilliams/Resources/tikzsnippets.php
超立方体图
定义 - 1-28 超立方体图 (\(k\)-cube graph) \(Q_n\)
- \(V(Q_n)=\{\overline{a_1a_2...a_n}:a_i\in\{0,1\},\forall i\in 1..n\}\)
- \(E(Q_n)=\{\{\overline{a_1a_2...a_n},\overline{b_1b_2...b_n}\}:\exists_1 i\in 1..n, a_x=b_x\iff x=i \}\)
不难发现
- \(Q_n\) 可以和 \(n\) 维超立方体一一对应
- \(Q_n\) 是二分图
\(Q_4\), From https://www.integral-domain.org/lwilliams/Resources/tikzsnippets.php
Ramsey 定理
定理 - 1-6 (Ramsey 定理) 对任意 \(6\) 顶点的图 \(G\), \(C_3\) 要么是 \(G\) 的子图，要么是 \(\bar G\) 的子图
证明
考虑对 \(K_6\) 的边染色，将 \(G\) 中的所有边在 \(K_6\) 中的对应均染为红色，其余染为蓝色，接下来只需证明无论如何染色，最终都会染出同色三角形即可
由抽屉原理，对于任意一个点，与其关联的 \(5\) 条边中要么有 \(3\) 条是红色，要么有 \(3\) 条是蓝色，那么对于这 \(3\) 条相同颜色的边来说，不难发现其另一边的端点两两之间的边无论如何染色，最终都会出现同色三角形
定义 - 1-29 Ramsey 数 \(R(k,m)\) 为最小的正整数 \(n\) 满足：对任意的 \(n\) 顶点的简单图 \(G\), 要么 \(K_k\) 是 \(G\) 的子图，要么 \(K_m\) 是 \(\bar G\) 的子图
我们可以得到两条性质:
- \(R(k,m)=R(m,k)\)
- 若 \(k,m\geq 2\), 则 \(R(k,m)\leq R(k-1,m)+R(k,m-1)\)
根据 定理 - 1-6, 我们知道 \(R(3,3)\leq 6\)
不难验证 \(R(3,3)=6\)
目前已知的 Ramsey 数
From https://mathworld.wolfram.com/RamseyNumber.html
| 3 | 3 | 6 | Greenwood and Gleason 1955 |
| 3 | 4 | 9 | Greenwood and Gleason 1955 |
| 3 | 5 | 14 | Greenwood and Gleason 1955 |
| 3 | 6 | 18 | Graver and Yackel 1968 |
| 3 | 7 | 23 | Kalbfleisch 1966 |
| 3 | 8 | 28 | McKay and Min 1992 |
| 3 | 9 | 36 | Grinstead and Roberts 1982 |
| 4 | 4 | 18 | Greenwood and Gleason 1955 |
| 4 | 5 | 25 | McKay and Radziszowski 1995 |
