|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
아일랜드 출신의 수학자 윌리엄 로원 해밀턴이 그래프 이론에 제기한 회로의 종류이다. 기본적으로 해밀턴 경로는 어떤 연결된 그래프에서 모든 꼭짓점을 한 번씩만 지나는 경로를 부르는 말이다. 또한 이 경로가 회로일 경우 해밀턴 회로라고 하며, 어떤 그래프가 해밀턴 회로를 가질 때, 이 그래프를 해밀턴 그래프라고 한다. 오일러 회로와 같이 다루기도 한다.2. 오일러 회로와의 비교
오일러 회로란 연결된 그래프의 모든 변을 중복 없이 지나는 회로로, 익히 알려진 한붓그리기로 그려진 회로를 의미한다. 여기서 중요한 것은 변으로, 어떤 꼭짓점은 2회 이상 지나는 것에 대해서는 신경쓰지 않는다. 그래프 이론에서는 트레일(trail)에 가깝다.해밀턴 회로는 그 반대이다. 여기서는 모든 변을 지날 필요가 없지만, 한 꼭짓점은 단 한 번만 지나야한다. 그래프 이론의 패스(path)이다.
길이로 비교하자면, 오일러 그래프이자 해밀턴 그래프인 [math(G)]에 대해 해밀턴 회로의 길이는 [math(n(V(G)))]이며, 오일러 그래프의 길이는 [math(n(E(G)))]이다.
오일러 그래프이면서 동시에 해밀턴 그래프일 수 있고[1], 둘 중 한 쪽에만 해당될 수도 있으며, 둘 다 아닐 수도 있다. 즉, 오일러 그래프와 해밀턴 그래프 사이에는 관계가 없다.
3. 필요충분조건
알려져 있지 않다. 어떤 연결된 그래프가 오일러 그래프이기 위한 필요충분조건은 알려져 있지만, 해밀턴 회로의 경우 그렇지 않다. 그렇기에 현재 해밀턴 회로를 가지는 그래프의 조건을 알아내고, 해밀턴 회로를 찾는 방법을 구하는 것은 그래프 연구의 중요한 문제 중 하나이다.3.1. 필요조건
- 필요조건이라 알려진 것은 전부 해밀턴 회로가 지니고 있는 성질을 나열하거나 변형한 것 뿐이라 그래프를 좁힐 수 없다.
차수가 [math(n)]인 연결그래프 [math(G)]에 대하여 이 그래프가 해밀턴 회로 [math(H)]라면 다음 성질을 만족한다.
- [math(|H|=n)]
- 각 꼭짓점에 인접한 변 중에서 오직 두 변만이 [math(H)]에 포함된다. 따라서, 차수가 2인 꼭짓점에 인접한 변은 모두 [math(H)]에 포함된다.[2]
- [math(H)]의 일부만으로 구성되는 회로는 존재하지 않는다.
- 꼭짓점 [math(v)]가 [math(H)]에 포함되어 있다면, [math(v)]에 인접한 변 중에서 [math(H)]에 포함되지 않은 변은 소거하더라도 [math(H)]를 찾는데는 문제가 발생하지 않는다.
3.2. 충분조건
- 오레의 정리(Ore's theorem): [math( n(V(G)) = n \ge 3 )]인 그래프 [math(G)]와 [math(u, v \in V(G))]인 임의의 서로 다른 두 꼭짓점 [math(u, v)]에 대해 [math( \displaystyle deg(u) + deg(v) \ge n )]이면 [math(G)]는 해밀턴 회로를 갖는다.[3]
[1]
대표적인 예가
다각형 형태의 그래프.
[2]
해밀턴 회로는 모든 점을 한번씩만 지나야 하기 때문에 해밀턴 회로의 모든 꼭짓점에서의 차수는 무조건 2 이하가 된다.
[3]
같은 조건의 그래프 G에 대해 임의의 꼭짓점의 차수가 n/2 이상이어도 성립한다.