Перечисление деревьев

– число помеченных деревьев с вершинами.

– число обычных (неизоморфных) деревьев с вершинами.

Пример. На рисунке 6.68 изображены все помеченные четырехвершинные деревья. Их 16.

Рисунок 6.68

Формула А. Кэли. Число помеченных деревьев с вершинами равно .

.

Числа обычных (неизоморфных) деревьев являются значительно меньшими, однако вычислить их существенно труднее. Современные алгоритмы нахождения значений и получения конфигураций неизоморфных деревьев с вершинами основаны на теории перечисления Д. Пойа.

Важный класс графов образуют деревья с одной помеченной вершиной, которая называется корнем. Само дерево с одной помеченной («выделенной») вершиной называется корневым деревом. Число корневых деревьев с вершинами обозначается через .

Все корневые деревья с числом вершин изображены на рисунке 6.69.

Рисунок 6.69

Все корневые деревья с числом вершин изображены на рисунке 6.70.

Рисунок 6.70