Що таке метод графів?
Слово «граф» в математиці означає картинку, де намальовано кілька точок, деякі з яких з'єднані лініями. Перш за все, варто сказати про те, що графи, про які піде мова, до аристократів минулих часів ніякого відношення не мають. Наші «графи» мають коренем грецьке слово «графо», що означає «пишу». Той же корінь в словах «графік», «біографія».
В математиці визначення графа дається так: графом називається кінцеве безліч точок, деякі з яких з'єднані лініями. Точки називаються вершинами графа, а що з'єднують лінії - ребрами.
Схема графа, що складається з «ізольованих» вершин, називається нульовим графом. (Рис.2)
Графи, в яких не побудовані всі можливі ребра, називаються неповними графами. (Рис.3)
Графи, в яких побудовані всі можливі ребра, називаються повними графами. (Рис.4)
Граф, кожна вершина якого з'єднана з ребром будь-який інший вершини, називається повним.
Зауважимо, що якщо повний граф має n вершин, то кількість ребер дорівнюватиме
Дійсно, кількість ребер в повному графі з n вершинами визначається як число невпорядкованих пар, складених з усіх n точок-ребер графа, т. Е. Як число поєднань з n елементів по 2:
Граф, який не є повним, можна доповнити до повного з тими ж вершинами, додавши відсутні ребра. Так, наприклад, на малюнку 3 зображено неповний граф з п'ятьма вершинами. На малюнку 4 ребра перетворюють граф в повний граф зображені іншим кольором, сукупність вершин графа з цими ребрами називається доповненням графа.
Ступені вершин і підрахунок числа ребер.
Кількість ребер, що виходять з вершини графа, називається ступенем вершини. Вершина графа, що має непарну ступінь, називається непарною. а парну ступінь - парної.
Якщо ступеня всіх вершин графа рівні, то граф називається однорідним. Таким чином, будь-який повний граф - однорідний.
На малюнку 5 зображено граф з п'ятьма вершинами. Ступінь вершини А позначимо Ст.А.
На малюнку. Ст.А = 1, ст.б = 2, ст.в = 3, Ст.Г = 2, Ст.Д = 0.
Сформулюємо деякі закономірності, притаманні певним графам.
Ступені вершин повного графа однакові, і кожна з них на 1 менше числа вершин цього графа.
Ця закономірність очевидна вже після розгляду повного графа. Кожна вершина з'єднана ребром з кожною вершиною, крім самої себе, т. Е. З кожної вершини графа, що має n вершин, виходить n-1 ребро, що й треба було довести.
Сума ступенів вершин графа число парне, рівне подвоєному числу ребер графа.
Ця закономірність справедлива не тільки для повного, але і для будь-якого графа. Доведення:
Дійсно, кожне ребро графа пов'язує дві вершини. Значить, якщо будемо складати число ступенів усіх вершин графа, то отримаємо подвоєне число ребер 2R (R - число ребер графа), т. К. Кожне ребро було підраховано двічі, що й треба було довести
Число непарних вершин будь-якого графа парне. Доведення:
Розглянемо довільний граф Г. Нехай в цьому графі число вершин, ступінь яких 1, дорівнює К1; число вершин, ступінь яких 2, так само K2 ;. ; число вершин, ступінь яких n, так само Кn. Тоді суму ступенів вершин цього графа можна записати як
K1 + 2К2 + ЗК3 +. + NКn.
З іншого боку: якщо число ребер графа R, то з закономірності 2 відомо, що сума ступенів усіх вершин графа дорівнює 2R. Тоді можна записати рівність
K1 + 2К2 + ЗК3 +. + NКn = 2R. (1)
Виділимо в лівій частині рівності суму, рівну числу непарних вершин графа (К1 + К3 +.):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 +. + Nк = 2R,
(К1 + К3 + К5 +.) + (2K2 + 2Х3 + 4K4 + 4К5 +.) = 2R
Друга скобка- парне число як сума парних чисел. Отримана сума (2R) парне число. Звідси (К1 + К3 + К5 +.) -четное число.
Розглянемо тепер завдання, які вирішуються за допомогою графів:
Задача.Первенство класу. У першості класу з настільного тенісу 6 учасників: Андрій, Борис, Віктор, Галина, Дмитро та Олена. Першість проводиться за коловою системою - кожен з учасників грає з кожним з інших один раз. До теперішнього моменту деякі ігри вже проведені: Андрій зіграв з Борисом, Галиною та Оленою; Борис, як уже говорилося, з Андрієм і ще з Галиною; Віктор - з Галиною, Дмитром та Оленою; Галина з Андрієм і Борисом; Дмитро - з Віктором і Олена - з Андрієм і Віктором. Скільки ігор проведено на цей момент і скільки ще залишилося?
Обговорення. Зобразимо дані завдання у вигляді схеми. Учасників будемо зображати точками: Андрія - точкою А, Бориса - точкою Б і т.д. Якщо двоє учасників вже зіграли між собою, то будемо з'єднувати зображують їх точки відрізками. Виходить схема, показана на малюнку 1.
Точки А, Б, В, Г, Д, Е - вершини графа, що з'єднують їх відрізки - ребра графа.
Зауважимо, що точки перетинання ребер графа не є його вершинами.
Число ігор, проведених на цей момент, дорівнює числу ребер, тобто 7.
Щоб уникнути плутанини вершини графа часто зображують не точками, а маленькими кружечками.
Щоб знайти число ігор, які треба провести, побудуємо ще один граф з тими ж вершинами, але ребрами будемо з'єднувати тих учасників, які ще не грали один з одним (рис.2) Ребер у цього графа виявилося 8, значить, залишилося провести 8 ігор : Андрій - з Віктором і Дмитром; Борис - З Віктором, Дмитром та Оленою і т.д.
Спробуємо побудувати граф для ситуації, описаної в наступної задачі:
Задача.Кто грає Ляпкина - Тяпкіна? У шкільному драмгуртку вирішили ставити гоголівського «Ревізора». І тут розгорівся запеклу суперечку. Все почалося з Ляпкина - Тяпкіна.
- Ляпкина - Тяпкіним буду я! - рішуче заявив Гена.
- Ні, я буду Ляпкина - Тяпкіним, заперечив Діма.- З раннього дитинства мріяв втілити цей образ на сцені.
- Ну, добре, поступитися цією роллю, якщо мені дадуть зіграти Хлестакова, - проявив великодушність Гена.
- ... А мені - Осипа, - не дав йому в довготерпінню Діма.
- Хочу бути суниці або Городничим, - сказав Вова.
- Ні, Городничим буду я, - хором закричали Алік і Боря. - Або Хлестакова, -
додали вони одночасно.
Чи вдасться розподілити ролі так, щоб виконавці були задоволені?
Обговорення. Зобразимо юних акторів кружками верхнього ряду: А - Алік, Б - Борис, В - Вова, Г - Гена, Д - Діма, а ролі, які вони збираються грати, - кружками другого ряду (1 - Ляпкин - Тяпкин, 2 - Хлестаков, 3 - Осип, 4 - Суниця, 5 - Городничий). Від кожного учасника проведемо відрізки, тобто ребра, до ролей, які він хотів би зіграти. У нас вийти граф з десятьма вершинами і десятьма ребрами (рис.3)
Щоб вирішити задачу, потрібно з десяти вибрати п'ять ребер, які не мають спільних вершин. Зробити це легко. Досить зауважити, що в вершини 3 і 4 ведуть по одному ребру, з вершин Д і В відповідно. Це означає, що Осипа (вершина 3) повинен грати Діма (хто ж ще?), А Суничку - Вова. Вершіна1 - Ляпкин - Тяпкин - з'єднана ребрами з Г і Д. Ребро 1 - Д віддає, так як Діма вже зайнятий, залишається 1 - Г, Ляпкина - Тяпкіна повинен грати Гена. Залишається з'єднати вершини А і Б з вершинами 2 і 5, відповідними ролями Хлестакова і Городничого. Це можна зробити двома способами: або вибрати ребро А -5 і Б - 2, або ребро А -2 і Б -5. У першому випадку Алік гратиме Городничого, а Боря - Хлестакова, у другому випадку навпаки. Як показує граф, інших рішень завдання не має.
Той же граф вийде при вирішенні наступного завдання:
Завдання. Сварливі сусіди. Жителі п'яти будинків посварилися один з одним і, щоб не зустрічатися у колодязів, вирішили поділити їх (колодязі) так, щоб господар кожного дому ходив до «свого» криниці по «своїй» стежкою. Чи вдасться їм це зробити?
Виникає питання: так чи потрібні були графи в розібраних задачах? Хіба не можна прийти до вирішення чисто логічним шляхом? Так можна. Але графи надали умов наочність, спростили рішення і виявили схожість завдань, перетворивши два завдання в одну, а це вже не так уже й мало. А тепер уявіть собі завдання, графи яких мають 100 або більше вершин. А адже саме такі завдання доводиться вирішувати сучасним інженерам і економістам. Тут без графів не обійтися.
III. Графи Ейлера.
Теорія графів - наука порівняно молода: за часів Ньютона такий науки ще не існувало, хоча і були в ходу «генеалогічні дерева», представ-ляющие собою різновиди графів. Перша робота з теорії графів належить Леонарду Ейлера, і з'явилася вона в 1736 році в публікаціях петербурзької Академії наук. Починалася ця робота з розгляду наступного завдання:
а) Завдання про кенігсберзькими мостах. Місто Кенігсберг (нині Калінінград) розташований на берегах і двох островах річки Прегель (Преголи) .Разлічние частини міста були з'єднані сім'ю мостами, як показано на малюнку. У недільні дні городяни здійснюють прогулянки по місту. Чи можна вибрати такий маршрут, щоб пройти один і тільки один раз по кожному мосту і потім повернутися в початкову точку шляху?
Перш ніж розглянути рішення даного завдання, ми введемо поняття «Ейлерови графи.
Спробуємо граф, зображену на рис.4, обвести одним розчерком. тобто, не відриваючи олівця від аркуша паперу і не проходячи по одній і тій же частині лінії більш ніж один раз.
Фігура ця, така проста на вигляд, виявляється, має цікаву особливість. Якщо ми почнемо рух з вершини В, то у нас це обов'язково вийде. А що буде, якщо ми почнемо рух з вершини А? Легко переконатися, що обвести лінію в цьому випадку нам не вдається: у нас завжди буде залишатися не пройдені ребра, дістатися до яких вже неможливо.
На рис. 5 зображено граф, який ви, напевно, вмієте малювати одним розчерком. Це зірка. Виявляється, хоча вона і виглядає значно складнішою, ніж попередній граф, обвести її можна, почавши з будь-якої вершини.
Графи, накреслені на рис.6 також можна накреслити одним розчерком пера.
Тепер спробуйте викреслити одним розчерком граф, зображений на рис.7
Вам це зробити не вдалося! Чому? Ви не можете знайти потрібну вершину? Ні! Справа не в цьому. Цей граф взагалі не можна викреслити одним розчерком пера.
Проведемо міркування, які переконають нас у цьому. Розглянемо вузол А. З нього виходять три вершини. Почнемо викреслювати граф з цієї вершини. Щоб пройти по кожному з цих ребер, ми повинні вийти з вершини А по одному з них, в якій - то момент обов'язково повернутися в нього по другому і вийти по третьому. А ось знову увійти вже не зможемо! Значить, якщо ми почнемо креслення з вершини А, то закінчити в ньому не зможемо.
Припустимо тепер, що вершина А не є початком. Тоді в процесі креслення ми повинні увійти в нього по одному з ребер, вийти за іншим і знову повернутися по третьому. А так як вийти з нього ми не зможемо, то вершина А в цьому випадку повинен бути кінцем.
Отже, вершина А повинен бути або початком, або кінцевим вузлом креслення.
Але про три інші вершини нашого графа можна сказати те ж саме. Але ж і початковою вершиною креслення може бути тільки одна вершина, і кінцевою вершиною також може бути тільки одна вершина! А значить, викреслювати цей граф одним розчерком неможливо.
Граф, який можна намалювати, не відриваючи олівця від паперу, називається ейлеровим (рис.6).
Такими графи названі в честь вченого Леонарда Ейлера.
Закономерность1. (Випливає з розглянутої нами теореми).
Неможливо накреслити граф з непарним числом непарних вершин.
Закономірність 2.
Якщо все вершини графа парні, то можна не відриваючи олівець від паперу ( «одним розчерком»), проводячи по кожному ребру тільки один раз, накреслити цей граф. Рух можна почати з будь-якої вершини і закінчити його в тій же вершині.
Закономірність 3.
Граф, який має всього дві непарні вершини, можна накреслити, не відриваючи олівець від паперу, при цьому рух потрібно почати з одного з цих непарних вершин і закінчити у другій з них.
Закономірність 4.
Граф, що має більше двох непарних вершин, неможливо накреслити «одним розчерком».
Фігура (граф), яку можна накреслити, не відриваючи олівець від паперу, називається унікурсальной.
Граф називається зв'язковим, якщо будь-які дві його вершини можуть бути з'єднані шляхом, т. Е. Послідовністю ребер, кожне наступне з яких починається в кінці попереднього.
Граф називається незв'язних, якщо ця умова не виконується.
На малюнку 7, очевидно, зображений незв'язних граф. Якщо, наприклад, на малюнку між вершинами Д і Е провести ребро, то граф стане зв'язковим. (Рис.8)
Таке ребро в теорії графів (після видалення якого граф з зв'язкового перетворюється в незв'язних) називається мостом.
Прикладами мостів на малюнку 7 могли б служити ребра ДЕ, A3, ВЖ і ін. Кожне з яких єднало б вершини «ізольованих» частин графа. (Рис.8)
Незв'язний граф складається з декількох «шматків». Ці «шматки» називаються компонентами зв'язності графа. Кожна компонента зв'язності є, звичайно, зв'язковим графом. Відзначимо, що зв'язний граф має одну компоненту зв'язності.
ТЕОРЕМА.
Граф є ейлеровим тоді і тільки тоді, коли він пов'язаний і має не більше двох непарних вершин.
Малюючи граф кожну вершину, за винятком початкової і кінцевої, ми увійдемо стільки ж раз, скільки вийдемо з неї. Тому ступеня всіх вершин повинні бути парними, крім двох, а значить, Ейлером граф має не більше двох непарних вершин.
Повернемося тепер до задачі про кенігсберзькими мостах.
Обговорення завдання. Позначимо різні частини міста буквами А, В, С, Д, а мости - буквами а, b, c, d, e, f, g - мости, що з'єднують відповідні частини міста. У цьому завданні існують лише переходи через мости: переходячи через будь-який міст, ми завжди з однієї частини міста потрапляємо в іншу, І, навпаки, переходячи з однієї частини міста в іншу, ми неодмінно пройдемо по мосту. Тому, зобразимо план міста у вигляді графа, вершини якого А, В, С, Д (рис.8) зображують окремі частини міста, а ребра a, b, c, d, e, f, g - мости, що з'єднують відповідні частини міста . Ребра часто виявляються зручніше зображати зручніше не прямолінійними відрізками, а криволінійними - «дугами».
Якби існував маршрут, що задовольняє умові завдання, то існував би замкнутий безперервний обхід цього графа, що проходить один раз по кожному ребру. Іншими словами цей граф повинен викреслюватися одним розчерком. Але це неможливо - яку б вершину ми не вибрали за вихідну, нам доведеться проходити через інші вершини, і при цьому кожному «входить» ребру (мосту, по якому ми увійшли в цю частину міста) буде відповідати «виходить» ребро міст, яким ми і скористаємося потім, щоб покинути цю частину міста): число ребер, що входять в кожну вершину, буде дорівнює числу ребер, що виходять з неї, т. е. загальне число ребер, що сходяться в кожній вершині, повинен бути парним. Наш граф цій умові не задовольняє, і тому необхідного маршруту не існує.
Для тих, хто вивчає англійську