Научная работа: Розвязування задач за допомогою графів
Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.
Наприклад, якщо один з людей є столяром, а другий - одночасно і столяром і сантехніка і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому вказані люди не можуть одночасно влаштуватися на роботу.
Виділену умову ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.
Інші формулювання
Ця задача, про встановлення на графі деякої відповідності між його вершинами, може мати і багато інших формулювань.
Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайомими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умови для хлопця знайдеться наречена з цього села? Знову ми можемо розв’язати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть з’єднані ребрами лише тоді, коли відповідні люди не є родичами.
А ось іще один варіант цієї задачі. В нашій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.
Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?
Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.
Щоб розв’язати цю задачу, ми знову звернемось до дводольного графа.
В цьому випадку одна множина вершин графа складатиметься із N гуртків,
А інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.
Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибору для них різних старост?
Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з п’яти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (додаток 2, де k = 4).
Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в п’яти гуртках, це означатиме, що ребра від k гуртків повинні йти принаймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана.
Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.
Потрібно, щоб в кожному гуртку брало участь принаймні t учнів і щоб, окрім того, жоден учень не брав участь більше ніж в t гуртках. Тоді завжди можна знайти для цих гуртків різних старост.
Висновок: ця задача допоможе керівникам дитячих закладів при організації гурткової роботи.
Спортивні змагання
У всіх змаганнях доводиться стикатися з питанням про те, яким чином об'єднувати в пари окремих учасників. Іноді завдання виявляється простим: наприклад, якщо після кожного туру всі переможені вибувають із гри, то з учасників, що залишилися, утворюються нові пари, причому можливо, що один з них виявиться вільним від гри.
Це завдання дещо складніше у разі "кругового турніру", подібного до звичних шахових турнірів. Тут кожен з учасників повинен грати з кожним іншим, і важливо заздалегідь приготувати турнірну таблицю.
Цю ситуацію знову зручно змалювати за допомогою графа. Припустимо, що є N гравців, так що кожен з них грає N - 1 ігор з рештою учасників. Кожна гра як і раніше представляється ребром (A, B), що сполучає двох гравців, дві вершини A і В графа. Вся сукупність ігор представиться таким повним графом, що має N вершин, на додатку 3 зображений такий граф для N=6.
B кожному турі гравці якось об'єднуються в пари. припустимо поки, що N парне, і це можна зробити. На графі таке об'єднання в пари відповідає вибору ½N несуміжних ребер, поодинці для кожної з N вершин. Для наступного туру можна вибрати нову множину ½N ребер і так далі до тих пір, поки всі ігри не будуть зіграні. На додатку 3 ребра помічені таким чином: ті, на яких стоїть число 1, відносяться до пар, що зустрічаються в першому турі, ті на яких стоїть цифра 2 - до пар, що зустрічаються в другому турі, і так далі.
При великій кількості гравців фактичне складання такої таблиці для всіх турів відразу стає досить трудомістким, якщо не вказаний який-небудь систематичний метод. Багато довідників по проведенню турнірів містять просторові таблиці. Об'єднання гравців в пари для різних кількостей гравців (N=6, 8, 10, 12 і т.д.). При складанні таблиці досить припускати як і раніше, що кількість гравців N парна. Якщо вона виявиться непарною, то завжди можна додати фіктивного гравця F, домовившись, що той, хто повинен грати з F, в цьому турі вільний від гри.
Опишемо простий і цілком загальний метод побудови турнірної таблиці для парної кількості гравців N. Позначимо гравців числами 1, 2,..., N і запишемо ці числа в їх природному порядку в першому рядку квадратної таблиці. B наступному рядку цієї таблиці ми хочемо поставити номери суперників цих гравців в першому турі матчу. Аналогічно в третьому рядку ми випишемо номери суперників тих же гравців 1,2..., N в другому турі і т, д. до тих пір, поки всі гравці не зіграють один з одним. Ясно, що наша таблиця має бути такою, щоб всі можливі пари гравців зустрілися в ній в точності по одному разу.
Спосіб зробити це показаний в таблиці на додатку 4.
