 |
|
Поняття орієнтованого дерева
Орієнтованим деревом називається орграф без напівконтурів, у якому існує вершина (коренева вершина, або корінь), з якої досяжна будь-яка інша вершина цього орграфу. Наприклад, орграф на рис.18,а є орієнтованим деревом, бо він не має напівконтурів, а з вершини 1 досяжні вершини 2 та 3. Орграф на рис.18,б також є орієнтованим деревом, оскільки у ньому немає напівконтурів, а з вершини 3 досяжні вершини 1 та 2. Орграф на рис.18,в не є орієнтованим деревом, тому що має напівконтур 1,2,3,1. Орграф на рис.18,г не є орієнтованим деревом, тому що з жодної його вершини не досяжні усі інші. З цієї ж причини не являється орієнтованим деревом й орграф на рис.18,д.
| 
| 
| 
| 
|
| а) | б) | в) | г) | д) |
| Рис. 18 |
Піддеревом орієнтованого дерева Т називається підграф дерева Т, який є орієнтованим деревом. Нехай Т=(V,E) – орієнтоване дерево, vÎV. Вершина v визначає піддерево Тv=(Vv,Ev) орієнтованого дерева Т, множина вершин якого (Vv) складається з вершини v та усіх досяжних з v вершин, а Ev= ={(u,w)|u,wÎVv, (u,w)ÎE}.
Розглянемо приклад. Нехай задано орієнтоване дерево Т=({1,2,3,4,5, 6,7,8},{(1,2),(1,3),(1,4),(2,5),(3,6),(3,7),(5,8)}). Вершина 2 визначає піддерево Т2=({2,5,8},{(2,5),(5,8)}), вершина 3 – піддерево Т3=({3,6,7}, {(3,6),(3,7)}), вершина 4 – піддерево Т4=({4},Æ).
Нехай T=(V,E) – орієнтоване дерево, (u,v)ÎE. Вершина u називається батьком вершини v, а вершина v – сином вершини u (або дочірньою вершиною вершини u). Вершина u орієнтованого дерева Т називається листком, якщо on(u)=0. Наприклад, у орієнтованому дереві ({1,2,3,4},{(1,2),(2,3),(2,4)}) вершини 3 та 4 є листками, вершина 1 являється батьком вершини 2, а вершина 2 – батьком вершин 3 та 4, вершина 2 є сином вершини 1, вершини 3 та 4 є дочірніми для вершини 2.
Орієнтоване дерево називається упорядкованим, якщо множина дочірніх вершин кожної його вершини упорядкована.
Орграф називається бінарним, якщо для будь-якої його вершини v on(v)£2. Бінарний орграф, що є орієнтованим деревом, називається бінарним деревом. Прикладом бінарного дерева є орграф Т=({1,2,3,4,5,6},{(1,2),(1,3),(2,4), (2,5),(3,6)}). Обчислимо для кожної вершини v орграфу Т напівстепінь виходу on(v) й переконаємося, що on(v)£2: on(1)=2, on(2)=2, on(3)=1, on(4)=0, on(5)=0, on(6)=0.
Нехай Т=(V,E) – орієнтоване дерево, vÎV. Глибиною вершини v (позначається d(v)) називається довжина шляху між коренем Т та вершиною v. Висотою вершини v (позначається h(v)) називається довжина найдовшого шляху між v та листком Т, досяжним з v. Висотою орієнтованого дерева Т (позначається hТ) називається висота вершини, що є коренем Т. Рівнем вершини v (позначається l(v)) називається величина hТ - d(v).
Нехай, наприклад, задано орієнтоване дерево Т=({1,2,3,4,5,6},{(1,2), (1,3),(3,4),(3,5),(4,6)}). Обчислимо висоту Т. Для цього потрібно визначити висоту кореня Т. Коренем Т є вершина 1, листки Т – вершини 2,5,6. Для кожного листка Т побудуємо шлях між коренем й цим листком. Маємо: 1,2 – шлях між 1 та 2; 1,3,5 – шлях між 1 та 5; 1,3,4,6 – шлях між 1 та 6. Найдовшим з цих трьох шляхів є шлях між 1 та 6; його довжина дорівнює трьом, отже, h(1)=hT=3. Аналогічно визначимо висоту кожної з некорене-вих вершин. Маємо: h(2)=h(5)=h(6)=0, h(3)=2, h(4)=1. Визначимо глибину кожної з вершин Т. Маємо: d(1)=0, d(2)=d(3)=1, d(4)=d(5)=2, d(6)=3. Об-числимо рівень кожної з вершин Т: l(1)=hT -d(1)=3-0=3, l(2)=hT -d(2)=3-1=2, l(3)=hT -d(3)=3-1=2, l(4)=hT -d(4)=3-2=1, l(5)=hT -d(5)=3-2=1, l(6)=hT -d(6)=3-3=0.
Бінарне дерево Т називається повним, якщо існує невід’ємне ціле число k таке, що для будь-якої вершини u бінарного дерева Т, глибина якої дорівнює k, on(u)=0, а для кожної вершини v, глибина якої менша k, on(v)=2. З даного означення випливає, що усі листки повного бінарного дерева мають однакову глибину, а напівстепінь виходу кожної вершини, що не є листком, дорівнює двом. Прикладом повного бінарного дерева є орграф Т=({1,2,3,4,5,6,7},{(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)}). Обчислимо глибину кожної вершини Т: d(1)=0, d(2)=1, d(3)=1, d(4)=d(5)=d(6)=d(7)=2. Обчислимо напівстепінь виходу кожної вершини Т: on(1)=on(2)=on(3)=2, on(4)=on(5)=on(6)=on(7)=0. Отже, для кожної вершини Т глибини два напівстепінь виходу дорівнює нулю, а напівстепінь виходу кожної вершини, глибина якої менша двох, дорівнює двом. Таким чином, Т є повним бінарним деревом. Бінарне дерево ({1,2,3,4}, {(1,2),(2,3),(2,4)}) не є повним, оскільки напівстепінь виходу вершини 1, яка не є листком, не дорівнює двом (on(1)=1).
Контрольні питання
1. Що таке: а) орграф, б) дуга орграфу, в) початок (кінець) дуги?
2. Що таке: а) напівстепінь заходу (виходу) вершини орграфу, б) степінь вершини орграфу?
3. Що таке: а) матриця суміжності орграфу, б) матриця інцидентності орграфу?
4. Як подати орграф у вигляді діаграми?
5. Що таке: а) шлях (орланцюг, контур) у орграфі, б) напівшлях (напівланцюг, напівконтур) у орграфі?
6. Який орграф називається: а) повним, б) сильно зв’язним, в) слабо зв’язним, г) незв’язним?
7. Що таке: а) орієнтоване (упорядковане орієнтоване) дерево, б) бінарне дерево?
8. Що таке глибина (висота, рівень) вершини орієнтованого дерева?
9. Що таке висота орієнтованого дерева?
10. Яке бінарне дерево називається повним?
Задачі та вправи
І. Побудувати орграф скінченного порядку, що: а) є простим; б) є повним; в) є однорідним; г) має стільки ж дуг, скільки вершин; д) має удвічі більше дуг, ніж вершин; е) має удвічі більше вершин, ніж дуг. Кожен з орграфів подати у вигляді: а) діаграми, б) матриці суміжності, в) матриці інцидентності.
ІІ. Для заданого орграфу визначити: а) які вершини суміжні; б) які дуги суміжні; в) які вершини та дуги інцидентні; г) напівстепінь заходу та напівстепінь виходу кожної вершини; д) чи має орграф вершини, з яких досяжна (не досяжна) кожна (жодна) його вершина; е) чи має орграф вершини, які досяжні (не досяжні) з кожної (жодної) його вершини; є) чи є він ациклічним; ж) чи є він слабо зв’язним (сильно зв’язним); з) чи є він орієнтованим деревом.
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)}).
III. На множині {1,2,3,4,5} задано бінарне відношення R={<1,1>,<1,2>, <2,1>,<2,2>,<3,5>,<5,3>}. Подати R у вигляді орграфу. Використати для подання: а) матрицю суміжності, б) матрицю інцидентності, в) діаграму.
ІV. Сформулювати правила побудови:
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)}).
VI. Побудувати усі попарно неізоморфні прості орграфи, що містять:
1) 3 вершини та 3 дуги;
2) 3 вершини та 4 дуги;
3) 4 вершини та 3 дуги.
VII. Як за допомогою: а) матриці інцидентності, б) матриці суміжності орграфу визначити:
1) напівстепені виходу та напівстепені заходу кожної вершини;
2) чи має орграф вершини, що не досяжні з жодної вершини орграфу;
3) чи має орграф вершини, з яких не досяжна жодна вершина орграфу;
4) чи є орграф повним?
VIII. Чи існує орграф із трьома вершинами, у якого напівстепені виходу вершин дорівнюють 2,2,0, а відповідні напівстепені заходу – 2,1,1?
ІХ. Побудувати:
1) усі попарно неізоморфні прості повні орграфи з трьома та чотирма вершинами; визначити серед них сильно зв’язні та слабо зв’язні орграфи;
2) усі попарно неізоморфні прості повні орграфи порядку 5, кожен з яких має принаймні одну вершину, з якої досяжна кожна інша вершина орграфу та принаймні по одній вершини, яка досяжна з кожної іншої вершини орграфу;
3) повний простий орграф порядку 6;
4) усі орієнтовані дерева порядку 4 та 5.
Х. Проведено турнір в одне коло (кожен учасник зустрівся з усіма іншими по одному разу) серед n баскетбольних команд. Визначити, скільки команд можуть:
1) не мати жодної поразки;
2) не мати жодної перемоги.
ХІ. Довести, що у повному орграфі:
1) існує вершина, з якої досяжна кожна інша вершина орграфу;
2) існує вершина, що досяжна з будь-якої іншої вершини орграфу;
3) не більше однієї вершини, що не досяжна з кожної іншої його вершини;
4) не більше однієї вершини, з якої не досяжна жодна інша його вершина;
5) існує простий ланцюг, що містить усі вершини орграфу.
ХІІ. Довести:
1) повний орграф сильно зв’язний тоді й тільки тоді, коли він має контур, що містить усі вершини орграфу;
2) будь-який шлях з вершини v у вершину w у орграфі містить простий ланцюг, що сполучає v з w;
3) будь-який циклічний шлях у орграфі містить контур;
4) орграф є сильно зв’язним тоді й тільки тоді, коли у ньому є замкнутий шлях, що містить усі вершини орграфу;
5) орграф є слабо зв’язний тоді й тільки тоді, коли у ньому є напівшлях , що містить усі вершини орграфу;
6) у безконтурному орграфі існує принаймні одна вершина, напівстепінь виходу якої дорівнює нулю, й принаймні одна вершина, напівстепінь заходу якої дорівнює нулю;
7) слабо зв’язний орграф є орієнтованим деревом тоді й тільки тоді, коли лише одна його вершина має напівстепінь заходу, рівний нулю, а кожна інша вершина має напівстепінь заходу, рівний одиниці.
ХІІІ. Нехай АG – матриця суміжності орграфу G з n вершинами. Довести:
1) кількість маршрутів довжини k між i-ю та j-ю вершинами орграфу G до-рівнює числу, що знаходиться на перетині i-го рядка та j-го стовпчика k-го степеня матриці AG;
2) вершина з номером j досяжна з вершини з номером i тоді й тільки тоді, коли число, що знаходиться на перетині i-го рядка та j-го стовпчика k-го степеня матриці AG для деякого k (0<k£n), більше 0.