Содержание
- 2. Зміст Вступ…………………………………………………. 3 Ейлер розв’язав.………………….........………….. ....4 Малій кроки є значущими.........……………………..6 Ейлерів цикл…………………………………...……..7 Теорема 1 ………………………………....…….........8 Крок
- 3. Вступ Початок теорії графів як розділу математики пов'язують із задачею про кенігсберзькі мости. Сім мостів міста
- 4. Ейлер розв’язав. Його розв’язання, опубліковане 1736 р., було першим явним застосуванням теорії графів. Ейлер поставив у
- 5. Отже, задачу про кенігсберзькі мости мовою теорії графів можна сформулювати так: чи існує в мультиграфі С
- 6. Ейлерів цикл Ейлеровим циклом у зв’язному мультиграфі С називають простий цикл, який містить усі ребра графа
- 7. Теорема 1 Зв’язний мультиграф С має ейлерів цикл тоді й лише тоді, коли степені всіх його
- 8. Крок 2. Достатність Почнемо шлях P1 із довільної вершини v1 продовжимо його, наскільки це можливо, вибираючи
- 9. Алгоритм Флері побудови ейлерового циклу Робота алгоритму полягає в нумерації ребер у процесі побудови ейлеровог циклу.
- 10. Крок 2. Ітерагоя. Нехай v — вершина, у яку ми перейшли на попередньому кроці, k —
- 11. Гамільтонів цикл у графі Шлях х0, х1 ..., xп_1,хп у зв’язному графі G = (V, E)
- 12. Кожній із двадцяти вершин додекаедра (правильного дванадцятигранника, грані якого — п’ятикутники) приписано назву одного з великих
- 13. Інтуїтивно зрозуміло, що граф із багатьма ребрами, достатньо рівномірно розподіленими, з великою ймовірністю має гамільтонів цикл.
- 14. Висновки Отже, для задач даного типу покищо не є відомий чіткий алгоритм, але є влучні спроби
- 16. Скачать презентацию