lekcii_dm

nn 2

Определение.

Дерево с одной выделенной вершиной называется корневым деревом.

Определение

Ориентированный граф, состоящий из нескольких деревьев, называется

лесом.

Определение.

Пусть G=(Х, Г) – граф, являющийся лесом. Если дуга (v,w) принадлежит Г, то v называется отцом узла w, а w – сыном узла v.

Определение.

Если есть путь из v в w, то v называется предком узла w, а w –

потомком узла v.

Определение.

Узел без потомков называется листом.

Определение.

Узел v и его потомки вместе образуют поддерево леса G, и узел v называется корнем этого поддерева.

Определение.

Глубина узла v в дереве – это длина пути из корня в v.

Определение.

71

Высота узла в дереве – это длина самого длинного пути из этого узла в какой-нибудь лист.

Определение.

Высотой дерева называется высота его корня.

Пример

kl

Глубина узла b, в данном примере, = 1, а его высота = 2. Высота дерева

= 3.

Определение.

Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядоченно. При изображении упорядоченного дерева, как правило, считается, что множество сыновей каждого узла упорядоченно слева направо.

Определение.

Бинарным деревом называется такое упорядоченное дерево, что

1.Каждый сын произвольного узла идентифицируется либо как левый сын,

либо как правый сын.

2.Каждый узел имеет не более одного левого и не более одного правого сына.

72

Обратите внимание, что бинарное дерево не является частным случаем дерева, это совершенно иное, хотя и тесно связанное понятие.

Например:

AA

B B

Указанные бинарные деревья различны между собой ( в первом случае корень имеет пустое правое поддерево, а во втором левое поддерево пусто), хотя как деревья они изоморфны, и мы можем рассматривать их как одно дерево.

Определение. Бинарное дерево называется полным, если для некоторого целого числа K каждый узел, глубины меньшей k имеет как левого, так и правого сына, и каждый узел глубины k является листом.

Полное дерево глубины k имеет 2k 1 1 узлов.

Очень часто используются алгоритмы, которые проходят дерево (посещают каждый его узел) в некотором порядке. Известно несколько способов сделать это: прохождение дерева в прямом порядке, обратном порядке и внутреннем.

2.12. Помеченные графы. Перечисление помеченных деревьев.

Определение.

73

Граф с n вершинами называется помеченным, если его множество вершин X 1,n N .

Определение.

Помеченные графы G1 и G2 с n вершинами называются изоморфными, если существует биективное отображение :U1 U2 такое, что (композиция) f2 u f1 u u U1,i 1,2.

Замечание.

Это определение похоже на определение изоморфизмов теории графов, отличие состоит в том, что изоморфизм графов реализуется парой биективных отображений : X1 X 2 , :U1 U2 , а — тождественное отображение.

Пример:

Задача.

Сколько существует не изоморфных между собой неориентированных помеченных деревьев с n вершинами.

74

Обозначим число неизоморфных помеченных деревьев через T n . Ясно, что

T 1 1;T 2 1;T 3 3;T 4 16

Теорема Келли.

T n nn 2

Свои результат по перечислению деревьев А. Келли успешно применил для определения количества химических изомеров углеродов CnH2n+2.

Структурные формулы таких молекул таких соединений (вершины — атомы, дуги — валентные связи) представляют собой деревья.

Бутан

H

Изобутон

75

Замечание: из полученного пути можно выделить простую цепь.

2.14. Поиск оптимального пути (маршрута)

Утверждение 1

Каждый минимальный путь (маршрут) является простой цепью

являющийся простой цепью. Тогда i и j такие, что 1 i j k и vi=vj.

Рассмотрим путь 1... i j 1... k. Его длина меньше, чем , что противоречит предположению.

Утверждение 2

Минимальный подпуть из минимального пути минимален.

Пусть П 1 2... k 1 k - минимальный путь (маршрут) в орграфе

D (в графе G). Тогда для i и j таких, что 1 i j k путь (маршрут) П0 i i 1... j тоже является минимальным.

Доказательство.

Предположим, что П0 не является оптимальным, тогда П1 i... j

т.ч. он короче чем 0. Тогда заменив 0 на 1 в можно найти более

77

короткий, чем путь не является минимальным. Пришли к противоречию.

Пусть D (V,X) орграф V— некоторая вершина V, V1 V.

Обозначим D( ) { V|( , ) X} — образ вершины ; D 1( ) { V|( , ) X} — прообраз вершины ;

D(V1) D( ) — образ множества вершин V1 ;

V1

D 1(V1) D 1( ) прообраз множества вершин V1.

V1

Для неориентированного графа образ и прообраз совпадают. Пусть G (V,X) граф V, V1 V.

Обозначим G( ) { V| , X} — образ вершины ;

G(V1) G( ) — образ множества вершин V1.

V1

Пусть D (V,X) орграф с n 2 вершинами и v,w (v w) – заданные вершины из V

Алгоритм поиска минимального пути из в в орграфе D

(алгоритм фронта волны).

1) Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.

78

k 2 FWk 2( ) D 1( k 1)

........................................

1 FW1( ) D 1( 2)

есть этот минимальный путь. Работа завершается.

4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем FWk 1( ). Присваиваем k:=k+1 и переходим к 2).

Замечание 1

Множество FWk( ) называется фронтом волны kго уровня.

Замечание 2

Вершины 1 2 3... k 1 могут быть выделены неоднозначно, что соответствует случаю, если существует несколько минимальных путей из в .

79