관계는

Question

나는 다음 질문 증명하기 위해 도움을 찾고 있어요 : < = 3, 이 (1)는 것을 증명 각각의 학위를 n 개의 정점을 가진 무향 트리 주어진이 우리가 제거하면 우리는 각 하나에 최대 수 (2 * n/3)의 꼭지점 수를 가진 두 개의 나무를 갖게 될 것입니다. (2)은 위의 주어진 트리에서 이러한 에지를 찾는 선형 알고리즘을 제안합니다.

Answer 1

임의의 루트를 선택하십시오. 각 하위 트리의 크기를 계산하기 위해 포스트 순회를 수행합니다. 루트로부터 하위 트리가 적어도 형제 크기 이상인 하위 항목을 통해 내림차순으로 크기가 (n-1)/3 이상 2 (n-1)/3 + 1 배의 크기 인 하위 트리를 찾습니다. 마이너스 1을 2로 나눈 것보다 더 많이 감소하는 것). 부모 가장자리를 끊으십시오.