图论-Path and Cycle
Walk/Trail/Path/Circle
在图$G$中，途径(Walk)是指如下形式的 边序列
$$
v_0v_1,v_1v_2,…,v_{n-1}v_n:=e_1,e_2,…,e_n
$$
- 边的数量$n$是迹的长度
- 简单图可以表示为$v_0 → v_1 → v_2 → · · · → v_n$
- 起始点initial vertex：$v_0$
- 终点final vertex：$v_n$
- 内部点internal ertex：$v_1,v_2,…,v_{n-1}$
特别地，我们称边集相异的途径称为 迹(trail)
我们称顶点集相异的迹称为路(path)
- 所有的点为$v_0,v_1,…v_n$,可能存在$v_n=v_0$
- 记作$P_{n+1}$
对于顶点和终点相同的路称作圈(circle);
- 所有的点为$v_0,v_1,…v_n$,$v_n=v_0$
- 记作$C_n$
- 长度为3的圈记作三角形(triangle)
Theorem
对于顶点集为$V={v_1,v_2,…,v_n}$和邻接矩阵$A=[a_{ij}]$,邻接矩阵的幂
$$
A^k = [a_{ij}^{(k)}]
$$
表示$v_i-v_j$间长度为$k$的迹的数目；
proof :归纳法
Theorem
对于所有点度数至少为2的图，必定包含一个圈;
proof:考虑最长路；
Lemma
对于简单图$G$,$\delta(G)\ge k$,那么$G$包含一条长度至少为$k$的路；
连通图
称图$G$是连通的(connected)，当且仅当对于点集中任意点对$x,y$,存在$x$到$y$的路；
连通分量的数目记作$\omega(G)$;
Theorem
对于具有$n$个顶点的简单图$G$ ,其有$k$个连通分量，边的数目满足以下不等式约束：
$$
n-k\le m\le \frac{(n-k+1)(n-k)}{2}
$$
proof: 下界显然，上界只需注意以下引理
$$
\binom{p+q-1}{2}=\binom{p}{2}+\binom{q}{2}+(p-1)(q-1)\ge \binom{p}{2}+\binom{q}{2}
$$
Corollary
任意具有$n$个顶点的简单图，若其边数大于$(n-1)(n-2)/2$, 则一定是连通的；
proof：这意味着连通分量个数小于2；
Distance
对于图上两点$u,v$
- 距离$d(u,v)$：从$u$到$v$的最短路的长度；
- 离心距$\varepsilon(x)$:对于点$x$,遍历可能的顶点$y$,使得$d(x,y)$最大化的距离值；
- 图的直径$D(G)$:使得$\varepsilon(x)$最大化的离心率值；
- 图的半径$R(G)$:使得$\varepsilon(x)$最小化的离心率值；
- 图的围长$g(G)$:图$G$的最短圈的长度；
- 图的周长$c(G)$:图$G$的最长圈的长度；
Theorem(Konig)
图$G$是二部图当且仅当图中不含有奇圈；
proof: 反证法；
Edge-Connectivity
断集(disconnecting set)是指对于连通图上的一组边，满足其消失导致图变得不连通；
对于$S,T\subseteq V(G)$，,如果两个点集之间的边，其顶点各在不同的两个点集之中，记作$[S,T]$;
边割(edge cut)就是指这样一种$[S,\overline S]$;这样的边割定义蕴含着某种对称差性质，记作$\partial(S)$;
称图的最小非空边割为键(bond)；
若一个边割只包含一条边，我们称这条边为割边(cut edge)/桥(bridge)；
对于连通图$G$，其边连通性（edge connectivity）定义为最小边割的大小，也就是我们使图$G$不连通所需要删除的最少边数，记作$\lambda(G)$;
换句话说，若$\lambda(G)=k$,称$G$是$k-$边连通的，但不是$(k+1)-$边连通的；
note:边连通性描述了图到底有多么连通的性质，删除多少条边才能使得图变得不连通，暗示着图两点之间的独立路径数；
Lemma
对于图$G$上的顶点子集$S$，满足
$$
|[S,\overline S]|= \sum_{v\in S}d(v)-2|E(G[S])|
$$
proof:统计贡献；
Corollary
图$G$是偶图(每个顶点的度为偶数)，当且仅当对于任意的非空顶点子集$S$,$[S,\overline S]$ 为偶图；
proof：充分性显然，必要性只需要取一个顶点构成的点集即可；
Lemma
对于图$G$,其点集的子集$X,Y$，有
$$
\partial(X) \triangle \partial(Y)=\partial(X\triangle Y)
$$
proof:如下图
Theorem
对于连通图$G$，一个边割$F$是键当且仅当$G-F$恰好有两个$2$个连通分量；一个边集$S$是边割的充分必要条件是$S$是若干键的不相交并；
proof：利用键的最小性即可；
Lemma
对于图$G$，一条边$e$是桥当且仅当$e$不在图$G$的圈中；
proof：反证法；
Vertex-Connectivity
对于连通图$G$，称一组顶点为点割(vertex cut)，如果删除这组顶点会导致图$G$不连通；若点割只包含一个顶点，则称这个点为割点（cut vertex）;
类似定义点连通性为点割的最小大小，记作$\kappa(G)$，也就是使得图$G$不连通的最少删除点数
若$\kappa(G)=k$，称作图$G$是$k-$点连通的，但不是$(k+1)-$点连通的；
Theorem
对于简单图,有$\kappa(G)\le \lambda(G)\le \delta(G)$;
proof：考虑度最小的点，尝试删除与其关联的边，有$\lambda(G)\le \delta(G)$;
取一组最小的边割$[S,\overline S]$,完全图的情况平凡，考虑非完全图，取出$x\in S,y\in\overline S, x\nleftrightarrow y$；
构造
$$
T={u|u\in \overline S, x\leftrightarrow u}\bigcup {v|v\in S,y\leftrightarrow v}
$$
这是一组点割，容易观察到$\kappa(G)\le |T|\le \lambda(G)$;
2-连通图
称两条路内部不相交(internally disjoint),如果他们没有共同的内部顶点；
2-连通图意味着它既是2-边连通的，也是2-点连通的；
Theorem
对一个至少有3个顶点的图$G$，若$G$是2-连通的，当且仅当对于每一个点对$u,v\in V(G)$,均存在两条内部不相交的路将他们相连；
proof:充分性：删去一条边/点仍有另一条路径将之连通；
必要性：对距离归纳，相邻情况平凡；考虑最短路径前面一个点，构造不相交路径，删去该点仍然存在一条路径将之连通，如下图，选择最后一次与先前构造的两条路径交汇的顶点即可；
Theorem(Menger,vertex version)
拥有至少$k+1$条路经的图$G$是$k$-点连通的当且仅当对于每一个点对$u,v$存在$k$条内部无公共点的路径；
Theorem(Menger,edge version)
图$G$是$k$-边连通的当且仅当对于每一个点对$u,v$存在$k$条内部无公共边的路径；
Eulerian Graph
欧拉迹(Eulerian trail)定义为包含图中所有边的迹；若这个迹闭合，称为欧拉圈（Eulerian circuit）；
若图包含一个欧拉圈，称该图为欧拉图(Eulerian graph)；若图不包含欧拉圈，但是包括一个欧拉迹，称该图为半欧拉图(semi Eulerian graph)；
Lemma
若图$G$是图，每个顶点的度至少为2，那么图$G$包含圈；
proof:对于非简单图，结论平凡，对于简单图，考虑最长路即可；
Theorem
若连通图$G$是欧拉图当且仅当每个顶点的度数为偶数；
proof：配对；
Theorem
若连通图$G$是半欧拉图，当且仅当恰好存在两个顶点的度数为奇数；
proof：除开迹首尾两个顶点外配对，迹首尾两个顶点为奇点；
Fleury Algorithm
构造欧拉圈可按照如下算法：
- 从一个顶点$u$开始，选择与之关联的，未被遍历的一条边；
- 若选择的边是桥，改选其他边，若没有别的选择，就选择桥；选择这条边的另一个顶点为$v$;
- 将这条边加入迹中，擦除这条边
- 若产生了新的孤立点，同时擦除这个孤立点；
- 将$u$更新为$v$，选择下一条边；
Hamilton Graph
一个哈密顿圈是指一个遍历图中所有顶点的圈；
一个图$G$为哈密顿图当且仅当图$G$包含一个哈密顿圈；
- 对于$n\ge 3$，$K_n$是哈密顿图
- 当且仅当$m=n\ge 2$时，$K_{m,n}$是哈密顿圈
- Peterson图不是哈密顿图
由此定义图$G$的哈密顿闭包$C(G)$:通过在不相邻的点对上增加边，达到不存在不相邻的点对使得$d(u)+d(v)\ge n$的状态，也就是无法继续加边；这样的加边是顺序无关的；
Theorem
若$G,H$均是哈密顿图，那么$G \square H$是哈密顿图;
proof:对于$p$为偶数，构造如下：
对于$p$为奇数，构造如下：
Theorem
对于哈密顿图$G$，取顶点集的非空真子集$S$，有
$$
\omega(G-S)\le |S|
$$
proof:取$G$的哈密顿圈$C$，$C-S$至多$|S|$个分量；意味着$G-S$至多$|S|$个分量；
Theorem(Erdos)
对于具有$n$个顶点的简单图$G$，若$\delta(G)\ge \frac n2$，则图$G$是哈密顿圈；
proof：反证法，增加边使得$G$成为没有哈密顿圈的最大图，取图$G$中的最长路$v_1v_2…v_n$;由假设$v_n\nleftrightarrow v_1$
注意到
$$
S={j|v_1\leftrightarrow v_j}\
T={j|v_{j+1}\leftrightarrow v_n}\
|Ｓ\cap T|=|S|+|T|-|S\cup T|\ge \frac n2+\frac n2 - (n-1)=1
$$
则存在哈密顿圈$v_1\to v_2\to\cdots\to v_j\to v_{j+1}\to\cdots \to v_n$;
注：可进一步加强为$d(u)+d(v)$对任意不相邻的点对成立，这说明在简单图上哈密顿闭包是良定义的；
Lemma(Bondy)
对于简单图$G$，$G$是哈密顿图当且仅当$G$的闭包是哈密顿图；
Theorem(Chvatal)
对于简单图$G$的度序列为$d_1\le d_2\le …\le d_n，n\ge 3$，$\forall i<\frac n2, d_i>i\vee d_{n-i}\ge n-i$，则图G是哈密顿图;
Theorem（Chvatal-Erdos）
若$\kappa(G)\ge \alpha(G)$，则$G$是哈密顿图，除非$G=K_2$
Claw-free Graph
称图$G$是**无爪的(**claw-free)，当且仅当其不含$K_{1,3}$
在无爪图中，任何顶点的邻居的生成子图只有两种类型，从而将顶点分为两类：
- Type1:连通图
- Type2:仅有两个连通分量，并且分量都是完全图；
对于Type1的顶点，定义操作：在邻居中添加原本没有的边；只要邻居不构成团，操作就可以进行；
定义Ryjáček闭包：对于无爪图$G$,反复应用上述操作使得每一个Type1顶点邻居都能导出团，增边结束后生成图$H$；
Theorem
$H$是哈密顿的当且仅当$G$是哈密顿的；
Theorem
设$G$是2-连通图，顶点数$n>2$,$u$和$v$是$G$的不同点。若
$$
d(u,v)=2\Rightarrow \max{d(u),d(v)}\ge \frac n2
$$
则$G$具有哈密顿圈。
Shortest Path Problem
Gravity法
Making a model of the map by knotting together pieces of string whose lengths are proportional a length of the roads. To find the shortest length, take hold of the knots corresponding to A to L–and pull tight !
Dijkstra算法
The idea is to move across the graph from left to right, associating with each vertex X a number l(X) indicating the shortest distance from A to X. This means that, when we reach a vertex such as Kin the figure, then l(K) is either l(H) + 6 or l(I) + 2, whichever is smaller.
Chinese Postmen Problem
邮递员希望投递信件，尽可能短的总距离并回到他的起点。显然，他必须至少穿过路线中的每条道路一次。
在一个具有非负权的带权连通图$G$中，找出一条总权重最小的环游，这种环游称为最优环游。
若$G$为欧拉图，任意欧拉圈都是最优环游；
考虑$G$为非欧拉图，其必然包含偶数个奇度顶点；并且， 对于任意一个环游必定通过某些边不止一次，选取重复边按相同权值加入图$G$中，问题等价描述为一个最优化问题：
添加重复边求一个欧拉赋权母图$G^=G+E_1,E_1\in E(G)$，最小化
$$
\sum_{e\in E(G^)-E(G)} \omega(e)
$$
同时找到$G^*$的欧拉圈；
Theorem
上述欧拉赋权母图拥有最小权值的欧拉圈当且仅当
- $G$的每一条边至多被添加一次
- 对于$G^*$的每一个圈$C$,均有$\sum_{e\in E_1\cap E(C)}\omega(e)\le \sum_{e\in E(C)-E_1}\omega(e)$
Ttravelling Saleman Problem
一位旅行推销员希望参观一些城镇，然后返回他的家。鉴于城镇之间的距离，他应该如何规划路线，以便他只访问每个城镇一次，并最大限度地减少总旅行距离？
该问题可形式化描述为最小化带权完全图的哈密顿圈权值，称问题的解为TSP环游；
这是一个NP-hard问题；
Aheuristicapproach:2-edge-exchange: 如果一个可以通过删除两条边并添加两条边从另一个获得，则两个TPS路径称为2-相邻；
通过上述边的对换， 我们可以迭代地挖掘出最优路径；
proof:注意到
