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

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

Граф зі шістьма вершинами та сімома ребрами

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

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

Формальні означення

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

M₂ = { (x_i,x_j): x_i ∈ X, x_j ∈ X, i ≠ j}

1. Граф G(V, E) — пара множин V, E ⊂ M₂. Множина V — це множина вершин, множина E — це множина ребер. Якщо (x_i,x_j) ∈ E, то ми говоримо, що ребро (x_i,x_j) сполучає вершину x_i з вершиною x_j; інша термінологія — ребро (x_i,x_j) і вершини x_i та x_j інцидентні.

2. Граф G(V, E) називається повним, якщо E = M₂.

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

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

4. Вершини x_i та x_j графа G(V, E) інцидентні, якщо (x_i,x_j) ∈ E.

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

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

7. Шляхом називається скінченна послідовність вершин, у якій будь-які дві сусідні вершини сполучені ребром.

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

9. Гомологічний цикл у графі — набір його ребер, для якого з кожної вершини виходить парне число ребер набору. Вживають також термін «замкнена крива» у графі. Наприклад, об'єднання ребер прямокутників, на які робивається пляшка Клейна на один багатокутник, є вісьміркою, тому у цьому графі є чотири цикли. Цикли у утворюють групу із рангом, який є цикломатичним числом, де чисельність компонент зв'язності графа .

10. Група усіх циклів у графі із операцією суми по модулю 2 називається групою гомологій графа (одновимірною із коефіцієнтами ). Наприклад, для зв'язного графа із вершинами та ребрами. Це слідує з того, що сума будь-якого елемента із собою дорівнює нулю, однак це є невірним для

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

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

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

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

15. Представляючий граф називається триангуляцією відповідного одновимірного поліедру.

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

У категорній логіці

Граф складається з класу стрілок (орієнтованих ребер), класу об'єктів (вершин) та двох відображень

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

Замість того, щоб писати

пишуть або

Дедуктивна система є графом, який може мати наступні операції на стрілках: для кожного об'єкта існує стрілка тотожності (ідемпотентна):

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

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

Зправа наліво це дає

а зліва направо дає транзитивність:

Звідси по рефлексивності й транзитивності отримується стрілка тотожності й композиція стрілок.

Дедуктивна категорія є дедуктивною системою, у якій наступні рівняння між доказами мають місце:

для усіх

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

Сагайдак

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

Розгляньмо поле комплексних чисел Тоді є комутативною простою алгеброю із одиницею:

Будь-який -модуль розкладається у пряму суму де На векторах алгебра діє як та навпаки, набір векторних просторів задає представлення алгебри на просторі із цією дією. Зокрема, представлення сагайдака дає представлення

Якщо є скінченновимірним, то усі скінченновимірні. У цьому випадку вектор із компонентами називається розмірністю -модуля. Множина усіх представлень на модулі де узгоджених із структурою -модуля, позначається Щоб задати таке представлення, потрібно узяти довільний набір лінійних операторів з у для кожного ребра таким чином, отримується (добуток по усім ), де  — простір лінійних операторів з у (комплексних матриць ).

Нехай  — скінченновимірний векторний простір, вільно породжений множиною На ньому існує натуральна структура -бімодуля

Алгебра шляхів сагайдака визначається як де є тензорною алгеброю бімодуля над алгеброю

Лінійний простір вільно породжений елементами виду де є ребрами, які послідово йдуть між вершинами Алгебра шляхів сагайдака є алгеброю із одиницею

де  — шлях довжини нуль із початком та кінцем у вершині

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

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

де  — ін'єктивна оболонка бімодулю

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

Якщо алгебра є самоін'єктивною і довжина Леві модулю дорівнює то

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

• Портал «Математика»

• Словник термінів теорії графів
• Дерево
• Теорема Турана
• Бондграф
• Алгебрична теорія графів
• Спектральна теорія графів
• Хімічна теорія графів

Примітки

1. А. C. Белозеров, Б. Ф. Мельников, Н. П. Чурикова - Алгоритмы локального поиска в задаче исследования инвариантов графа. 
2. В.Л.Васюков - Категорная логика. 
3. А.В.Силантьев - Функтор отражения в теории представлений алгебр для колчанов и интегрируемые системы. Физика элементарных частиц и атомного ядра, 2018, т.49, вып.3, с.710-775. 
4. С. О. Иванов, Стабильная Калаби–Яу размерность препроективных алгебр типа Ln, Алгебра и анализ, 2012, том 24, выпуск 3, 148–162. 
5. K. Yamagata, Frobenius algebras, in Handbook of algebra, Vol. 1, 841–887, Elsevier, Amsterdam, 1996. 

Література

• Басакер Р., Сааті Т. Кінцеві графи та мережі. М.: Наука, 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.
• К. В. Ніколаєва, В. В. Койбічук ДИСКРЕТНИЙ АНАЛІЗ. Графи та їх застосування в економіці

Посилання

• Основи ідентифікації та систематизації графів [ 11 липня 2019 у Wayback Machine.] (pdf)