5．4欧拉图与汉密尔顿图

欧拉回路给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路。

欧拉图存在欧拉回路的图，称为欧拉图。

定理5．4．1无向图G，具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。

推论无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数都是偶数。

一笔画的判别问题。要判定一个图G是否可以一笔画出，有两种情况：一是从图G的某一点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次再回到该结点。

单向欧拉路（回路）给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。

定理5．4．2有向图G具有一条单向欧拉路，当且仅当是可达的，且每个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当是可达的，而且除两个结点外，每个结点的入度等于出度，而这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。

汉密尔顿路给定图G，若存在一条路，经过图中每个结点恰好一次，这条路称作汉密尔顿路。

汉密尔顿回路给定图G，若存在一条回路，经过图中每个结点恰好一次，这条回路称作汉密尔顿回路。

汉密尔顿图具有汉密尔顿回路的图，称作汉密尔顿图。

定理5．4．3若图G=<V，E>具有汉密尔顿回路，则对于结点集V的每个非空子集S，均有成立。

其中W(G-S)是G-S的连通分支数。

定理5．4．4设G为具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。

定理5．4．5设G是具有n个结点的简单图，如果G中每一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路。

找汉密尔顿图是NPC问题，只能DFS穷举，找是否存在有效的解。

在一个图里找欧拉图是没意思的，可能能找到。验证欧拉图看起来和验证汉密尔顿图问题一样， 是个P问题。 http://www.geeksforgeeks.org/eulerian-path-and-circuit/

• 欧拉回路满足的条件

  • 所有度不为0的点都连接

  • 所有节点的度都为0

• 欧拉路径满足条件

  • 所有度不为0的点都连接

  • 如果度为奇数的点有两个，是欧拉路径。如果是0个，欧拉回路。因为是无向图，等于1是不可能。大于两个没法组成欧拉图