Diameter of Tree (1) 썸네일형 리스트형 113. Diameter of Tree 트리의 지름은 다음과 같이 정의된다. 트리에 존재하는 임의의 정점 $u$와 $v$에 대해, 두 정점 사이에는 항상 한 개의 단순 경로가 존재하며 이 단순 경로의 길이를 정점 $u$와 $v$ 사이의 거리(Distance)라고 한다. 트리의 한 정점 $u$과 임의의 정점 $v$에 대해, 정점 $u$와 $v$ 사이의 거리의 최대값을 정점 $u$에서의 이심률(Eccentricity)이라고 한다. 트리의 각 정점에서의 이심률의 최소값을 트리의 반지름(Radius of Tree)이라고 하고 이심률의 최대값을 트리의 지름(Diameter of Tree)이라고 한다. 쉽게 말해서 트리의 지름은 트리에 존재하는 두 정점 사이의 거리의 최대값과 같다. 다음과 같은 트리에서 지름은 $4$, 반지름은 $2$이다. 간선에 가중.. 이전 1 다음
