Деревья на множестве вершин
Пусть множество v содержит р вершин, которые пронумерованы v1,… vр. Связав эти вершины (р-1) ребрами так, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее данное множество р вершин. При р=2 такое дерево единственное и состоит из одной ветви. С увеличением р число различных деревьев tp быстро возрастает
tp=рр-2
многие из них являются изоморфными, т.е. отличаются только нумерацией вершин. Так при р=0 имеем 108 различных деревьев, из которых 106 неизоморфны.
На рис. показаны 16 различных деревьев, которые можно построить на множестве четырех вершин.
