[그래프이론] #3. The Degree of Vertex

 

Def. Neighbour and Degree. 그래프 $G=(V, E)$에 대하여, 정점 $v \in V$의 neighbor의 집합, 즉 $v$와 간선으로 연결된 모든 정점의 집합을 $N(v)$로 나타낸다. 정점 $v$에 대하여 $E(v)$, 즉 $v$에 연결된 모든 간선의 개수를 $v$의 degree (차수)라고 하며 $d(v)$로 나타낸다. 자명하게 $d(v)=|E(v)|=|N(v)|$가 성립한다. 그래프 $G$에서 minimum degree는 모든 정점 중 최소 차수를 갖는 정점의 차수 $\delta(G)=\mathrm{min}\left\{d(v)|v \in V \right\}$로 정의하며 비슷하게 maximum degree는 최대 차수로 정의하여 $\Delta(G)=\mathrm{max}\left\{d(v)|v \in V \right\}$로 나타낸다. 마지막으로, $d(G)=\frac{1}{|V|} \sum_{v\in V}d(v)$로 $G$의 정점의 평균 차수, average degree를 정의한다. $\delta(G)\leq d(G) \leq \Delta(G)$가 성립한다. 

 

참고로, 특별한 언급이 없는 이상, 모든 그래프는 유한개의 정점과 간선을 가지는 그래프이다.   

 

Def. 그래프 $G=(V, E)$에 대하여 정점의 개수와 간선의 개수의 비율을 $\varepsilon(G)=|E|/|V|$로 정의한다. 이때, 그래프의 정점의 차수를 모두 더하면, 각 간선의 개수를 두 번씩 (양 끝에서 각각 한 번) 세게 되므로, 다음이 성립한다.

$$|E|=\frac{1}{2}\sum_{v \in V}d(v)=\frac{1}{2}d(G) \cdot |V|, \varepsilon(G)=\frac{1}{2}d(G)$$ 

여기서 알 수 있는 사실은, 그래프 $G$에서 홀수 차수를 가지는 정점의 개수는 항상 짝수여야 한다는 것이다. $|E|$는 자연수이므로 $\sum_{v\in V}d(v)$가 짝수가 되어야 하기 때문이다.

 

 

---

 

 

어떤 그래프가 큰 최소 차수를 가진다면, 모든 정점이 많은 수의 간선에 연결되어있다는 의미이다. 하지만 반대로, 어떤 그래프의 평균 차수가 크다고 해서 그 그래프의 최소 차수를 가진 정점 역시 많은 수의 간선에 연결되어있다고는 할 수 없다. 예를 들어 10개의정점을 가지는 그래프에서 9개의 정점은 서로 연결되어있고, 하나의 정점은 아무런 간선도 가지지 않는다면, 총 간선은 36개이지만 최소 차수는 0이 된다. 

 

평균 차수라는 정보는 주어진 그래프에서 전역적인 정보이다. 모든 정점들의 차수와 관련이 있는 정보이다. 반면, 최소 차수는 국소한 조건이다. 앞서 얘기했듯, 간선의 개수가 많다고 해서 neighbour의 개수가 적은 정점이 존재하지 않음이 보장되지 않는다. 이는, 한 반의 시험 점수의 평균이 80점이라고 해서, 그 반에 빵점을 받은 학생이 존재하지 않는다고 말할 수는 없다는 것과 비슷하다. 그런데, 아래 theorem은, 전체 그래프에서는 어려웠던 평균 차수를 통해 최소 차수에 대한 정보를 얻는 것이 해당 그래프의 부분 그래프에서는 가능하다는 사실을 보이고 있다.          

 

Theorem. 임의의 그래프 $G$는 다음이 성립하는 subgraph $H \subset G$가 존재한다.

$$\delta(H) > \varepsilon(H) \geq \varepsilon(G)$$

즉, 최소 차수가 $G$의 평균 차수의 절반보다 큼이 보장되는 $G$의 subgraph $H$를 항상 찾을 수 있다는 것이다.

Proof. 다음과 같은 알고리즘을 생각해보자. 

$G_0 \leftarrow G$
$d_0 \leftarrow 2|E(G)|/|V(G)|$
$i=0$
while True:
    $v \leftarrow V(G_i) s.t. deg(v) \leq \frac{1}{2}d_i$
    if no such $v$ exists:
       $H \leftarrow G_i$
       break
    end if
    $G_{i+1} \leftarrow G_i-v$
    $d_{i+1} \leftarrow d(G_{i+1})$
end while
return $H$

 

이 알고리즘에서 $d_{i+1} \geq d_i$임을 보이자. 

$|V_{i+1}|=|V_i|-1$이고, $|E_{i+1}|=|E_i|-deg(v)$이다. 따라서 다음이 성립한다.

$$deg(v)\leq \frac{|E_i|}{|V_i|}, |E_i|-deg(v)\geq |E_i|(1-\frac{1}{|V_i|})$$

따라서, 

$$\begin{align} d_{i+1} &= \frac{2(|E_i|-deg(v))}{|V_i|-1} \\ &\geq \frac{2}{|V_i|-1}\cdot |E_i| \frac{|V_i|-1}{|V_i|}\\ &= 2\frac{|E_i|}{|V_i|}=d_i \end{align}$$ 

이므로 $d_{i+1} \geq d_i$가 성립한다. 따라서 $\delta(H)\geq \frac{1}{2}d_i \geq \frac{1}{2}d_0 = \varepsilon(G)$가 성립한다.

추가적으로, 위의 알고리즘은 종료할 수밖에 없는데 그 이유는 $G$의 정점의 개수가 유한하기 때문이다. $\blacksquare$