존 호프크로프트 / 로버트 타잔

그래프의 평면성 검사

‘컴퓨터 과학’이라는 식당에서 ‘그래프’는 단골 메뉴이다. 그런데 이 ‘그래프^graph‘라는 단어에서 막대 그래프나 컴퓨터 그래픽 같은 단어를 연상하면 아주 곤란하다. 여기서 말하는 그래프는 수학의 세계에서 다루는 특별한 형태를 지칭한다. 수학의 세계에서 다루는 그래프는 다음과 같이 정의된다.

,
여기서 는 꼭짓점vertex의 집합이고, 는 꼭짓점과 꼭짓점을 연결한 변edge의 집합니다.

쉽게 풀어서 말하자면, 선으로 연결된 점들의 집합인 셈이다. 컴퓨터 과학에서 왜 그래프가 중요하냐면 워낙 여기저기에서 튀어나오기 때문이다. 다음은 그래프의 예들이다.

이렇듯 컴퓨터 과학의 다양한 분야에서 그래프가 중요한 도구로 사용되고 있기 때문에 그래프 자체의 특성에 대한 연구도 활발할 수밖에 없다.

그렇다면 평면성^planarity이란 무엇일까? 우리가 위에 예로 든 것들은 모두 평면 위에 그려 놓은 형태이지만 이는 종이가 평면이기 때문에 어쩔 수 없이 그렇게 보일 뿐, 실제로 그래프가 만드시 평면적이어야 할 이유는 없다. 그래프의 정의에 따르면 꼭짓점이 변으로 연결되어 있는 형태이기만 하면 되기 때문이다. 그런데 만약 그래프를 평면 위에 그려 놓았을 때 서로 가로지르는 변^edge들이 없다면 우리는 그 그래프에 ‘평면성’이 있다고 말한다. 위의 나온 네 개의 예는 공교롭게도 모두 ‘평면성’을 가지고 있다. 하지만 아래의 그래프는 ‘평면성’이 없다.

한 가지 주의할 점이 있다. 그래프의 정의를 보면 변^edge이 직선이어야 한다는 조항이 없다. 앞의 모든 예에서 변^edge이 직선으로 표현된 것은 그냥 편의상 그렇게 그렸을 뿐이다.

‘평면성’ 논의가 수학자들의 지적 놀이로만 보인다면 천만의 말씀이다. 예를 들어, 전자회로에서 매우 중요하게 쓰인다. 전자회로는 부품(혹은 소자)들이 전선으로 연결되어 있는 형태이다. 부품이 꼭짓점이고 전선이 변이라면 결국 그래프로 표현이 가능하다. 그런데 요즘은 전선을 사용하지 않고 기판 위에 금속 패턴을 만들어서 연결한다. 그래서 전자회로를 구현한다는 것은, 결국 부품을 기판이라는 평면 위에 배치하고 부품 간의 연결을 위해서 기판 위에 금속 패턴선으로 만들어주는 일로 바뀌게 된다. 그런데 이때 부품을 연결해 주는 패턴선들이 서로 만나서는 안 된다. 왜냐하면 합선이 되면 전기 신호가 왜곡되기 때문이다. 따라서, 기판 위에 전자회로를 안전하게 구현하기 위해서는 그 회로가 평면성을 가져야만 한다.

그래프의 평면성을 따지는 알고리듬을 만들기 위해서는, 그래프를 표현하기 위한 자료구조가 필요하다. 초창기에는 2차원 행렬을 사용했다. 앞의 예 중에서 최단 경로 찾기용 그래프를 2차원 행렬로 표현하면 다음과 같다.

이렇게 하면 직관적으로 이해는 쉽지만 공간의 낭비가 많이 생긴다. (사실, 위의 표는 대각선을 중심으로 대칭이어서 사실 절반으로 줄일 수 있기는 하다.) 이런 자료구조를 사용하면 공간에 대한 점근적 복잡도는 이며 시간에 대한 점근적 복잡도 또한, 행렬을 모두 뒤져야 하기 때문에 가 된다. 여기서 는 꼭짓점의 개수이다.

타잔과 호프크로프트는 리스트 구조를 도입했다. 인접 리스트^{adjacency list}라고 이름 붙였는데, 각 노드 별로 연결된 노드 정보를 따로 관리했다. 아래와 같은 식이다.

이제 공간의 점근적 복잡도는 이 되었다.

타잔과 호프크로프트의 평면성 검사 알고리듬은 크게 세 단계로 구성된다. 먼저 주어진 그래프를 야자수 트리^{palm tree}라는 형태로 변환한다.^​6​ 야자수 트리란 이름이 붙은 이유는 아마도 그 모양 때문인 듯 싶다. 주어진 그래프에서 일단 신장 트리^{spanning tree}를 찾아내어 그것을 중심에 두고, 신장 트리에 속하지 않은 나머지 변들은 점선으로 표현한다.

위의 그림을 보면 (a)에 있는 그래프에 대해 (b)와 같은 야자수 트리를 만들어 낼 수 있다. (a)에서 (b)를 찾아내기 위해서 깊이 우선 탐색을 하는데 이 알고리듬의 점근적 복잡도는 이다. 즉, 꼭짓점과 변의 개수에 비례한다.

야자수 트리를 구했으면 이 그래프에서 사이클^cycle을 찾아낸 후 사이클에 속하지 않는 변들을 하나씩 붙여나가면서 서로 가로지르지 않도록 배치 가능한지를 검사한다. 사이클을 찾아내는 과정도 깊이 우선 탐색을 사용하기 때문에 역시 점근적 복잡도는 이다.

그런데 문제는, 찾아낸 사이클에 나머지 변들을 하나씩 붙여나가면서 서로 가로지르는 변이 없도록 만들어가는 과정에서 발생한다. 처음에 타잔이 찾은 방법은 의 복잡도가 나왔다. 이렇게 될 수밖에 없었던 것은 변을 하나씩 붙이다보면 이미 앞에 처리한 변들을 다시 재배치해야 하는 경우가 생겼기 때문이다. 호프크로프트는 의 복잡도를 원했고 해답을 구하는 데 일 년이 걸렸다. 결국 해결책은 자료구조와 알고리듬을 절묘하게 조합하는 데서 나왔다. 두 개의 스택 구조를 도입했는데 변을 재배치해야 하는 경우까지 미리 예상하여 진행하는 식이었다. 이렇게 해서 이 작업의 점근적 복잡도도 로 가능해졌다.

변^edge의 개수(E)는 꼭짓점의 개수(V)에 의해 제한되므로 결국 이 알고리듬의 점근적 복잡도는 인 셈이다.

1 2 3 4 5