에르되시-갈라이 정리
빌드업
- 그래프 $G$ 의 차수를 중복을 포함해 모아놓은 집합을 그래프 스코어graph Score라 하고, $G$ 의 그래프 스코어를 내림차순으로 정렬한 시퀀스를 $G$ 의 디그리 시퀀스degree Sequence라 한다.
- 증가하지 않는 자연수들의 시퀀스 $D = (d_{1} , \cdots , d_{n})$ 에 대해 $n$ 개의 버텍스 $v_{1} , \cdots , v_{n}$ 가 다음을 만족 시키게끔 하는 그래프 $G$ 가 존재하면 $D$ 가 그래픽graphic하다고 말하고, 그 그래프 $G$ 를 $D$ 의 실현realiasation이라 부른다.
가령 위와 같은 그래프 $G_{0}$ 가 주어져 있다면 그래프 스코어는 $$ \left\{ 1,5,3,5,2,1,5,2 \right\} $$ 가 될 것이고, 내림차순으로(증가하지 않는) 정렬한 디그리 시퀀스는 다음과 같다. $$ D_{0} = (5,5,5,3,2,2,1,1) $$
수학도라면 자연스레 디그리 시퀀스만을 가지고 그래프를 만들어낼 수 있는지에 관심을 가질 수밖에 없을 것이다. 만약 그것이 가능하다면 그 시퀀스를 원천으로 하는 그래프로 만들 수 있다는 뜻이 되므로, 그래프적이다 혹은 그래프가능하다는 식의 개념을 생각해낼 수 있을 것이다. 위의 예시에서 이어가자면 $G_{0}$ 는 $D_{0}$ 의 실현 중 하나로 볼 수 있다. [ NOTE: 실현은 유일하게 존재할 필요가 없다. ]
이렇듯 시퀀스가 그래픽한지에 대한 동치조건은 다음과 같은 정리로 규명되어 있다.
정리
에르되시-갈라이 정리
시퀀스 $(d_{1} , \cdots , d_{n})$ 가 그래픽한 것은 다음 두 가지 조건을 동시에 만족시키는 것과 동치다. $$ \sum_{i=1}^{k} d_{i} \in 2 \mathbb{Z} \\ \sum_{i=1}^{k} d_{i} \le k ( k-1) + \sum_{i=k+1}^{n} \min (k, d_{i}) , \qquad 1 \le k \le n $$
- $2 \mathbb{Z}$ 는 짝수 집합을 의미한다.
증명 1
생략한다.
같이보기
다만 이는 실현의 존재성을 보장할 뿐, 구체적으로 그 실현이 어떻게 생겼는지는 알려주지 않기 때문에 하벨-하키미 알고리즘과 같은 방법으로 직접 찾아볼 필요가 있다. 이는 오일러 그래프의 판별과 별개로 구체적인 오일러 트레일을 찾을 땐 플뢰리 알고리즘을 써야하는 것과 비슷하다.