오일러 경로

오일러 회로는 그래프 이론에서 모든 간선을 정확히 한 번씩만 지나며, 시작점과 끝점이 동일한 경로를 의미한다. 즉, 그래프의 모든 간선을 중복 없이 한 번씩 모두 통과하여 출발한 정점으로 돌아오는 순환 경로이다. 이 개념은 레온하르트 오일러가 1736년 쾨니히스베르크의 다리 문제를 연구하면서 처음으로 체계화하였다.

무향 그래프에서 오일러 회로가 존재하기 위한 필요충분 조건은 모든 정점의 차수가 짝수인 것이다. 이는 오일러 정리로 알려져 있다. 예를 들어, 모든 정점의 차수가 2, 4, 6과 같은 짝수인 연결된 그래프에서는 항상 오일러 회로를 찾을 수 있다. 이 조건은 그래프가 연결되어 있어야 한다는 전제를 포함한다.

오일러 회로는 오일러 경로의 특수한 경우로 볼 수 있다. 오일러 경로는 시작점과 끝점이 달라도 되지만, 오일러 회로는 시작점과 끝점이 반드시 같아야 한다는 점이 다르다. 따라서 오일러 회로는 '닫힌 오일러 경로'라고도 불린다.

이 개념은 실제 문제 해결에 다양하게 응용된다. 대표적으로 회로 기판의 배선 검사, DNA 서열 조립, 우편 배달 경로 최적화(중국인 우체부 문제) 등에서 모든 연결 통로나 간선을 효율적으로 한 번씩 순회해야 하는 상황에 오일러 회로의 원리가 활용된다.

오일러 경로는 주어진 그래프에서 모든 간선을 정확히 한 번씩만 지나가는 경로를 의미한다. 이때, 경로의 시작점과 끝점이 동일할 필요는 없다. 이 개념은 1736년 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 해결하며 처음 연구한 것으로, 그래프 이론의 시초를 이루는 중요한 문제 중 하나이다.

오일러 경로와 밀접한 관련이 있는 개념으로 오일러 회로가 있다. 오일러 회로는 모든 간선을 한 번씩만 지나되, 경로의 시작점과 끝점이 동일한, 즉 순환을 이루는 특수한 형태의 오일러 경로이다. 따라서 모든 오일러 회로는 오일러 경로이지만, 그 역은 성립하지 않는다.

무향 그래프에서 오일러 경로가 존재하기 위한 필요 충분 조건은 그래프가 연결 그래프이면서, 홀수 차수를 가진 정점의 개수가 정확히 0개 또는 2개여야 한다는 것이다. 홀수 차수 정점이 0개인 경우, 이는 오일러 회로가 존재하는 조건과 동일하며, 이때는 임의의 정점에서 시작하여 같은 정점으로 돌아오는 경로를 찾을 수 있다. 홀수 차수 정점이 2개인 경우, 오일러 경로는 반드시 그 두 정점 중 하나에서 시작하여 다른 하나에서 끝나게 된다.

무향 그래프에서 오일러 경로와 오일러 회로의 존재 여부는 각 정점의 차수, 즉 그 정점에 연결된 간선의 개수를 통해 간단히 판별할 수 있다. 이는 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 연구하며 발견한 핵심 조건으로, 그래프 이론의 기초를 이루는 중요한 정리이다.

오일러 회로가 존재하기 위한 필요충분조건은 두 가지이다. 첫째, 그래프의 모든 정점의 차수가 짝수여야 한다. 둘째, 그래프가 연결되어 있어야 한다. 이 조건을 만족하면 모든 간선을 정확히 한 번씩 지나 시작점으로 돌아오는 회로를 찾을 수 있다.

오일러 경로가 존재하기 위한 조건은 이보다 약간 느슨하다. 그래프가 연결되어 있어야 하며, 홀수 차수를 가진 정점이 정확히 0개 또는 2개여야 한다. 홀수 차수 정점이 0개인 경우는 위의 오일러 회로 조건과 동일하며, 이 경로는 사실상 회로가 된다. 홀수 차수 정점이 2개인 경우, 이 두 정점이 각각 경로의 시작점과 끝점이 된다. 이는 모든 간선을 한 번씩만 통과하되, 시작점과 끝점이 다른 경로를 의미한다.

이러한 조건은 직관적으로 이해할 수 있다. 경로가 한 정점을 통과할 때마다 들어오는 간선과 나가는 간선이 쌍을 이루므로, 시작점과 끝점을 제외한 모든 정점에서는 짝수 개의 간선이 연결되어 있어야 한다. 시작점과 끝점이 같은 회로의 경우, 모든 이동이 쌍을 이루므로 모든 정점의 차수가 짝수여야 한다.

유향 그래프에서 오일러 경로와 오일러 회로의 존재 조건은 무향 그래프의 조건과 유사하지만, 정점의 차수를 진입차수와 진출차수로 구분하여 고려한다는 점이 다르다. 유향 그래프에서 정점의 차수는 들어오는 간선의 수인 진입차수와 나가는 간선의 수인 진출차수로 나뉜다.

유향 그래프에서 오일러 회로가 존재하기 위한 필요충분 조건은 모든 정점의 진입차수와 진출차수가 서로 같아야 한다는 것이다. 이는 무향 그래프에서 모든 정점의 차수가 짝수여야 한다는 조건에 대응한다. 오일러 경로가 존재하기 위한 조건은, 모든 정점의 진입차수와 진출차수가 같은 상태에서, 시작점이 될 하나의 정점은 진출차수가 진입차수보다 1 크고, 끝점이 될 하나의 정점은 진입차수가 진출차수보다 1 커야 한다. 이는 무향 그래프에서 홀수 차수를 가진 정점이 정확히 두 개여야 한다는 조건과 맥을 같이한다.

이러한 조건들은 레온하르트 오일러가 최초로 연구한 쾨니히스베르크의 다리 문제를 확장한 것으로, 그래프 이론의 중요한 기초를 이룬다. 유향 그래프에서의 오일러 경로 문제는 네트워크 흐름 분석이나 DNA 시퀀싱과 같은 현대 응용 분야에서도 활용된다.

Fleury의 알고리즘은 주어진 그래프에서 오일러 경로나 오일러 회로를 찾는 고전적인 알고리즘이다. 이 알고리즘은 1883년 M. Fleury에 의해 제안되었으며, 기본적인 아이디어는 가능한 한 브리지(다리, 즉 제거하면 그래프가 두 개 이상의 연결 요소로 분리되는 간선)를 피해가며 모든 간선을 순회하는 것이다.

알고리즘의 구체적인 단계는 다음과 같다. 먼저, 그래프가 오일러 경로나 회로를 가질 수 있는지 조건을 확인한다. 조건을 만족하면, 오일러 회로의 경우 아무 정점에서나 시작하고, 오일러 경로의 경우 홀수 차수를 가진 정점 중 하나에서 시작한다. 이후, 현재 정점에서 아직 지나지 않은 간선 중 하나를 선택해 이동하는 과정을 반복한다. 이때 선택 규칙은, 브리지가 아닌 간선이 존재하면 그 간선을 우선적으로 선택하고, 모든 남은 간선이 브리지일 경우에만 브리지를 선택한다. 모든 간선을 지날 때까지 이 과정을 반복하면 오일러 경로나 회로가 완성된다.

Fleury의 알고리즘은 직관적이지만, 매 단계마다 브리지를 판별해야 하므로 구현이 다소 복잡하고 효율성이 떨어진다는 단점이 있다. 특히 그래프가 복잡할수록 브리지 판별에 드는 시간이 증가한다. 이러한 이유로 현대에는 보다 효율적인 Hierholzer의 알고리즘이 더 널리 사용된다.

그럼에도 불구하고 Fleury의 알고리즘은 그래프 이론의 기본 개념인 브리지의 중요성을 잘 보여주는 교육적인 가치가 있으며, 오일러 경로 문제를 해결하는 알고리즘의 역사적 발전 과정을 이해하는 데 중요한 의미를 지닌다.

Hierholzer의 알고리즘은 주어진 그래프에 오일러 회로 또는 오일러 경로가 존재할 때, 이를 효율적으로 찾는 알고리즘이다. 이 알고리즘은 깊이 우선 탐색을 기반으로 하며, 시간 복잡도는 O(E)로 매우 효율적이다. Fleury의 알고리즘에 비해 구현이 간단하고 성능이 우수하여 현대에 널리 사용된다.

알고리즘의 핵심 아이디어는 그래프에서 간선을 삭제해가며 순환을 찾고, 이 순환들을 연결하여 하나의 큰 회로를 구성하는 것이다. 구체적인 동작 과정은 먼저, 모든 정점의 차수가 짝수인지 확인하여 오일러 회로의 존재 조건을 만족하는지 판단한다. 그 후, 임의의 시작 정점에서 깊이 우선 탐색을 시작하여 더 이상 나아갈 간선이 없는 정점에 도달할 때까지 탐색한다. 이렇게 형성된 부분 회로를 스택에 저장하고, 아직 방문하지 않은 간선이 남아 있는 정점을 찾아 해당 정점에서 다시 탐색을 시작하여 새로운 부분 회로를 찾는다. 이 과정을 모든 간선을 방문할 때까지 반복한 후, 스택에 저장된 부분 회로들을 역순으로 결합하면 최종적인 오일러 회로가 완성된다.

만약 오일러 경로를 찾아야 하는 경우, 즉 홀수 차수를 가진 정점이 두 개인 경우에는 알고리즘의 시작점을 두 홀수 차수 정점 중 하나로 설정하면 된다. 이후 알고리즘의 과정은 동일하게 적용되어 시작점에서 다른 홀수 차수 정점으로 끝나는 오일러 경로를 찾을 수 있다.

Hierholzer의 알고리즘은 그래프 이론의 여러 실용적 문제, 예를 들어 회로 설계나 DNA 시퀀싱과 같은 생정보학 분야에서 경로를 찾는 데 응용된다. 이 알고리즘은 오일러 정리에 기반한 존재 조건을 만족하는 그래프에 대해 항상 정확한 해를 제공한다는 점에서 이론적 중요성과 실용성을 모두 갖추고 있다.

해밀턴 경로는 그래프 이론에서 모든 정점을 정확히 한 번씩만 방문하는 경로를 말한다. 이와 유사하게, 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 사이클은 해밀턴 순환이라고 한다. 이러한 개념은 19세기 수학자 윌리엄 로언 해밀턴의 이름을 따서 명명되었다.

해밀턴 경로 문제는 주어진 그래프에서 해밀턴 경로가 존재하는지 판별하는 문제로, NP-완전 문제에 속한다. 이는 모든 정점을 한 번씩만 방문해야 한다는 조건이 조합 최적화적으로 매우 어려운 문제를 만들어내기 때문이다. 이 문제는 외판원 문제와도 밀접하게 연관되어 있다.

오일러 경로가 모든 간선을 한 번씩 지나는 데 초점을 맞춘다면, 해밀턴 경로는 모든 정점을 한 번씩 방문하는 데 초점을 맞춘다. 이는 두 개념의 근본적인 차이점이다. 예를 들어, 오일러 경로의 존재 여부는 정점의 차수만으로 비교적 쉽게 판단할 수 있지만, 해밀턴 경로의 존재 여부를 판별하는 일반적이고 효율적인 필요충분조건은 아직 알려져 있지 않다.

해밀턴 경로와 순환은 이론적 중요성뿐만 아니라, 일정 계획, 물류 경로 최적화, DNA 시퀀싱, 게임 이론 등 다양한 실생활 문제를 모델링하는 데 활용된다.

중국인 우체부 문제는 주어진 그래프에서 모든 간선을 최소한 한 번 이상 지나면서 시작점으로 돌아오는 최단 경로를 찾는 문제이다. 이는 모든 간선을 정확히 한 번씩만 지나야 하는 오일러 회로 문제와 달리, 간선을 여러 번 지날 수 있지만 총 이동 거리(또는 비용)를 최소화해야 한다는 점에서 차이가 있다. 이 문제는 우체부가 모든 거리를 최단으로 돌아다녀야 하는 실제 업무에서 착안되어 명명되었다.

문제는 가중치가 부여된 무방향 그래프에서 정의되며, 최적 경로를 찾기 위해서는 그래프가 오일러 회로를 갖도록 만드는 것이 핵심이다. 만약 그래프의 모든 정점이 짝수 차수를 가진다면, 이는 이미 오일러 회로가 존재하므로 그 회로 자체가 최적 해가 된다. 그러나 홀수 차수를 가진 정점이 존재할 경우, 이들 간에 추가적인 경로(간선의 복제)를 설정하여 모든 정점의 차수를 짝수로 만들어야 한다.

이를 해결하는 알고리즘은 기본적으로 다음과 같은 단계를 따른다. 먼저 그래프에서 홀수 차수를 가진 정점들을 찾는다. 이들 정점 사이의 최단 경로를 계산한 후, 최소 비용으로 이들을 짝지을 수 있는 매칭을 찾는다. 마지막으로, 이 최소 비용 매칭에 해당하는 경로들의 간선을 원래 그래프에 추가(중복)하여 모든 정점의 차수가 짝수인 새로운 그래프를 구성하고, 이 그래프에서 오일러 회로를 찾으면 그것이 최적 해가 된다. 이 문제는 조합 최적화와 운용 연구 분야에서 중요한 사례로 다루어진다.