그래프 이론 4

Hamiltonian graphs and digraphs

한 그래프 안에 두 정점들 사이에 한 path는 해밀턴 path 이면 이것은 그래프의 모든 정점들을 통하는 pass이다. 한 가까운 해밀턴 path는 그래프 안에  해밀턴 사이클이라고 불린다. 다시 말해서, 한 해밀턴 path는 spanning path이며, 또 해밀턴 cycle은 spanning cycle이다. 해밀턴 그래프는 해밀턴 사이클을 가진 그래프이다. 모든 해밀턴 그래프는 해밀턴 path 가지고 있으며, 그러나 정반대는 진실이 아니다; 그래프에 path를 고려해야된다. 해밀턴 그래프의 우리의 논의는, 우리는 간단한 그래프들 우리의 주의를 제한한다. 왜냐하면 즉시 정점을 통한 pass를 고려해야된다. 유도된 그래프들의 경우 안에, 정의들 유사하다.

오일러 그래프와 달리, 여긴 해밀턴 그래프들의 묘사는 우아하지 않으며(쉽게 검증가능), 많은 필요족건을 통하여 짝수이고 많은 충분 조건은 알려진 spanning cycles의 존재이고 연속된 그래프안에 spanning paths고 약한 연결 방항성그래프이다. 물론, 어떤 해밀턴 그래프는 필연적으로 2-연결된 이전 정점의 삭제로부터 그래프 결과들 연결된 그래프 안에 해밀턴 path를 가진다.(??)   그 결과, 그래프 아님과 함께 절단 정점 해밀턴이다. 모든 사이클 그래프는 해밀턴이며, 또한 모든 완전 그래프 이며 3개 또는 더 많은 정점들을 가진다. 연결된 상호 그래프 Km.n은 해밀턴이면 오직 m=n 성립한다.

따라서 필요한 조건은 fact의 간단한 일반화  그것은 해밀턴 그래프의  정점이 없는 절단 정점이다.