Minimum possible number of maximal independent sets in tree T. (maximal independent set) / Graph Theory Prob. #2

문제

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 minimum number.

Maximal Independent Sets

  • Independent sets은 vertices로 이루어진 집합이다. Graph G의 vertices로 이루어진 집합 S가 있을 때, S의 원소들 사이에 edge가 없으면 S는 independent set이다. G에서 다양한 independent set을 구성할 수 있다.
  • Maximal independent set을 이해할 때, maximummaximal의 차이를 아는 것이 좋다.
  • Maximum independent set in GG안에서 만들 수 있는 모든 independent set 중에서 크기가 가장 큰 independent set를 의미한다. Maximum independent set은 여러 개 있을 수도 있겠으나, 모든 maximum independent set의 크기는 동일할 것이다.
  • Maximal independent set in G은 더 이상 추가할 vertex가 없는 independent set을 의미한다. G의 vertex 중 어떤 것을 추가하더라도 independent set의 조건이 깨진다는 의미이다. Maximal independent set도 여러 개 있을 수 있으며, maximal independent set의 크기도 다를 수 있다.

풀이

트리 T가 nontrivial하다. 즉, vertex가 여러 개(2개 이상)이다. Maximal independent set의 개수가 가장 작은 경우를 물어보았으므로 vertex가 가장 작은 경우를 생각하여 보자.

Tree T의 vertices를 v_1,~v_2라고 하자. 두 vertices는 edge e_1으로 연결되어 있다. 따라서, \{v_1\},~\{v_2\}가 maximal independent set이 될 것이다. 따라서, maximal independent set의 개수가 2개까지 작아질 수 있다는 것을 확인했다.

조금 더 세분화하여 살펴보자. Graph G\text{diam}(G)의 값에 따라서 분류하여 보자.

diam(G)

\text{diam}(G)는 그래프의 “지름”을 의미하는데, 지름의 정의를 이해하기 위해서 d_G(u,v)를 먼저 알아보자. d_G(u,v)는 두 vertices uv를 끝점으로 하는 uv-path 중에서 가장 짧은 path의 길이를 의미한다.

Graph G에서 두 vertices uv를 선택해서 얻는 d_G(u,v) 중 최대값을 \text{diam(G)}라고 하며 아래와 같이 정의된다.

\text{diam}(G)=\max_{u, v\in V(G)}d(u, v)

diam(G)=1

\text{diam}(G)=1인 graph는 위에서 다룬 vertices가 2개인 grpah이다. Maximal independent set이 2개인 것을 확인했다.

diam(G)=2

G=K_{m,n}~(m,n>0)\text{diam}(G)=2를 만족시킨다. GXY-bipartite graph라면 G의 maximal independent graph는 XY가 된다. X 또는 Y의 subset은 maximal 조건을 만족시키지 못하고, XY의 원소가 섞인다면 그 원소들 사이에 edge가 있기 때문에 independent set이 아니다.

아래와 같은 graph G\text{diam}(G)=2를 만족시키지만 3개의 maximal independent sets (\{v_2\},~\{v_1,v_3\},~\{v_1,v_4\})을 가진다.

diam=2 case

따라서, \text{diam}(G)=2일 때, maximal independent sets의 개수는 2 이상이 될 수 있다.

diam(G)가 3 이상

\text{diam}(G)가 3 이상인 경우, G가 길이가 3 이상인 path (v_0~v_1~v_2~v_3)를 가지고 있다. 이 path만 가지고도 3개의 maximal independent sets을 만들 수 있다. (\{v_0,v_2\},\{v_0,v_3\},\{v_1,v_3\}) 이 path에 추가적인 vertices가 연결되어 있을 것이기 때문에 위의 3개의 경우보다도 더 다양한 maximal independent sets을 만들 수 있을 것이다.

따라서, \text{diam}(G)\geq 3인 경우, maximal independent sets의 개수가 3 이상이라고 할 수 있다.

결론

따라서, 두 개의 maximal independent sets이 가장 적은 경우이고, GK_{n,m}인 경우가 해당된다. (Vertices가 2개인 경우는 K_{1,1}에 해당된다.)

Leave a Comment

Index