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

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

Раніше ми називали кінцевим реб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).

Якщо S - циклічне ребро, то воно входить в деякий цикл С і тоді на всіх ребрах циклу С можна встановити циклічну орієнтацію; ясно, що з будь-якої вершини G можна перейти до будь-якої іншої, прямуючи вказаним на ребрах напрямом (додаток 13).

Цей процес можна продовжити. Припустимо, що ми вже орієнтували деяку частину H даного графа так, що з будь-якої вершини графа H можна пройти в будь-яку іншу його вершину з дотриманням правил одностороннього руху. Оскільки граф G є зв'язним, то або N збігається з усім графом G, або знайдеться ребро S = (А, В), що "торкається" Н, тобто таке, що воно не належить H, але одна з його вершин, скажемо A, належить Н.

Якщо S - зв'язуюче ребро АВ, то, як ми вже умовилися, воно залишається двостороннім. Тоді для будь-якої вершини X графа H можна знайти орієнтований ланцюг R, що сполучає X з A, а значить (через ребро S), і з B. Назад, від вершини B через ребро S можна перейти до A, а потім - по орієнтованому ланцюгу Z - від А до X (додаток 14).

Приєднуючи S до H, ми отримаємо вже велику частину графа G, що має необхідну властивість.

Якщо ж ребро S = (А, B) є циклічним, воно належить деякому циклу С. Ми встановимо напрям на С від А до B і далі уподовж С до першої вершини D з С, що належить H (додаток 15)

Всі ці ребра ми приєднаємо до H. Нехай X - довільна вершина з Н, а Y - будь-яка вершина із С: можна знайти орієнтований ланцюг Р, що належить Н і що сполучає Х з A, а потім уподовж С пройти до вершини Y з С. Назад від Y можна пройти уздовж С до вершини D, а від неї - належним Н, орієнтованим ланцюгом Z - від D до X. Тому орієнтований граф, отриманий додаванням до Н вказаних ребер циклу С, також задовольняє необхідні умови: те, що від будь-якої з доданих вершин циклу С можна пройти до будь-якої іншої з цих вершин з дотриманням умов, пов'язаних з орієнтацією ребер, очевидно (додаток 15), продовжуючи цей процес, ми в кінці кінців орієнтуємо необхідним чином початковий граф G.

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

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

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

Подивимося на план, складений нами заздалегідь, якщо ми вже обійшли всі вулиці міста, то наше завдання вирішене. B протилежному випадку знайдеться ще не пройдена вулиця (с, d). По припущенню, існує орієнтований ланцюг, сполучаючий а1 з с; ми підемо по ньому, а потім пройдемо вулицю (с, d) (зрозуміло, найзручніше починати з не пройдених раніше вулиць, що виходять з а1) Ясно, що, діючи і далі так само, ми врешті-решт обійдемо всі вулиці міста.

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

Висновок

В моїй роботі описувались важливі методи, які можуть допомогти розв’язати деякі життєві проблеми.

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

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

Список використаної літератури

1. Барболин М.П. Головоломки и графы. Квант, 1975, №2

2. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999

3. Уилсон Р. Введение в теорию графов. М., Мир, 1977

4. Головина Л.И. Графы и их применения. Математика в школе, 1965,№ 3

5. Новиков Ф.А. Дискретная математика, 2001

6. Шедиви Я. Решение логических задач при помощи графов. - Математика в школе, 1967, № 6

7. Головина Л.И. і Яглом И.М., Индукция в геометрии, М., Физматгиз, 2000.

Словник термінів

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

Дерево. Зв'язний граф, що не має циклів.

Многогранник. Тривимірне тіло, межа якого складається з плоских багатокутників.

Нульовий граф. Граф, що складається тільки з ізольованих вершин: граф, що не має ребер.

Ациклічний граф. Орієнтований граф, що не містить ніякого орієнтованого циклу.

Вершина графа. Або кінець якого-небудь ребра графа, або ізольована точка графа.

Гамільтонова лінія. Елементарний цикл, що проходить по всіх вершинах графа.

Грань багатокутного графа G. Частина площини, обмежена яким-небудь мінімальним циклом G або максимальним циклом C1 графа G; у останньому випадку це частина площини, що лежить поза С1; її називають також нескінченною гранню.

Степінь р(А) вершини A. Число ребер, що сходяться у вершині A. Для орієнтованого графа р(А) означає кількість ребер, що виходять, а р*(А) - кількість вхідних ребер у вершину A; в цьому випадку є два степені.

Ребро графа. Крива, що сполучає дві вершини графа і що не містить інших вершин.

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

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

Додекаедр. Многогранник, обмежений 12 п'ятикутними гранями.

Доповнення G графа G. Граф G+ складається зі всіх ребер (і їх кінців), які необхідно додати до G для того, щоб вийшов повний граф.

Ізольована вершина. Вершина, з якої не виходитиме жодного ребра.

Плоский граф. Граф, якого можна накреслити на площині так, щоб його ребра перетиналися тільки в його вершинах.

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

Ікосаедр. Многогранник, обмежений 20 трикутними гранями.

Інцидентність ребра і вершини. Ребро називається інцидентним вершині, якщо вона є одним з його кінців.

Корінь дерева. Будь-яка вершина, яку ми вибираємо за початкову точку дерева.