Історія виникнення графів, основні поняття теорії та різновиди: повні, регулярні, платонові, двочастинні. Маршрути, ланцюги і цикли. Означення гамільтонового та напівгамільтонового графа, достатні умови. Задача побудови гамільтонових циклів у графі.
Краткое сожержание материала:

Размещено на

Размещено на

Курсова робота

«Гамільтонові графи»

Вступ

Традиційно до дискретної математики відносять такі області математики, як комбінаторика, теорія чисел, математична логіка, теорія систем алгебри, теорія графів і мереж і так далі. Дискретна математика завжди залишалася найбільш динамічною областю знань. Сьогодні найвагомішою областю застосування методів дискретної математики є область комп'ютерних технологій. Це пояснюється необхідністю створення і експлуатації електронно обчислювальних машин, засобів передачі і обробки інформації, автоматизованих систем управління і проектування. На грані дискретної математики і програмування з'являються нові дисципліни, такі як розробка і аналіз обчислювальних алгоритмів, комбінаторні алгоритми та алгоритмізація процесів. Дискретна математика і дисципліни, що є суміжними з нею, вивчаються в всіх університетах і інститутах, де здійснюється підготовка фахівців в області програмування, математики, а також по економічних, технічних і гуманітарних напрямах.

Проблема теорії графів є однією з актуальних проблем сучасної дискретної математики. Її вирішення дозволить ефективно застосовувати отриманні знання в різних галузях науки і техніки.

Теорія графів - молода область дискретної дискретної математики. Порте методи теорії графів завоювали визнання не тільки математиків, а й інженерів, економістів, психологів, біологів, хіміків. Використання мови і методів теорії графів прискорює розв'язання практичних задач, спрощує розрахунки. Теорія графів є однією з важливих частин математичного апарату інформатики і кібернетики. У термінах теорії графів формулюють велику кількість задач, пов'язних з дискретними об'єктами. Вивчення достатніх умов існування в графі гамільтонового циклу - один із важливих напрямків у теорії графів.

Мета курсової роботи - дослідити основні властивості гамільтонових графів, розглянути приклади практичного застосування відшукання гамільтонового циклу.

Об'єкт дослідження - теорія графів.

Методи дослідження - теоретичний аналіз наукової літератури з проблеми, аналіз навчальних програм, підручників.

Завдання дослідженя:

1. Означити основні поняття теорії графів (граф, маршрут, цикл і т.д.), проілюструвати їх на прикладах і навести зразки задач, які зводяться до встановлення ти чи інших властивостей графів.

2. Дати означення гамільтонового та напівгамільтонового графів, навести приклади.

3. Довести теорему Дірака про достатні умови гамільтоновості графа.

4. Розглянути задачу побудови гамільтонових циклів у графі.

1. Основні поняття теорії графів

1.1 Історія виникнення графів

граф гамільтоновий цикл платоновий

Графи виникли у вісімнадцятому сторіччі, коли відомий математик, Леонард Ейлер, намагався вирішити тепер уже класичну задачу про Кенігсбергські мости. У той час в місті Кенігсберг були два острови, сполучених сімома мостами з берегами річки Преголь і один з одним так, як показано на мал. 1. Завдання полягає в наступному: здійснити прогулянку по місту так, щоб, пройшовши рівно по одному разу по кожному мосту, повернутися в те ж місце, звідки починалася прогулянка. Вирішуючи цю задачу, Ейлер зобразив Кенігсберг у вигляді графа, ототожнивши його вершини з частинами міста, а ребра - з мостами, якими зв'язані ці частини. Ейлерові вдалося довести, що шуканого маршруту обходу міста не існує. Довгий час дослідження Ейлера були єдиними результатами теорії графів. Нові результати були отримані лише в середині ХІХ століття. Інтенсивно теорія почала розвиватись лише в 50-60 роки в теорії автоматів, проектуванні, економіці.

Рис. 1.1.1 Схема Кенігсберга

1.2 Основні поняття теорії графів

У завданні, до якого звернувся Ейлер, запитується: чи можна знайти маршрут прогулянки, який проходить рівно один раз по кожному з мостів і починається і закінчується в одному і тому ж місці міста?

Модель завдання - це граф, що складається з безлічі вершин і безлічі ребер, що сполучають вершини. Вершини символізують береги річки і острова, а ребра позначають сім мостів. Шуканий маршрут (якщо він існує) відповідає обходу ребер графа таким чином, що кожне з них проходиться тільки один раз. Прохід ребра, очевидно, відповідає перетину річки по мосту.

Означення 1.2.1 Графом називається система, яка складається з непорожньої множини V і множини U, деяких невпорядкованих пар елементів з множини V. Множина V називається вершинами, U - ребрами.

Дві вершини U і V в простому графові називаються суміжними, якщо вони з'єднуються будь-яким ребром, про яке говорять, що воно інцидентне вершині u. Аналогічно вводиться поняття суміжних ребер. Таким чином, ми можемо уявляти собі множину ребер як множину пар суміжних вершин, визначаючи тим самим нерефлексивне, симетричне відношення на множині V'. Відсутність рефлексивності пов'язана з тим, що в простому графові немає петель, тобто ребер, обидва кінці яких знаходяться в одній вершині. Симетричність же відношення витікає з того факту, що ребро, що сполучає вершину U з V, (інакше кажучи, ребра не орієнтовані, тобто не мають напряму).

Приведемо приклад задачі, яка може бути розв'язана, за допомогою графів.

Задача 1.2.1:

На вечірку запрошено шестеро людей, чи може бути така ситуація, що кожен знав тільки двох запрошених.

Розв'язання:

Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх. Якщо двоє знайомі, то з'єднаємо їх відрізком (ребром). Виявляється, що така ситуація не тільки можлива, але й може описуватися декількома схемами.

Тобто можна сказати, що граф - це сукупність об'єктів, зв'язками між якими служать ребра.

Приклади графів з декількома вершинами та ребрами. На рис. 1.2.1 показаний граф з чотирма вершинами та п'ятьма ребрами На рис. 1.2.2 зображено граф з п'ятьма вершинами та двома ребрами

Рис. 1.2.1 Рис. 1.2.2

Прикладами графів можуть слугувати схеми метрополітенів, схеми шосейних чи залізничних доріг, карти, які показують зв'язки між окремими об'єктами.

Лема 1.2.1 (Про рукостискання). Сума степенів всіх вершин графа є парним числом.

Дійсно, кожне ребро вносить у суму всіх вершин графа число 2, тобто



Якщо інтерпретувати кожне ребро як рукостискання двох людей, то отримаємо, що при будь-якому числі рукостискань загальна кількість потиснутих рук буде парною.

Наслідок 1.2.1 У будь-якому графі число вершин непарного степеня парне. Дійсно, якби це було не так, то сума степенів всіх вершин графа не могла б бути парним числом, що суперечить лемі про рукостискання.

Графи зручно зображувати на площині або в просторі у вигляді діаграм, які складаються з точок і відрізків, що з'єднують деякі з цих точок. При цьому точки ототожнюються з вершинами графа, а відрізки - з його ребрами.

Граф може містити декілька однакових ребер. Такі ребра називаються кратними. Граф який містить кратні ребра називається мультиграфом.

Означення 1.2.2 Підграфом графа G = (V, Е) називається граф G' = (V', Е'), у якому Е' з Е і V з V.

Якщо кінці ребра співпадають то він називається петлею.

Граф, який містить кратні ребра і петлі називається псевдографом.

Рис. 1.2.3 Зображено а) псевдограф, б) мультограф, в) граф

1.3 Різновиди графів

Розглянемо деякі різновиди графів, які часто зустрічаються.



Рис. 1.3.1 Граф К₄ Рис. 1.3.2 Граф К₅

Повні графи

Означення 1.3.1.1 Граф, будь-які дві вершини якого суміжні, називається повним графом. Отже, якщо G= (V, Е) - повний граф, то Е = V². Повний граф з n вершинами позначаємо Кn Графи К4 і К5 зображені на рис. 1.3.1 і 1.3.2 відповідно.

Р...