欧拉回路
【定义】欧拉回路 一个连通图，如果存在一条路，它经过每条边且仅一次，这个路叫做 欧拉路；如果它是个回路，称为 欧拉回路
【定理】 一个无向图 G 有一条欧拉路，当且仅当 G 是连通的，并且有0个或2个奇数度节点。
- 必要性。如果有一条欧拉路，G 显然就是连通的。假设欧拉路是 $v_0v_1…v_n$，那么对于每个中间的点，它每次出现都对应左右两个边，所以它们“带来”偶数个度。两个端点则带来2个奇数度（如果两个端点相同，带来 0 个奇数度）
- 充分性。
- 如果有 2 个奇数度节点，找这两个节点之间的路径 L1；如果没有奇数度节点，找任意闭合路径 L1。
- G-L1 也构成一个图，其每个节点度必然为偶数，可以找出任意闭合路径L2。
- 如此重复找到 Ln，直到边全部用完。
- 由于是连通图，它们之间有共享节点。
- （得到结论）
对于有向图，有类似结论：有单向欧拉回路当且仅当：
- 连通
- 每个节点的入度等于出度。或者除了两个节点外其它节点的入度等于出度，这两个节点一个入度比出度多1，一个出度比入度多1
（感觉上面的定理应该从“回路”出发，否则证明和表述会出现）
汉密尔顿图
【定义】汉密尔顿图 一个图，存在一个路径，它经过图上每个节点恰好一次，这个路径叫做 汉密尔顿路径，如果它是回路，叫做 汉密尔顿回路。含有汉密尔顿回路的图叫做 汉密尔顿图
平面图
一个图，如果能画在一个平面上，使边不交叉，叫做 平面图
