Основи теорії графів. Властивості ойлерових та гамільтонових графів
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
?аф гамільтонів.
Нагадаємо , що степінь вершини , тобто число ребер , які виходять з вершини .
Доведення.
Будемо доводити від супротивного. Припустимо , що існує негамільтонів граф з вершинами, в якому для будь-якої пари несуміжних вершин і виконується умова (3.1). Додавання до графа нових ребер не порушує умову (3.1). Позначимо через максимальний негамільтонів граф , тобто таrий граф , приєднання до якого нового ребра перетворює граф на гамільтонів. Вочевидь, не може бути повним графом, бо повний граф гамільтонів. Тому в існує пара несуміжних вершин і . Приєднання до ребра перетворює граф на гамільтонів в силу максимальної негамільтоновості . Таким чином , існує гамільтонів ланцюг. який сполучає і , він проходить через всі вершини ( рисунок 3.2)
Рис. 3.2. Гамільтонів ланцюг (1)
Оточимо кожну з , які суміжні з , кружечком, і вершину , яка лежить лівіше, квадратиком так, як зображено на рисунку, поданому нижче:
Рис. 3.3. Гамільтонів ланцюг(2)
з цих вершин оточені кружечком;
з цих вершин оточені квардатиком;
- не оточені квадратиком.
Зазначимо , що в силу умови теореми
Звідси випливає , що вершина суміжна з деякою вершиною, яка оточена квадратиком . Таким чином , виходить , що граф має гамільтонів цикл , зображений на рисунку 3.4
Рис.3.4. Гамільтонів ланцюг(3)
Отже прийшли до суперечності . Теорема доведена.
З теореми 3.1 випливає наступна теорема.
Теорема 3.2 (Г.Дірака, 1952) Якщо для будь-якої вершини графа з вершинами виконується нерівність , то граф гамільтонів.
Доведення. Від супротивного. Нехай не гамільтонів. Додамо до мінімальну кількість нових вершин , … ,, зєднуючи їх з усіма вершинами так, щоб := + + … + був гамільтонів.
Нехай , , , … , гамільтонів цикл у графі , причому , , . Така пари вершин і у гамільтоновому циклі обовязково знайдеться, інакше граф був би гамільтонов. Тоді , {,…,},інакше вершина була б не потрібна. Більше того, вершина несуміжна з вершиною , інакше вершина була б не потрібна.
Далі, якщо в циклі , , , … ,,, … , є вершина , суміжна з вершиною w, те вершина v несуміжна з вершиною v, тому що інакше можна було б побудувати гамільтонов цикл ,, … ,,, … , без вершини , взявши послідовність вершин , … , у зворотному порядку. Звідси треба, що число вершин графа , не суміжних з , не менш числа вершин, суміжних з . Але для будь-якої вершини графа d() ? p/2+n по побудові, у тому числі d() p/2+n. Загальне число вершин (суміжних і не суміжних з ) становить n+ p-1. Таким чином, маємо:
n+ p-1 = d(v)+d(V) ? d(w)+d(v) ? p/2+n+p/2+n = 2n+p.
Отже, 0 n+1, що суперечить тому, що n > 0. Теорема доведена.
3.3 Приклади гамільтонових графів
Приклад 3.1. Знайти всі гамільтонові цикли для графа, наведеного на рис.3. 5 [10]
Рис.3.5. Пошук всіх гамільтонових циклів для орієнтованого графа
Таблиця 3.1
Результати пошуку гамільтонових циклів
Приклад 3.2. Знайти найкоротший гамільтонов цикл в задачі комівояжера для 6 міст, розташованих згідно графу на рис.3.6 [10]
Рис.3.6. Графи при вирішенні задачі комівояжера [ ]
Результати розрахунків довжини гамільтонових циклів в задачі комівояжера (рис.3.6) наведені в табл.3.2
Таблиця 3.2
Результати розрахунків довжини гамільтонових циклів
Приклад 3.3. Покажіть, що граф, зображений на рисунку 3.7 , не є гамільтоновим [11].
Рис. 3.7. Приклад не гамільтонового графа
Розвязання.
Припустимо, що в звязному графі знайдеться гамільтонов цикл. Кожна вершина v включается в гамільтонів цикл С вибором двох інцидентних з нею ребер, а значить, степінь кожної вершини в гамільтоновому циклі (після вида-лення зайвих ребер) дорівнює 2. Степень вершин даного графа 2 чи 3. Вер-шини степеня 2 входять в цикл разом з обома інцидентними з ними ребрами. Отже,ребра аb, ае, cd, cb, hi, hg и ij у тім або іншому порядку входять в гаміль-тонов цикл С (див. рис. 3.8).
Ребро bf не може бути частиною циклу С, оскільки кожна вершина
Такого циклу повинна мати ступінь 2. Значить, ребра fj і fg зобовязані входити в цикл С, щоб включити в нього вершину f . Але тоді ребра je и gd ніяк не мо-жуть належати циклу С, оскільки у противному випадку у ньому зявляться вершини степеня три. Це змушує нас включити в цикл ребро ed, що приводить нас до протиріччя: ребра, котрі ми були змушені вибрати, утворюють два незвязних цикла, а не один, існування котрого ми припускали. Висновок: граф, зображений на рисунку 3.8, не є гамільтоновим
Рис.3.8. До доведення негамільтоновості графа
ВИСНОВКИ
Теорія графів це розділ дискретної математики, особливістю якого є геометричний підхід до вивчення обєктів. Основне поняття теорії граф. Поняття графа опирається на основні поняття теорії множин, тому що граф можна розглядати як обєкт, що складається із двох множин множини крапок (вершин) X і множини ліній (ребер) W, які зєднують деякі вершини, кожне ребро являє собою неупорядковану пару вершин із множини X.
При цьому зовсім несуттєво, чи зєднані вершини графа відрізками прямих ліній або криволінійних дуг, яка довжина ліній, як розташовані вершини графа на площини й інші геометричні характеристики графа.
Останнім часом графи і повязані з ними методи досліджень використовуються практично в усіх розділах сучасної математики і, зокрема, дискретної математики.
Гр