Приклади ойлерових графів

2.3 Приклади ойлерових графів

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

Чи можна кожному з цих людей надати одну з тих посад, які йому підло-дять?

Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра (м,р), що з’єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд, наведений на рис.2.12:

Рис.2.12. Граф для рішення задачі про призначення на посаду

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

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

Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:

Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.

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

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

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