"justify"> Наприклад, якщо один з людей є столяром, а другий - одночасно і столяром і сантехніком і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому зазначені люди не можуть одночасно влаштуватися на роботу.
Виділену умова ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватися працівниками служби зайнятості для правильного розміщення працівників на посади.
Приклад 2.2 Інші формулювання.
Ця задача, про встановлення на графі деякого відповідності між його вершинами, може мати й багато інших формулювань.
Припустимо, наприклад, що у нас є група з к хлопців і до дівчат. Дехто з них уже знайомі між собою, і виникає питання: у якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали з знайомими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; не допускається, щоб хлопець одружився на близькій родичці - сестрі, названої сестрі або двоюрідній сестрі. За якої умови для хлопця знайдеться наречена з цього села? Знову ми можемо вирішити цю задачу за допомогою двудольного графа - в цьому випадку його вершини будуть з'єднані ребрами лише тоді, коли відповідні люди не є родичами.
Ще один варіант цього завдання. У нашій школі є кілька гуртків: C1, C2., CN. Кожен з цих гуртків повинен мати старосту.
Для того, щоб виключити перевантаження учнів, була поставлена ??умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?
Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дуже велика, то це неможливо.
Щоб вирішити це завдання, ми знову звернемося до дводольний граф.
У цьому випадку одне множина вершин графа складатиметься з N гуртків
А інше множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група з до гуртків (при к=1, 2 ..., N) повинна включати щонайменше до різних учнів. Згідно вище вказаною - це та умова при якій гуртки можуть мати різних старост.
Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання: Чи можна вказати яку-небудь просте правило формування гуртків, яке гарантує можливість вибора для них різних старост?
Це дійсно можливо. Для того, щоб показати, що ми маємо на увазі, допустимо, що кожен гурток складається принаймні з п'яти учнів. Тоді на відповідному графі з кожної вершини множини С буде виходити принаймні 5 ребер. Для групи з до гуртків буде не менше 5k ребер, які виходять з відповідних вершин С до вершин з Р (додаток 2, де к=4).
Рис.2.13 Граф для вирішення завдання вибору
Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж у п'яти гуртках, це означатиме, що ребра від до гуртків повинні йти хоча б до до вершин з р, і, відповідно , умова різноманітності буде виконано.
РОЗДІЛ 3 Гамільтонових ГРАФИ
3.1 Сутність гамільтонових графів
Цикли Ейлера характеризуються властивістю проходити по одному разу через кожне ребро графа, а гамільтонів цикл - через кожну вершину.
Назва гамільтонів граф виникла у зв'язку з тим, що в 1859 році відомий ірландський математик Вільям Гамільтон випустив у продаж своєрідну іграшкову головоломку. Її основою частиною був правильний додекаедр, зроблений з дерева [4] (рис.3.1). Це один з так званих правильних багатогранників: його гранями є 12 правильних п'ятикутників, в кожній з його вершин сходиться три ребра.
Кожна з вершин гамільтонова додекаедра була позначена назвою одного з великих міст земного шара- Брюссель, Кантон, Делі, Лондон і так далі. Завдання полягає в знаходженнішляху вздовж ребер додекаедра, який проходить через кожне місто в точності один раз. Гамільтонів цикл на додекаедр не покриває, звичайно, всіх ребер додекаедра, тому що в кожній вершині він проходить в точності за двома ребрах.
Рис.3.1 Гамільтон цикл в додекаедрів
3.2 Основні поняття та визначення
Визначення 3.1.
Зв'язний граф називається гамільтоновим графом, якщо існує замкнута ланцюг, який проходить через кожну вершину графа рівно один раз.
Визначення 3.2.
Зв'язний граф називаєт...
