[그래프이론 (Graph Theory) 문제풀이] Prove that the number of simple Eulerian graphs with vertex set {1, 2, · · · , n} is 2 ( n−1 2 ).

by

그래프이론 (Graph Theory) 문제 풀이를 해보겠습니다. 이번에 풀고 싶은 문제는 Prove that the number of simple Eulerian graphs with vertex set {1, 2, · · · , n} is 2^{\binom{n-1}{2}}입니다. Simple Eulerian Graph 갯수를 말하는 것인데요. 어떻게 푸는지는 글을 진행하가며 알아보겠습니다.




그래프이론 (Graph Theory)문제 풀이

문제는 아래와 같습니다.

Prove that the number of simple Eulerian graphs with vertex set {1, 2, · · · , n} is 2^{\binom{n-1}{2}}

천천히 풀어보도록 하겠습니다. 먼저 {1,2,…,n-1} 위에 정의된 Simple graph 갯수를 구해보겠습니다.{1,2,…,n-1}를 이용하여 만들 수 있는 edge 수는 총 \binom{n-1}{2} 개 입니다. 따라서 이 엣지들을 조합해서 만들 수 있는 {1,2,…,n-1} 위의 simple graph 갯수는 2^\binom{n-1}{2} 개 입니다. 이 사실을 이용해 보겠습니다. 아래와 같이 Eulerian graph 와 Simple graph 를 담고있는 set을 정의합니다.

G_{n-1} = \{ \{1,2,...,n-1\} \text{ 에서 정의된 simple graph} \} E_{n} = \{ \{1,2,...,n\} \text{ 에서 정의된 Eulerian graph} \}

이제 E_n , G_{n-1} 사이에 biejection 을 만들것입니다. f : G_{n-1} \to E_n 를 아래와 같은 방식으로 정의할 것입니다.

  1. G \in G_{n-1} 를 꺼낸다.
  2. G 에서 odd degree 를 갖는 vertex 는 n 과 edge를 만들어서 그래프를 확장하고 확장 된 그래프를 E 라고 표시합니다. 이 때 odd degree를 갖는 vertex의 갯수는 짝수개였으므로 E 의 vertex의 degree는 모두 짝수입니다. 따라서 E는 Eulerian graph 입니다.
  3. 만약에 G 가 even graph 이면, vertex n 만 추가하여 Eulerian graph E를 만듭니다.

위와 같은 방식으로 G_{n-1} 에서 E_n 으로 mapping f 를 만들 수 있습니다. f 가 1-1 인것은 쉽게 보일 수 잇습니다. 그리고 f 가 surjective 이라는 사실은 Eulerian graph 에서 vertex하나만 제거하면 보일 수 있습니다.

참고할만한 글:

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제

 

Leave a Comment