Содержание
- 2. 5.1. Історія розвитку теорії графів Ейлер 1736 p. Головоломка про кенігсберські мости, у якій знайдено умову
- 3. Гамільтон 1859 р. Задача комівояжера, який виходить і повертається до вихідного міста так, щоб відвідати решту
- 4. 5.2. Основні терміни
- 5. Нехай X - довільна множина точок, Y - сукупність ліній, з'єднуючих задані точки у трьохвимірному просторі
- 6. Суміжні вершини (х2, х3) — це вершини, з'єднані ребром, суміжні ребра (у2, у3) — це ребра,
- 7. Граф G = (X, Y) називається: порожнім, якщо множина його ребер порожня; простим, якщо він не
- 8. Якщо на кожному ребрі обрати певний напрямок, то такий граф називається орієнтованим, а його ребра з
- 9. В орграфі, крім степеня вершини δ(х), вводиться додатний степінь δ+(х) — число дуг, що починаються у
- 10. Визначення абстрактного графа Графом G називається трійка G=(X,Y,f), де X, Y — довільні множини, f:Y→X×X —
- 11. 5.3. Способи задання графа список ребер матриця інциденцій матриця суміжності список суміжності
- 12. Список ребер G=(X,Y), X = {х1, х2, х3, x4, x5}; Y = {y1, y2, y3, y4,
- 13. Матриця інциденцій Оскільки вершини і дуги орграфа G=(X,Y,f) без петель занумеровані: X={х1,...,хn}, Y={у1,...,уm}, дію інцидентора f
- 14. Матриця інциденцій, приклад
- 15. Матриця суміжності Квадратна матриця А розміру n = |Х|, елемент якої аі,j дорівнює числу дуг, що
- 16. Матриця суміжності, приклад
- 17. Список суміжності Орієнтований граф G (без кратних дуг, але, можливо, з петлями) можна подати у вигляді
- 18. Список суміжності, приклад
- 19. Список суміжності, приклад х1 х2 х3 х4 х2 х3 х1 х3 х1 х2 х3 х5 х5
- 20. 5.4. Операції над графами 1 2 3 4 5 6 1 5 4 3 2 6
- 21. Два графа G і G' називаються ізоморфними (G ~ G'), якщо існують взаємно однозначні відображення вершин
- 22. Матриці суміжності дозволяють сформулювати простий алгебраїчний критерій ізоморфізму, який спирається на те, що вигляд матриць та
- 23. Підграф — будь-яка частина графа, що сама є графом. Остовний підграф – множини вершин співпадають, множина
- 24. Додатковим (доповненням) до графа G=(X,Y) називається граф G̃=(X,Ỹ) з тією ж множиною вершин, що доповнює G
- 25. Операції з двома графами Сума G+G1=(X;Y∪Y1) Перетин G∩G1=(X;Y∩Y1) = = ∪ ∩
- 26. При множенні GG1=(X;Y0) з вершини xi до вершини xj йде стільки дуг, скільки існує шляхів довжини
- 27. 5.5. Маршрути та зв'язність Маршрут (з'єднуючий вершини хa, хb) — скінченна послідовність ребер та інцидентних їм
- 28. Маршрут називається ланцюгом (шляхом – в орграфі), якщо всі його ребра (дуги) різні, і простим ланцюгом
- 29. Граф називається зв'язним, якщо будь-яка пара його вершин з'єднується ланцюгом. Орграф називається сильно зв'язним, якщо для
- 30. Точка зчленування графа — вершина, видалення якої разом з інцидентними їй ребрами призводить до збільшення числа
- 31. Ексцентриситет е(х) вершини x ∈ X у зв'язному графі G є відстань від x до найбільш
- 32. Центром графа G називається множина всіх його центральних вершин; центр може складатися з єдиної вершини, а
- 33. 5.6. Ейлерові графи Головоломка про кенігсберські мости. Чи можна здійснити прогулянку по місту, пройшовши по кожному
- 34. Ейлеровим шляхом у графі називають шлях, який містить кожне ребро графу рівно один раз. Замкнений ейлерів
- 35. Побудова ейлерового циклу (шляху). Алгоритм Флері 1. Ейлерів цикл можна починати з будь-якої вершини (ейлерів шлях
- 36. Приклад.
- 37. 5.7. Гамільтонові графи Головоломка “кругосвітня подорож”, запропонована у 1859р. ірландським математиком Уільямом Гамільтоном. Чи можна обїхати
- 38. Гамільтоновим шляхом у графі називають шлях, який містить кожну вершину графу рівно один раз. Замкнений гамільтонів
- 39. Задача про гамільтонів цикл не має на сьогодні ані повного теоретичного розв'язку, ані задовільного алгоритму відшукання
- 40. 5.8. Планарність графів Граф, що має плоску реалізацію, називається планарним.
- 41. Два графи називаються гомеоморфними, якщо після вилучення з них вершин другого степеня з подальшим об’єднанням інцидентних
- 42. 5.9. Розфарбування графів Під час розв’язання багатьох проблем доцільно розглядати графи з фарбованими вершинами – мічені
- 43. Приклад. Оцінити хроматичне число графа. Цей граф містить підграф, що є повним графом з трьома вершинами,
- 44. Приклад. Оцінити хроматичне число графа. Цей граф містить підграф, що є повним графом з чотирма вершинами,
- 45. Фарбування вершин графа Алгоритм Уелша-Пауелла Вершини графу впорядковуються за спаданням степенів. i=1. Вершина, що перша у
- 46. Приклад. Розфарбувати вершини графа. 1.Розташуємо вершини за спаданням степенів: v1,v4,v2,v3. 2.Зіставимо вершині v1 колір c1; вершин,
- 47. Однією з перших задач, пов’язаних із фарбуванням графів, є фарбування географічної карти так, щоб сусідні країни
- 48. Гранню (коміркою) плоского графа називається така непорожня замкнена підобласть площини, що будь-які дві точки області можна
- 49. Задачу фарбування граней графу можна звести до задачі фарбування вершин, якщо перейти від заданого графа до
- 50. Приклад. Розфарбувати грані графа. v1 v3 v2 v4 x1 x2 x3 Цей граф містить підграф, що
- 51. Приклад. Побудувати двоїстий граф. v1 v3 v2 v4 x1 x2 v5
- 52. Прикладні задачі, що зв'язані з розфарбуваннями: 1. Задача завантаження (розміщення) n продуктів (предметів) по ящикам (сховищам).
- 54. Скачать презентацию