Содержание
- 2. §1 Ейлерові графи Однією з перших задач теорії графів у працях видатного математика ХVIII сторіччя Л.
- 3. Скінченний граф G є ейлеровим графом тоді й лише тоді, коли: 1) G – зв’язний; 2)
- 4. §2 Гамільтонові графи Гамільтоновим циклом називається простий цикл, що проходить через усі вершини розглянутого графа. Гамільтонів
- 5. Для 20 країн задача є обходом додекаедра: 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1
- 6. Гамільтонові графи
- 7. Графи, які не мають гамільтонових циклів Граф, який має гамільтонів ланцюг називають напівгамільтоновим.
- 8. Дерева.
- 9. §1 Основні визначення Деревом називається зв’язний граф без циклів. Дерево не може мати ані кратних ребер,
- 10. Усі можливі дерева з шістьма вершинами – неізоморфні.
- 11. Теорема (перелічуються властивості дерев, кожна з яких повністю схарактеризовує дерево). Еквівалентні є такі означення дерева: а)
- 12. §2 Остовне (Кістякове) дерево графа Вилучання з довільного зв’язного графа всіх циклових ребер дає в наслідок
- 13. Нехай у графі G виокремлено остовне дерево T. Ребра графа, які не ввійшли до T, називатимемо
- 14. Граф G Остовні дерева Т Т1 Т2 Т3 Т4 Т5
- 15. Довільний незв’язний граф, який не містить циклів, називається лісом. Еквівалентне визначення лісу: граф G, усі компоненти
- 16. §3 Кореневі дерева Дерево – це сукупність елементів, що називаються вузлами (один з яких корінь), та
- 17. Висота вузла дерева - це довжина самого довгого шляху з цього вузла до будь-якого листа. Висота
- 18. Повне бінарне дерево - це дерево для якого на всіх рівнях менше чим n вузли мають
- 19. Строго бінарне дерево складається тільки з вузлів, що мають степінь 2 або 0. Нестрого бінарне дерево
- 20. §4 Застосування графів і дерев 4.1 У вигляді графа можуть бути зображені: 1) Електричні і транспортні
- 21. 3) Структури молекул хімічних речовин; 4) Моделі кристалів; 5) Моделі ігор; 6) Інформаційні і комп'ютерні мережі;
- 22. 8) План діяльності або план виконання певних робіт (розклад). Наприклад, можливість переливання крові: 9) Лабіринти; 10)
- 23. 11) Генеалогічні дерева.
- 25. Скачать презентацию