그래프이론 (Graph Theory) 문제 풀이 해보겠습니다. 이번 글에서 풀이할 문제는 “Let T be a nontrivial tree. Determine the minimum possible number of maximal independent sets in T. Determine all the possible structure of T achieving the minumum number.” 입니다.
그래프이론 (Graph Theory) 문제풀이
다시 문제를 보겠습니다.
Let T be a nontrivial tree. Determine the minimum possible number of maximal independent sets in T. Determine all the possible structure of T achieving the minumum number.
Tree T가 있을 때, 이 Tree안에는 여러개의 maximal independent set이 존재할 수 있습니다. 이 문제에서는 두가지를 물어보고 있습니다.
- Tree가 가질 수 있는 maximal independent set 의 최소갯수
- 이 최소갯수만큼 maximal independent set 을 갖는 Tree의 종류
이것을 어떻게 풀까 고민을 하다가 극단적인 예시를 생각해봤습니다. K_{1,m} 인데요.
K_{1,m} 에는 maximal independent sets이 두 개밖에 없습니다.
왜 그런지를 생각해보니 K_{1,1} 의 경우 path의 최대길이가 1이고 K_{1,n} \text{ when } n\geq 2 인 경우엔 path의 최대길이가 2라는 것을 관찰했습니다.
그러면 길이가 3 이상인 path가 존재하는 경우 길이가 3이상인 path가 존재하지 않는 경우로 나눠서 생각을 할 수 있겠죠.
첫번째 경우, 길이 3이상인 path가 존재할 때
길이가 3인 path를 v_0 - v_1 - v_2 - v_3 가 tree T 안에 존재한다고 합시다.
이 path를 포함하는 tree T 안에서 independent set을 \{v_0,v_2\}, \{v_0,v_3\}, \{v_1,v_3\} 세개 찾을 수 있습니다. (tree는 cycle을 갖고 있지 않기 때문)
\{v_0,v_2\}, \{v_0,v_3\}, \{v_1,v_3\} 를 확장하여 tree T 안에서 maximal independent set을 최소 3개 이상 만들 수 있습니다.
두번째 경우, 길이 3이상인 path가 존재하지 않는다면
길이 3이상인 path가 존재하지 않는 tree T 가 있다고 합시다. 여기서도 경우가 나뉘는데요.
1. diam(T) = 1인 경우, T는 두개의 vertex로 구성된 edge가 됩니다. 두개의 vertex를 v,w라고 표시한다면 maximal independent set이 {v}, {w} 두 종류만 나옵니다.
2. diam(T) = 2인 경우, T는 K_{1,n} , n\geq 2 가 됩니다. 이 경우에도 maximal independent set이 두 종류만 있습니다.
이를 종합해서 생각해보면 tree가 가질 수 있는 maximal independent sets의 최소 종류는 2 입니다. 2개의 maximal independent sets만 가지는 Tree는 K_{1,n} 만 있습니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 4 문제