그래프이론 세상을 바꾸다

18세기 쾨니히스베르크에는 강을 건너는 다리가 일곱 개 있었다. 모든 다리를 한 번씩만 건너 출발점으로 돌아올 수 있는지가 시민들 사이의 물음이었다.

오일러의 정리

레온하르트 오일러는 1736년 이 문제에 답했다. 불가능하다는 것이었다.

그의 접근은 지도를 버리는 데서 시작됐다. 땅덩어리의 크기와 다리의 길이는 문제와 무관하다. 중요한 것은 어느 땅이 어느 땅과 이어져 있는지뿐이다. 땅을 점으로, 다리를 선으로 바꾸면 문제가 단순해진다.

그다음 논증은 이렇다. 어떤 점을 지나간다면 들어오는 선 하나와 나가는 선 하나를 쓴다. 따라서 출발점과 도착점을 뺀 모든 점에서는 선의 개수가 짝수여야 한다.

쾨니히스베르크의 네 땅은 모두 홀수 개의 다리와 이어져 있었다. 그래서 불가능했다.

이 논증은 거리와 모양을 다루지 않고 연결 관계만 다뤘다는 점에서 새로웠다. 그래프 이론과 위상수학의 출발점으로 꼽힌다.

최단 경로

그래프에서 가장 널리 쓰이는 문제는 두 점 사이의 최단 경로를 찾는 것이다.

다익스트라 알고리즘이 대표적이다. 출발점에서 가까운 점부터 차례로 확정해 나가는 방식으로, 각 점까지의 최단 거리를 하나씩 확정한다.

지도 안내 서비스가 이 계열의 방법을 쓴다. 다만 실제 도로망은 정점이 수억 개에 이르므로, 기본 알고리즘을 그대로 쓰지 않는다. 미리 계산해 둔 정보를 활용해 탐색 범위를 줄이는 기법이 함께 쓰인다.

중요한 점 찾기

웹 페이지를 점으로, 링크를 선으로 보면 웹 전체가 하나의 거대한 그래프가 된다.

초기 검색엔진의 순위 알고리즘은 이 구조를 이용했다. 많은 페이지가 링크하는 페이지를 중요하게 보되, 중요한 페이지가 건 링크에 더 큰 무게를 두는 방식이다. 중요도가 링크를 따라 흐르는 구조이므로 계산이 순환적이며, 반복 계산으로 수렴값을 구한다.

같은 아이디어가 논문 인용망, 감염 경로 추적, 금융 거래망 분석에 쓰인다.

좁은 세상

사회 관계망을 그래프로 보면 특이한 성질이 나타난다. 임의의 두 사람 사이의 거리가 생각보다 짧다는 점이다.

대부분의 사람은 가까운 사람들끼리 뭉쳐 있다. 그런데 소수의 먼 연결이 섞이면 전체의 거리가 급격히 줄어든다. 이 구조를 좁은 세상 연결망이라 한다.

연결 수의 분포도 고르지 않다. 대부분은 적은 수의 연결을 갖고, 소수가 아주 많은 연결을 갖는다. 이런 구조는 무작위 고장에는 강하지만 중심 지점을 겨냥한 공격에는 약하다는 성질이 있다. 통신망과 전력망의 안정성을 논할 때 인용된다.

어려운 문제

그래프 문제라고 모두 빨리 풀리지는 않는다.

모든 도시를 한 번씩 들르는 최단 경로를 찾는 문제는 도시 수가 늘면 경우의 수가 폭발한다. 효율적인 해법이 알려져 있지 않으며, 존재하는지도 밝혀지지 않았다.

실무에서는 정확한 최적해 대신 충분히 좋은 답을 빠르게 찾는 방법을 쓴다. 물류 배송 경로를 짜는 작업이 대표적이다.