한붓그리기(오일러 경로) 판정 계산기
선 목록을 넣으면 정점의 차수를 세어 한붓그리기가 되는지 판정하고, 가능하면 실제 경로 하나를 찾아 줍니다. 쾨니히스베르크의 다리가 왜 안 되는지도 차수로 확인할 수 있습니다.
선 목록 (한 줄에 하나)
«A B»는 A와 B를 잇는 선입니다. 같은 줄을 두 번 적으면 두 선으로 셉니다 — 쾨니히스베르크의 다리가 실제로 그렇습니다.
한붓그리기
한붓그리기 불가능
홀수 차수 정점이 4개입니다. 0개면 회로, 2개면 경로이고 그 밖에는 방법이 없습니다.
| 정점 | 차수 | 홀짝 |
|---|---|---|
| A | 5 | 홀수 |
| B | 3 | 홀수 |
| C | 3 | 홀수 |
| D | 3 | 홀수 |
계산 방법
- 1선을 한 줄에 하나씩 넣습니다. 같은 줄을 두 번 적으면 두 선으로 셉니다.
- 2정점별 차수와 홀수 차수 정점의 개수를 확인합니다.
- 3가능하면 실제 경로가 나오고, 안 되면 왜 안 되는지 알려 줍니다.
- 4선을 더하거나 빼 가며 홀수 차수가 어떻게 바뀌는지 살펴봅니다.
자주 묻는 질문
선이 있는 정점들이 하나로 이어져 있고, 홀수 차수 정점이 0개이거나 2개여야 합니다. 0개면 아무 데서나 시작해 제자리로 돌아오는 오일러 회로가 있고, 2개면 그 둘 중 하나에서 시작해 다른 하나에서 끝나는 오일러 경로가 있습니다. 4개 이상이면 방법이 없습니다.
지나가는 점은 들어온 선과 나가는 선이 짝을 이뤄야 하므로 차수가 짝수여야 하기 때문입니다. 짝이 안 맞는 점은 시작점이거나 끝점일 수밖에 없는데 그 자리는 많아야 둘입니다. 그래서 홀수 차수 정점이 셋 이상이면 답이 아예 없습니다.
네 땅의 차수가 5·3·3·3으로 모두 홀수이기 때문입니다. 시작점과 끝점이 될 수 있는 자리는 둘뿐인데 홀수 차수 정점이 넷이라 자리가 모자랍니다. 다리를 하나 없애거나 새로 놓아 홀수 차수를 둘로 줄이면 그때부터 가능해집니다.
없습니다. 모든 차수를 더하면 선 하나가 양쪽에 하나씩 보태므로 언제나 선의 수의 두 배, 곧 짝수가 되기 때문입니다. 그래서 홀수 차수 정점은 반드시 짝수 개입니다.
오일러는 모든 «선»을 한 번씩, 해밀턴은 모든 «점»을 한 번씩 지납니다. 이름이 비슷하지만 난이도가 전혀 달라, 오일러는 차수만 세면 바로 판정되는 반면 해밀턴은 빠른 판정법이 알려져 있지 않은 NP-완전 문제입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 같은 두 점을 잇는 선을 여러 번 적으면 그만큼 여러 선으로 셉니다. 쾨니히스베르크의 다리가 실제로 그런 다중 그래프입니다.
- 자기 자신으로 돌아오는 고리는 차수를 2 더합니다. 들어왔다 나가기 때문이며, 그래서 고리는 홀짝을 바꾸지 않습니다.
- 경로가 여러 개일 때는 «이름이 앞서는 이웃부터» 가는 규약으로 그중 하나를 보여 줍니다. 다른 순서로 가도 모든 선을 한 번씩 지나면 똑같이 옳은 답입니다.
- 방향이 있는 그래프는 다루지 않습니다. 방향 그래프에서는 들어오는 차수와 나가는 차수를 따로 세는 다른 조건이 필요합니다.
- 선은 60개까지 봅니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.