Введение в информационные системы. Брюхомицкий Ю.А. - 63 стр.

UptoLike

Составители:

Рубрика:

Связав вершины р – 1 ребрами так, чтобы отсутствовали циклы, полу-

чим некоторое дерево, покрывающее данное множество р вершин. При р = 2

такое дерево единственно и состоит из одной ветви (рис. 5.9).

Рис. 5.9. Дерево при р = 2

С увеличением р число различных деревьев t

быстро возрастает и вы-

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

= p

p - 2

Многие из них являются изоморфными, т.е. отличаются только нумера-

цией вершин. Так, при р = 10 имеем 10

различных деревьев, из которых только

106 неизоморфны. Обычно деревья считаются существенно различными, если

они не изоморфны.

Деревья на множествах р = 3 и р = 4 показаны на рис. 5.10, а и б соот-

ветственно. При этом неизоморфным для р = 3 является только одно дерево

(рис. 5.10, в), а для р = 4 – только два дерева (рис. 5.10, г).

Рис. 5.10. Деревья на множестве р = 3 (а), р = 4 (б) вершин и

неизоморфные деревья для р = 3 (в) и р = 4 (г)