欧拉环游和哈密尔顿环游

欧拉环游

定义

欧拉回路：我们称一个通过图的每条边恰好一次的闭途径为欧拉环游 (Eulertour)；
欧拉通路：我们称一个通过图的每条边恰好一次的路为欧拉通路；
欧拉图：如果一个图包含一个欧拉环游，就称它是欧拉的(Eulerian)；

判断的充要条件

对于无向连通图，一个连通图是欧拉的当且仅当它的每个顶点度是偶数。
连通图$G$是存在从$a$到$b$的欧拉路径，当且仅当$G$是连通的，并且除$a$和$b$($a \ne b$)的度为奇数(odd)之外，没有度为奇数(odd)的顶点；

对于有向连通图，一个连通图是欧拉的当且仅当$G$是连通的，且每个顶点的出度 = 入度；
有向连通图$G$含有欧拉通路，当且仅当$G$是连通的，并且$G$中除两个顶点(节点不相等)外，其余每个顶点的入度=出度，且此两点满足$\left |deg^+{(u)} - deg^-{(v)}\right | = 1$

哈密尔顿通路

定义

哈密尔顿回路：图$G$的哈密顿回路(Hamiltonian circuit)指的是遍历$G$中每一个点且只遍历一次的回路, 这样的轨迹称为哈密顿环游(Hamiltonian tour)；
哈密尔顿通路：1. 图G的哈密顿路径(Hamiltonian path)指的是遍历G中每一个点且只遍历一次的路径, 这样的轨迹称为哈密顿轨迹(Hamiltonian trail)；

一些充分条件

Dirac’s theorem狄拉克定理

对于简单连通图$G$，如果$G$的顶点数$n \ge 3$，且所有顶点的度都$\ge \frac{n}{2}$，那么$G$存在哈密尔顿回路；

Ore’s theorem欧尔定理

对于简单连通图$G$，如果$G$的顶点数$n \ge 3$，且对于每一对不相邻的顶点$u, v$，都有$deg(u) + deg(v) \ge n$，那么$G$存在哈密尔顿回路；

必要条件(可以用来判断不是哈密尔顿通路)

设无向图$G = (V,E)$，非空子集$V_1 \subset V$，则$P(G - V_1)\le \left | V_1 \right |$，其中$p(G - V_1)$为图$G$删除$V_1$中的节点后的连通分支数；