欧拉图和哈密顿图

• 欧拉图
  • 定义
    • 欧拉通路：经过图中每条边恰好一次且仅一次行遍所有顶点的通路。
    • 欧拉回路：经过图中每条边恰好一次且仅一次行遍所有顶点的回路。
    • 欧拉图：具有欧拉回路的图。规定平凡图为欧拉图。
    • 半欧拉图：具有欧拉通路而无欧拉回路的图。
  • 性质
    • 环不影响图的欧拉性。
  • 判定
    • 无向图判定：
      • $G$ 是欧拉图 $\iff$ $G$ 连通且无奇数度数结点。
      • $G$ 是半欧拉图 $\iff$ $G$ 连通且恰好有 $2$ 个奇数度数结点。
      • $G$ 是非平凡的欧拉图 $\iff$ $G$ 连通且是若干个边不重复的圈的并。
    • 有向图判定：
      • $D$ 是欧拉图 $\iff$ $D$ 强连通且每个结点 $d^+_D(v_i)=d^-_D(v_i)$。
      • $D$ 是半欧拉图 $\iff$ $D$ 强连通且恰好有一个结点 $d^+_D(v_i)=d^-_D(v_i)+1$，恰好一个 $d^+_D(v_i)=d^-_D(v_i)-1$，其他结点 $d^+_D(v_i)=d^-_D(v_i)$。
• 哈密顿图
  • 定义
    • 哈密顿通路：经过图中所有顶点恰好一次的通路。
    • 哈密顿回路：经过图中所有顶点恰好一次的回路。
    • 哈密顿图：具有哈密顿回路的图。
    • 半哈密顿图：具有哈密顿通路且无哈密顿回路的图。
  • 性质
    • 环与平行边不影响哈密顿性。
    • 哈密顿图中，图中的所有顶点可以排在同一个圈上。
  • 判定
    • 无向图判定的必要条件：
      • $G=\langle V,E\rangle$ 是哈密顿图 $\implies$ 对任意非空 $V'\subset V$，$p(G-V')\le |V'|$。
      • $G=\langle V,E\rangle$ 是半哈密顿图 $\implies$ 对任意非空 $V'\subset V$，$p(G-V')\le |V'| + 1$。
    • 无向图判定的充分条件：
      • 已知 $G$ 是无向简单图（$n\ge 3$），$G$ 中任意不相邻 $u,v$ 满足 $d(u)+d(v) \ge n$ $\implies$ $G$ 是哈密顿图。
      • 已知 $G$ 是无向简单图，$G$ 中任意不相邻 $u,v$ 满足 $d(u)+d(v) \ge n-1$ $\implies$ $G$ 是半哈密顿图。
    • 无向图判定的充要条件：
      • 已知 $G$ 是无向简单图，$u,v$ 不相邻且 $d(u)+d(v) \ge n$，则 $G$ 是哈密顿图 $\iff$ $G\cup (u,v)$ 是哈密顿图。