Практичне заняття №15-1. Дерева та їх застосування

1. Які з наведених нижче графів є деревами?

а) б) в)

г) д) е)

є) ж) з)

2. Для кожного дерева з попередньої вправи:

a) використовуйте як корінь вершину і намалюйте кореневе дерево;

b) намалюйте породжене кореневе орієнтоване дерево;

c) використовуйте як корінь вершину і намалюйте кореневе дерево;

d) намалюйте породжене кореневе орієнтоване дерево.

3. Покажіть, що якщо ліс містить компонент, то .

4. Які з наведених нижче графів є кореневими орієнтованими деревами?

а) б) в)

г) д)

5. Для кореневого орієнтованого дерева, зображеного на мал.:

a) знайдіть нащадків вершини ;

b) знайдіть предків вершини ;

c) знайдіть батька вершини ;

d) визначте рівень вершини

e) знайдіть синів вершини ;

f) знайдіть висоту дерева;

g) знайдіть листи дерева;

h) визначте, чи є це дерево бінарним?

6. Для кореневого орієнтованого дерева, зображеного на мал.:

a) знайдіть нащадків вершини ;

b) знайдіть предків вершини ;

c) знайдіть батька вершини ;

d) визначте рівень вершини ;

e) знайдіть синів вершини ;

f) знайдіть висоту дерева;

g) знайдіть листи дерева.

7. Намалюйте генеалогічне дерево, починаючи з одного зі своїх прадідів.

8. Намалюйте генеалогічне дерево, починаючи з однієї зі своїх прабаб (але не із дружини прадіда з попереднього завдання).

9. Які з наведених нижче графів являють собою дерева?

10. Дати відповідь на запитання щодо дерева, зображеного на рисунку.

а) Яка вершина являє собою корінь?

б) Які вершини внутрішні?

в) Які вершини являють собою листки?

г) Які вершини – сини вершинну ?

д) Яка вершина – батько вершини ?

є) Які вершини – предки вершини ?

ж) Які вершини – нащадки вершини ?

11. Для яких значень й повний дводольний граф являє собою дерево?

12. Скільки ребер має дерево з 1000 вершинами?

13. Скільки вершин має повне 5-арне дерево зі 100 внутрішніми вершинами?

14. Скільки ребер має повне бінарне дерево з 1000 внутрішніх вершин?

15. Скільки листків має повне 3-арне дерево зі 100 вершинами?

16. У шаховому турнірі беруть участь 1000 гравців. Скільки ігор потрібно зіграти для визначення переможця, якщо турнір проводять за олімпійською системою (той, хто програв, вибуває)?

17. Чи існує повне -арне дерево Т, яке має 84 листки та висоту 3?

18. Побудувати завершене бінарне дерево висотою 4 та завершене 3-арне дерево висотою 3.

19. Довести, що завершене -арне дерево висотою має вершин і листків.

20. Ексцентриситет вершини в некореневому дереві – це довжина найдовшого простого шляху, який починається в цій вершині. Вершину називають центром, якщо вона має найменший ексцентриситет. Знайти центри дерев:

21. Довести, що центр у некореневому дереві можна знайти як корінь кореневого дерева з мінімальною висотою.

22. Довести, що дерево має один або два центри, суміжні між собою. Навести приклад дерева, яке має два центри.

23. Записати послідовності вершин упорядкованих кореневих дерев, наведених нижче, в разі їх обходу в прямому, зворотному та внутрішньому порядку.

24. Побудувати впорядковане кореневе дерево, обхід якого в прямому порядку дає послідовність , причому вершина має чотирьох синів, – трьох, – двох, й – по одному, а решта вершин – листки.

25. Показати, що обхід наведених нижче кореневих дерев зверху вниз дає однакові списки вершин.

26. Показати, що обхід наведених нижче кореневих дерев знизу вверх дає однакові списки вершин.

27. Довести, що впорядковане кореневе дерево можна однозначно задати списком вершин, одержаним обходом у прямому порядку, якщо для кожної вершини зазначити кількість її синів.

28. Довести, що впорядковане кореневе дерево можна однозначно задати списком вершин, отриманим обходом у зворотному порядку, якщо для кожної вершини зазначити кількість її синів.