Деревья

Определение. Связный граф, не содержащий циклов, называют деревом. В общем случае граф без циклов (состоящий из деревьев), называются лесом. Дерево с n вершинами обозначают Т_n, лес, содержащий n вершин и k деревьев, обозначают W_n,k .

Пример дерева (Т₉) показан на рис.1.6 а) пример леса (W_16,3) ― на рис. 1.6 б).

Определение. Звездой называют дерево, у которого все рёбра инцидентны в одной вершине, называемой центром звезды. Рёбра звезды называют лучами.

Примеры звёзд с количеством лучей m = 0,1,5,8 показаны на рис.1.7.

а б

Рис.1.6. Дерево Т₉ и лес W_16,3

Рис.1.7. Примеры звёзд с количеством лучей m = 0,1,5,8

Деревья являются одним из наиболее распространенных видов графов, используемых при анализе и синтезе систем, алгоритмов и других объектов. Рассмотрим примеры применения деревьев.