离散：3.欧拉图与哈密顿图

设G是一个图，G中包含所有边的通路/迹(即每条边恰好出现一次的路径)称为Euler通路/迹，闭的Euler迹称为Euler闭迹或Euler回路；

具有Euler回路的图称为Euler图，开的Euler迹称为Euler开迹，具有Euler开迹的图称为半Euler图。

Euler Circuit(欧拉回路)：An Euler circuit in a graph G is a simple circuit containing every edge of G.
- 欧拉回路，是包含着G的每一条边的简单回路
- （回路，即闭迹）
- 设 $v_0e_1v_1e_2v_2…e_kv_k$ 为图G中的一条路径，若边 $e_1，e_2，…，e_k$ 互不相同，则称该路径为迹；若点序列 $v_0，v_1，…，v_k$ 互不相同，则称该路径为路。
Euler Path(欧拉通路)：An Euler path in G is a simple path containing every edge of G.
- 欧拉通路，是包含着G的每一条边的简单通路
Euler Graph(欧拉图)：A graph contains an Euler circuit.
- 包含欧拉回路的图称为欧拉图。
Simple Path/Circuit（简单路径/回路）：A path or circuit is called simple if it does not contain the same edge more than once.
- 不包含重复边的路径或回路称为简单路径/回路

A directed multigraph having no isolated vertices has an Euler circuit if and only if

A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if

the graph is weakly connected
- 弱连通的
the in-degree and out-degree of each vertex are equal for all but two vertices, one that has in-degree 1 larger than its out-degree and the other that has out-degree 1 larger than its in-degree.
- 除去两个顶点外每个顶点的出度和入度相等，其中一个顶点的出度比入度大1，另一个顶点的入度比出度大1.

A Hamilton path in a graph G is a path which visits ever vertex in G exactly once.
- 哈密顿通路是一个访问图G中每个顶点次数有且仅有一次的通路
AHamilton circuit (or Hamilton cycle) is a cycle which visits every vertex exactly once, except for the first vertex, which is also visited at the end of the cycle.
- 哈密顿回路，仅访问每个顶点一次，但除去始点，这个始点同样也是终点。
If a connected graph G has a Hamilton circuit, then G is called aHamilton graph.
- 如果一个连通图G含有哈密顿回路，那么G是哈密顿图
Note: 定义适用与所有类型的有向图和无向图.