Деревья на множестве вершин

Пусть множество v содержит р вершин, которые пронумерованы v₁,… v_р. Связав эти вершины (р -1) ребрами так, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее данное множество р вершин. При р =2 такое дерево единственное и состоит из одной ветви. С увеличением р число различных деревьев t_p быстро возрастает

t_p = р^р-2

многие из них являются изоморфными, т.е. отличаются только нумерацией вершин. Так при р =0 имеем 10⁸ различных деревьев, из которых 106 неизоморфны.

На рис. показаны 16 различных деревьев, которые можно построить на множестве четырех вершин.