Теорія графів. Застосування графів у різних сферах життя людей

Тема графів – це цікава, корисна та лякаюча тема. Теорія графів - "Жах студента". Алгоритми на графах - приголомшливий розум людей, які їх відкрили.

Що таке граф? Щоб відповісти на це запитання своїм читачам, я описуватиму тему трохи по-своєму.
Граф – це безліч об'єктів.
Здебільшого це однотипні об'єкти. (Багато міст або безліч будинків, або безліч людей, або безліч чогось ще однотипного)

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

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

Як я й писав раніше — граф це якась безліч об'єктів. Ці об'єкти зазвичай однотипні. Найпростіше наводити приклад на містах. Кожен із нас знає, що таке місто та що таке дорога. Кожен із нас знає, що до міста можуть бути дорогі, а можуть і не бути. Загалом, будь-яку кількість об'єктів можна охарактеризувати як граф.

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

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

У літературі, в інтернеті і взагалі скрізь, де щось написано про графи, ви зустрічатимете такі поняття, як дуги та ребра. На цьому малюнку зображено ребра графа. Тобто. це три ребра Е1, Е2 та Е3.

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

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

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

Багато чого не описано, але ця частина інформації може бути комусь допоможе.

Теорія графів – це розділ дискретної математики, вивчає об'єкти, які у вигляді окремих елементів (вершин) і зв'язків з-поміж них (дуг, ребер).

Теорія графів бере початок з розв'язання задачі про кенігсберзькі мости в 1736 знаменитим математиком Леонардом Ейлером(1707-1783: народився у Швейцарії, жив та працював у Росії).

Завдання про кенігсберзькі мости.

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

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

Послідовність вершин (можливо з повторенням), якими проходить шуканий маршрут, як і сам маршрут, називаєтьсяЕйлеровим циклом .

Завдання про три будинки та три колодязі.

Є три будинки та три колодязі, якимось чином розташовані на площині. Провести від кожного будинку до кожної криниці стежку так, щоб стежки не перетиналися. Це завдання було вирішено (показано, що рішення не існує) Куратовським (1896 – 1979) у 1930 році.

Завдання про чотири фарби. Розбиття площини на області, що не перетинаються, називається карткою. Області картки називаються сусідніми, якщо вони мають спільний кордон. Завдання полягає у розмальовуванні карти таким чином, щоб жодні дві сусідні області не були зафарбовані одним кольором. З кінця ХІХ століття відома гіпотеза, що цього досить чотирьох фарб. Гіпотезу не доведено досі.

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

Перевірити «вручну» отримане рішення неможливо – обсяг перебору виходить за межі людських можливостей. Багато математиків порушують питання: чи можна вважати такий «програмний доказ» дійсним доказом? Адже у програмі можуть бути помилки.

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

Визначення 7.1. Графом G= G(V, E) називається сукупність двох кінцевих множин: V – званого безліччю вершинта множини E пар елементів з V, тобто. EIV'V, званого безліччю реберякщо пари невпорядковані, або безліччю дугякщо пари впорядковані.

У першому випадку граф G(V, E) називається неорієнтованим, у другому - орієнтованим.

ПРИКЛАД. Граф з безліччю вершин V = (а, b, с) і безліччю ребер Е = ((а, b), (b, с))

ПРИКЛАД. Граф, у якого V = (a, b, c, d, e) та Е = ((а, b), (а, е), (b, е), (b, d), (b, с) , (С, d)),

Якщо e=(v 1 ,v 2), еÎЕ, то кажуть, що ребро е з'єднуєвершини v 1 та v 2 .

Дві вершини v 1 ,v 2 називаються суміжними, якщо існує ребро, що з'єднує їх. У цій ситуації кожна з вершин називається інцидентної відповідному ребру .

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

Число вершин графа Gпозначимо v, а число ребер - e:

.

Геометричне представлення графів таке:

1) вершина графа – точка у просторі (на площині);

2) ребро неорієнтованого графа – відрізок;

3) дуга орієнтованого графа – спрямований відрізок.

Визначення 7.2.Якщо ребері e=(v 1 ,v 2) має місце v 1 =v 2 , то ребро е називається петлею. Якщо у графі допускається наявність петель, він називається графом із петлями або псевдографом .

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

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

Визначення 7.3.Граф G (V , E ) називається підграфом (або частиною ) графа G(V,E), якщо V V, E E. Якщо V = V, то G називається остовним підграфом G.

приклад 7 . 1 . Дано неорієнтований граф.

Визначення 7.4.Граф називається повним , якщо будь-які дві його вершини з'єднані рубом. Повний граф з nвершинами позначається через K n .

Графи К 2 , К 3, До 4 і К 5 .

Визначення 7.5.Граф G=G(V, E) називається дводольним , якщо Vможна уявити як об'єднання непересічних множин, скажімо V=AB, так що кожне ребро має вигляд ( v i , v j), де v i Aі v j B.

Кожне ребро пов'язує вершину з А з вершиною В, але ніякі дві вершини А або дві вершини В не є пов'язаними.

Дводольний граф називається повним дводольним графом K m , n, якщо Aмістить mвершин, Bмістить nвершин і для кожного v i A, v j Bмаємо ( v i , v j)E.

Таким чином, для кожного v i A, і v j Bє їхнє ребро.

K 12 K 23 K 22 K 33

приклад 7 . 2 . Побудувати повний дводольний граф K 2,4 та повний граф K 4 .

Граф одиничногоn-мірного кубаУ n .

Вершини графа – n-мірні двійкові набори. Ребра з'єднують вершини, що відрізняються однією координатою.

Приклад:

Серед жителів Кенігсберга була поширена така практична головоломка: чи можна пройти всіма мостами через річку Преголя, не проходячи ні по одному з них двічі? В 1736 видатний математик Леонард Ейлер зацікавився завданням і в листі другові навів суворий доказ того, що зробити це неможливо. У тому року він довів чудову формулу, яка пов'язує число вершин, граней і ребер багатогранника в тривимірному просторі. Формула таємниче вірна і для графів, які називаються "планарними". Ці два результати заклали основу теорії графів і непогано ілюструють напрямок її розвитку до цього дня.

Про курс

Цей курс є введенням у сучасну теорію графів. Граф як математичний об'єкт виявляється корисним у багатьох теоретичних та практичних завданнях. Справа, мабуть, у тому, що складність його структури добре відповідає можливостям нашого мозку: це структура наочна і зрозуміло влаштована, але, з іншого боку, досить багата, щоб уловлювати багато нетривіальних явищ. Якщо говорити про програми, то, звичайно, відразу ж на думку спадають великі мережі: Інтернет, карта доріг, покриття мобільного зв'язку тощо. В основах пошукових машин, таких як Yandex та Google, лежать алгоритми на графах. Крім computer science, графи активно використовують у біоінформатиці, хімії, соціології. У нашому курсі ми, звичайно ж, обговоримо класичні завдання, але й поговоримо про нещодавніші результати та тенденції, наприклад, про екстремальну теорію графів.

Формат

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

Інформаційні ресурси

1. В. А. Ємелічев, О. І. Мельников, В. І. Сарванов, Р. І. Тишкевич. Лекції з теорії графів. М.: Книжковий дім "Ліброком", 2009.
2. А. А. Зиков. Теорія кінцевих графів. Новосибірськ: Наука, 1969.
3. М. “Свамі, К.” Тхуласіраман. Графи, мережі та алгоритми. М.: Світ, 1984.
4. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009
5. B. Bollobás. Modern Graph Theory. Springer, 1998.
6. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008

Вимоги

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

Програма курсу

1. Поняття графа та види графів.
2. Різні застосування графів: від мостів Кенігсбергів до Інтернету.
3. Зв'язність графа, підграфи та ступінь вершини.
4. Еквівалентні визначення дерев.
5. Планарність та критерій Куратовського
6. Формула Ейлер.
7. Хроматична кількість планарного графа.
8. Перелік дерев: код Прюфера та формула Келі.
9. Формула числа уніциклічних графів.
10. Ейлерові цикли та критерій ейлеровості.
11. Гамільтонові цикли. Критерій Дірака та критерій Хватала.
12. Паросопоєднання. Теорема Холла та Кеніга.
13. Екстремальна теорія графів. Теорема Турану.
14. Аналог теореми Турану для графів на площині.
15. Теорія Рамсея. Знайомства серед шістьох людей.
16. Визначення числа Рамсея.
17. Нижня та верхня оцінки чисел Рамсея.

Результати навчання

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

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

Що таке граф

Часто для опису будови систем використовують графічні схеми. Елементи в них зображують кружками, крапками, квадратами тощо, а зв'язки між елементами – лініями чи стрілками. У цьому ні те, як зображуються елементи, ні довжина чи форма ліній не важливі - має значення лише, які з'єднані. Отже, граф - це пара виду (A, M), де A - кінцева множина вершин, а M - множина ребер - ліній, що зв'язують деякі вершини.

Основні поняття теорії графів

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

У неорієнтованого графа (див. малюнок нижче) ребра зображуються лініями без орієнтації. Відповідно пара вершин, яку пов'язує ребро, є невпорядкованою. Обидві вершини є кінці ребра.

Якщо вершини a і b - кінці ребра (або початок і кінець дуги) графа, то кажуть, що вершини a і b інцидентні цьому ребру (дузі), також ребро (дуга) інцидентно вершинам a і b. Якщо вершини a і b - кінці ребра, всі вони (a і b) називаються суміжними.

Найчастіше розглядають графи, ребра яких мають один тип – є орієнтованими чи ні.

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

Теорія графів також використовує поняття «петля» - ребро, що виходить і заходить в ту саму вершину. Граф, у якому є петлі, називається псевдографом.

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

Кожна вершина орграфа характеризується:

• Напівступенем результату. Це кількість дуг, що виходять із неї.
• Напівступенем заходу. Це кількість дуг, які входять у цю вершину.

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

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

Вершина зі ступенем 0 називається ізольованою.

Висячою вершиною є вершина зі ступенем 1.

Теорія графів називає порожнім графом такий, у якому немає жодного ребра. Повний граф - це звичайний граф, у якому суміжні будь-які 2 вершини.

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

Графи: ізоморфізм

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

Шляхи та цикли

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

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

Теорія графів- один із найширших розділів дискретної математики, широко застосовується у вирішенні економічних та управлінських завдань, у програмуванні, хімії, конструюванні та вивченні електричних ланцюгів, комунікації, психології, психології, соціології, лінгвістиці, інших галузях знань. Теорія графівсистематично і послідовно вивчає властивості графів, про які можна сказати, що вони складаються з множини точок і множини ліній, що відображають зв'язки між цими точками. Засновником теорії графів вважається Леонард Ейлер (1707-1882), який вирішив у 1736 році відому на той час завдання про кенігсберзькі мости.

Графи будуютьдля того, щоб відобразити відносини на множинах . Нехай, наприклад, безліч A = {a1 , a 2 , ... a n)- безліч людей, а кожен елемент буде відображено у вигляді точки. Безліч B = {b1 , b 2 , ... b m)- безліч зв'язок (прямих, дуг, відрізків - поки що не важливо). На безлічі Aзадано ставлення знайомства між людьми з цієї множини. Будуємо графз точок та зв'язок. Зв'язки пов'язуватимуть пари людей, знайомих між собою. Природно, кількість знайомих в одних людей може відрізнятися від числа знайомих в інших людей, а деякі можуть і не бути ні з ким знайомі (такі елементи будуть точками, не з'єднаними з жодною іншою). Ось і вийшов граф!

Те, що ми спочатку назвали "точками", слід називати вершинами графа, а те, що називали "зв'язками" - ребрами графа.

Теорія графів не враховує конкретну природу множин Aі B. Існує велика кількість різних конкретних завдань, при вирішенні яких можна тимчасово забути про специфічний зміст множин і їх елементів. Ця специфіка ніяк не позначається під час вирішення завдання, незалежно від її проблеми! Наприклад, при вирішенні питання про те, чи можна з точки aдістатися до точки e, рухаючись тільки лініями, що з'єднують точки, неважливо, чи маємо ми справу з людьми, містами, числами і т.д. Але, коли завдання вирішене, ми отримуємо рішення, правильне для будь-якого змісту, що було змодельовано у вигляді графа. Не дивно тому, що теорія графів - один із найбільш затребуваних інструментів при створенні штучного інтелекту: адже штучний інтелект може обговорити із співрозмовником і питання кохання, і питання музики чи спорту, і питання розв'язання різних завдань, причому робить це без будь-якого переходу (перемикання) , без якого у подібних випадках не обійтися людині.

Нині ж суворі математичні визначення графа.

Визначення 1.Графом називаєтьсясистема об'єктів довільної природи (вершин) та зв'язок (ребер), що з'єднують деякі пари цих об'єктів.

Визначення 2.Нехай V- (Непорожня) безліч вершин, елементи v∈V- Вершини. Граф G = G(V) з безліччю вершин Vє деяке сімейство пар виду: e = (a, b) , де a,b∈V , що вказують, які вершини залишаються з'єднаними. Кожна пара e = (a, b) - Ребро графа. Безліч U- безліч ребер eграфа. Вершини aі b- Кінцеві точки ребра e .

Графи як структура даних.Широким застосуванням теорії графів у комп'ютерних науках та інформаційних технологіях обумовлено додаванням до вищевикладених визначень поняття графа як структури даних. У комп'ютерних науках та інформаційних технологіях граф визначається як нелінійна структура даних. Що ж тоді – лінійна структура даних і чим від них відрізняються графи? Лінійні структури даних характеризуються тим, що елементи зв'язують відносинами типу "простого сусідства". Лінійними структурами даних є, наприклад, масиви, таблиці, списки, черги, стеки, рядки. На противагу їм нелінійні структури даних - такі, у яких елементи розташовуються різних рівнях ієрархії і поділяються на три виду: вихідні, породжені і подібні. Отже, граф – нелінійна структура даних.

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

Основні поняття теорії графів

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

Класичні завдання теорії графів та їх вирішення

Один із перших опублікованих прикладів робіт з теорії графів та застосування графів - робота про "завдання з Кенігсберзькими мостами" (1736), автором якої є видатний математик 18-го століття Леонард Ейлер. У задачі дано річку, острови, які омиваються цією річкою, та кілька мостів. Питання задачі: чи можливо, вийшовши з певного пункту, пройти кожен міст лише по одному разу і повернутися до початкового пункту? (Рисунок нижче)

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

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

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

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

Келі у 1858 р., займаючись суто практичними завданнями органічної хімії, відкрив важливий клас графів, які називають деревами. Він прагнув перерахувати ізомери насичених вуглеводнів, з цим числом атомів вуглецю. Келі перш за все сформулював завдання абстрактно: знайти число всіх дерев з pвершинами, кожне з яких має вершини зі ступенями 1 і 4. Йому не вдалося відразу вирішити це завдання, і він став змінювати її формулювання таким чином, щоб можна було вирішити нове завдання про перерахування:

• кореневих дерев (у яких виділено одну з вершин);
• всіх дерев;
• дерев, у яких ступеня вершин не перевищують 4;
• дерев, у яких ступеня вершин дорівнюють 1 і 4 (постановка задачі з хімії).

Завдання із графами для закріплення основних понять

приклад 1.Нехай A- безліч чисел 1, 2, 3: A= (1, 2, 3). Побудувати граф для відображення відносини

Рішення. Очевидно, що числа 1, 2, 3 слід подати у вигляді вершин графа. Тоді кожну пару вершин має з'єднувати одне ребро. Вирішуючи це завдання, ми дійшли таких основних понять теорії графів, як орієнтовані та неорієнтовані графи. Неорієнтовані графи - такі, ребра яких мали напрями. Або, як кажуть ще частіше, порядок двох кінців ребра не суттєвий. Справді, граф, побудований на самому початку цього уроку і відображав ставлення знайомства між людьми, не потребує напрямів ребер, оскільки можна стверджувати, що "людина номер 1" знайома з "людинам номер 2" так само, як і "людина номер 2" з "чоловіком номер 1". У нашому ж нинішньому прикладі одне число менше за інше, але не навпаки. Тому відповідне ребро графа повинно мати напрямок, що показує, яке все ж таки число менше іншого. Тобто порядок кінців ребра суттєвий. Такий граф (з ребрами, що мають напрямок) називається орієнтованим графом або орграфом.

Отже, у нашій множині Aчисло 1 менше від числа 2 і числа 3, а число 2 менше від числа 3. Цей факт відображаємо ребрами, що мають напрямок, що показується стрілками. Отримуємо наступний граф:

приклад 2.Нехай A- безліч чисел 2, 4, 6, 14: A= (2, 4, 6, 14). Постоїть граф для відображення відносини "ділиться націло на" на цій множині.

Рішення. У цьому прикладі частина ребер матимуть напрямок, а деякі не будуть, тобто будуємо змішаний граф. Перелічимо відносини на безлічі: 4 ділиться націло на 2, 6 ділиться націло на 2, 14 ділиться націло на 2, і ще кожне число з цієї множини ділиться націло на себе. Це відношення, тобто коли число ділиться націло на себе, будемо відображати у вигляді ребер, які з'єднують вершину саму з собою. Такі ребра називаються петлями. У разі немає необхідності давати напрямок петлі. Таким чином, у нашому прикладі три звичайних спрямованих ребра та чотири петлі. Отримуємо наступний граф:

приклад 3.Нехай дані безлічі A= (α, β, γ) та B= (a, b, c). Побудувати граф для відображення відносини "декартове твір множин".

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

приклад 4.В агентстві з нерухомості працюють менеджери Ігор, Сергій та Петро. Обслуговуються об'єкти О1, О2, О3, О4, О5, О6, О7, О8. Побудувати граф для відображення відносин "Ігор працює з об'єктами О4, О7", "Сергій працює з об'єктами О1, О2, О3, О5, О6", "Петр працює з об'єктом О8".

Рішення. Граф, який відображатиме дані відносини, буде так само дводольним, оскільки менеджер не працює з менеджером і об'єкт не працює з об'єктом. Проте, на відміну попереднього прикладу, граф буде орієнтованим. Справді, наприклад, Ігор працює з об'єктом О4, але з об'єкт О4 працює з Ігорем. Часто, коли така властивість відносин очевидна, необхідність давати ребрам напряму може здатися "математичною тупістю". Але все ж таки, і це випливає із суворого характеру математики, якщо відношення носить односторонній характер, то давати напрями ребрам потрібно. У додатках відносин ця строгість окупається, наприклад, у програмах, призначених для планування, де також застосовуються графи і маршрут по вершинах і ребрам повинен проходити строго в заданому напрямку. Отже, отримуємо наступний орієнтований дводольний граф:

І знову до прикладів із числами.

Приклад 5.Нехай задано безліч C = {2, 3, 5, 6, 15, 18} . Побудувати граф, що реалізує ставлення, що визначає всі пари чисел aі bз множини C, У яких при розподілі другого елемента на перший отримуємо приватне, яке є цілим числом більше 1.

Рішення. Граф, що відображає дані відносини, буде орієнтованим, оскільки в умові є згадка про другий і перший елемент, тобто ребро буде направлено від першого елемента до другого. З цього однозначно зрозуміло, який елемент є перим, а який другим. Ще додамо термінології: орієнтовані ребра прийнято називати дугами. У нашому графі буде 7 дуг: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . У цьому прикладі ребра (дуги) графа просто пронумеровані, але порядкові номери не єдине, що можна приписати дузі. Дузі можна приписати також ваги, що означають, наприклад, вартість пересилання вантажу з одного пункту в інший. Але з вагами дуг ми познайомимося пізніше та докладніше. Отже, отримуємо наступний орієнтований граф:

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

Приклад 6.На шматочку шахової дошки розміром 3 Х 3 розміщені два білі коні і два чорні коні так, як показано на малюнку нижче.

Чи можна перемістити коней у стан, зображений на наступному малюнку, не забуваючи, що дві постаті що неспроможні перебувати однією клітині?

Рішення. У графі, що конструюється, пари вершин будуть пов'язані ставленням "хід коня". Тобто одна вершина - та, з якої кінь пішов, а інша - та, до якої прийшов, а проміжна клітина літери "г" буде за межами цього відношення. Отримуємо наступний граф:

І все ж конструкція вийшла громіздкою. У ній видно клітини шахівниці, а багато ребер графа перетинаються. Чи не можна абстрагуватися від фізичного вигляду шахівниці і уявити відносини простіше? Виявляється, можна. У новому графі сусідніми вершинами будуть ті, які пов'язані ставленням "хід коня", а не сусідні по шахівниці (рисунок нижче).

Тепер легко побачити, що відповідь на питання цього завдання – негативна. У початковому стані між двома білими кіньми немає чорного коня, а в кінцевому стані цей чорний кінь має бути. Ребра графа розміщені так, що два коня, що знаходяться поруч, не можуть перестрибнути один через одного.

Приклад 7.Завдання про вовка, козу і капусту. На одному березі річки знаходяться людина (Ч), човен, вовк (В), коза (Кз) та капуста (Кп). У човні одночасно можуть перебувати людина і не більше одного з об'єктів, що перевозяться. Людина повинна перевезти на інший берег усі об'єкти, дотримуючись умови: не можна залишати без нагляду вовка разом із козою та козу разом із капустою.

Рішення. У графі, що конструюється, вершини - конфігурації, а ребра - відношення "зв'язок одним плаванням човна" між конфігураціями. Конфігурація означає розташування об'єктів на початковому березі та протилежному березі. Кожна конфігурація відображається у вигляді ( A|B), де A- об'єкти, що знаходяться на первісному березі, а B- Об'єкти, що знаходяться на протилежному березі. Початкова конфігурація, таким чином, - (ПВКпКз| ) . Наприклад, після переправлення на інший берег кози конфігурація буде (ВКп|ЧКЗ) . Кінцева конфігурація завжди ( |ПВКпКз) . Тепер можемо побудувати граф, знаючи вже, що означають вершини та ребра:

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

Як бачимо, існують два різні безперервні маршрути з початкової конфігурації в кінцеву. Тому завдання має два різні рішення (і обидва правильні).

Теорія графів та найважливіші сучасні прикладні завдання

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

Графи-дерева застосовуються, наприклад, для побудови дерев рішень(служать для аналізу ризиків, аналізу можливих придбань та збитків за умов невизначеностей). Із застосуванням теорії графів розроблено та інші численні математичні моделіна вирішення завдань у конкретних предметних областях.

Графи та завдання про потоки

Постановка задачі. Є система водопровідних труб, представлена ​​графом малюнку нижче.

Кожна дуга графа відображає трубу. Числа над дугами (ваги) – пропускна здатність труб. Вузли – місця з'єднання труб. Вода тече трубами тільки в одному напрямку. Вузол S- джерело води, вузол T- Стік. Потрібно максимізувати обсяг води, що протікає від джерела до стоку.

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

Графи та мережеве планування

У задачах планування складних процесів, що складаються з безлічі робіт, частина з яких виконується паралельно, а частина послідовно, широке застосування отримали зважені графи, відомі під назвою ПЕРТ мережі (PERT).

PERT - Program (Project) Evaluation and Review Technique - техніка оцінки та аналізу програм (проектів), що використовується під час управління проектами.

Мережа ПЕРТ - зважений ациклічний орієнтований граф, у якому кожна дуга представляє роботу (дія, операцію), а вага дуги - час, необхідне її виконання.

Якщо в мережі є дуги ( a, b) та ( b, c) , то робота, представлена ​​дугою ( a, b) , повинна бути завершена до початку виконання роботи, представленої дугою ( b, c). Кожна вершина ( vi)представляє момент часу, до якого повинні бути завершені всі роботи, що задаються дугами, що закінчуються у вершині ( vi).

У такому графі:

• одна вершина, яка не має попередників, визначає момент часу початку виконання робіт;
• одна вершина, яка має послідовників, відповідає моменту часу завершення комплексу работ.

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

Весь блок "Теорія графів"