Научная работа: Розвязування задач за допомогою графів

На цьому графові показано, що команда А виграла у 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).

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

Раніше ми називали кінцевим ребpом таке ребро S - (А, В), один з кінців якого, наприклад A, не належить ніякому іншому ребру графа (додаток 10).

Таке ребро теж повинне розглядатися як зв'язуюче, оскільки, окрім S, немає шляху, який сполучає A з B.

Можна вважати, що граф G1 (додаток 9) наче "стягнутий" в одну вершину A. На плані міста кінцеве ребро відповідає глухому куту; на якому теж не можна встановити односторонній рух, не блокуючи цим в'їзд в A або виїзді з A.

Якщо ребро S1= (А1, В1) Не є таким, що зв'язує, то знайдеться і інший шлях, що сполучає, А1 і В1 і що не проходить по S1 (додаток 11).

Тому таке ребро S1, називається циклічним ребром. Отже, на графі є ребра двох типів - циклічні і зв'язуючі.

Тепер ми можемо довести наступну теорему.

ТЕОРЕМА. ЯКЩО G - неорієнтований зв'язний граф, то завжди можна так орієнтувати циклічні ребра з G, залишивши зв'язуючі ребра неорієнтованими, щоб будь-яку пару вершин цього графа можна було з'єднати орієнтованим ланцюгом.

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

Ми можемо довести цю теорему; вказавши спосіб відповідного орієнтування графа. Почнемо з того, що виберемо в G довільне ребро S= (А,B). Якщо S - зв'язуюче ребро, воно залишиться двостороннім, і тоді можна буде перейти від В до А і назад уподовж S (додаток 12).