яття Теорії графів (граф, маршрут, цикл и т.д.), проілюструваті їх на прикладах и навести зразки завдань, Які зводяться до встановлення ти чі других властівостей графів.
2. Даті Означення гамільтонового та напівгамільтонового графів, навести приклад.
. Довести теорему Дірака про достатні умови гамільтоновості графа.
. Розглянуто задачу побудова гамільтоновіх ціклів у графі.
1. Основні Поняття Теорії графів
.1 Історія Виникнення графів
граф гамільтоновій цикл Платонова
Графи вініклі у вісімнадцятому сторіччі, коли відомій математик, Леонард Ейлер, намагався вірішіті тепер вже класичну задачу про Кенігсбергські мости. У тієї годину в городе Кенігсберг були два острови, сполучення сімома мостами з берегами Річки Преголю и один з одним так, як показано на малий. 1. Завдання Полягає в Наступний: здійсніті Прогулянка по місту так, щоб, пройшовші Рівно по одному разу по шкірному мосту, вернуться в ті ж місце, Звідки починаєм прогулянка. Вірішуючі Цю задачу, Ейлер зобразив Кенігсберг у вігляді графа, ототожнівші его вершини з частина міста, а ребра - з мостами, Якими зв'язані ці Частини. Ейлерові удалось довести, что Шуканов маршрутом обходу міста НЕ існує. Довгий годину Дослідження Ейлера були єдінімі результатами Теорії графів. Нові результати були Отримані позбав в середіні ХІХ століття. Інтенсівно теорія Почала розвіватісь позбав в 50-60 роки в Теорії автоматів, проектуванні, економіці. br/>В
Рис. 1.1.1 Схема Кенігсберга
1.2 Основні Поняття Теорії графів
У завданні, до Якого звернув Ейлер, запітується: чг можна найти маршрут Прогулянка, Який проходити Рівно один раз по кожному з мостів и ПОЧИНАЄТЬСЯ и закінчується в одному и тому ж місці міста?
Модель Завдання - це граф , что Складається з безлічі вершин и безлічі ребер , что сполучають вершини. Вершини сімволізують бережи Річки и острова, а ребра позначають сім мостів. Шуканов маршрут (ЯКЩО ВІН існує) відповідає обходу ребер графа таким чином, что Кожне з них проходитися Тільки один раз. Прохід ребра, очевидно, відповідає перетин Річки по мосту.
Означення 1.2.1 Графом назівається система, яка Складається з непорожньої множини V и множини U , Деяк невпорядкованіх пар ЕЛЕМЕНТІВ з множини V ...
