728x90
반응형
[Algorithm] 그래프 알고리즘 - 오일러의 정리와 오일러 경로, 해밀턴 경로와 해민턴 순환, 회판원 문제, NP 복잡도
지금으로부터 300여 년 전 프로이센 공국의 쾨니히스베르크에는 프레겔 강이 흐르고 있었다. 프레겔 강에는 2개의 큰 섬이 있었고, 섬과 도시를 연결하는 7개의 다리가 놓여 있었다. 어느날 도시의 시민 한 명이 "이 7개 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?"라는 흥미로운 문제를 냈다. 그러나 쉽게 풀릴 것처럼 보였던 이 문제를 풀 수 있는 이는 아무도 없었다. '수학의 모차르트'라 불리는 레온하르트 오일러가 '쾨니히스베르크의 다리 문제'를 조사하기 시작했다. 오일러는 이 문제가 도형 문제처럼 보이지만, 당시까지 알려진 기하학으로는 풀 수 없음을 알았다. 그리고 미지의 영역에 그 해법이 있다는 사실을 처재적인 직관으로 간파했다. 이것이 바로 '그래프 이론..
Algorithm
2020. 12. 17. 08:00
728x90
반응형