그래프 이론 트리를 묘사하기

Question

트리가 차수 8의 1000 정점과 차수 5의 정점 40 그리고 아마도 다른 정점을 가지고 있다고 가정합니다. 그러한 나무는 4000 잎보다 적은 수 있습니까? 그렇다면 어떻게 그러한 트리 하나를 설명 할 수 있습니까? 그렇지 않으면 그런 트리가 존재할 수 없다고 주장하는 방법은 무엇입니까?

Answer 1

번호 n이 정점의 총 수인 경우 트리는 n-1 개의 모서리를 가지며 정점 도의 합은 모서리 수의 두 배이므로 2n-2입니다.

r을 차수가 8 인 노드의 수라고 할 때 차수 1 (잎)의 노드와 나머지 노드 (따라서 차수가 최소 2). 그러면 n = r + s + t와 2n-2 = 2r + 2s + 2t-2> = 8r + s + 2t (도의 합에 대한 하한). 그래서 s-2> = 6r. r = 1000의 경우 6,000 개가 넘습니다.