第四章 Euler图与Hamilton图

4.1 Euler图

Euler迹：经过连通图\(G\)的每条边的迹称为Euler迹。（注意区分迹与闭迹）
Euler图：对于连通图\(G\)，如果\(G\)中存在经过每条边的闭迹，则称\(G\)为欧拉图，简称\(G\)为\(E\)图。欧拉闭迹又称为欧拉环游，或欧拉回路。（通俗理解为遍历边回到起点）

性质：

Hamilton图：如果经过图\(G\)的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称\(H\)图。所经过的闭途径是\(G\)的一个生成圈，称为\(G\)的哈密尔顿圈。(通俗理解为遍历点回到起点)
Hamilton路：如果存在经过\(G\)的每个顶点恰好一次的路，称该路为\(G\)的哈密尔顿路，简称\(H\)路

性质与判定：

(必要条件) 若\(G\)为\(H\)图，则对\(V(G)\)的任一非空顶点子集\(S\)，有\(\omega (G-S)\leq |S|\)。（即满足不等式的图不一定是\(H\)图，不满足不等式的图一定是非\(H\)图）
(充分条件) 对于\(n\geq 3\)的单图\(G\)，如果G中有\(\displaystyle \delta (G)\geq \frac{n}{2}\)，那么\(G\)是\(H\)图。
(充分条件) 对于\(n\geq 3\)的单图\(G\)，如果\(G\)中的任意两个不相邻顶点\(u\)与\(v\)，有\(d(u)+d(v)\geq n\)，那么\(G\)是\(H\)图。
(邦迪-闭包)定理：图\(G\)是\(H\)图当且仅当它的闭包是\(H\)图。
- 在\(n\)阶单图中，若对\(d(u)+d(v)\geq n\)的任意一对顶点\(u\)与\(v\)，均有\(u\ adj\ v\), 则称\(G\)是闭图。
- 称\(\bar{G}\)是图\(G\)的闭包，如果它是包含\(G\)的极小闭图。
  - 如果\(G\)本身是闭图，则其闭包是它本身；如果\(G\)不是闭图，则由定义可以通过在度和大于等于\(n\)的不相邻顶点对间加边来构造\(G\)的闭图。
- 图\(G\)的闭包是唯一的。
度序列判定法：设\(G\)是度序列为\((d_1,d_2,...,d_n)\)的简单图，这里\(d_1\leq d_2\leq ...\leq d_n\)，并且\(n\geq 3\)。若对任何\(\displaystyle m<\frac{n}{2}\)，或有\(d_m>m\)，或有\(d_{n-m}\geq n-m\)，则\(G\)是\(H\)图

图\(G\)称为度极大非\(H\)图，如果它的度不弱于其它非\(H\)图
\(C_{m,n}\)图：对于\(\displaystyle 1\leq m<\frac{n}{2}\)，\(C_{m,n}\)图定义为\(C_{m,n}=K_m\vee （\bar{K}_m+K_{n-2m}）\)
- 注意理解\(C_{m,n}\)的度序列为： \[(\underbrace{m,...,m,}_{m}\ \underbrace{n-m-1,...,n-m-1,}_{n-2m}\ \underbrace{n-1,...,n-1}_{m})\]
对于\(\displaystyle 1\leq m<\frac{n}{2}\)，\(C_{m,n}\)图是非\(H\)图

定理1

若\(G\)是\(n\geq 3\)的非\(H\)简单图，则\(G\)度弱于某个\(C_{m,n}\)图。（证明P85）
- 定理1刻画了非\(H\)单图的特征：从度序列角度看，\(C_{m,n}\)图族中某个图是某个\(n\)阶非\(H\)单图的极图
- 定理1的条件是充分条件而非必要条件。例如当\(n=5\)时，其度极大非\(H\)图族是：\(C_{1,5}\)与\(C_{2,5}\)，5阶圈\(C_5\)度弱于\(C_{2,5}\)，但是\(C_5\)是\(H\)图
- 如果\(n\)阶单图\(G\)度优于所有的\(C_{m,n}\)图族，则\(G\)是\(H\)图

推论：

设\(G\)是\(n\)阶单图。若\(n\geq 3\)且\(\displaystyle |E(G)|>\begin{pmatrix} n-1 \\ 2\end{pmatrix}+1\)，则\(G\)是\(H\)图。并且具有\(n\)个顶点\(\begin{pmatrix} n-1 \\ 2\end{pmatrix}+1\)条边的非\(H\)图只有\(C_{1,n}\)以及\(C_{2,5}\)
证明P86，注：推论的条件是充分而非必要的