오일러 회로

최적설계 수치해석 마지막 수정: 2026-08-19 04:37:52

1. 개요[편집]

오일러 회로 Eulerian Circuit
정의	모든 간선을 정확히 한 번씩 지나 출발점으로 돌아오는 폐로
존재 조건 (무향)	연결 + 모든 정점의 차수가 짝수
오일러 경로	홀수 차수 정점이 정확히 0개 또는 2개
존재 조건 (유향)	모든 정점에서 $\deg^{+} = \deg^{-}$ + 간선 있는 부분이 강연결
기원	오일러, 쾨니히스베르크 다리 (1736 · 출판 1741)
구성	히어홀처 알고리즘 (1873) — $O(E)$
대비	해밀턴 회로(정점 방문)는 NP-완전

오일러 회로(Eulerian circuit)는 그래프의 모든 간선을 정확히 한 번씩 지나 출발점으로 되돌아오는 닫힌 경로다. 출발점 복귀 조건을 뺀 것이 오일러 경로(Eulerian trail)다. 한붓그리기의 정식 명칭이라고 보면 된다.

이 개념이 특별한 대접을 받는 이유는 두 가지다. 첫째, 그래프 이론이라는 분야 자체가 여기서 시작했다. 1736년 오일러가 쾨니히스베르크 다리 문제를 풀면서 “다리의 길이도, 섬의 모양도, 지도상의 위치도 상관없고 무엇이 무엇과 연결되어 있는가만 중요하다”고 선언한 것이 위상수학적 사고의 출발점으로 꼽힌다.

둘째, 판정과 구성이 모두 선형 시간에 끝난다. 겉보기에 거의 똑같은 문제인 해밀턴 회로(모든 정점을 한 번씩 방문)가 NP-완전인 것과 극명하게 대비된다. “간선을 다 지나기”와 “정점을 다 들르기”라는 한 칸 차이가 다항시간과 NP-완전을 가른다는 사실은, 조합 문제의 난이도가 얼마나 미묘한 데서 갈리는지 보여 주는 표준 예시다.¹

2. 오일러 정리[편집]

연결 그래프(차수 0인 고립 정점은 무시)에 오일러 회로가 존재할 필요충분조건은 모든 정점의 차수가 짝수인 것이다.

필요조건은 세는 것으로 끝난다. 회로가 어떤 정점을 지날 때마다 들어오는 간선 하나와 나가는 간선 하나를 소비하고, 출발점도 처음 나가는 간선과 마지막 들어오는 간선이 짝을 이룬다. 모든 간선이 정확히 한 번씩 쓰이므로 각 정점의 차수는 2의 배수여야 한다.

충분조건은 오일러 본인이 자명하다며 넘어갔고, 엄밀한 구성적 증명은 137년 뒤 히어홀처(1873)가 채웠다. 수학사에서 “너무 당연해 보여서 아무도 안 썼다”의 대표 사례로 자주 인용된다.²

오일러 경로 쪽은 따름정리다. 홀수 차수 정점 $u, v$ 두 개가 있으면 가상의 간선 $uv$ 를 하나 추가해 모두 짝수로 만든 뒤 회로를 찾고, 그 가상 간선을 잘라 내면 $u$ 에서 $v$ 로 가는 오일러 경로가 된다. 악수 보조정리에 의해 홀수 차수 정점의 개수는 늘 짝수이므로, 홀수 정점이 정확히 0개(회로) 또는 2개(경로) 외의 경우는 아예 존재할 수 없다. 4개 이상이면 어떤 한붓그리기도 불가능하다.

쾨니히스베르크의 다리. 프레겔 강의 두 섬과 양쪽 강변을 잇는 다리 7개를 한 번씩만 건너 원위치로 돌아올 수 있는가 — 답은 불가능이다. 네 육지 덩어리를 정점으로 놓으면 차수가 각각 5, 3, 3, 3으로 넷 다 홀수다. 회로는커녕 경로도 안 된다.

베블런 정리도 같은 계열이다. 모든 정점의 차수가 짝수인 것과 간선 집합을 서로소인 사이클들로 분할할 수 있는 것이 동치이며, 히어홀처 알고리즘은 사실상 이 분해를 만들어 하나로 꿰매는 절차다.

3. 유향 그래프판[편집]

방향이 붙으면 조건이 이렇게 바뀐다.

\deg^{+}(v) = \deg^{-}(v) \quad \forall v, \qquad \text{그리고 간선을 가진 정점들이 강연결}

여기서 강연결이 진짜로 필요하다는 점이 무향과 다른 부분이다. 무향에서는 “연결”이면 충분했지만, 유향에서는 진출·진입 차수가 전부 균형이어도 방향 때문에 되돌아오지 못하는 구조를 만들 수 있다. 다만 차수 균형이 이미 성립하면 약연결과 강연결이 일치하므로, 구현에서는 “간선 있는 정점들이 한 덩어리인가”만 확인하면 된다.

오일러 경로 쪽은 정확히 한 정점에서 $\deg^{+} - \deg^{-} = 1$ (출발점), 다른 한 정점에서 $-1$ (도착점), 나머지는 0이면 된다.

4. 히어홀처 알고리즘[편집]

$O(E)$ 짜리 구성 알고리즘이며, 아이디어가 한 문장이다. 아무 폐로나 만들고, 아직 안 쓴 간선이 남은 정점에서 곁가지 폐로를 만들어 끼워 넣는다.

임의의 정점에서 출발해 아직 쓰지 않은 간선을 따라 계속 걷는다. 차수가 짝수이므로 막히는 곳은 출발점뿐이고, 결국 폐로 $C$ 가 하나 닫힌다.
$C$ 위의 정점 중 아직 쓰지 않은 간선이 남은 정점 $v$ 를 찾는다. 없으면 끝.
$v$ 에서 같은 방식으로 새 폐로 $C'$ 를 만들고, $C$ 의 $v$ 자리에 $C'$ 를 통째로 삽입한다. 2번으로 돌아간다.

구현은 보통 재귀 대신 명시적 스택으로 한다. 정점을 스택에 쌓으며 미사용 간선을 타고 전진하고, 더 갈 곳이 없으면 팝해서 결과 리스트에 붙인다. 마지막에 결과를 뒤집으면 오일러 회로다. 각 정점마다 “다음에 볼 간선” 포인터를 유지해 이미 지난 간선을 다시 훑지 않는 것이 $O(E)$ 의 핵심이다 — 이걸 빼면 인접 리스트를 반복 스캔해 $O(VE)$ 로 퇴화한다.

대안인 플뢰리 알고리즘은 “다리(bridge)가 아닌 간선을 우선 선택”하는 탐욕인데, 매 걸음 다리 판정을 해야 해서 소박하게 짜면 $O(E^2)$ 다. 손으로 풀 때는 직관적이지만 코드로는 히어홀처가 정답이다. 재귀 구현은 간선이 많으면 스택이 터지므로 반복 버전을 쓰는 것이 무난하다.

5. 오일러 회로 세기 — BEST 정리[편집]

“하나 찾기”는 선형 시간인데 “몇 개인가”는 사정이 다르다. 유향 그래프에서는 놀랍게도 닫힌 형태의 공식이 있다.

\mathrm{ec}(G) \;=\; t_w(G) \cdot \prod_{v \in V} \left(\deg^{+}(v) - 1\right)!

여기서 $t_w(G)$ 는 임의로 고정한 정점 $w$ 를 향하는 뿌리 방향 신장 수목(arborescence)의 개수이며, 유향 행렬-수형도 정리에 따라 라플라시안의 여인수, 즉 행렬식 하나로 계산된다. 오일러 그래프에서는 이 값이 $w$ 의 선택과 무관하다. 이 결과를 BEST 정리라 부르는데, 이름이 최상급이 아니라 de Bruijn, van Aardenne-Ehrenfest, Smith, Tutte의 머리글자다.

반면 무향 그래프에서 오일러 회로의 개수를 세는 것은 #P-완전이다. 셈 문제의 난이도가 방향의 유무만으로 갈리는 인상적인 사례다.

6. 드 브루인 수열[편집]

알파벳 크기 $k$ , 차수 $n$ 의 드 브루인 수열 $B(k,n)$ 은 가능한 모든 길이 $n$ 문자열이 순환적으로 정확히 한 번씩 부분문자열로 등장하는 길이 $k^n$ 의 순환 수열이다. $B(2,3)$ 의 예로 00010111이 있고, 순환으로 읽으면 000, 001, 010, 101, 011, 111, 110, 100이 한 번씩 나온다.

구성은 오일러 경로의 정석적 응용이다. 드 브루인 그래프 $G(k, n-1)$ 을 이렇게 짓는다.

정점 = 길이 $n-1$ 문자열 ( $k^{n-1}$ 개)
간선 = 길이 $n$ 문자열 ( $k^n$ 개). 문자열 $a_1 a_2 \cdots a_n$ 은 $a_1\cdots a_{n-1}$ 에서 $a_2 \cdots a_n$ 으로 가는 간선.

모든 정점의 진입·진출 차수가 $k$ 로 같고 강연결이므로 오일러 회로가 존재하며, 그 회로가 곧 드 브루인 수열이다. 회로의 개수를 BEST 정리로 세면

\left|B(k,n)\right| = \frac{(k!)^{k^{n-1}}}{k^{n}}

가 나온다. 같은 구조를 정점=길이 $n$ 문자열로 잡으면 해밀턴 회로 문제가 되는데, 정확히 같은 대상을 오일러로 보면 다항시간, 해밀턴으로 보면 일반적으로는 어려운 문제가 된다. 모델링의 각도가 난이도를 만든다는 점을 이보다 깔끔하게 보여 주는 예는 드물다.

응용은 생각보다 실용적이다. 회전 드럼·로터리 인코더의 각도 절대 위치 판별(연속한 $n$ 비트만 읽으면 위치가 유일하게 결정된다), 카드 마술, 의사난수 생성용 최대 길이 시프트 레지스터 수열(m-수열)이 전부 이 계열이며, 저장 공간 없이 위치를 알아내는 트릭의 뿌리다.

7. 유전체 조립의 오일러 경로 접근[편집]

DNA 시퀀서는 유전체 전체가 아니라 짧은 리드(read)를 대량으로 뱉는다. 이걸 이어 붙여 원래 서열을 복원하는 것이 조립(assembly)이고, 두 가지 그래프 모델이 경쟁해 왔다.

OLC(overlap-layout-consensus). 리드를 정점, 겹침을 간선으로 놓고 모든 정점을 한 번씩 지나는 경로를 찾는다. 즉 해밀턴 경로. 개념은 자연스럽지만 리드가 수억 개면 겹침 계산부터 감당이 안 되고, 경로 찾기 자체가 NP-난해다.
드 브루인 그래프 방식. 리드를 길이 $k$ 조각( $k$ -mer)으로 잘게 부수고, 길이 $k-1$ 접두·접미사를 정점, $k$ -mer를 간선으로 놓는다. 그러면 유전체는 모든 간선을 지나는 오일러 경로가 된다. 판정과 구성이 선형 시간이라 규모가 통째로 바뀐다.

아이더리(Idury)와 워터먼(1995)이 서열 조립을 이 틀로 정식화했고, 페브즈너·탕·워터먼(2001)이 대규모 숏리드 조립으로 밀어붙이면서 표준이 됐다. Velvet, ABySS, SOAPdenovo, SPAdes 같은 조립기가 전부 이 계열이다.

물론 현실은 교과서보다 지저분하다.

시퀀싱 오류가 존재하지 않는 $k$ -mer를 만들어 그래프에 잔가지(tip)와 거품(bubble)을 심는다. 저빈도 $k$ -mer 제거, 팁 트리밍, 버블 병합이 표준 전처리다.
반복 서열이 있으면 그래프에 차수 큰 정점이 생겨 오일러 경로가 여러 개가 되고, 그중 어느 것이 진짜 유전체인지 그래프만으로는 알 수 없다. 페브즈너 계열은 리드가 지지하는 경로만 허용하는 오일러 초경로(Eulerian superpath) 문제로 이 제약을 얹었다.
실제 데이터는 커버리지가 고르지 않아 애초에 오일러 조건이 정확히 성립하지 않는다. 그래서 실무 조립기는 “오일러 경로 하나를 찾는다”기보다 그래프를 정리한 뒤 모호하지 않은 구간(unitig)만 뽑아 내는 쪽으로 간다.

그래도 뼈대는 여전히 오일러다. 정점 중심(해밀턴)에서 간선 중심(오일러)으로 시점을 옮긴 것만으로 NP-난해가 선형 시간이 된 이 전환은, 계산생물학에서 가장 자주 인용되는 모델링 승리 사례다.³

8. 최적화로 넘어가면 — 중국 우편배달부[편집]

오일러 회로가 존재하지 않는 그래프에서 “모든 간선을 지나되 총 비용을 최소로” 하려면 어떤 간선을 되밟을지 골라야 한다. 이것이 중국 우편배달부 문제이며, 홀수 차수 정점들을 최단경로 거리로 최소가중 완전매칭해 간선을 복제하면 짝수 차수가 회복되어 다시 오일러 문제가 된다.

같은 구조가 근사 알고리즘 쪽에서도 나온다. 메트릭 외판원 문제의 크리스토피디스 $3/2$ -근사는 최소 신장 트리에 홀수 차수 정점의 최소 매칭을 붙여 오일러 회로를 만든 뒤 중복 방문을 지름길로 건너뛴다. 한쪽에서는 정확 알고리즘의 뼈대, 다른 쪽에서는 근사의 뼈대인 셈이다.

9. 그 밖의 응용[편집]

공구 경로 계획. 레이저·플라즈마 절단, 펜 플로터, 3D 프린터의 연속 압출 경로는 “모든 선분을 지나되 이동을 최소로”라 오일러/아크 라우팅 문제다. 프린터의 리트랙션 횟수가 곧 되밟기 비용.
회로·배관 검사. 모든 링크를 검증하는 시험 경로 생성.
메시 처리. 삼각형 스트립화나 정점 캐시 최적화에서 인접 그래프의 긴 경로를 뽑는 문제가 오일러 계열로 정식화되곤 한다.
미로와 퍼즐. 한붓그리기 퍼즐의 판정은 홀수 차수 정점을 세는 것으로 3초면 끝난다.

10. 관련 문서[편집]

그래서 알고리즘 수업에서 이 둘을 붙여 가르친다. “간선 vs 정점”만 바꿨는데 P와 NP-완전이 갈린다는 걸 처음 보면 대개 납득이 안 가고, 납득하려고 해밀턴 회로 다항 알고리즘을 짜 보다가 학기를 보낸 사람이 매년 나온다. 참고로 성공하면 100만 달러다. ↩
오일러의 1736년 논문이 실제로 보인 것은 “쾨니히스베르크에서는 불가능하다”는 부정 쪽이었다. 존재 조건의 충분성은 진술만 남기고 증명을 생략했다. 수학에서 “it is easy to see”의 원조 격이며, 실제로 쉽긴 했지만 137년이 걸렸다. ↩
이 전환의 대가도 있다. $k$ -mer로 부수는 순간 리드 하나가 들고 있던 장거리 연결 정보가 통째로 버려진다. 그래서 리드가 길어진 나노포어·PacBio 시대에는 OLC 계열(정확히는 그 후예인 스트링 그래프)이 다시 주류로 돌아왔다. 알고리즘의 우열은 데이터의 모양이 정한다는 교훈. ↩