Листовая вершина
Листовая вершина, или лист, — это вершина дерева, соединённая ровно с одним соседом. Листья находятся на «краях» дерева: через них нельзя пройти дальше, не возвращаясь по уже пройденному ребру.
Чтобы определить, является ли вершина листом, сначала используют понятие степени вершины: считают, сколько рёбер с ней соединено. Если степень равна \(1\), вершина листовая. В корневом дереве иногда отдельно учитывают корень: если у корня один потомок, его степень в неориентированном дереве равна \(1\), поэтому по обычному определению корень тоже является листом.
Сколько листьев бывает у дерева
В любом дереве с числом вершин \(n \ge 2\) есть хотя бы два листа. Например, если выбрать самый длинный простой путь в дереве, его концевые вершины не могут иметь дополнительных соседей вне этого пути: иначе путь можно было бы продолжить. Поэтому обе концевые вершины — листья.
Рассмотрим цепочку \(A-B-C-D-E\). Степени вершин равны: \(\deg(A)=1\), \(\deg(B)=2\), \(\deg(C)=2\), \(\deg(D)=2\), \(\deg(E)=1\). Значит, \(A\) и \(E\) — листовые вершины, а остальные вершины — не листья.
Листовая вершина — это не вершина, которая просто находится на рисунке с краю. Положение рисунка не имеет значения. Важна только степень: вершина является листом тогда и только тогда, когда у неё ровно один сосед. Также лист не следует путать с конечной точкой произвольного пути: это свойство самого дерева или выбранного подграфа.
В дереве степени вершин равны \(1, 1, 2, 2, 3, 3\). Сколько в нём листовых вершин?
Главное
- Листовая вершина — вершина дерева степени \(1\).
- У дерева, содержащего не менее двух вершин, есть хотя бы два листа.
- Положение вершины на рисунке не важно: лист определяется только числом её соседей.