Теорія графів

 

Теорія графів




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

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

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

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

     Формальне означення графа:

Нехай X = { x1,…,xn} — деяка скінченна множина (множина вершин), M2 — множина всіх невпорядкованих пар елементів з X,

M2 = { (xi,xj): xi  X, xj  X, i ≠ j}

1. Граф G(X, W) — пара множин X, W ⊂ M2. Множина X — це множина вершин, множина W — це множина ребер. Якщо (xi,xj) ∈ W, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.

2.Граф G(X, W) називається повним, якщо W = M2.

Якщо множина X містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.

3. Граф G(X, W) називається порожнім, якщо W = ∅.

4. Вершини xi та xj графа G(X, W) інцидентні, якщо (xi,xj) ∈ W.

5. Степенем d(xi) вершини xi графа G(X, W) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).

6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(X, W). Якщо d(xi)=0, то вершина xi називаєтьсяізольованою.

Зміст

  1.  Історія виникнення теорії графів
  2.  Алгоритми на графах
  3.  Термінологія теорії графів
  4.  Зображення графів на площині
  5.  Деякі задачі теорії графів
  6.  Застосування теорії графів

     Історія виникнення теорії графів

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

Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.

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

 

Алгоритми на графах

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

     Термінологія теорії графів

Термінологія теорії графів не визначена суворо. Зокрема в монографії Гудман, Хідетніемі, 1981 сказано: "У програмістському світі немає єдиної думки про вибір з двох термінів «граф» або «мережа».

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

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

Лісом називається граф, який не містить циклів. Зв'язний ліс називається деревом.

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

Планарним графом називається граф G, ізоморфний деякому плоскому графу. Останній називається плоскою картою графа G.

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

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

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

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

      Зображення графів на площині

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

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

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

 

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

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


Создан 03 дек 2016