本章主要进一步介绍连通性，路与圈相关的内容
路径，迹，简单路径，圈
定义 - 2-1
路径 (walk): 若序列 \(v_0\to v_1\to...\to v_n\) 中，\(\forall i=0..n-1\), \(v_i\) 与 \(v_{i+1}\) 相邻，则称该序列为一条路径
称 \(v_0\) 为起点 (initial vertex), \(v_n\) 为终点 (final vertex), \(n\) 为路径的长度 (length)
迹 (trail): 若一条路径经过的边没有重复，则称其为迹
简单路径 (path): 若一条迹经过的点没有重复 (起点和终点重复的情况除外), 则称其为简单路径
若一条路径 (迹，简单路径) 的起点和终点相同，则称其为闭路径 (闭迹 , 闭简单路径), 闭简单路径又叫圈 (cycle)
另外，我们将长度为 3 的圈称为三角形 (triangle)
例如，对于下图
- \(v\to w\to x\to y\to z\to z\to x\) 是迹
- \(v\to w\to x\to y\to z\to x\to v\) 是闭迹
- \(v\to w\to x\to y\to z\) 是简单路径
- \(v\to w\to x\to y\to v\) 是圈
定义 - 2-2 对于图 \(G\), 定义
- \(\delta(G):=\min\{\deg(v):v\in V(G)\}\)
- \(\Delta(G):=\max\{\deg(v):v\in V(G)\}\)
- 围长 (girth) \(g(G)\): \(G\) 的最短圈长度，若 \(G\) 没有圈，则 \(g(G)=0\)
- 距离 (distance) \(d(x,y)\): 为 \(x,y\) 之间所有路径中的最短长度，若 \(x,y\) 之间不存在路径，则 \(d(x,y)=\infty\)
- 直径 (diameter) \(\operatorname{diam}(G):=\max\{d(u,v):u,v\in G\}\)
定理 - 2-1
- 若图 \(G\) 满足 \(\delta(G)\geq 2\), 则 \(G\) 中笔有一条长为 \(\delta(G)\) 的路和长为 \(\delta(G)+1\) 的圈
- 若图 \(G\) 有圈，则 \(g(G)\leq 2\operatorname{diam}(G)+1\)
定理 - 2-2 一个图是二分图当且仅当图中所有的圈都是偶长的
证明
- \(\implies\): 假设 \(v_0\to v_1\to...\to v_n\) 是一个圈，只需按下标的奇偶性来划分即可
- \(\impliedby\): 不妨假设图是连通的，任取一个点 \(v\), 考虑其他点和 \(v\) 的最短距离，将与 \(v\) 距离是偶数的点和 \(v\) 划分到同一组，剩下的划分为另一组，不难发现这两个划分不交且所有点都能划分到这两组中
定理 - 2-3 若简单图 \(G\) 有 \(n\) 个顶点，\(m\) 条边，\(k\) 个部件，则
\[ n-k\leq m\leq \frac{(n-k)(n-k+1)}{2} \]
推论 - 2-4 若有 \(n\) 个顶点的简单图有至少 \((n-1)(n-2)/2\) 条边，则该图连通
连通性
定义 - 2-3
不连通集 / 边割 (disconnecting set/edge cut): 若 \(E_0\subseteq E(G)\) 满足 \(G-E_0\) 不连通，则称 \(E_0\) 为不连通集 / 边割
极小边割 (cutset): 若边割 \(E_0\) 的任意真子集均不是边割，则称 \(E_0\) 为极小边割
若极小边割 \(E_0=\{e\}\), 则称 \(e\) 为桥 (bridge)
定义 \(\lambda(G)\) 为 \(G\) 的最小边割的大小，称为边连通度 (edge-connectivity)
若 \(\lambda(G)\geq k\), 则称 \(G\) 是 \(k\)- 边连通 (\(k\)-edge-connected) 的
\(E(X,Y)\) 为图 \(G\) 中边的端点分别落在点集 \(X,Y\) 的所有边的集合
\(e(X,Y)=|E(X,Y)|\), \(e(X)=e(X,X)\)
\(\partial(X):=E(X,V(G)\setminus X)\), 显然 \(\parallel(X)\) 是边割
不难得出
\[ |\partial(X)|=\sum_{v\in V(G)}\deg(v)-2e(X) \]
平凡边割: 对于无自环图 \(G\), 任取一点 \(v\), 称 \(\partial(v)\) 是平凡边割，显然 \(|\partial(v)|=\deg(v)\)
显然
- \(\lambda(K_n)=n-1\)
- \(\lambda(P_n)=1\)
- \(\lambda(C_n)=2\)
- \(\lambda(K_{n,m})=\min\{n,m\}\)
定理 - 2-6 称所有点的度均为奇数的图 \(G\) 为奇图，则
\[ |\partial(X)|\equiv|X|\pmod 2,~\forall X\subset V(G) \]
定义 - 2-4
- 分离集 / 点割 (disconnecting set/vertex cut): 若 \(V_0\subseteq V(G)\) 满足 \(G-V_0\) 不连通，则称 \(V_0\) 为分离集 / 点割
- 若点割 \(V_0=\{v\}\), 则称 \(v\) 为割点 (cut-vertex)
- 定义 \(\kappa(G)\) 为 \(G\) 的最小点割的大小，称为 (点) 连通度 (vertex-connectivity)
- 若 \(\kappa(G)\geq k\), 则称 \(G\) 是 \(k\)-(点) 连通 (\(k\)-connected) 的
显然
- \(\kappa(K_n)=n-1\)
- \(\kappa(P_n)=1\)
- \(\kappa(C_n)=2\)
- \(\kappa(K_{n,m})=\min\{n,m\}\)
关于连通度，我们有如下的 Menger 定理
定理 - 2-7 (Menger, 1927)
- 图 \(G\) 是 \(k\)- 边连通的当且仅当图中任意两个不相同的点之间都有 \(k\) 条路径，且这些路径之间的任意两条均没有公共边
- 至少有 \(k+1\) 个点的图 \(G\) 是 \(k\)- 连通的当且仅当图中任意两个点之间都有 \(k\) 条路径，且这些路径之间的任意两条除起点和终点外没有公共点
具体证明将在图的匹配中讲解
另外，对任意连通图，我们有如下结论
定理 - 2-8 对任意连通图 \(G\),
\[ \kappa(G)\leq\lambda(G)\leq\delta(G) \]
证明
显然，\(\lambda(G)\leq\delta(G)\), 接下来考虑证明 \(\kappa(G)\leq\lambda(G)\)
首先 \(G\) 是完全图的情况下结论显然成立，接下来假设 \(G\) 不是完全图
任取极小边割 \(F\), 只需证明存在点割 \(V_0\) 满足
\[ \kappa(G)\leq|V_0|\leq|F| \]
显然 \(G-F\) 有两个部件，设为 \(C_1\) 和 \(C_2\)
若某个部件中有一点 \(v\) 不与 \(F\) 中所有的边均相关联，不妨假设在 \(C_1\) 中
设 \(V_0\) 是 \(C_1\) 中所有与 \(F\) 中某条边相关联的点组成的集合，显然这个集合就是我们要找的点割
若 \(C_1\), \(C_2\) 中所有的点均与 \(F\) 中的边相关联，则存在一点 \(v\) 使得其不与所有点相邻，则 \(N(v)\) 即是我们要找的点割
有向图的情况
有向图情况下的路径，迹，简单路径，圈的定义类似，在此不再赘述
有向图的连通性略有不同:
定义 - 2-5
- 若有向图的底图是连通的，则称其为弱连通的 (weakly connected)
- 若有向图中任意两个不同的点之间均有有向路径，则称其为强连通的 (strongly connected)
定义 - 2-6 对一个图 \(G\), 若对其所有边存在一种定向方案，使得得到的有向图是强连通的，则称该图是可定向的 (orientable), 称得到的有向图是定向 (orientation)
定理 - 2-9 一个连通图 \(G\) 是可定向的当且仅当图上任意一条边均在图上的至少一个圈上 (即图是 \(2\)- 边连通的)
证明
\(\implies\): 显然
\(\impliedby\): 我们随意取一个圈 \(C\), 然后按某个顺序定向
若 \(E(G)\setminus E(C)=\varnothing\), 则命题得证，否则取与 \(C\) 相关联的边，由假设知其在某个圈上，所以我们可以继续以同样的方式定向，不难发现这样不断进行下去后得到的图是强连通的
推论 - 2-10 对任意一个图，其中的一条边 \(e\) 是桥当且仅当其不属于任何一个圈
Euler 圈，Euler 路
Hamilton 圈，Hamilton 路