какое максимальное число висячих вершин может иметь дерево построенное на 9 вершинах

В теории графов в дереве (связном графе без циклов) количество висячих вершин (или листьев) может быть определено по следующему принципу:

Во-первых, каждое дерево с \( n \) вершинами всегда имеет как минимум 2 висячие вершины, если \( n > 1 \). Для максимального количества висячих вершин, необходимо рассмотреть структуру дерева.

Дерево с максимальным количеством висячих вершин можно построить в форме "звезды". В таком случае одна из вершин будет центральной (пусть это будет одна не висячая вершина), а остальные \( n - 1 \) вершин будут соединены с ней.

Для дерева на 9 вершинах это означает, что:

• 1 вершина является центральной (не висячей),
• остальные 8 вершин являются висячими.

Таким образом, максимальное количество висячих вершин в дереве на 9 вершинах равно 8.