📂그래프이론

하벨-하키미 알고리즘 증명

정리

증가하지 않는 시퀀스 $D = (d_{1} , \cdots , d_{n})$ 가 주어져있다고 하자. $D$ 가 그래픽하다면 다음과 같은 방법으로 $D$ 의 실현 $G$ 를 찾을 수 있다.

• Step 1.
  $n$ 개의 버텍스 $v_{1} , \cdots , v_{n}$ 를 가지는 널 그래프를 만든다.
• Step 2. $k = 1, \cdots , n$
  • Step 2-1.
    $v_{k}$ 과 $v_{k+1} , \cdots , v_{d_{k} + 1}$ 를 잇는다.
  • Step 2-2.
    $d_{k+1} , \cdots , d_{d_{k}+1}$ 를 $1$ 씩 감소시킨다.
  • Step 2-3.
    $d_{k} \gets 0$ 와 같이 대입한다. $D = (0,\cdots , 0)$ 이 될때까지 Step 2.를 반복한다.

$D$ 가 그래픽하다면 차수가 $d_{1}$ 인 $v_{1}$ 은 $v_{2} , \cdots , v_{d_{1} + 1}$ 과 인접한 실현 $G$ 가 존재한다.

설명

하벨-하키미 알고리즘은 에르되시-갈라이 정리가 그 존재성을 보장하는 실현을 구체적으로 찾는 알고리즘이다. 그 원리는 단순히 덩치가 큰―제일 차수가 높은 버텍스부터 처리해서 자잘자잘하게 남는 것이 없도록 하는 것 뿐이다. 차수를 먼저 주고나서 그래프를 구축한다는 점에서 랜덤 그래프의 차수가 어떤 분포를 따르게끔 구축하는데에 곧바로 쓰일 수 있다.

가령 $(5,5,5,3,2,2,1,1)$ 과 같은 시퀀스가 있다면 하벨-하키미 알고리즘으로 얻을 수 있는 실현은 위와 같다. 시간이 여유롭다면 에르되시-갈라이 정리를 이용해 그래픽한 시퀀스를 만들어보고 하벨-하키미 알고리즘 없이 노가다로 실현을 찾아보는 것을 추천한다. 이 방법이 얼마나 유용한지 알 수 있을 것이다.

증명

$D$ 가 업데이트 될 때마다 차수의 최대값은 점점 작아진다. 각 단계에서 차수가 최대값인 노드 $v_{k}$ 가 $v_{k+1} , \cdots , v_{d_{k} + 1}$ 와 인접하면 되고, 차수가 $d_{1}$ 인 첫 버텍스 $v_{1}$ 가 $v_{2} , \cdots , v_{d_{1} + 1}$ 와 인접한 것만을 보이면 수학적 귀납법에 의해 증명이 끝난다.

$D$ 의 임의의 실현 $R$ 의 버텍스들이 $\deg (v_{i}) = d_{i}$ 를 만족한다고 하고 다음과 같이 두 집합을 정의하자. $$T_{R} := \left\{ v_{2} , \cdots , v_{d_{1} + 1} \right\} \\ N_{R}(v_{1}) := \left\{ v \in V(R) : vv_{1} \in E(R) \right\}$$ 정의에서 $T_{R}$ 는 시퀀스 $D$ 의 $v_{1}$ 이후 $d_{1}$ 개만큼의 버텍스를 모아놓은 집합이고, $N_{R}(v_{1})$ 는 $v_{1}$ 의 네이버후드, 즉 $R$ 에서 실제로 $v_{1}$ 와 인접한 버텍스들의 집합이다. 이에 대해 다음과 같은 정수 $t_{R}$ 를 생각해보자. $$t_{R} := \left| N_{R} (v_{1}) \cap T_{R} \right|$$ 이제 $G$ 는 $D$ 의 실현들 중 $t_{G}$ 를 가장 최대화하는 실현임을 보여야한다. 이는 다시 말해 $T_{G} = N_{G}(v_{1})$ 과 $t_{G} = d_{1}$ 을 만족해서 차수가 $d_{1}$ 인 $v_{1}$ 가 $v_{2} , \cdots , v_{d_{1} + 1}$ 과 인접하다는 것이다. 만약 $t_{G} = d_{1}$ 이면 당연히 $T_{G} = N_{G}(v_{1})$ 이므로 $G$ 가 $t_{G}$ 를 최대화하는 실현이 되어 더 이상 보일 것이 없다. 이제 $t_{G} < d_{1}$ 인 경우를 가정해보자. 만약 $t_{G'} = t_{G} + 1$ 가 되게끔 하는 $D$ 의 또 다른 실현 $G'$ 이 존재한다면

$t_{G'}<d_{1}$ 인 경우 $v_{1}$ 은 어떤 $v_{x} \in T_{G'}$ 와 인접하지 않는 대신 어떤 $v_{y} \in T_{G'}^{c}$ 와 인접해야한다. 위 그림에서 적색 점선은 $G$ 에서는 존재하는 에지지만 $G'$ 에선 지워진 에지고, 적색 실선은 그 대신 $v_{1}$ 의 차수가 일정해야하므로 새롭게 만들어진 에지다.

$v_{1}$ 과 마찬가지로 $v_{x}$ 와 $v_{y}$ 의 차수도 유지되어야하므로, 원래 $G$ 에서는 $v_{x}$ 와 인접하지 않았고 $v_{y}$ 와 인접했던 $v_{z}$ 를 하나 골라서 $v_{x} v_{z}$ 를 추가하고 $v_{y} v_{z}$ 를 지운다. 이렇게 되면 원래의 디그리 시퀀스 $D$ 는 전혀 달라지지 않고, $G'$ 는 $D$ 의 실현이라고 할 수 있다. 그러나 $G'$ 는 $T_{G'}$ 에서 $v_{x}$ 하나가 빠졌고 $N_{G'}(v_{1})$ 에 $v_{y}$ 하나가 추가 되었으므로 $t_{G'}$ 는 오히려 $t_{G}$ 보다 작아졌다. 이는 $t_{G'} = t_{G} + 1$ 를 만족시키는 실현 $G'$ 의 존재성에 모순이고, 따라서 $t_{G} = d_{1}$ 이어야한다. 다시 말해, 실현 $G$ 의 $v_{1}$ 은 $v_{2} , \cdots , v_{d_{1} + 1}$ 과 인접하다.

■