한붓그리기
홀수 꼭짓점
그린 변
그리는 방법 수

    • 홀수 꼭짓점 0개: 어느 꼭짓점에서 출발해도 그 자리로 돌아오는 회로
    • 홀수 꼭짓점 2개: 한쪽에서 다른 쪽으로 가는 경로
    • 4개 이상: 한붓그리기 불가능

    방법

    오일러 경로와 오일러 회로 더 알아보기

    오일러 경로 찾기

    산타클로스의 집을 연필을 떼지 않고, 어떤 선도 두 번 덧긋지 않고 그릴 수 있을까요? 그릴 수 있습니다. 다만 아래 두 모서리 중 하나에서 시작할 때만 가능하고, 각 모서리마다 44가지 방법이 있습니다. 이유는 꼭짓점의 차수, 곧 그곳에 모이는 선의 개수입니다. 연필이 한 꼭짓점을 지날 때마다 그 꼭짓점의 선을 두 개씩 씁니다. 레온하르트 오일러는 1736년 쾨니히스베르크의 일곱 다리에서 이 규칙을 찾아냈습니다. 직접 도형을 따라 그리며 어디서 왜 막히는지 보고, 힌트를 받거나 알고리즘이 그리는 모습을 지켜보세요. 도형을 고르고 따라 그리세요. 먼저 꼭짓점을 눌러 시작한 다음 변이나 다음 꼭짓점을 차례로 누르거나, 꼭짓점에서 꼭짓점으로 끌면 됩니다. 각 변은 한 번만 쓸 수 있습니다. 되돌리기는 한 수를 물리고, 힌트는 다음에 안전한 변을 보여 주며, 풀기는 플뢰리 알고리즘이나 히어홀처 알고리즘을 한 단계씩 재생합니다. 차수가 홀수인 꼭짓점은 채워져 있고, 꼭짓점 옆 표시는 그 차수입니다. 그리기 모드에서는 빈 곳을 누르면 꼭짓점이 생기고, 두 꼭짓점을 누르면 이어지며, 한 번 더 누르면 변이 하나 더 생깁니다. 꼭짓점은 끌어서 옮길 수 있습니다. 지우기는 꼭짓점과 변을 없앱니다. 홀수 꼭짓점이 두 개를 넘으면 추가를 눌러 한붓그리기가 되도록 하는 변을 넣을 수 있습니다.

    작동 원리

    1. 쾨니히스베르크의 일곱 다리, 산타클로스의 집, 별 같은 도형을 고르거나, 그리기 모드에서 직접 그려 보세요. 두 꼭짓점 사이에 변을 원하는 만큼 그을 수 있습니다.
    2. 꼭짓점을 눌러 시작한 다음 변이나 꼭짓점을 차례로 누르거나, 꼭짓점에서 꼭짓점으로 끄세요. 막히면 상태 줄이 이유를 알려 줍니다. 되돌리기는 한 수를 물리고, 힌트는 안전한 변을 보여 줍니다.
    3. 도형 아래의 차수 규칙을 읽고, 그릴 수 없는 도형에는 제안된 변을 추가하거나, 풀기를 눌러 플뢰리나 히어홀처 알고리즘이 한 단계씩 그리는 모습을 보세요.

    왜 홀수 꼭짓점이 결정하는가

    꼭짓점을 지나는 획은 한 선으로 들어와 다른 선으로 나갑니다. 즉 그 꼭짓점의 선을 둘씩 짝지어 씁니다. 선이 짝 없이 남을 수 있는 곳은 획이 시작하거나 끝나는 자리뿐입니다. 그래서 선의 개수가 홀수인 꼭짓점은 시작점이거나 끝점이어야 합니다. 홀수 꼭짓점이 없으면 획은 시작한 자리에서 끝나며, 이것이 오일러 회로입니다. 둘이면 한쪽에서 다른 쪽으로 가며, 이것이 오일러 경로입니다. 넷 이상이면 한 획에 비해 끝이 너무 많고, 홀수 꼭짓점이 k개면 k/2획이 필요합니다. 쾨니히스베르크에는 네 땅이 있었고 다리는 다섯, 셋, 셋, 셋이었습니다. 넷 모두 홀수여서 어떤 산책도 모든 다리를 한 번씩 건널 수 없었습니다. 그중 둘 사이에 다리를 하나만 새로 놓았다면 산책이 가능했을 것입니다.

    플뢰리와 히어홀처 알고리즘

    도형을 그릴 수 있다는 것을 아는 일과 실제로 그리는 일은 다릅니다. 부주의한 한 획은 아직 필요한 선들에서 스스로를 끊어 버릴 수 있습니다. 1883년 플뢰리의 알고리즘은 한 가지 규칙으로 이를 막습니다. 다리, 곧 없애면 남은 선들이 두 조각으로 갈라지는 선은 다른 선이 없을 때를 빼고는 결코 건너지 말라는 규칙입니다. 1873년에 발표된 논문에서 비롯한 히어홀처의 알고리즘은 더 빠릅니다. 먼저 막힐 때까지 아무 데로나 걸어가고(이는 출발점에서만 일어납니다), 다음에는 순회 위에서 아직 빈 선이 남은 꼭짓점에서 닫힌 고리를 하나 더 돈 뒤 순회에 끼워 넣습니다. 걸리는 시간은 변의 개수에 비례하며, 컴퓨터는 이 방법으로 오일러 경로를 찾습니다.

    자주 묻는 질문

    오일러 경로와 오일러 회로는 어떻게 다른가요?

    둘 다 그래프의 모든 변을 정확히 한 번씩 씁니다. 오일러 회로는 시작한 자리에서 끝나고, 오일러 경로는 다른 자리에서 끝납니다. 연결 그래프는 모든 꼭짓점의 차수가 짝수일 때 회로를, 차수가 홀수인 꼭짓점이 정확히 둘일 때 경로를 가집니다. 그때 경로는 한쪽에서 다른 쪽으로 갑니다.

    쾨니히스베르크의 일곱 다리를 한 번씩 건널 수 없는 이유는 무엇인가요?

    각 땅을 꼭짓점으로, 각 다리를 변으로 그려 보세요. 크나이프호프섬에는 다리가 다섯, 나머지 세 땅에는 셋씩 있었으므로 네 꼭짓점이 모두 홀수입니다. 산책은 홀수 꼭짓점에서만 시작하거나 끝날 수 있는데 넷은 너무 많습니다. 그중 둘 사이에 다리를 하나 더하면 홀수 꼭짓점이 둘만 남아 산책이 가능해집니다.

    산타클로스의 집은 몇 가지 방법으로 그릴 수 있나요?

    아래 두 모서리에서 각각 44가지, 모두 88가지입니다. 순서나 방향이 다르면 다른 방법으로 셉니다. 다른 꼭짓점에서는 그릴 수 없습니다. 선의 개수가 홀수인 곳은 그 두 모서리뿐이기 때문입니다. 이 앱은 작은 도형의 방법 수를 이렇게 셉니다.

    그래프의 다리란 무엇인가요?

    없애면 연결 그래프가 두 조각으로 갈라지는 변입니다. 플뢰리 알고리즘은 다른 선택이 있는 한 남은 변들 가운데 다리를 결코 건너지 않습니다. 건너면 도형의 일부가 뒤에 남기 때문입니다. 이 앱에서는 다리를 너무 일찍 건너 막힌 획에 그것이 몇 번째 수였는지 알려 줍니다.

    두 꼭짓점 사이에 변이 여러 개일 수 있나요?

    그럴 수 있습니다. 평행한 변이 있는 그래프를 다중 그래프라 하며, 쾨니히스베르크에는 그것이 필요합니다. 크나이프호프와 각 기슭은 다리 두 개로 이어져 있었습니다. 그리기 모드에서 두 꼭짓점을 다시 누르면 그 사이에 변을 하나 더, 최대 네 개까지 넣을 수 있습니다. 차수 규칙은 그대로 적용되며 모든 변을 셉니다.

    시도해 볼 준비가 되셨나요?

    브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

    편집기로 이동