Задание
Опеределите диаметр дерева на рисунке
Решение
Напомним, что
Определение
Диаметром дерева называется количество рёбер в максимальной цепи (длина цепи, связывающей две наиболее удалённые вершины).
Замечание / комментарий
Заметим, что максимальная цепь может связывать только две висячие вершины.
Если вершина не является висячей, цепь может быть продолжена.
Представленное на рисунке дерево имеет \(\displaystyle 3\) висячие вершины: \(\displaystyle J {\small,}\, H\) и \(\displaystyle G {\small.}\)
Найдем длины цепей между висячими вершинами дерева.
Длина цепи, связывающей вершины \(\displaystyle J\) и \(\displaystyle H{\small,}\) равна \(\displaystyle 3\)
Длина цепи, связывающей вершины \(\displaystyle J\) и \(\displaystyle G{\small,}\) равна \(\displaystyle 4\)
Длина цепи, связывающей вершины \(\displaystyle H\) и \(\displaystyle G{\small,}\) равна \(\displaystyle 3\)
Получили, что максимальная цепь в данном дереве имеет длину \(\displaystyle 4{\small.}\)
Значит, диаметр дерева равен\(\displaystyle 4{\small.}\)
Ответ: \(\displaystyle 4 {\small.}\)