欧拉环游

定义

欧拉回路：我们称一个通过图的每条边恰好一次的闭途径为欧拉环游 (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\)中的节点后的连通分支数；