Основи теорії графів. Властивості ойлерових та гамільтонових графів (стр. 7 из 8)

Доведення. Від супротивного. Нехай

— не гамільтонів. Додамо до мінімальну кількість нових вершин , … , , з'єднуючи їх з усіма вершинами так, щоб := + + … + був гамільтонів.

Нехай

, , , … , — гамільтонів цикл у графі , причому , , . Така пари вершин і у гамільтоновому циклі обов'язково знайдеться, інакше граф був би гамільтонов. Тоді , { ,…, },інакше вершина була б не потрібна. Більше того, вершина несуміжна з вершиною , інакше вершина була б не потрібна.

Далі, якщо в циклі

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

Останнім часом графи і пов’язані з ними методи досліджень використовуються практично в усіх розділах сучасної математики і, зокрема, дискретної математики.

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