哈密顿图

哈密顿图

• 哈密顿图
  • 哈密顿通（回）路：通过图中所有顶点一次的通（回）路
  • 具有哈密顿回路的图称为哈密顿图;
  • 具有哈密顿通路而无哈密顿回路的图称为半哈密顿图;
  • 二部图 |V1| ≥ |V2| ≥ 2，性质有：
    • G 是哈密顿图，则 |V1| = |V2|
    • G 是半哈密顿图，则 |V1| = |V2| + 1;
    • |V1| ≥ |V2| + 2，则 G 既不是哈密顿图，也不是半哈密顿图。
• 哈密顿图判定
  • 无向
    • 必要（哈密顿图性质）
      • 对于任意非空的顶点集 V1 ⊂ V，均有 p(G − V1) ≤ |V1|。
    • 充分（存在哈密顿回路）
      • G 是 n 阶简单无向图，对于任意不相邻的顶点 vi 和 vj 均有 d(vi)+d(vj) ≥ n
• 半哈密顿图判定
  • 无向
    • 必要
      • 对于任意非空的顶点集 V1 ⊂ V，均有 p(G − V1) ≤ |V1| + 1。
    • 充分（存在哈密顿通路）
      • G 是 n 阶简单无向图，对于任意不相邻的顶点 vi 和 vj 均有 d(vi)+d(vj) ≥ n−1