티스토리 블로그 관리 페이지에는 유입 키워드를 확인할 수 있는 기능이 있습니다. 저는 하루에 몇 번씩 유입 키워드를 살펴보면서 어떤 검색어로 제 블로그에 유입되는지를 확인하고는 합니다. 그러다 최근 'hakimi 방식', 'hakimi의 방법' 등의 키워드로 제 블로그에 방문한 사람이 있다는 사실을 알게 되었습니다. 최근에 제가 작성한 거리의 그래프 실현 가능성에 대한 포스트로 유입된 것이었습니다.
2022.05.15 - [수학적 도구/Graph theory] - 거리의 트리 실현 가능성 (Tree Realizability of Distance)
거리의 트리 실현 가능성 (Tree Realizability of Distance)
오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum co
gazelle-and-cs.tistory.com
그 이유는 명확했습니다. 해당 글을 작성할 때 참조한 논문의 저자 중 한 명이 하키미(S. L. Hakimi)였기 때문이었습니다.
아무래도 해당 검색어로 찾고 싶었던 것이 거리의 그래프 실현 가능성은 아니었으리라 생각했습니다. 대신 어떤 것을 찾고 싶었던 것인지 궁금해졌죠. 바로 검색해 보니 가장 먼저 뜬 것이 바로 하벨-하키미 알고리즘(Havel-Hakimi algorithm)이었습니다. 이 알고리즘에 관한 내용을 위키피디아에서 찾아 가볍게 훑어보았습니다. 알고리즘이 어떻게 동작하는지와 그것이 올바르게 동작함을 보이기 위한 정리의 명제가 적혀 있었습니다. 여기까지는 읽었습니다. 그다음에는 정리의 증명이 적혀 있었는데 읽지 않았습니다. 직접 증명을 할 수 있을 것 같았거든요. 퇴근 후에 가볍게 끄적여 보니 쉽게 증명이 되었습니다.
이번 포스트에서는 하벨-하키미 알고리즘에 관해 가볍게 정리해 보겠습니다. 'hakimi 방식'이나 'hakimi의 방법' 등으로 검색해서 들어온 분이 실제로 찾은 내용이 이 알고리즘이었기를 바라 봅니다. 혹여나 다시 방문한다면 이 포스트가 도움이 되면 좋겠습니다.
하벨-하키미 알고리즘이 푸는 문제를 설명하기 위해서는 몇 가지 개념을 알아야 합니다. 어떤 그래프가 주어졌을 때, 각 정점 \(v\)에 대해, 한 끝점이 \(v\)인 간선(다른 말로 해당 정점에 딸린(incident) 간선)의 총 개수를 우리는 \(v\)의 차수(degree)라고 부릅니다. 또한, 모든 정점의 차수를 나열한 것을 그래프의 차수열(degree sequence)이라고 부릅니다. 수열(sequence)라는 이름으로 불리지만 순서는 상관 없습니다. 그저 같은 숫자가 같은 개수만큼 있으면 동일합니다. 예를 들어, \( (1, 2, 3, 2) \)와 \( (2, 3, 1, 2) \)는 동일합니다.
어떤 그래프에 한 정점에서 출발해 해당 정점으로 다시 돌아오는 루프(loop)나 두 정점 사이를 복수의 간선이 있는 평행 간선(parallel edges)이 존재하지 않을 때, 우리는 이 그래프가 단순(simple)하다고 합니다.
이제 풀고자 하는 문제를 정확히 정의할 수 있습니다. 문제의 입력으로는 길이가 \(n\)인 음이 아닌 정수로 이루어진 어떤 수열이 하나 주어집니다. 우리의 목표는 해당 수열을 차수열로 갖는 단순 그래프가 존재하는지를 판별하고, 만일 존재한다면, 그러한 그래프를 하나 출력하는 것입니다.
알고리즘을 소개하기에 앞서 수열이 어떤 단순 그래프의 차수열이 될 조건이 무엇인지에 대해서 알아 보겠습니다. 먼저 우리는 수열에 0이 없다고 가정해도 괜찮습니다. 0은 딸린 간선이 없다는 의미이므로, 0을 모두 제외한 수열이 어떤 단순 그래프의 차수열이라면, 해당 단순 그래프에 제외했던 수만큼 고립된(isolated) 정점을 추가하는 방식으로 원래 수열을 차수열로 갖는 단순 그래프를 만들 수 있습니다.
이제 어떤 수열 \( (a_1, a_2, \cdots, a_n) \)이 주어졌다고 하겠습니다. 일반성을 잃지 않고, 수열이 내림차순으로 정렬되어 있다고 하겠습니다. 즉, \( a_1 \geq a_2 \geq \cdots \geq a_n \)을 만족합니다. 이때 만약 \(a_1 \geq n\)이라면 우리는 해당 수열이 절대 어떤 단순 그래프의 차수열이 될 수 없음을 알 수 있습니다. \(a_1\)의 차수를 갖는 정점을 제외하고는 \(n - 1\) 개의 정점이 존재하는데, \(a_1\)이 \(n - 1\)보다 크다면 반드시 루프나 평행 간선이 생기기 때문입니다. 따라서 이제부터 \( n > a_1 \geq a_2 \geq \cdots \geq a_n \)이라고 가정하겠습니다.
마지막으로 이번 포스트에서 가장 중요한 아래의 정리는 주어진 수열이 단순 그래프의 차수열이 되기 위한 필요충분조건이 무엇인지 알려 줍니다.
정리 1. 단순 그래프의 차수열이 되기 위한 필요충분조건
위 가정을 모두 만족하는 수열 \( (a_1, a_2, \cdots, a_n) \)이 어떤 단순 그래프의 차수열이 되기 위한 필요충분조건은 이 수열에서 \(a_1\)을 제외한 가장 앞의 \(a_1\) 개의 수(즉, \(a_2, \cdots, a_{a_1 + 1}\))에 각각 1을 뺀 수열, 다시 말해, \[ (b_2, \cdots, b_n) := (a_2 - 1, a_3 - 1, \cdots, a_{a_1 + 1} - 1, a_{a_1 + 2}, \cdots, a_n) \]이 어떤 단순 그래프의 차수열이 되는 것이다.
[증명] (\( \Leftarrow \)) 이 방향은 쉽습니다. \( (b_2, \cdots, b_n) \)을 차수열로 갖는 단순 그래프를 갖고 오겠습니다. 각 \(i = 2, \cdots, n\)에 대해서, 이 그래프는 \( b_i \)의 차수를 갖는 정점 \(v_i\)를 포함하고 있다고 하겠습니다. 이제 이 그래프에 \(v_1\)이라는 정점을 추가한 다음 이 정점을 \( v_2, \cdots, v_{a_1 + 1} \)과 각각 간선으로 연결해 줍니다. 이렇게 만들어진 그래프는 정확히 \( (a_1, \cdots, a_n) \)의 차수열을 갖는다는 것을 쉽게 확인할 수 있습니다.
(\( \Rightarrow \)) 이 방향은 약간 까다롭습니다. 먼저 \( (a_1, \cdots, a_n) \)을 차수열로 갖는 단순 그래프를 하나 가정하겠습니다. 이 그래프의 정점을 \(v_1, \cdots, v_n\)이라고 부르겠습니다. 각 \(i = 1, \cdots, n\)에 대해, \(v_i\)의 차수는 \(a_i\)입니다. 만약 \( v_1 \)이 인접한 정점이 \( v_2, \cdots, v_{a_1 + 1} \)이라면 우리는 현재 그래프에서 \(v_1\)과 그에 딸린 간선을 모두 제거함으로써 \( (b_2, \cdots, b_n) \)을 차수열로 갖는 단순 그래프를 하나 만들 수 있습니다. 그러면 증명이 완료됩니다.
문제는 \(v_1\)이 \(v_2, \cdots, v_{a_1 + 1}\)이 아닌 어떤 정점 \(v_k\)와 인접할 수 있다는 것입니다. 그럼 분명 \( v_2, \cdots, v_{a_1 + 1} \) 중에는 \(v_1\)과 인접하지 않은 정점이 하나 존재합니다. 이를 \(v_j\)라고 부르겠습니다. 우리의 목표는 \(v_1\)이 \(v_k\)가 아닌 \(v_j\)와 인접하면서 동일한 차수열을 갖는 그래프를 만드는 것입니다. 이 작업이 가능하다면, 이를 계속 적용하여 \( v_1 \)이 \( v_2, \cdots, v_{a_1 + 1} \)과만 인접한 그래프를 만들 수 있고, 그러면 앞의 논의를 통해 증명을 완성할 수 있습니다.
해당 작업이 가능한지 논의해 봅시다. 현재 \(v_j\)는 \(v_1\)과 인접하지 않지만, \( v_k \)는 \( v_1 \)과 인접한 상태입니다. 따라서 \( v_j \)는 총 \(a_j\) 개의 \(v_1\)이 아닌 정점과 인접한 상태이며, \( v_k \)는 \(a_k - 1\) 개의 \(v_1\)이 아닌 정점과 인접한 상태입니다. 앞서 우리는 \( (a_1, \cdots, a_n) \)이 내림차순으로 정렬되어 있다고 가정하였습니다. 따라서, \[ a_j \geq a_k \]를 만족합니다. 이를 통해서 우리가 알 수 있는 사실은 \( v_j \)와는 인접하였지만, \( v_k \)와는 인접하지 않은 어떤 정점이 반드시 하나는 존재한다는 것입니다. 이 정점을 \(v_\ell\)이라고 부르겠습니다.
이제 퍼즐 조각이 모두 준비되었습니다. 현재 그래프에는 \[ (v_1, v_k), \; (v_j, v_\ell) \]이 간선으로 들어가 있습니다. 그 그래프에서 이 두 간선을 제거하고 대신 \[ (v_1, v_j), \; (v_k, v_\ell) \]을 추가해 보겠습니다. 이렇게 얻은 그래프가 우리가 원하는 그래프임을 논증하겠습니다. 먼저 모든 정점의 차수의 변화는 없다는 것은 쉽게 확인할 수 있습니다. 또한 원래 간선이 존재하지 않던 정점의 쌍에 간선을 넣은 것이므로 그래프의 단순성도 위배하지 않습니다. 하지만 새로운 그래프에서 \(v_1\)은 \(v_k\) 대신 \(v_j\)에 인접한 상태입니다. ■
위에서 발견한 성질들을 활용하면 다음의 알고리즘을 만들 수 있습니다.
알고리즘 1. 하벨-하키미 알고리즘 (Havel-Hakimi algorithm)
입력: 음이 아닌 정수의 수열
출력: 입력 수열을 차수열로 하는 단순 그래프 (혹은 비존재성)
- 수열에서 0을 모두 제거한다. 대신, 수열에서 0의 개수를 \(n_0\)라고 한다.
- 만약 수열에 아무것도 없다면, \(n_0\) 개의 고립된 정점을 갖는 그래프를 반환한다.
- 양수로 이루어진 수열을 내림차순으로 정렬한다. 정렬된 수열을 \( (a_1, \cdots, a_n) \)이라고 부른다.
- 만일 \( a_1 \geq n \)이라면, 존재하지 않는다고 반환한다.
- 정리 1에서와 같이 \( (b_2, \cdots, b_n) \)을 만든 후 재귀적으로 알고리즘을 수행한다.
- 만약 재귀 호출의 결과가 존재하지 않는다는 것이면 존재하지 않는다고 반환한다.
- 각 \(i = 2, \cdots, a_1 + 1\)에 대해, 재귀 호출의 결과 그래프 \(G\)에서 \(b_i\)의 차수를 갖는 정점을 \(v_i\)라고 하자.
- \(G\)에 \(v_1\)을 추가하고 \( v_2, \cdots, v_{a_1 + 1} \)을 각각 연결한다.
- \(G\)에 \(n_0\)만큼 고립된 정점을 추가한다.
- \(G\)를 반환한다.
간단히 수행 시간을 분석해 보겠습니다. 이 알고리즘은 재귀적으로 동작합니다. 재귀적으로 호출될 때마다 수열의 길이가 적어도 1씩은 감소하므로 최대 \(n\) 번 반복됩니다. 하나의 재귀 호출에 대해서 분석해 보죠. 단계 1은 수열을 한 번 순회하는 것으로 충분하므로 \(O(n)\)입니다. 단계 2는 마지막 호출에서 한 번 수행되고, 이는 \(O(n)\)에 동작합니다. 단계 3은 \(O(n \log n)\)의 시간이 필요하겠죠. 단계 8은 \( v_1 \)을 넣을 때 \(O(1)\), 그 후 간선을 넣을 때 \( O(a_1) \) 만큼의 시간이 필요합니다. 단계 9는 \( O(n) \) 시간이면 충분합니다. 이를 종합하면, 이 알고리즘의 수행 시간은 \[ O \left( n^2 \log n + \sum_{i = 1}^n a_i \right) \]라고 말할 수 있습니다.
한 가지를 빼 먹었습니다. 위 수행 시간은 \(a_i\)가 무진장 커질 경우 알고리즘의 수행 시간도 무진장 커질 수 있다는 의미입니다. 하지만 그렇지 않습니다. 만약 수열의 어떤 숫자가 무진장 크다면 분명 단계 4에서 걸러졌을 것입니다. 악수 정리(handshaking lemma)에 의해 차수의 합은 간선의 개수의 두 배와 같습니다. 알고리즘이 출력하는 그래프는 단순해야 합니다. 단순 그래프에는 \( \frac{n(n-1)}{2} \) 개를 초과하는 간선이 존재할 수 없습니다. 따라서 \( \sum_{i = 1}^n a_i > n(n - 1) \)이라면 분명 알고리즘이 중간에 단계 4에서 진행을 멈췄을 것입니다. 따라서 이 알고리즘의 수행 시간은 \[ O \left( n^2 \log n + \min \left\{ \sum_{i=1}^n a_i, n^2 \right\} \right) = O(n^2 \log n) \]이 되겠습니다.
조금 더 생각해 보니 \(O(n^2)\) 시간도 가능해 보입니다. 어떻게 하면 될까요? 힌트는 수열을 정렬하는 것은 한 번이면 충분하다는 것입니다. 그러면 처음 호출을 제외한 나머지 재귀 호출 때마다 단계 3을 \(O(n)\)에 수행해야 \(O(n^2)\) 시간을 얻을 수 있을 것입니다. 매 재귀 호출 마다 입력되는 수열이 중구난방이라면 쉽지 않겠지만, 잘 따져 보면 이 수열은 꽤 정돈된 모습을 하고 있습니다. 이를 활용한다면 선형 시간에 정렬이 가능할 것입니다.
참조
[1] Havel-Hakimi algorithm. Wikipedia.
Link: https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm
'수학적 도구 > Graph theory' 카테고리의 다른 글
| 거리의 트리 실현 가능성 (Tree Realizability of Distance) (2) | 2022.05.15 |
|---|---|
| 그래프 트리에 관한 간단한 성질들 (0) | 2020.03.25 |
