Короткі теоретичні відомості

Теорія графів.

Лабораторна робота №5.

Тема. Представлення дерев.

Мета. Використовуючи довільну мову програмування, побудувати модель бінарного дерева через список суміжностей і символ дерева (код Прюфера).

Короткі теоретичні відомості.

Дерева у прикладній теорії графів відіграють важливу роль у програмуванні, теорії інформаційних систем, електротехніці, хімії і т.п. Клас алгоритмів на деревах становить одних з найважливіших і найвикористовуваніших у програмуванні класів алгоритмів теорії графів.

Деревом називається зв’язний граф без циклів. Дерево називається кореневим, якщо у ньому виділена вершина, що називається коренем. Орієнтованим деревом з коренем r називається кореневе дерево, у котрому кожне ребро замінене дугою таким чином, що або з кожної вершини можна потрапити у корінь, рухаючись уздовж орієнтації дуг (вхідне дерево), або в кожну вершину можна потрапити з кореня, рухаючись вздовж орієнтації дуг (вихідне дерево). У вхідном орієнтованому дереві корінь досяжний з кожної вершини, у вихідному – кожна вершина досяжна з кореня. Приклад вихідного дерева, а також деякі основні поняття, що стосуються дерев, зображено на мал.1.

З усіх дерев виділяють бінарні дерева. Дерево називають бінарним, якщо воно визначається наступним рекурсивним шляхом:

· одновершинне дерево є бінарним деревом;

· трійка є бінарним деревом з коренем r, лівим піддеревом T_l і правим піддеревом T_r, причому як T_l, так і T_r теж бінарні дерева, можливо порожні.

Дерева представляються різним чином, але найпоширеніші способи – це список суміжності та символ дерева (код Прюфера).

Список суміжностей.

При представленні дерева списком суміжності кожній вершині дерева співставляється список суміжних вершин виду:

Тобто, кожен вузол такого списку відповідає за одну вершину дерева і містить в свою чергу ще один лінійний список, у вузлах котрого розміщені всі суміжні вершини до даної.

Код Прюфера (символ дерева)

Для представлення дерева Т кодом Прюфера використовують наступний алгоритм:

функ КОД_ПРЮФЕРА(Т: дерево)=

1. Нехай n – число вершин в графі Т, а

А – цілочисельний вектор довжиною п -2;

2. В == [1: n ];

3. для і від 1 до п -1 цикл

4. b = min { k Î B; k – номер висячої вершини}

5. A [ i ] = номер вершини, суміжної з вершиною з номером b;

6. B = B – { b }

7. Витерти з Т вершину з номером A [ i ]

Все

8. повернути А

Все

Для дерева, зображеного на мал. 2 код Прюфера має вигляд:

.

Розпаковка коду Прюфера здійснюється за алгоритмом:

функ РОЗПАКОВКА (А: код) =

1. Нехай Т складається з вершин { v₁,v₂,…,v_n } таких, що номер

вершини v_і рівний і, де п – довжина коду А плюс 2;

2. В == [1: n ];

3. для і від 1 до п -1 цикл

4. b = min { k Î B; k ¹ A [ j ] для будь-якого j ³ i };

5. В Т добавити ребро, що з’єднує вершини з номерами b та A [ j ];

6. B = B – { b }

Все

7. повернути Т

Все

У випадку кореневого дерева процедури побудови коду Прюфера та його розпаковки аналогічні. Необхідно тільки на останньому місці в А вказувати кореневу вершину і при розпаковці коду А виключати номер цієї вершини з множини В.