Tree with i degree vertices (i: 2~k) and n-k+1 leaves (tree) / Graph Theory Prob. #1

바로가기

문제

Let T be an n-vertex tree having one vertex of each degree i with 2\leq i\leq k; the remaining n-k+1 vertices are leaves. Determine n in terms of k.

Tree

  • Tree는 acyclic하다. 즉, cycle이 없다. 그리고 connected해야한다.
    위의 조건에 따라서, n-vertex tree는 edge의 개수가 n-1이다.
    n개의 vertices를 깔아두고 edges를 추가해보자. 첫 edge는 아무렇게 추가하고, 이후의 edge들은 degree가 0이 아닌 vertex와 0인 vertex를 이어주자. 그러면 cycle이 생기지 않으면서 connected하도록 edge가 추가된다.
    이 때, edges의 개수가 n-1이면 모든 vertices들이 connected이고, cycle도 없다. 하지만 n-1보다 적으면 connected가 아니고, n-1보다 크면 cycle이 생길 수 밖에 없다.
    아래의 vertices가 4개인 graph를 보면 edges가 3개일 때, connected acyclic graph, tree가 되는 것을 볼 수 있다.
  • Leaves(leaf)는 tree에서 degree가 1인 vertices를 의미한다.

풀이

2부터 k까지의 degree를 가진 vertex가 “하나 씩” 존재한다고 한다. 그리고 나머지 n-k+1개의 vertices는 leaves라고 한다. 즉, degree가 1이라는 의미이다. 따라서, 모든 vertices의 degree 총합은 다음과 같다.

\sum_{i=2}^{k}i+(n-k+1)\cdot 1

위에서 살핀 tree의 성질에 따라서, tree는 edge가 n-1개 이기 때문에 degree의 총합이 2(n-1)가 된다. 따라서, 아래와 같은 등식이 성립한다.

\sum_{i=1}^{n}d_i=\sum_{i=2}^{k}i+(n-k+1)\cdot 1=2(n-1)\\ \frac{(k+2)(k-1)}{2}+n-k+1=2n-2\\ n=\frac{k^2+k-2}{2}-k+3\\ \therefore~n=\frac{k(k-1)}{2}+2

결과적으로, nk가 위와 같은 관계를 가지면 문제의 조건과 같은 tree를 만들 수 있다.

Leave a Comment

바로가기

Index