欧拉路径与哈密顿路径

• 欧拉路

  1、欧拉路径：从某一点出发经过一条不间断的路径，这条路径刚好访问整个图的所有边一次且仅一次(一笔画问题)。一个图可能有多条欧拉路径
  2、欧拉回路：一条首尾相接的欧拉路径(首尾相接的一笔画问题)。一个图可能有多条欧拉回路
  3、欧拉图：具有欧拉回路的图。特点为：无向图中所有顶点的度都是偶数；有向图中所有顶点的入度和出度都相等
  4、半欧拉图：具有欧拉路径但不具有欧拉回路的图。特点为：无向图中有且仅有两个顶点的度为奇数，这两个顶点分别为起点和终点；有向图中有且仅有一个顶点的出度 - 入度 $= 1$，另有且仅有一个顶点的入度 - 出度 $= 1$，这两个顶点分别为起点和终点
  5、推论：欧拉图的所有欧拉路径都是欧拉回路，所以计算欧拉回路与欧拉路径的算法完全一样
  6、无向图中，在欧拉路的 2 个奇数度点之外，每多有 2 个奇数度点，画完所需要最少的笔数增加一笔