Математическое моделирование на графах. Часть 1. Берцун В.Н. - 30 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

30 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
цвета и т.п.). Например, на рис. 1.32 изображены два различных по-
меченных дерева, содержащих одно и то же множество вершин.
1
2
3
4
5
6
3
2
1
4
5
6
Рис. 1.32
Пусть нумерация вершин дерева G с n вершинами (1, 2, …,n) при
различном соединении их ребрами остается неизменной. В дереве
всегда есть хотя бы две висячие вершины. Выберем ту из них, кото-
рая имеет минимальный номер, и удалим ее вместе с инцидентным
ей ребром. Если другой конец этого ребра был инцидентен вершине
с номером i
1
, то эту вершину поместим в вектор v(i
1
). На втором и
последующих шагах процесс повторяется, пока не останется одно
ребро. Таким образом, получим вектор v(i
1
, i
2
,…, i
n–2
), состоящий из
n – 2 компонент, который называется кодом дерева G. Например, для
дерева на рис. 1.32, а – v(2, 2, 2, 5), а для дерева на рис. 1.32, б –
v(1, 2, 2, 5).
Утверждение 1.8 (теорема Кэли). Число различных помеченных
деревьев с n вершинами t
p
= n
n–2
.
Доказательство. Число возможных вариантов записи кода дере-
ва v(i
1
, i
2
,…, i
n–2
) совпадает с числом размещений с повторениями из
n элементов по n – 2 [26, 27]. Тогда число различных помеченных
деревьев
22nn
pn
tA n
−−
==. ■
Отметим, что в формуле Кэли подсчитывается число всех поме-
ченных деревьев. Если их рассматривать как свободные деревья, то
многие из них изоморфны. В табл. 1.3 для четырех значений n при-
ведено число различных деревьев [28, 29 ].

Страницы