[그래프이론(Graph Theory) 문제풀이] Prove or disprove: Every tree T has at least ∆(T) leaves.

그래프이론 (Graph Theory) 문제풀이 글 입니다. 이번에 풀어볼 문제는 “Prove or disprove: Every tree T has at least ∆(T) leaves.”입니다. 이것을 어떻게 풀까요?



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

이번에 풀어볼 문제를 다시 정리하면 아래와 같습니다.

Prove or disprove: Every tree T has at least ∆(T) leaves.

어떤 Tree이건 이것의 maximum degree이상의 leaf를 갖는가를 묻는 문제입니다. 문제풀이 해보겠습니다. maximum degree를 M이라 표시할 게요.  v를 maximum degree를 갖는 T의 vertex라고 합시다. 그랬을 때 v 의 neighbors는 M개가 있습니다. 이 M개의 vertex는 leaf이던가 leaf가 아니면 쭉쭉 타고가서 leaf를 한개 이상 만듭니다. 즉 어쨋든 M개 이상의 leaf를 만든다는 뜻입니다. 따라서 Tree T는 최소 M개 이상의 leaf를 갖는다.

참고할만한 글:

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

Leave a Comment