고정 헤더 영역
상세 컨텐츠
본문
1. edge 수와 degree의 합의 관계.
Graph에서 모든 정점의 degree의 합은 간선의 수의 두배와 같다. $V$와 $E$를 graph의 vertex set, edge set이라 했을 때,
$$ \sum_{v\in V}d(v)=2|E| $$
가 성립한다. 증명은 모든 vertex에 대해서 degree의 합을 구할 때 각 edge가 2번씩 세졌다는 것으로 할 수 있다. (이를 통해 degree가 홀수인 vertex의 수가 짝수임을 알 수 있다.)
Note. Directed graph인 경우 $\sum_{v\in V}d^-(v) = |E| = \sum_{v\in V}d^+(v) $가 성립한다.
Triangle이 존재하기 위해선...
Graph에 triangle의 존재성을 보장하기 위해 edge가 얼마나 있어야 하는가? (Triangle은 length 3짜리 cycle이다.)
$G=(V,E)$가 simple graph이고 $n$과 $m$이 각각 $G$에서의 vertex 수와 edge 수를 나타낸다고 할 때,
$m>\displaystyle\frac{n^2}{4}$면 $G$는 triangle을 포함한다.
증명은 edge 수와 degree의 합의 관계를 이용해 contradiction으로 할 수 있다.
더보기
위 조건을 만족하는 $G$가 triangle이 없다고 하자. 그러면 어떤 $(u,v)$ edge를 골랐을 때 $u$의 neighbor과 $v$의 neighbor은 겹치지 않을 것이다. 따라서 다음의 부등식이 성립한다.
$$d(u)+d(v)\le n$$
이것을 모든 edge에 대해서 합해보자. 한 vertex $v$를 고르고, 합친 수식에서 $d(v)$가 총 몇번 등장하는지 $v$의 입장에서 생각을 해보자. 그러면 총 $d(v)$번 등장함을 알 수 있다. 따라서 모든 edge에 대해서 위 수식을 합하면,
$$\sum_{v \in V}{d(v)}^2 \le mn$$
이 성립함을 알 수 있다. 좌변을 풀기 위해 우리는 코시-슈바르츠 부등식을 사용한다.
$$ (a_1x_1+a_2x_2+\cdots+a_nx_n)^2 \le (a_1^2+a_2^2+\cdots+a_n^2)(x_1^2+x_2^2+\cdots+x_n^2) $$
각 $x$가 각 vertex의 degree라고 생각하고 모든 $a$가 0이라 생각하면,
$$ \left(\sum_{v \in V}{d(v)}\right)^2 \le n\sum_{v \in V}{d(v)}^2 $$
이다.
그래서 $\sum_{v \in V}{d(v)}=2m$을 이용해 정리하면,
$$\frac{4m^2}{n} = \frac{\left(\sum_{v \in V}{d(v)}\right)^2}{n}\le \sum_{v \in V}{d(v)}^2 \le mn$$
이 된다. 이는 그래프의 조건인 $m>n^2/4$와 모순이 된다.
Note. $K_{n/2,n/2}$인 complete bipartite graph에서 이 bound는 tight하다.
2. minimum degree와 path, cycle의 관계.
Graph가 minimum degree가 $\delta$인 simple graph라 하자. 그러면 다음 두가지가 성립한다.
Graph는 length가 최소 $\delta$인 path $P$를 포함한다.
만약 $\delta \ge2$라면, graph는 length가 최소 $\delta+1$인 cycle $C$를 포함한다.
이것의 증명도 간단하다. $P=v_0v_1\cdots v_l$를 graph의 maximal path(현재 상태에서 더 늘릴 수 없는 path)라고 하자. Maximal path이기 때문에 $v_0$의 모든 neighbor $N(v_0)$은 $P$에 속한다. $|N(v_0)|=d(v_0)\ge\delta$가 성립하기 때문에 이 path의 길이는 최소 $\delta$다. 여기서 만약 $\delta \ge2$라면, $v_0$과 $v_l$을 연결하면 cycle이 생기는데 이것의 길이는 최소 $\delta+1$이다.
3. even graph와 cycle decomposition
Even graph는 모든 vertex의 degree가 even인 graph를 말한다. Even graph는 cycles라고도 불렸는데 그 이유는 다음과 같다.
Cycle decomposition이 가능하면 even graph이고
even graph는 cycle decomposition이 가능하다.
즉, if and only if 관계로 이 둘이 성립을 하기 때문이다. Cycle decomposition이 가능하면 even graph라는 것은 보이기 쉽다. Cycle 위에 있는 vertex의 degree는 2이고 위에 있지 않은 vertex는 0이기 때문에 cycle은 even graph인데, cycle과 cycle을 합쳐도 여전히 모든 vertex의 degree가 even으로 유지되기 때문이다.
반대 방향의 증명도 그렇게 어렵지 않다. Even graph이면 최소한 하나의 cycle이 존재함을 보이기만 하면 되기 때문이다. 왜냐하면 최소한 하나의 cycle이 존재하면, 그 cycle을 제거했을 때의 graph도 even graph이기 때문이다. (이때 edge가 없는 graph는 자명하기에 생각하지 않는다.) Even graph의 minimum degree $\delta$는 최소 2이기 때문에 위의 2번에서 보인 것처럼 length가 최소 $\delta+1$인 cycle이 하나 존재한다.
Extra.
썸네일 사진은 Koh digraph다. 이는 directed even cycle이 없는 strong 2-diregular digraph이다. 이는 (증명은 안할테지만) strong digraph에서 directed even cycle이 존재하기 위해서는 minimum indegree와 minimum outdegree가 최소 3이어야 한다는 bound가 sharp하다는 것을 알려준다.
Digraph에서의 directed cycle에 관심이 있는 이유는 많은 문제와 관련되어 있기 때문이다.
1. Kernel
Kernel은 digraph에서 pairwise nonadjacent하면서 다른 모든 vertex를 dominate하는 vertices set이다. 많은 digraph는 kernel을 가지지 않는데 대표적인 것이 directed odd cycle이다. Digraph에서 kernel의 존재성을 다음과 같이 characterize 할 수 있다.
- Directed odd cycle이 없는 digraph는 kernel을 가진다.
이것의 증명은 digraph에서 maximal strong component를 하나 잡고 (odd cycle이 없기 때문에) 그것을 bipartition을 하여 한쪽을 kernel로 설정한 후, 그것이 dominate하는 vertices를 제거하고를 반복하는 것으로 보일 수 있다. (Odd cycle과 bipartite graph의 관계는 if and only if다.)
Note. Kernel은 graph위에서의 game을 할 때 winning position이 어디인가에 대한 분석에서 등장한 개념이라고 한다.
2. Directed even cycle
Shortest directed odd cycle은 (존재한다면) adjacency matrix에 nonzero diagonal entry가 등장할 때까지 odd power를 취함으로써 polynomial time에 찾을 수 있다. 하지만 directed even cycle은 이보다 더 어렵다.
- $A$가 digraph의 adjacency matrix라고 했을 때 directed even cycle의 존재성과 $per(I+A) \neq det(I+A)$는 if and only if 관계다. (per과 det는 permanent와 determinant를 뜻한다.)
이것으로 directed even cycle의 존재에 대한 필요충분조건을 찾기는 했지만, 실제로 찾는 polynomial time algorithm은 발견되지 않았고 NP-complete 하다는 것 또한 증명되지 않았다고 한다. (이보다 더 어려운 문제인 directed even cycle이나 directed odd cycle의 존재성을 결정하는 문제는 NP-complete하다는 것이 나와있다.)
Reference - Handbook of Combinatorics, Volume 1, Basic graph theory: Paths and circuits
댓글 영역