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

UptoLike

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

Рубрика:

34 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

большей ветви называется высотой ордерева. Изображение генеало-

гических (родословных) деревьев предполагает, что для дуги (u,v)

вершина u называется отцом (родителем) вершины v, а вершина v

называется сыном (потомком) вершины u. Сыновья одной вершины

называются братьями. Если в ордереве множество сыновей каждой

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

упорядоченным. На рис. 1.36 приведено упорядоченное родословное

дерево семьи швейцарских ученых Бернулли.

В классе орграфов существуют бинарные (двоичные) деревья, ко-

торые часто используются для хранения, обработки и представления

информации. Бинарное дерево состоит из корня и двух непересе-

кающихся бинарных деревьев – левого и правого, возможно пустых.

Такое дерево не является упорядоченным.

Например, на рис. 1.37 приведено левое и

правое бинарные деревья, которые изоморф-

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

свободные деревья, но не изоморфны как би-

нарные деревья.

На рис. 1.38 изображено двоичное дерево с весами, которое

используется при кодировании информации по алгоритму Хаффмана

[16]. В соответствии с этим деревом кода, например, слово ММF со-

ответствует двоичному коду: 000110001101001.

Рис. 1.38

Рис. 1.37