오일러 경로 시각화
그래프의 모든 간선을 정확히 한 번씩 지나는 오일러 경로와 회로를 찾는 과정을 학습하세요
그래프★★☆
속도
1 / 1정점 수: 0간선 수: 0방문된 간선: 0
유형:
현재 간선 방문된 간선 홀수 차수 정점 남은 간선
Hierholzer 알고리즘이 간선을 탐색하며 오일러 경로/회로를 구성하는 과정을 관찰하세요.
Hierholzer 알고리즘이 간선을 탐색하며 오일러 경로/회로를 구성하는 과정을 관찰하세요.
오일러 경로란?
그래프의 모든 간선을 정확히 한 번씩 지나는 경로입니다. 시작점으로 돌아오면 오일러 회로(circuit), 아니면 오일러 경로(path)입니다. 쾨니히스베르크 다리 문제로 유명합니다.
사용 방법
- 1그래프를 생성하면 오일러 경로/회로 존재 여부를 자동 판별합니다
- 2실행하면 Hierholzer 알고리즘으로 경로를 찾는 과정을 보여줍니다
- 3홀수 차수 정점이 표시되어 존재 조건을 직관적으로 이해할 수 있습니다
- 4방향/무방향 그래프를 전환해보세요
동작 원리
- 1존재 조건 확인: 무방향 — 홀수 차수 정점 0개(회로) 또는 2개(경로)
- 2방향 그래프 — 모든 in-degree == out-degree(회로), 또는 정확히 하나가 ±1 차이(경로)
- 3Hierholzer: 임의 정점에서 출발, 간선을 사용하며 진행하다 막히면 서킷에 추가
- 4이전에 미사용 간선이 남은 정점으로 돌아가 확장을 반복합니다
실무 활용
- •쓰레기 수거/우편 배달 경로 최적화 (Chinese Postman Problem)
- •DNA 시퀀싱에서 De Bruijn 그래프를 이용한 서열 조립
- •PCB 회로 기판 테스트의 배선 경로 설계
- •네트워크 장비 테스트 — 모든 링크를 한 번씩 검사
비슷한 알고리즘
- •해밀턴 경로 — 모든 '정점'을 한 번씩 방문 (NP-완전, 오일러는 P)
- •Chinese Postman — 오일러 경로가 없을 때 간선 중복을 최소화하는 문제
- •DFS — 오일러 경로 알고리즘의 기반 탐색 방법
학습 팁
- •먼저 차수를 세어 오일러 경로/회로 존재 여부를 판단하는 연습을 하세요
- •Hierholzer 알고리즘의 서킷 병합 과정에 집중하세요
- •쾨니히스베르크 다리 문제를 그래프로 모델링해보세요
자주 묻는 질문
Q. 오일러 경로와 해밀턴 경로 차이?
A. 오일러는 모든 간선을, 해밀턴은 모든 정점을 한 번씩 방문합니다. 오일러는 다항 시간, 해밀턴은 NP-완전입니다.
Q. 연결 그래프가 아니면?
A. 간선이 있는 부분이 연결되어야 합니다. 고립된 정점은 무시합니다.