Xreferat.com » Рефераты по математике » Основи теорії графів. Властивості ойлерових та гамільтонових графів

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

столя-ром і сантехніка і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому вказані люди не можуть одночасно влаштуватися на роботу.

Виділену умову ми коротко назвемо умовою різноманітності.

Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.

Приклад 2.2. Інші формулювання

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

Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайо-мими дівчатами?

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

А ось іще один варіант цієї задачі. В нашій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.

Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?

Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.

Щоб розв’язати цю задачу, ми знову звернемось до дводольного графа.

В цьому випадку одна множина вершин графа складатиметься із N гуртків,

А інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.

Якщо кількість гуртків занадто велика, не завжди легко довести спра-ведливість умови різноманітності. Тому поставимо питання: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибо-ру для них різних старост?

Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з п’яти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (додаток 2, де k = 4).


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

Рис.2.13. Граф для вирішення задачі вибору


Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в п’яти гуртках, це означатиме, що ребра від k гуртків повинні йти при-наймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана.

Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.


РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ


Сутність гамільтонових графів


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

Назва гамільтонів граф виникла у зв язку з тим , що в 1859 році відомий ірландський математик сер Вільям Гамільтон випустив до продажу своєрідну іграшкову головоломку . ЇЇ основою частиною був правильний додекаедр, зроблений з дерева (рис.3.1). Це один з так званих правильних багатогранників: його граням є 12 правильних п’ятикутників, в кожній з його вершин сходиться три ребра. Кожна з вершин гамільтонового додекаедра була позначена назвою одного з крупних міст Земної кулі –Брюсель, Кантон, Делі, Лондон і так далі. Задача полягає в знаходженні шляху вздовж ребер додекаедра, який проходить через кожне місто в точності один раз. Гамільтонів цикл на додекаедрі не пок-риває, звичайно, всіх ребер додекаедра, бо в кожній вершині він проходить в точності по двох ребрах.


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

Рис.3.1. Гамільтонів цикл у додекаедрі [4]


3.2 Основні поняття та означення


Означення 3.1.

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

Означення.3.2 .

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

Не дивлячись на подібність в означеннях ойлерових та гамільтонових графів, відповідно теорії для цих класів графів сильно відрізняються.

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

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

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

Встановлено різні достатні умови гамільтоновості графа . Сформулюємо дві з них.

Теорема 3.1.( О.Оре , 1960). Якщо для будь-якої пари Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графівнесуміжних вершин графа Основи теорії графів. Властивості ойлерових та гамільтонових графів з Основи теорії графів. Властивості ойлерових та гамільтонових графів вершинами Основи теорії графів. Властивості ойлерових та гамільтонових графів має місце нерівніть


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


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

Нагадаємо , що Основи теорії графів. Властивості ойлерових та гамільтонових графів степінь вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів , тобто число ребер , які виходять з вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів .

Доведення.

Будемо доводити від супротивного. Припустимо , що існує негамільтонів граф з Основи теорії графів. Властивості ойлерових та гамільтонових графів вершинами, в якому для будь-якої пари несуміжних вершин Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графів виконується умова (3.1). Додавання до графа нових ребер не порушує умову (3.1). Позначимо через Основи теорії графів. Властивості ойлерових та гамільтонових графів максимальний негамільтонів граф , тобто таrий граф , приєднання до якого нового ребра перетворює граф на гамільтонів. Вочевидь, Основи теорії графів. Властивості ойлерових та гамільтонових графів не може бути повним графом, бо повний граф гамільтонів. Тому в Основи теорії графів. Властивості ойлерових та гамільтонових графів існує пара несуміжних вершин Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графів . Приєднання до Основи теорії графів. Властивості ойлерових та гамільтонових графів ребра Основи теорії графів. Властивості ойлерових та гамільтонових графів перетворює граф Основи теорії графів. Властивості ойлерових та гамільтонових графів на гамільтонів в силу максимальної негамільтоновості Основи теорії графів. Властивості ойлерових та гамільтонових графів. Таким чином , існує гамільтонів ланцюг. який сполучає Основи теорії графів. Властивості ойлерових та гамільтонових графів і Основи теорії графів. Властивості ойлерових та гамільтонових графів , він проходить через всі вершини ( рисунок 3.2)


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

Рис. 3.2. Гамільтонів ланцюг (1)


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


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

Рис. 3.3. Гамільтонів ланцюг(2)


Основи теорії графів. Властивості ойлерових та гамільтонових графів з цих Основи теорії графів. Властивості ойлерових та гамільтонових графів вершин оточені кружечком;

Основи теорії графів. Властивості ойлерових та гамільтонових графів з цих Основи теорії графів. Властивості ойлерових та гамільтонових графів вершин оточені квардатиком;

Основи теорії графів. Властивості ойлерових та гамільтонових графів- не оточені квадратиком.

Зазначимо , що в силу умови теореми

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

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


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

Рис.3.4. Гамільтонів ланцюг(3)


Отже прийшли до суперечності . Теорема доведена.

З теореми 3.1 випливає наступна теорема.

Теорема 3.2 (Г.Дірака, 1952) Якщо для будь-якої вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів графа Основи теорії графів. Властивості ойлерових та гамільтонових графів з Основи теорії графів. Властивості ойлерових та гамільтонових графівОснови теорії графів. Властивості ойлерових та гамільтонових графіввершинами Основи теорії графів. Властивості ойлерових та гамільтонових графів виконується нерівність Основи теорії графів. Властивості ойлерових та гамільтонових графів, то граф Основи теорії графів. Властивості ойлерових та гамільтонових графів гамільтонів.

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

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

Далі, якщо в циклі Основи теорії графів. Властивості ойлерових та гамільтонових графів, Основи теорії графів. Властивості ойлерових та гамільтонових графів, Основи теорії графів. Властивості ойлерових та гамільтонових графів, … ,Основи теорії графів. Властивості ойлерових та гамільтонових графів,Основи теорії графів.
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: