Контрольні питання

Що таке: а) орграф, б) дуга орграфу, в) початок (кінець) дуги?

Що таке: а) напівстепінь заходу (виходу) вершини орграфу, б) степінь вершини орграфу?

Що таке: а) матриця суміжності орграфу, б) матриця інцидентності орграфу?

Як подати орграф у вигляді діаграми?

Що таке: а) шлях (орланцюг, контур) у орграфі, б) напівшлях (напівланцюг, напівконтур) у орграфі?

Який орграф називається: а) повним, б) сильно зв’язним, в) слабо зв’язним, г) незв’язним?

Що таке: а) орієнтоване (упорядковане орієнтоване) дерево, б) бінарне дерево?

Що таке глибина (висота, рівень) вершини орієнтованого дерева?

Що таке висота орієнтованого дерева?

Яке бінарне дерево називається повним?

Задачі та вправи

І. Побудувати орграф скінченного порядку, що: а) є простим; б) є повним; в) є однорідним; г) має стільки ж дуг, скільки вершин; д) має удвічі більше дуг, ніж вершин; е) має удвічі більше вершин, ніж дуг.

ІІ. Для заданого орграфу визначити: а) які вершини суміжні; б) які дуги суміж-ні; в) які вершини та дуги інцидентні; г) напівстепінь заходу та напівстепінь виходу кожної вершини; д) чи має орграф вершини, з яких досяжна (не до-сяжна) кожна (жодна) його вершина; е) чи має орграф вершини, які досяжні (не досяжні) з кожної (жодної) його вершини; є) чи є він ациклічним; ж) чи є він слабо зв’язним (сильно зв’язним); з) чи є він орієнтованим деревом.

1) ({1,2,3},{(1,2),(3,2)});

2) ({1,2,3,4,5},{(1,3),(1,4),(2,4),(2,5),(3,4),(4,5)});

3) ({1,2,3,4,5,6},{(1,2),(1,6),(2,3),(3,4),(4,5)});

4) ({1,2,3,4},{(1,2),(1,3),(1,4),(2,3),(2,4),(4,3)});

5) ({1,2,3,4,5},{(1,4),(2,4),(4,5),(4,3),(1,1),(3,3)});

6) ({1,2,3,4,5,6},{(1,2),(1,5),(3,4),(5,6),(6,2)});

7) ({1,2,3,4,5,6,7,8,9},{(1,2),(2,7),(7,1),(7,9),(5,6),(8,7)});

8) ({1,2,3},{(1,1),(1,2),(2,3),(3,3)});

9) ({1,2,3},{(1,2),(1,1),(2,1),(2,2),(2,3),(3,3)});

10) ({1,2,3,4,5,6},{(1,4),(5,2),(3,6)}).

ІІІ. Сформулювати правила побудови:

1) діаграми орграфу за його матрицею суміжності (й навпаки);

2) діаграми орграфу за його матрицею інцидентності (й навпаки);

3) матриці інцидентності орграфу за його матрицею суміжності (й навпаки).

ІV. Для заданого орієнтованого дерева Т визначити: а) чи є Т бінарним (пов-ним бінарним); б) множину листків Т; в) напівстепінь виходу кореня; г) гли-бину (висоту, рівень) кожної вершини; д) висоту Т.

1) Т=({1,2,3,4,5,6,7},{(1,2),(1,3),(2,4),(2,5),(2,6),(3,7)});

2) Т=({1,2,3,4,5,6,7},{(1,2),(2,3),(2,4),(4,5),(5,6),(5,7)});

3) Т=({1,2,3,4,5,6,7},{(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)});

4) Т=({1,2,3,4,5,6,7},{(1,2),(1,3),(1,4),(2,5),(3,6),(6,7)});

5) Т=({1,2,3,4,5,6,7},{(1,2),(2,3),(3,4),(3,5),(5,6),(6,7)}).

Лекція 6. Алгоритми на графах Обходи орієнтованих дерев

При виконанні алгоритмів, що використовують орієнтовані дерева, часто здійснюється обхід (відвідування) вершин дерева у деякому порядку. Відомі кілька способів організації таких обходів. Розглянемо процедури обходу орієнтованого дерева у прямому порядку та зворотному порядку. Нехай Т – упорядковане орієнтоване дерево; корінь дерева позначимо r.

Процедура обходу упорядкованого орієнтованого дерева у прямому порядку:

1) відвідати корінь r;

2) якщо v₁,…,v_k – дочірні вершини r, то застосувати процедуру обходу упорядкованого орієнтованого дерева у прямому порядку до піддерев з коренями v₁,…,v_k у зазначеному порядку.

Процедура обходу упорядкованого орієнтованого дерева у зворотному порядку:

1) якщо v₁,…,v_k – дочірні вершини r, то застосувати процедуру обходу упорядкованого орієнтованого дерева у зворотному порядку до піддерев з коренями v₁,…,v_k у зазначеному порядку;

2) відвідати r.

Розглянемо приклад. Нехай задано орієнтоване упорядковане дерево Т=({v₁,v₂,v₃,v₄,v₅,v₆,v₇},{(v₁,v₂),(v₁,v₃),(v₁,v₄),(v₃,v₅),(v₅,v₆),(v₅,v₇)}). Будемо вважа-ти, що сини кожної вершини упорядковані згідно зі своїми номерами (наприклад, сини вершини v₁ упорядковані таким чином: v₂,v₃,v₄). Застосуємо до Т процедури обходу у прямому та зворотному порядку. Щоб відобразити порядок, у якому обходяться вершини дерева Т, будемо нумерувати верши-ну, коли вона відвідується. Нумерацію здійснюватимемо за допомогою цілих додатних чисел. Результати обходу Т у прямому та зворотному порядку зображено на рис.19,а,б.

Для обходу бінарного дерева визначимо процедуру обходу у внутрішньому порядку. Кожна вершина бінарного дерева, яка не є листком, має одного або двох синів. Нехай маємо упорядковане бінарне дерево. При-пишемо кожній його вершині, що є сином якоїсь вершини, одну з ознак: лівий (син) чи правий (син). Зазначимо, що коли вершина має лише одного сина, то він може мати будь-яку з цих ознак.

а)	б)
Рис. 19

Процедура обходу упорядкованого бінарного дерева у внутрішньому порядку:

1) якщо корінь дерева r має лівого сина v_l, то застосувати процедуру обходу упорядкованого бінарного дерева у внутрішньому порядку до піддерева, що визначається вершиною v_l;

2) відвідати корінь r;

3) якщо корінь дерева r має правого сина v_r, то застосувати процедуру обходу упорядкованого бінарного дерева у внутрішньому порядку до піддерева, що визначається вершиною v_r.

Розглянемо приклад. Нехай задано бінарне дерево Т=({a,b,c,d,e,f},{(a,b), (a,c),(b,d),(c,e),(e,f)}). Припишемо кожній вершині-сину ознаку лівий або правий: b – лівий син вершини a, c – правий син вершини a, d – правий син вершини b, e – правий син вершини c, f – лівий син вершини e. Діаграма бінарного дерева Т зображена на рис.20,а. Ознаки лівий-правий визначаються нахилом дуг. На рис.20,б,в,г зображено результати обходу Т у прямому, зворотному та внутрішньому порядку.

а)	б)	в)	г)
Рис. 20