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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф зі шістьма вершинами та сімома ребрами

Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин 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 називається ізольованою.

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

Родоначальником теорії графів вважається Леонард Ейлер. У 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.

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

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

Зображення графів на площині[ред.ред. код]

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

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

Деякі задачі теорії графів[ред.ред. код]

  • Проблема чотирьох фарб — була сформульована в 1852, але некласичне доведення отримано лише в 1976 (достатньо 4-х фарб для карти на сфері (площині).
  • Задача про клік — ще одна NP-повна задача.
  • Знаходження мінімального стягуючого (остовного) дерева.
  • Знаходження мінімального дерева Штейнера — найкоротшої мережі, що з'єднує заданий кінцевий набір точок площини, при умові, що дозволяється додавати до мережі нові точки. NP-повна задача.
  • Ізоморфізм графів — чи можна шляхом зміни нумерації вершин одного графа отримати інший.
  • Планарними графа — чи можна зобразити граф на площині без перетинань ребер (або з мінімальним числом шарів, що знаходить застосування при трасуванні з'єднань елементів друкованих плат або мікросхем).

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

Застосування теорії графів[ред.ред. код]

Література[ред.ред. код]

  • Басакер Р., Сааті Т. Кінцеві графи та мережі. М.: Наука, 1974. 368c.
  • Бєлов В. В., Воробйов Є. М., Шаталов В. Є. Теорія графів - М .: Вища. школа, 1976. - С. 392.
  • Берж К. Теорія графів та її застосування. М.: ІЛ, 1962. 320c.
  • Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М.: Наука, 1990. 384с. (Ізд.2, испр. М.: УРСС, 2009. 392 с.)
  • Зиков О. О. Основи теорії графів - М .: "Вузівська книга", 2004. - С. 664. - ISBN 5-9502-0057-8. (М.: Наука, 1987. 383c.)
  • Хімічні програми топології і теорії графів. Під ред. Р. Кінга. Пер. з англ. М.: Мир, 1987.
  • Кірсанов М. Н. Графи в Maple. М.: Физматлит, 2007. 168
  • Крістофідес Н. Теорія графів. Алгоритмічний підхід. М.: Мир, 1978. 429c.
  • Кормен Т. Х. та ін Частина VI. Алгоритми для роботи з графами // Алгоритми: побудова й аналіз = Introduction to Algorithms - 2-е изд .. - М .: Вільямс, 2006. - С. 1296. - ISBN 0-07-013151-1.
  • Оре О. Теорія графів - 2-е изд .. - М .: Наука, 1980. - С. 336.
  • Салій В. Н. Богомолов А. М. Алгебраїчні основи теорії дискретних систем - М .: Фізико-математична література, 1997. - ISBN 5-02-015033-9.
  • Свамі М., Тхулаліраман К. Графи, мережі та алгоритми. М: Світ, 1984. 455с.
  • Татт У. Теорія графів. Пер. з англ. М.: Мир, 1988. 424 с.
  • Уілсон Р. Введення в теорію графів. Пер з англ. М.: Мир, 1977. 208с.
  • Харарі Ф. Теорія графів - М .: Світ, 1973. (Вид. 3, М.: КомКніга, 2006. - 296 с.)
  • Харарі Ф., Палмер Е. Перерахування графів - Світ, 1977.
  • Diestel R. Graph Theory, Electronic Edition - NY: Springer-Verlag, 2005. - С. 422.
  • К.В. Ніколаєва, В.В. Койбічук ДИСКРЕТНИЙ АНАЛІЗ. Графи та їх застосування в економіці

Див. також[ред.ред. код]



Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.
Основні розділи Математики
АлгебраДискретна математикаДиференціальні рівнянняГеометріяКомбінаторикаЛінійна алгебраМатематична логікаМатематична статистикаМатематичний аналізТеорія ймовірностейТеорія множинТеорія чиселТригонометріяМатематична фізикаТопологіяФункціональний аналізРекреаційна математика