-
정규
-
완전
그래프 이론 놀이터
그래프는 정점이라 부르는 점들을 간선이라 부르는 선으로 이은 것입니다. 여기서 몇 번 클릭해 그래프를 그리면, 놀이터가 어떤 그래프인지 알려 줍니다. 몇 덩어리로 나뉘는지, 트리인지, 최소 몇 가지 색이 필요한지, 한붓그리기가 가능한지 등을요. 성질을 클릭하면 그래프 위에서 볼 수 있습니다. 간선을 바꾸고 답이 어떻게 달라지는지 지켜보세요. 빈 곳을 클릭하면 정점이 추가됩니다. 정점을 클릭한 뒤 다른 정점을 클릭하면 간선으로 이어지고, 한 번 더 하면 그 간선이 지워집니다. 정점을 끌어서 옮길 수 있습니다. 클릭을 지우기로 바꾸고 정점이나 간선을 클릭하면 삭제됩니다. 정점을 선택한 상태에서 Delete 키는 정점을 지우고, Escape 키는 선택을 해제합니다. 성질을 클릭하면 그래프 위에 표시됩니다. 예시는 잘 알려진 그래프를 불러오고, 무작위 그래프는 그래프를 새로 만들고, 정리는 정점을 고르게 펼치고, 여그래프는 이어져 있지 않던 쌍만 정확히 잇습니다. Ctrl+Z로 한 단계 되돌립니다.
작동 원리
- 빈 곳을 클릭해 정점을 추가하세요. 정점을 클릭한 뒤 다른 정점을 클릭하면 이어지고, 한 번 더 하면 간선이 지워집니다. 정점을 끌어서 옮길 수 있습니다.
- 그래프 아래의 성질을 읽고, 하나를 클릭해 표시해 보세요. 채색, 두 편, 오일러 경로, 신장 트리, 최단 사이클, 지름을 볼 수 있습니다.
- 페테르센 그래프 같은 예시를 불러오거나, 무작위 그래프를 만들거나, 여그래프를 구하거나, 클릭을 지우기로 바꿔 정점과 간선을 삭제해 보세요.
성질의 의미
정점의 차수는 그 정점에 연결된 간선의 수입니다. 모든 정점이 간선을 따라 다른 모든 정점에 갈 수 있으면 그래프는 연결되어 있고, 연결되어 있으면서 사이클이 없으면 트리입니다. 정점을 두 편으로 나눠 모든 간선이 두 편을 가로지르게 할 수 있으면 이분 그래프인데, 이는 길이가 홀수인 사이클이 없는 것과 정확히 같습니다. 채색수는 이웃한 정점끼리 다른 색이 되도록 칠하는 데 필요한 최소 색 수입니다. 최단 사이클의 길이를 둘레라고 하며, 지름은 두 정점 사이 거리(간선 수로 셈)의 최댓값입니다.
한붓그리기
오일러 경로는 모든 간선을 정확히 한 번씩 지납니다. 1736년 레온하르트 오일러는 쾨니히스베르크의 일곱 다리 문제에서 무엇이 걸림돌인지 알아냈습니다. 경로가 정점을 지날 때마다 그 정점의 간선을 두 개씩 쓴다는 것입니다. 따라서 모든 차수가 짝수여서 출발한 곳에서 끝날 수 있거나, 정확히 두 차수가 홀수여서 그중 하나에서 다른 하나로 가야 합니다. 나중에 카를 히어홀처는 모든 간선이 한 덩어리로 이어져 있다면 이 조건으로 충분하다는 것도 증명했습니다. 집 예시를 불러와 한붓그리기를 어디서 시작해야 하는지 찾아보세요.
자주 묻는 질문
그래프 이론에서 그래프란 무엇인가요?
정점 또는 노드라 부르는 점들의 집합과, 그중 일부 쌍을 잇는 간선이라 부르는 선입니다. 함수의 그래프와는 달리, 무엇이 무엇과 이어져 있는지만 나타냅니다. 도로 지도, 소셜 네트워크, 분자, 컴퓨터 네트워크는 모두 그래프입니다.
채색수는 어떻게 구하나요?
놀이터는 먼저 한 가지 색으로 그래프를 칠해 보고, 다음에 두 가지, 세 가지 하는 식으로 늘려 갑니다. 각 색 수마다 의미 있는 모든 방법을 탐색하며, 항상 이웃이 이미 가장 많은 색을 쓰고 있는 정점부터 칠합니다. 처음으로 성공한 수가 채색수입니다. 여기서 그릴 수 있는 그래프라면 길어야 잠깐이면 끝나지만, 매우 어려운 그래프에서는 탐색을 일찍 멈추고 그 값을 상한으로 표시합니다.
그래프에 오일러 경로가 있는 것은 언제인가요?
모든 간선이 한 덩어리로 이어져 있고 차수가 홀수인 정점이 두 개 이하일 때입니다. 홀수 정점이 없으면 출발한 곳에서 끝나는 오일러 회로가 있고, 두 개이면 모든 오일러 경로가 그중 하나에서 시작해 다른 하나에서 끝납니다. 홀수 정점의 수는 항상 짝수이므로 정확히 하나일 수는 없습니다.
그래프의 여그래프란 무엇인가요?
같은 정점을 가지면서, 원래 이어져 있지 않던 쌍을 정확히 간선으로 갖는 그래프입니다. 여그래프의 여그래프는 처음 그래프로 돌아옵니다. 예를 들어 페테르센 그래프의 여그래프는 6-정규 그래프인데, 각 정점이 나머지 9개 중 3개와 이어져 있었기 때문입니다.
페테르센 그래프는 왜 유명한가요?
정점 10개와 간선 15개로 된 작은 그래프이지만, 많은 낙관적인 추측의 반례가 됩니다. 모든 정점의 차수가 3이고, 최단 사이클의 길이는 5이며, 어느 두 정점도 간선 2개 이내로 떨어져 있고, 간선을 교차시키지 않고는 그릴 수 없습니다. 놀이터는 이 그래프로 시작합니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동