2017년 2월 6일 (월) 16:45에 Maintenance script님의 편집

2017-02-06T16:45:08Z

새 문서

[목차]

== 개요 ==
아일랜드 출신의 수학자 [[윌리엄 로원 해밀턴]]이 그래프 이론에 제기한 회로의 종류이다. 기본적으로 해밀턴 경로는 어떤 연결된 그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 부르는 말이다. 또한 이 경로가 회로일 경우 해밀턴 회로라고 하며, 어떤 그래프가 해밀턴 회로를 가질 때, 이 그래프를 해밀턴 그래프라고 한다. [[한붓그리기|오일러 회로]]와 같이 다루기도 한다.

== 오일러 회로와의 비교 ==
[[오일러 회로]]란 연결된 그래프의 모든 변을 중복 없이 지나는 회로로, 익히 알려진 [[한붓그리기]]로 그려진 회로를 의미한다. 여기서 중요한 것은 '''변'''으로, 어떤 꼭짓점은 2회 이상 지나는 것에 대해서는 신경쓰지 않는다. 그래프 이론에서는 트레일(trail)에 가깝다.
해밀턴 회로는 그 반대이다. 여기서는 모든 변을 지날 필요가 없지만, '''한 꼭짓점은 단 한 번만 지나야한다.''' 그래프 이론의 패스(path)이다.

길이로 비교하자면, 오일러 그래프이자 해밀턴 그래프인 <math>G</math>에 대해 해밀턴 회로의 길이는 <math>n(V(G))</math>이며, 오일러 그래프의 길이는 <math>n(E(G))</math>이다.

오일러 그래프이면서 동시에 해밀턴 그래프일 수 있고[* 대표적인 예가 [[다각형]] 형태의 그래프.], 둘 중 한 쪽에만 해당될 수도 있으며, 둘 다 아닐 수도 있다. 즉, '''오일러 그래프와 해밀턴 그래프 사이에는 관계가 없다.'''

== 필요충분조건 ==
'''{{{+3 [[그런 거 없다]]}}}'''
어떤 연결된 그래프가 오일러 그래프이기 위한 필요충분조건은 알려져 있지만, 해밀턴 회로의 경우 그렇지 않다.[* 문서 작성일인 2016.06.08 기준. 발견 시 [[수정바람]] ~~언제?~~] 그렇기에 현재 해밀턴회로를 가지는 그래프의 조건을 알아내고, 해밀턴 회로를 찾는 방법을 구하는 것은 그래프 연구의 중요한 문제 중 하나이다.

=== 필요조건 ===
=== 충분조건 ===
* <math> n(V(G)) = n \ge 3 </math>인 그래프 <math>G</math>와 <math>u, v \in V(G)</math>인 임의의 서로 다른 두 꼭짓점 <math>u, v</math>에 대해 <math> \displaystyle deg(u) + deg(v) \ge n </math>이면 <math>G</math>는 해밀턴 회로를 갖는다.[*응용 같은 조건의 그래프 G에 대해 임의의 꼭짓점의 차수가 n/2 이상이어도 성립한다.]

[[분류:해석학]]

해밀턴 회로 - 편집 역사

2017년 2월 6일 (월) 16:45에 Maintenance script님의 편집