Графи та їх застосування

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЖИТОМИРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІМЕНІ ІВАНА ФРАНКА

Кафедра математичного аналізу

Курсова робота на тему:

«Графи та їх застосування»

Зміст

Вступ

1.1 Застосування теорії графів

1.2 Що таке граф?

1.3 Основні строгі означення теорії графів

Розділ 2

2.1 Графи в логічних задачах

2.2 Елементи теорії графів у задачах

2.3 Задачі на використання дерев2

Висновки

Література

1. Вступ

Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлеру, з'явилася в 1736 р. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися при побудові схем.

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

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

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

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

Розділ 1

1.1 Застосування теорії графів

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

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

Наприклад, у вигляді графа можуть бути зображені:

      електричні і транспортні мережі;

      інформаційні і комп’ютерні мережі;

      карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

      моделі кристалів;

      структури молекул хімічних речовин;

      моделі ігор;

      різні математичні об’єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

      лабіринти;

      плани діяльності або плани виконання певних робіт (розклади);

      генеалогічні дерева тощо.

Приклади застосування теорії графів:

      пошук зв’язних компонентів у комунікаційних мережах;

      пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

      побудова кістякового дерева:  зв’язність з найменшою можливою кількістю ребер;

      пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

      ізоморфізм графів: ідентичність структур молекул (ізометрія);

      знаходження циклів графів:

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

      ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

      розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

      планарність графів: проектування друкованих електронних та електричних схем, транспортних розв’язок тощо;

      знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”)

тощо.

1.2 Що таке граф?

  Для початку розглянемо рис. 1.1 і 1.2, на яких зображено відповідно ділянка електричного кола і частина карти дороги. Ясно, що обидва малюнка можуть бути представлені однією і тією ж самою діаграмою з точок і ліній, що зображені на рис. 1.3. Точки Р, Q, R , S i T  називаються вершинами, лінії називаються ребрами, а вся діаграма називається графом. Степенем вершини називається число ребер, кінцем якої являється дана вершина; на рис. 1.2 це відповідає числу доріг, що сходяться у перехресті; так, степінь вершини Q рівна 4.

Розглянуті ситуації можна описати іншим графом, що зображений на рис. 1.4.

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

                         Тим самим хочеться наголосити, що граф – це представлення деякої множини точок і способу їх з’єднання і що «метричні» властивості несуттєві. Виходячи з цього, будь-які 2 графа, що представляють одну і ту ж ситуацію, будуть вважатись однаковими. Точніше кажучи, що 2 графа ізоморфні, якщо існує взаємнооднозначна відповідність між їх вершинами, що володіють тими же властивостями, що і 2 вершини з’єднані ребром в одному графі тоді і тільки тоді, коли відповідні їм вершини з’єднані ребром в іншому. На рис. 1.5 зображений ще один граф, ізоморфний двом попереднім.

              Розглянутий раніше граф, «простий» у тому сенсі, що у ньому будь-яку пару вершин з’єднує не більш ніж одне ребро. Припустимо, що дороги від Q до S і від S до T (рис 1.5) занадто загружені і для їх розгрузки проклали паралельні дороги, що з’єднують ті самі точки; тоді діаграма буде виглядати так, як на рис. 1.6 (ребра, що з’єднують Q з S або S з T, називаються кратними). Якщо ж ми ще хочемо побудувати гараж в пункті P, то на діаграмі це можна відмітити ребром, що проходить з Р в Р; таке ребро звичайно називають петлею (рис 1.7); графи що не містять петель називатимемо простими.

                         Багато уваги приділяється в теорії графів вивченню різного роду ланцюгів; під ланцюгом розуміється послідовність ребер, що йдуть один за одним. Так наприклад на рис. 1.5 один із способів потрапити з Р в R описується ланцюгом Р →Q→R довжини 2; аналогічно, P→S→Q→T→S→R є ланцюг довжини 5. По очевидним міркуванням ланцюг виду Q→S→T→Q називається циклом. Граф, у якому будь-які 2 вершини з’єднані ланцюгом називається зв’язковим графом.

1.3 Основні означення теорії графів

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

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

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

Надалі вершини графа ми будемо позначати латинськими літерами A, B, C, D. Іноді граф в цілому будемо позначати однією великою літерою.

Означення 2. Вершини графа, які не належать жодному ребру, називають ізольованими.

Означення 3. Граф, що складається лише з ізольованих графів, називається нуль-графом (рис. 2.2).

Означення 4. Граф, в якому кожна пара вершин з’єднана ребром, називається повним.

Означення 5. Степенем вершини називається число ребер, яким належить вершина. Вершина може мати будь-який степінь від 0 до п-1, де п – число вершин графа. Вершина називається непарною (парною), якщо її степінь – число непарне (парне). Якщо степінь вершини дорівнює 0, то вона називається ізольованою.

Означення 6. Граф, степінь всіх k вершин якого однакові, називається однорідним графом степеня k (рис. 2.3 – граф 4 степеня).

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

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

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

Означення 10. Шляхом від A до X називається послідовність ребер, що веде від A до X, така, що кожні два сусідніх ребра мають загальну вершину, і ніяке ребро не зустрічається більше одного разу.

Означення 11. Циклом називається шлях, в якому співпадають початкова і кінцева точка. На рис. 2.1 послідовність ребер AFEDFBCA являє собою цикл.

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

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

Означення 14. Дві вершини A и B у графі називаються зв’язними (незв’язними), якщо в ньому існує (не існує) шлях, що веде з A в B.

Означення 15.  Граф називається зв’язним, якщо кожні дві його вершини зв’язні; якщо ж в графі знайдеться хоча б одна пара незв’язних вершин, то граф називається незв’язним. На рис. 2.5 зображений граф, що складається з 4 зв’язних елементів, один з яких представляє собою ізольовану вершину.

Означення 16. Деревом називається зв'язний граф, який не містить циклів. Тривимірною моделлю графа-дерева служить, наприклад, справжнє дерево з його хитромудро розгалуженою кроною; ріка та її притоки також утворюють дерево, але вже плоске - на поверхні землі. Для того, щоб побудувати дерево, виберемо деяку вершину виберемо деяку вершину А0. З А0 проведемо ребра в сусідні вершини А1, А2,…, з них проведемо ребра до їх сусідів А11, А12,…, А21, А22,… і так далі (рис. 2.6)

Означення 17. Незв'язний граф, що складається виключно з дерев, називається лісом (не містить циклів).

Означення 18.  Дерево, всі n  вершин якого мають номери от 1 до n, називають деревом с пронумерованими вершинами.

              Отже, ми розглянули основні визначення теорії графів, без яких було б неможливо доказ теорем, а, отже і рішення задач.

Розділ 2

2.1 Графи і логічні задачі

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

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

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

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