Практичне заняття №14. Пошук маршрутів у графа
1. Визначити, які пари графів, наведених нижче, ізоморфні.
2. Знайти кількість неізоморфних простих графів з 
вершинами, якщо дорівнює: а) 2; б) 3; в) 4.
3. Знайти кількість неізоморфних простих графів з п'ятьма вершинами та трьома ребрами.
4. Визначити, які пари орієнтованих графів ізоморфні.
5. Знайти кількість шляхів довжиною між двома різними вершинами графа Кn, якщо дорівнює 2; 3; 4; 5.
6. Знайти кількість шляхів довжиною між двома несуміжними вершинами графа Кn,n, якщо дорівнює 2, 3, 4, 5. Визначити те саме для суміжних вершин.
7. Визначити, які з наведених нижче графів мають ейлерів цикл. Зобразити його.
8. Чи можна утворити ейлерів цикл у разі розміщення мостів?
а) 
б) 
9. Серед наведених нижче графів знайдіть ті, які мають ейлеровий цикл.
а) 
б) 
в) 
г) 
д) 
е) 
ж) 
з) 
10. Серед наведених нижче графів знайдіть ті, які мають власний ейлеровий цикл.
а) 
б) 
в) 
г) 
д) 
е) 
є) 
ж) 
11. Які з наступних орієнтованих графів мають ейлеровий цикли?
а) 
б) 
в) 
г) 
д) 
е) 
є) 
ж) 
12. Доведіть, що граф (мультиграф або псевдограф) має власний ейлеровий шлях тоді й тільки тоді, коли він зв'язний і рівно дві його вершини мають непарний ступінь.
13. Доведіть, що якщо граф містить цикл від вершини 
до неї самої, то він містить простий цикл від вершини до неї самої.
14. Доведіть, що орієнтований граф є сильно зв'язним, якщо в графі існує вершина така, що кожна інша вершина графа досяжна з і вершина досяжна з будь-якої іншої вершини графа.
15. Доведіть, що орієнтований граф має ейлеровий шлях тоді й тільки тоді, коли він сильно зв'язний і ступінь входу кожної вершини дорівнює її ступені виходу.
16. Для яких значень графи 
; 
; 
; 
мають ейлерів цикл?
17. Для яких значень графи ; ; ; мають ейлерів шлях, але не мають ейлерового циклу?
18. Визначити довжину найкоротшого циклу в наведених нижче графах, який проходить через кожне ребро принаймні один раз:
а) 
; б) ; в) 
; г) 
.
19. Які з наведених нижче графів мають гамільтоновий цикл?
20. Знайдіть гамільтоновий цикл, якщо він існує, для кожного з наведених нижче графів.
а) 
б) 
в) 
г) 
д) 
е) 
ж) 
з) 
и) 
21. Намалюйте граф із шістьма вершинами, що має гамільтоновий цикл, але не має ейлерового циклу.
22. Намалюйте граф із шістьма вершинами, що має ейлеровий цикл, але не має гамільтонового циклу.
23. Для яких значень графи ; ; ; мають гамільтоновий цикл?
24. Для яких значень 
і граф має гамільтоновий цикл?
25. Навести приклад графа, який має ейлерів цикл, але не має гамільтонового циклу, а також графа, який має гамільтонів цикл, але не має ейлерового циклу. Як можна охарактеризувати графи, які мають водночас і ейлерів, і гамільтонів цикли?
26. Кожний з наведених нижче графів перевірити на планарність.
а) 
б) 
в) 
г) 
д) 
е) 
є) 
ж) 
27. Для кожного планарного графа з попередньої вправи перевірити, що 
.
28. Зв'язний планарний граф має шість вершин степеня 4. Скільки граней має цей граф?
29. Зв'язний планарний граф регулярний і містить 30 ребер. Кількість його граней дорівнює 20. Скільки вершин має цей граф?
30. Нехай зв'язний простий планарний граф містить 
вершин і ребер. Довести, що 
.
31. Нехай зв'язний дводольний планарний граф містить вершин і ребер. Довести, що 
.
32. Довести, що в будь-якому простому планарному графі є вершина, степінь якої не більший ніж 5.
33. За допомогою теореми Куратовського довести, що графи, наведені нижче, непланарні.
34. Побудувати графи, які відповідають наведеним нижче картам, і визначити найменшу кількість кольорів для їх розфарбовування.
35. Знайти хроматичні числа графів: а) ; б) ; в) ?