Hamilton Path, Cycle

○Hamilton Path

 ▷|V| ≥ 3인 그래프/멀티그래프에 대해

 ▷모든 vertex를 경유하는 Path

 

 ▶Sufficient Condition for Existence of Hamilton Path

  ▷|V| = n ≥ 2인 루프가 없는 그래프/멀티그래프에 대해

  ▷vertex x,y에 대해 deg(x) + deg(y) ≥ n-1이 항상 성립하면 Hamilton Path가 존재한다.

  ▷또는 모든 vertex x에 대해 deg(x) ≥ (n-1)/2가 항상 성립하면 Hamilton Path가 존재한다. (윗 조건보다 더 까다로움)

  ▷주의! 해당 조건이 성립하지 않는다고 Hamilton Path가 존재하지 않는 것은 아니다. (역->X)

 

 

○Hamilton Cycle

 ▷|V| ≥ 3인 그래프/멀티그래프에 대해

 ▷모든 vertex를 경유하는 Cycle

 

 ▶Sufficient Condition for Existence of Hamilton Cycle

  ▷|V| = n ≥ 3인 루프가 없는 undirected 그래프/멀티그래프에 대해

  ▷인접하지 않는 vertex x,y에 대해 deg(x) + deg(y) ≥ n이 항상 성립하면 Hamilton Cycle가 존재한다.

  ▷또는 모든 vertex x에 대해 deg(x) ≥ n/2가 항상 성립하면 Hamilton Cycle가 존재한다. (윗 조건보다 더 까다로움)

  ▷또는 |E| ≥ n-1C2 + 2가 성립한다면 Hamilton Cycle가 존재한다.

  ▷주의! 해당 조건이 성립하지 않는다고 Hamilton Cycle가 존재하지 않는 것은 아니다. (역->X)