그래프 이론

점들과 그 사이를 잇는 선, 그래프는 그게 전부입니다. 그런데 같은 그림이 도로 지도, 친구 관계망, 분자, 인터넷을 나타내고, 그에 대해 던질 수 있는 질문들은 필요한 색의 수부터 한붓그리기가 가능한지까지, 1736년부터 수학자들을 바쁘게 해 왔습니다.

정점 10개로 된 그래프인 페테르센 그래프. 같은 색의 두 정점을 잇는 간선이 없도록 정점이 세 가지 색으로 칠해져 있다
정점 10개로 된 그래프인 페테르센 그래프. 같은 색의 두 정점을 잇는 간선이 없도록 정점이 세 가지 색으로 칠해져 있다

정점과 간선

그래프에는 정점(노드라고도 함)과 간선이 있고, 각 간선은 두 정점을 잇습니다. 정점을 어디에 그리는지는 중요하지 않고 어떤 쌍이 이어져 있는지만 중요하므로, 같은 그래프도 종이 위에서는 전혀 달라 보일 수 있습니다. 놀이터의 그래프는 단순 그래프입니다. 정점에서 자기 자신으로 가는 간선은 없고, 두 정점 사이의 간선은 많아야 하나입니다. 정점이 n개이면 간선은 최대 n(n − 1) / 2개이고, 간선을 모두 가진 그래프를 완전 그래프라고 합니다. K5는 정점 다섯 개의 완전 그래프입니다.

차수와 악수 보조정리

정점의 차수는 그 정점에 연결된 간선의 수입니다. 모든 차수를 더하면 정확히 간선 수의 두 배가 되는데, 모든 간선에는 끝이 두 개 있고 각 끝에서 한 번씩 세어지기 때문입니다. 이것이 악수 보조정리입니다. 어떤 모임에서든 사람마다 센 악수 횟수를 더하면 전체 악수 횟수의 두 배가 됩니다. 이는 차수가 홀수인 정점의 수가 항상 짝수라는 뜻이기도 합니다. 모든 정점의 차수가 같은 k인 그래프를 k-정규 그래프라고 합니다.

연결 그래프, 트리, 사이클

어느 정점에서든 간선을 따라 다른 모든 정점에 갈 수 있으면 그래프는 연결되어 있습니다. 그렇지 않으면 연결 요소라 부르는 여러 부분으로 나뉩니다. 사이클은 같은 정점을 두 번 지나지 않고 출발점으로 돌아오는 순환 경로이고, 가장 짧은 사이클의 길이를 둘레라고 합니다. 사이클이 없는 연결 그래프가 트리이며, 정점이 n개인 트리에는 항상 정확히 n − 1개의 간선이 있습니다. 하나가 적으면 끊어지고, 하나가 많으면 사이클이 생깁니다. 모든 연결 그래프에는 신장 트리, 즉 간선의 일부만 써서 모든 정점에 닿는 트리가 들어 있습니다.

이분 그래프와 채색

같은 색의 두 정점을 잇는 간선이 없도록 정점에 색을 칠합니다. 이렇게 하는 데 필요한 최소 색 수가 채색수입니다. 한 가지 색으로 충분한 것은 간선이 없을 때뿐입니다. 두 가지 색으로 충분한 것은 정확히 그래프가 이분 그래프일 때, 즉 정점이 두 편으로 나뉘고 모든 간선이 두 편을 가로지를 때입니다. 1936년 데네시 쾨니그는 이것이 길이가 홀수인 사이클이 없는 것과 같다는 것을 보였습니다. 홀수 사이클은 두 색을 번갈아 칠할 수 없기 때문입니다. 세 가지 이상의 색에 대해서는 이런 간단한 판정법이 알려져 있지 않습니다. 세 가지 색으로 충분한지 판정하는 문제는 NP-완전이므로, 프로그램은 놀이터처럼 탐색을 합니다.

예시: 페테르센 그래프

오각형 A–B–C–D–E와 그 안에 있는 오각별 F–H–J–G–I를 놓고, 오각형의 각 꼭짓점을 별의 한 점과 잇습니다: A–F, B–G, C–H, D–I, E–J. 이것이 정점 10개와 간선 15개로 된 페테르센 그래프입니다. 모든 정점의 차수가 3이므로 차수의 합은 15의 두 배인 30입니다. 최단 사이클의 길이가 5이므로 삼각형은 없지만, 오각형은 홀수 사이클이므로 이분 그래프가 아니고 3가지 색이 필요합니다. 어느 두 정점도 간선 2개 이내로 떨어져 있으므로 지름은 2입니다. 열 개의 차수가 모두 홀수이므로 오일러 경로가 없고, 교차 없이 그릴 수도 없습니다.

오일러 경로와 쾨니히스베르크의 다리

쾨니히스베르크라는 도시에는 네 개의 땅을 잇는 일곱 개의 다리가 있었고, 사람들은 모든 다리를 정확히 한 번씩 건너며 걸을 수 있는지 궁금해했습니다. 1736년 레온하르트 오일러는 그것이 불가능하다는 것을 보였고, 그래프 이론이 시작되었습니다. 걸어서 어떤 땅을 지날 때마다 다리 두 개를 쓰므로, 다리 수가 홀수일 수 있는 것은 출발점과 도착점뿐인데, 쾨니히스베르크의 네 땅은 모두 다리 수가 홀수였습니다. 오늘날 모든 간선을 한 번씩 지나는 경로를 오일러 경로라 하고, 출발한 곳에서 끝나면 오일러 회로라고 합니다. 1873년 카를 히어홀처는 이 조건이 충분하기도 하다는 것을 증명했습니다. 모든 간선이 한 덩어리로 이어져 있고 홀수 차수가 두 개 이하이면 그런 경로가 존재하며, 순환 경로들을 이어 붙이는 그의 방법은 지금도 그 경로를 찾아냅니다.

쾨니히스베르크(지도에는 Koningsberga)의 역사적 조감도. 프레겔 강과 일곱 다리 문제의 중심에 있는 섬이 보인다. 1736년 레온하르트 오일러는 각 다리를 정확히 한 번씩 건너는 산책이 불가능함을 보였고, 그래프 이론이 시작되었다.
쾨니히스베르크(지도에는 Koningsberga)의 역사적 조감도. 프레겔 강과 일곱 다리 문제의 중심에 있는 섬이 보인다. 1736년 레온하르트 오일러는 각 다리를 정확히 한 번씩 건너는 산책이 불가능함을 보였고, 그래프 이론이 시작되었다.
레온하르트 오일러의 초상
레온하르트 오일러의 초상

거리, 지름, 여그래프

두 정점 사이의 거리는 두 정점을 잇는 경로에 있는 간선의 최소 개수이고, 지름은 그래프에서 가장 큰 거리입니다. 연결되지 않은 그래프에서는 지름이 무한대입니다. 소셜 네트워크는 지름이 작은데, 이것이 여섯 단계 분리 이론의 바탕이 되는 생각입니다. 그래프의 여그래프는 같은 정점을 가지며, 이어져 있지 않던 쌍을 정확히 잇습니다. 그래프와 그 여그래프 중 적어도 하나는 항상 연결되어 있습니다.

직접 해 보기

놀이터를 열면 세 가지 색으로 칠한 페테르센 그래프가 나옵니다. 차수를 클릭해 악수 보조정리를 확인하고, 이분 그래프를 클릭해 홀수 사이클을 본 다음, 정육면체를 불러와 두 편이 나타나는 것을 보세요. 집을 불러와 오일러 경로를 클릭하면 한붓그리기를 어디서 시작해야 하는지 알 수 있습니다. 직접 그래프를 그리고 간선을 하나씩 더해 보세요. 최단 사이클이 짧아지고, 지름이 줄어들고, K4의 마지막 간선이 들어갈 때 채색수가 올라가는 것을 볼 수 있습니다.

자주 묻는 질문

경로, 트레일, 워크는 어떻게 다른가요?

워크는 간선으로 이어진 정점들의 아무 나열이며, 정점과 간선을 모두 반복할 수 있습니다. 트레일은 정점은 반복해도 되지만 간선은 반복할 수 없는데, 그래서 오일러 경로(엄밀히는 오일러 트레일)는 한 정점을 여러 번 지날 수 있습니다. 경로는 둘 다 반복하지 않습니다.

4색 정리란 무엇인가요?

간선을 교차시키지 않고 종이에 그릴 수 있는 모든 그래프는 최대 네 가지 색으로 칠할 수 있다는 정리로, 어떤 지도든 네 가지 색이면 충분하다는 뜻입니다. 1976년 케네스 아펠과 볼프강 하켄이 컴퓨터의 도움을 받아 증명했으며, 이런 방식으로 증명된 최초의 주요 정리입니다.

해밀턴 사이클이란 무엇인가요?

모든 간선이 아니라 모든 정점을 정확히 한 번씩 방문하는 사이클입니다. 오일러 문제와 비슷해 보이지만, 간단한 판정법은 알려져 있지 않습니다. 그래프에 해밀턴 사이클이 있는지 판정하는 문제는 NP-완전입니다. 페테르센 그래프에는 해밀턴 경로는 있지만 해밀턴 사이클은 없습니다.

그래프 이론은 어디에 쓰이나요?

길 찾기 서비스는 도로 그래프를 탐색하고, 검색 엔진은 링크를 바탕으로 웹 페이지의 순위를 매기며, 컴파일러는 그래프를 채색해 프로세서 레지스터를 나눠 쓰고, 시간표는 충돌 그래프를 채색해 겹침을 피합니다. 화학자는 분자를 그래프로 보고 개수를 세며, 컴퓨터 네트워크와 전력망, 친구 관계망도 그래프로 연구됩니다.

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

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

그래프 이론 놀이터 열기