图

图相关定义

• 图：点和边的集合$G=(V,E),E=\{\{u,v\}\mid u,v\in V\}$。点边可以都是空集。
• 子图：点和边都是原图的子集；$G^{\prime }=(V^{\prime },E^{\prime }),V^{\prime }\subset V,E^{\prime }\subset E$。
• 真子图：至少点和边中的一个是原图的真子集。
• 生成子图（Spanning Subgraph）：顶点和原图相同的子图；$G^{\prime }=(V,E^{\prime }),E^{\prime }\subset E$。
• 导出子图（Induced Subgraph）：对于导出子图中任意两点，若原图有边则导出子图也有边。
• 通路（walk）：可重复的顶点序列。序列中相邻顶点在原图有边。通路中经过的边数为路径的长度。单个顶点是长度为零的通路。
• 迹（trail）：边不重复的通路。
• 路径（path）：顶点不重复的通路。
• 回路（circuit）：长度至少为3的闭合通路。
• 环（cycle）：顶点不重复的回路。
• 图的连通性：任意两个顶点都连通（存在至少一条路径）。

图的常见种类：

• $n$个顶点的路径：$P_n$
• $n$个顶点的环：$C_n$
• $n$个顶点的完全图：$K_n$
• 分别有$s,t$个顶点的完全二分图：$K_{s,t}$
• 图的加法：$A+B=(A.V\cup B.V,A.E\cup B.E\cup \{(a,b)\mid a\in A.V,b\in B.V\})$
• 图的笛卡尔积：$A.V\times B.V$个顶点，其中顶点$(u,v)$和顶点$(x,y)$有边当且仅当$u=x\wedge (v,y)\in B.E$或者$v=y\wedge (u,x)\in A.E$。
• 正则图：$H_{r,n}$所有顶点的度都是$r$。当且仅当$r,n$都是偶数才存在正则图。

图的度

• 顶点的度：相连的边数。
• 图的最小度$\delta (G)$：顶点的最小度。
• 图的最大度$\Delta (G)$：顶点的最大度。
• 图论第一定理：所有顶点的度数之和等于两倍的边数。
• 如果$\mathrm{deg}u+\mathrm{deg}v\ge n-1$对所有非相邻的顶点都成立，那么图联通且图的直径小于等于2。

同构

• 同构：$G$和$H$存在顶点的一一映射$\varphi :V(G)\to V(H)$使得对于任意$(u,v)\in E(G)\to (\varphi (u),\varphi (v))\in E(H)$。那么$G$和$H$同构，$phi$称为$G$到$H$的同构映射。
• $G$和$H$同构当且仅当$\bar{G}$和$\bar{H}$同构。
• 同构是一种等价关系（自反，对称，传递）。

树

• 桥：对于$e$所在的连通分量$G$，$G-e$不连通则$e$是桥。
• 某条边是桥当且仅当它不在某个环上。
• 树：联通的无环图
• 由定义可推出树任意两点由唯一路径、$m=n-1$。
• 最小生成树。Kruskal、Prim。
• Kruskal正确性：若Kruskal产生的$T$不是最小生成树，按生成树中边的权值排序$e_1,e_2,\cdots ,e_i,\cdots ,e_{n-1}$，取最小不同边$e_i$最大的最小生成树$H$。$T$与$H$相比存在一个最小的与$H$不同的边$e_i$。$H+e_i$显然会产生环，取环上不在$T$中的边$e_0$，做$T^{\prime }=H+e_i-e_0$。显然$e_0\le e_i$。然而由Kruskal选边的方式，得$e_i\le e_0$，故$e_i=e_0$。又由$H$是最小生成树，$w(H)\le w(T^{\prime })$。而$w(T^{\prime })=w(H)+w(e_i)-w(e_0)=w(H)$。故$T^{\prime }$也是最小生成树，且与$H$相比$T^{\prime }$有更大的相同边$e_i$。与假设矛盾。
• Prim正确性：数学归纳法。若$T_0$是最小生成树，对$X_0\cup y$的图，则新边显然一端为$y$，一端为$x\in X_0$。可用替换法证明选择权值最小的边一定是最小生成树。
• 判断最小生成树的唯一性？
• 矩阵树定理

连通性

• 割点：删除后某个连通分量不再连通。

• 块：一个极大的不可分（无割点）的子图称为块。

• Theorem 5.1: 如果$v$是一个桥的顶点，那么$v$是一个割点当且仅当$\mathrm{deg}v\ge 2$。

• Theorem 5.3: 如果$v$是一个割点，且$u,w$是$G-v$的两个不同分量中的点，则任意$u⇝w$的路径都含$v$。

• Theorem 5.5: 如果$G$是一个非平凡的连通图，$u$是图中的一个顶点。如果$v$是一个离$u$最远的顶点，那么$v$不是一个割点。

• Theorem 5.7: 一个至少有三个点图是不可分图（没有割点）当且仅当任意两个顶点都在同一个环内。

• Theorem 5.8: 定义一个在非平凡连通图上的关系$R$，其中$eRf$当且仅当$e=f$或$e$和$f$在同一个环内。那么$R$是一个等价关系（自反、对称、传递）。

• Corollary 5.9: 任意两个不同的块$B_1,B_2$有以下关系

  1. 两个块没有相同的边
  2. 两个块最多只有一个公共点
  3. 如果两个块有一个公共点，则该点是原图的一个割点。

• 最小点割集：最小的点集$U$使得$G-U$不连通。

• 点连通度：最小点割集的大小称为点连通度$\kappa (G)$。

• k-连通图：$\kappa (G)\ge k$。注意大于等于。也即删掉任意$k$个点后图还连通。

• 最小边割集：最小的边集$X$使得$G-X$不连通。

• 边连通度：最小边割集的大小称为边连通度$\lambda (G)$。

• k-边连通图：$\lambda (G)\ge k$。注意大于等于。也即删掉任意$k$条边后图还连通。

• Theorem 5.11: 任意图$G$，$\kappa (G)\le \lambda (G)\le \delta (G)$。

• Theorem 5.16: 门格尔（Menger）定理：$u,v$是两个互不相邻的顶点，则最小的$u-v$分割集的大小等于最大的内部（除端点外）互不相交的$u-v$路径数。 证明：对边数归纳。

  • 若存在与$u,v$均直接相邻的点，则可归纳为$G-x$。
  • 若存在一个与$u$不相邻的点和一个与$v$不相邻的点，则对于最小的$u-v$分割集$W$，构造$G_u^{\prime }=u⇝W\to v^{\prime }$和$G_v^{\prime }=u^{\prime }\to W⇝v$，两个图都分别满足归纳条件，最大的内部不相交的路径数为$|W|$。
  • 剩下的情况为所有的$W$中的所有点要么同时与$u$相邻，要么同时与$v$相邻。不妨设$u-v$最短路径上的边$xy$中$x$与$u$相邻。显然有$G-xy$最小分割集至少为$k-1$。如果$G-xy$的最小分割集为$k-1$，不妨设其为$Z$，那么$Z\cup \{x\}$是原图的一个最小分割集，不妨设其同时与$u$相邻。那么$Z\cup \{y\}$也应该同时与$u$相邻，这说明存在边$uy$且显然$u\to y⇝v$比$u\to x\to y⇝v$更短，与假设矛盾。因此$G-xy$最小分割集应该为$k$。由归纳假设，$G-xy$最多有$k$条互不相交的路径。因此$G$也有$k$条互不相交的路径。

  使用门格尔定理时注意互不相邻。

• Theorem 5.17: Whitney定理：任意非平凡图是k-连通的（$k\ge 2$）当且仅当任意两个点都存在至少$k$条互不相同的路径。

• 点的离心距离：该点和所有顶点的最大距离。

• 图的半径rad：所有顶点中最小的离心距离。

• 图的直径diam：所有顶点中最大的离心距离。

• 中心点：离心距离等于半径的点（可能有多个）。

• 图的中心：所有中心节点的导出子图。

• 外围点：离心距离等于直径的点（可能有多个）。

• 图的外围：所有外围点的导出子图。

• 离心点：对于某个顶点$u$，$v$是所有顶点中距离$u$最远的顶点，则$v$是离心点。离心点未必是外围点。

• 图的离心点：所有的离心点。

• 边界点：对于某个顶点$u$，$v$比所有其邻居都远于$u$，则$v$是边界点。

• 中间节点：对于

图的旅行

欧拉图

每条边经过且仅经过一次。

$G$是欧拉图（存在欧拉回路）当且仅当$G$中每一个顶点的度数均为偶数。

$G$是半欧拉图（存在欧拉路径）当且仅当$G$中恰有两个奇度点。

哈密顿图

除了首尾顶点相同外，每个点经过且仅经过一次。

性质：

（必要条件）$G$是哈密顿图，则$G$中的任意非空点集$S$都满足$k(G-S)\le |S|$（$k(G)$为$G$中极大连通分量的个数）。也即，在哈密顿回路上删除$k$个顶点，最多形成$k$个连通分支。

（充分条件）若任意两个顶点$u,v$满足$\mathrm{deg}u+\mathrm{deg}v\ge n$，则$G$是哈密顿图。

闭包：对于任意两个顶点，如果其度数之和大于$n$，就连接一条边。不断重复直至边不再增加。

图是哈密顿图当且仅当它的闭包是哈密顿图。

匹配

边独立集${\alpha }^{\prime }(G)$：集合中的边不存在相同顶点。

边覆盖集${\beta }^{\prime }(G)$：集合中的边覆盖所有顶点。

Theorem 8.7: 若图$G$中不包含孤立点，则${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n$。

点独立集$\alpha (G)$：集合中的点不相邻。

点覆盖集$\beta (G)$：集合中的点覆盖所有边。

Theorem 8.8: 若图$G$中不包含孤立点，则$\alpha (G)+\beta (G)=n$。

霍尔婚姻定理：对任意二分图，存在完美匹配当且仅当对任意$X$，$|X|\le |R(X)|$。其中$R(X)$为与$X$中点有关系的点的集合。

二分图最大匹配数为$|A|-\underset{X\subset A}{\max }(|X|-|R(X)|)$。

k-因子分解：k-正则生成子图（每个点度均为$k$）。

奇分支：阶（点数）为奇数的连通分量。$k_o$为奇极大连通分量的个数。

Theorem 8.10: 图有一个1-因子分解的的充要条件是$\forall S\subset V(G)$，都有$k_o(G-S)\le |S|$。

平面图和图着色

欧拉定理：对于一个连通的平面图，有$n$个顶点$m$条边和$r$个区域，$n-m+r=2$。

若$G$是连通平面图，则$m\le 3n-6$。证明：面的最小边数是3，一条边分割两个平面。故$3r\le 2m$。

根据上述定理，$K_5$不是平面图。对于二分图，区域边数至少是4。重新推导定理，$K_{3,3}$也不是平面图。

$G$是平面图当且仅当$G$中不含$K_5$或$K_{3,3}$同胚的子图，也不含可以收缩到含$K_5$或$K_{3,3}$的子图。

k-着色图：用最多$k$个颜色给每个顶点指定颜色，使得任意相邻顶点的颜色均互不相同。$k$-着色图同时也是(k+1)-着色图等。

着色数$\chi (G)$：最小的$k$。

$\omega (G)$：图$G$的最大完全子图的顶点数。

Theorem 10.5: $\chi (G)\ge \frac{n}{\alpha (G)}$。

Theorem 10.7: $\chi (G)\le 1+\Delta (G)$。

Theorem 10.8: $\chi (G)\le \Delta (G)$。如果$G$不存在任何奇环或是完全图。