📂그래프이론

해밀톤 그래프

정의 ¹

$G$ 가 연결 그래프라고 하자.

$G$ 의 모든 버텍스를 포함하는 닫힌 패스가 존재하면 $G$ 를 해밀톤 그래프라 하고 그 사이클을 해밀턴 사이클이라 한다. 모든 버텍스를 포함하지만 닫혀있지 않은 패스가 존재하면 $G$ 를 세미 해밀톤 그래프라 한다.

설명

오일러 그래프가 모든 에지를 지나는 트레일에 관심이 있듯 해밀톤 그래프는 모든 버텍스를 지나는 패스에 관심이 있다. 오일러 그래프와 해밀톤 그래프가 논리적인 관계를 가지지는 않는다. 가령 다음 그래프들은 차례대로 해밀톤이지만 오일러가 아닌 그래프, 해밀톤이면서 오일러인 그래프, 해밀톤이 아니지만 오일러인 그래프를 나타낸다:

언뜻 모든 에지를 지나지 않아도 된다는 점이 쉬워보일지도 모르지만, 대신 하나의 버텍스는 단 한번만 지나갈 수 있기 때문에 더 까다로워지는 부분이 있다. 그래서 오일러 그래프는 깔끔하게 그 차수로 동치조건이 주어져 있으나 해밀톤 그래프는 그렇지 못하다.

다만 충분히 많은 에지가 있다면 해밀톤 그래프임을 보장해주는 정리가 알려져 있다. 이는 흔히 디락 정리Dirac ' s Theorem로 알려져있다. 디락 정리는 1952년 증명된 이후 1960년 오레^ore에 의해 쉬운 증명으로 일반화되어 오레 정리의 따름 정리가 되어버렸으나, 아직도 디락 정리라고 부르는 경우가 많다.

같이보기

• 모든 에지를 포함하는 닫힌 트레일이 존재하는 그래프 : 오일러 그래프