Розвязування задач за допомогою графів (стр. 2 из 4)

Опишемо простий і цілком загальний метод побудови турнірної таблиці для парної кількості гравців N. Позначимо гравців числами 1, 2,..., N і запишемо ці числа в їх природному порядку в першому рядку квадратної таблиці. B наступному рядку цієї таблиці ми хочемо поставити номери суперників цих гравців в першому турі матчу. Аналогічно в третьому рядку ми випишемо номери суперників тих же гравців 1,2..., N в другому турі і т, д. до тих пір, поки всі гравці не зіграють один з одним. Ясно, що наша таблиця має бути такою, щоб всі можливі пари гравців зустрілися в ній в точності по одному разу.

Спосіб зробити це показаний в таблиці на додатку 4.

Щоб встановити суперника j-го гравця в k-м турі, досить поглянути на перетин j-го стовпця і (k + 1) - го рядка цієї таблиці.

Таблиця влаштована таким чином.

У першому рядку, як вже було сказано, перераховані гравці від 1 до N; ці ж числа ми поставили і в першому стовпці. Тепер на N - 1, що залишилися, місць кожного рядка ми ставимо числа від 2 до N в циклічному порядку по вибуванню. Перші ½N рядків починаються з парних чисел 2,4..., N і виглядають так:

Решта рядків починається з непарних чисел 3,5..., N - 1 і мають вигляд

Відмітимо, що в цій таблиці відсутнє число 1; з іншого боку, оскільки ніхто не грає проти самого себе, те число, що стоїть зверху стовпця, ніколи не повинне в цьому стовпці повторюватися. Ми усунемо обидва недоліки, якщо замінимо всі числа, що стоять на головній діагоналі, одиницями, як показано на додатку 4. Тепер кожен гравець знайде під своїм номером номери гравців, з якими він грає в різних турах. Наприклад, гравець 4 грає з гравцем N - 1 в першому турі, з гравцем 2 в другому турі, з гравцем 1 в третьому турі, з гравцем 6 в четвертому турі і так далі і, нарешті, з гравцем N - 3 в (N - 1) - му турі.

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

Задача про сполучення міст

Я хочу зупинитися на задачі про засоби сполучення, поставивши її спочатку формі питання про проведення доріг. Є декілька міст А, B, С,..., які потрібно з'єднати між собою мережею шосейних або залізних доріг. Для кожної пари міст A, B відома вартість с(А, B) будівництва сполучаючої їх дороги. Завдання полягає в тому, щоб побудувати найдешевшу з можливих мереж доріг. Замість того, щоб говорити про мережу залізниць, можна було б говорити про електричні лінії, або про водопроводи, або про нафтопроводи і тому подібне

B тому окремому випадку, коли є всього три міста A, B, C, досить побудувати одну із ліній АВС, АСВ, ВАС, причому, якщо ВС - найдорожча лінія, то саме її і треба виключити, побудувавши дорогу ВАС.

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

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

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

с(Т) = с(S1) + с(S2) +... + с(Sn-1).

Нам треба довести, що жодне інше дерево В, що сполучає ті ж вершини, не може виявитись дешевше за економічне дерево Т. Нехай В - найдешевше дерево, що сполучає наші вершини, а Т - будь-яке економічне дерево. Припустимо, що ребра S1, S2... економічного дерева Т занумеровані в тому порядку, в якому вони приєднувалися при побудові Т. Якщо найдешевше дерево В не збігається з Т, то Т має щонайменше одне ребро,що не належить В. Нехай S1= (A, В) - перше таке ребро, і нехай Р(А, В) - ланцюг графа В, що сполучає вершини A і B (додаток 5).

Якщо ребро S1 додати до В, то граф В+S1, міститиме цикл С= S1+Р(А, В), а оскільки Т не має циклів, то цикл С повинен містити принаймні одне ребро, що не належить Т. Видаливши це ребро S1 ми отримаємо дерево

В’=В+S1 - S1’

з тією ж кількістю вершин, що і В, причому його вартість дорівнює

C(В’) =c(В) +с(S1) - с(S1’)

Оскільки В має найменшу можливу вартість, то

с(S1) ≥с(S1’)

Але S1; було ланкою найменшої вартості, при додаванні якого до S1, S2..., Sn-1 не виходить циклів.

Оскільки при додаванні ребра S1’ до цих ребер ми теж не отримаємо ніякого циклу, то

с(S1) = с(S1’)

і, отже, В' теж має мінімальну вартість:

c(В) = c(В’).

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

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

Знову спортивні змагання

Розв’язуючи задачу про спортивні змагання, ми об’єднували дві команди, скажімо А і C ребром АС у тому випадку, коли ці команди вже грали один з одним. Проте такий граф не дає відповіді на одне вельми суттєве питання: хто саме виграв гру?

Цей недолік легко може бути усунений. Якщо команда A виграла у C, домовимося ставити на ребрі АС стрілку, направлену від А до C. Припустимо, що нам відомі результати всіх вже зіграних ігор, і додамо до графа відповідні стрілки; хай при цьому вийде граф, зображений на додатку 6.

На цьому графові показано, що команда А виграла у C, команда F програла D, а В виграла всі ігри - з C, E, F і так далі

Граф G, на якому вказаний напрям кожного його ребра, називається орієнтованим графом. Такий граф, як ми бачили, може містити інформацію про результати змагання між командами або окремими гравцями. Навпаки, кожен орієнтований граф можна розглядати як геометричне представлення результатів деякого змагання. Додаток 7

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

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

B якості прикладу змішаного графа розглянемо граф, зображений на додатку 7; на цьому графові вказані результати ігор чотирьох команд A, B, С і D; команда А виграла у В і С і зіграла внічию з D; В програла A, зіграла внічию із С і виграла у D; С програла A, виграла у D і зіграла внічию з B; D зіграла внічию з А і програла В і C.

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

Односторонній рух

Карта будь-якої мережі доріг або вулиць дає нам дещо спеціальний, але наочний приклад графа. На сучасному плані міста мають бути показані не тільки відносне розташування вулиць і їх перетину, але також і те, на яких вулицях є двосторонній потік транспорту, а на яких односторонній рух, причому в останньому випадку: повинно бути вказано і напрям руху. При цьому знову виходить орієнтований або, частіше, змішаний граф, якщо односторонній рух встановлений не на всіх вулицях міста (додаток 8).

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

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

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

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

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

Ясно, що такий граф має бути зв'язним. Проте цього недостатньо.

Ребро S=(A, В) графа ми називатимемо зв'язуючим ребром, або перешийком, якщо воно є єдиним шляхом від A до B або назад.

Зв'язуюче ребро ділить всі вершини графа на дві множини: ті, в які можна прийти з A, не проходячи по ребру S, і ті, в які можна прийти з B, не проходячи по S. Граф в цьому випадку складається з двох частин G1 і G2i сполучених тільки ребром S (додаток 9).