Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V.
Визначення графа є настільки загальним, що цим терміном можна описувати безліч подій та об'єктів повсякденного життя. Високий рівень абстракції та узагальнення дозволяє використовувати типові алгоритми теорії графів для вирішення зовнішньо несхожих задач у транспортних і комп'ютерних мережах, будівельному проектуванні, молекулярному моделюванні тощо. Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали тощо розглядаються як вершини, а дороги, інженерні мережі, лінії електропередачі, що їй з'єднують, тощо — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Формальні означення
Нехай X = { x1,…,xn} — деяка скінченна множина (множина вершин), M2 — множина всіх невпорядкованих пар елементів з X,
M2 = { (xi,xj): xi ∈ X, xj ∈ X, i ≠ j}
1. Граф G(V, E) — пара множин V, E ⊂ M2. Множина V — це множина вершин, множина E — це множина ребер. Якщо (xi,xj) ∈ E, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.
2. Граф G(V, E) називається повним, якщо E = M2.
Якщо множина V містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.
3. Граф G(V, E) називається порожнім, якщо V = ∅.
4. Вершини xi та xj графа G(V, E) інцидентні, якщо (xi,xj) ∈ E.
5. Степенем d(xi) вершини xi графа G(V, E) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).
6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(V, E). Якщо d(xi)=0, то вершина xi називається ізольованою.
7. Шляхом називається скінченна послідовність вершин, у якій будь-які дві сусідні вершини сполучені ребром.
8. Циклом є шлях, в якому перша і остання вершини збігаються. Наприклад, через позначається граф, гомеоморфний циклу (1-поліедр, тобто клас еквівалентності декотрого графа за відношенням гомеоморфності). Одновимірні поліедри є ламаними лініями (причому припускається їх розпадання на шматки, а також галуження: в одній вершині можуть змикатися скільки завгодно відрізків). Іншими словами, у топологічному сенсі граф представляє собою CW-комплекс розмірності 1 (ребра такого графа представляють відкриті підможини, гомеоморфні одиничному інтервалу (див. Шлях (топологія))).
9. Гомологічний цикл у графі — набір його ребер, для якого з кожної вершини виходить парне число ребер набору. Вживають також термін «замкнена крива» у графі. Наприклад, об'єднання ребер прямокутників, на які робивається пляшка Клейна на один багатокутник, є вісьміркою, тому у цьому графі є чотири цикли. Цикли у утворюють групу із рангом, який є цикломатичним числом, де чисельність компонент зв'язності графа .
10. Група усіх циклів у графі із операцією суми по модулю 2 називається групою гомологій графа (одновимірною із коефіцієнтами ). Наприклад, для зв'язного графа із вершинами та ребрами. Це слідує з того, що сума будь-якого елемента із собою дорівнює нулю, однак це є невірним для
11. Граф є зв'язним, якщо будь-які його вершини можна сполучити шляхом. Кількості вершин, ребер та компонент зв'язності позначаються відповідно.
12. Граф є підграфом графа якщо кожна вершина графа є вершиною графа і кожне ребро графа є ребром графа При цьому дві вершини , сполучені ребром у не обов'язково сполучені ребром у .
13. Графи та є ізоморфними, якщо існує бієкція множини вершини графа на множину вершин графа , яке задовільняє умові: вершини є сполученими ребром лише у тому випадку, якщо вершини сполучені ребром. Задача перевірки ізоморфізму графів належить до класу задач, для яких поки що невідомо, чи є вони поліноміально вирішуваними, чи ні. Тобто поки що не побудований поліноміальний алгоритм перевірки ізоморфізму графів. Ізоморфізм можна розглядати також як перенумерацію вершин графа, тому будь-яка кількісна характеристика структури графа залишається незмінною. Такі характеристики називаються інваріантами графа.
14. Два графи є гомеоморфними, якщо від одного можна перейти до іншого за допомогою операцій підрозділення ребра й зворотних до них. Це є еквівалентним існуванню графа, який можна отримати з даних графів операціями підрозділення ребра. Одновимірні групи гомологій гомеоморфних графів є ізоморфними. Наприклад, коли один граф отримується з іншого підрозділенням ребра.
15. Представляючий граф називається триангуляцією відповідного одновимірного поліедру.
16. Кожному графу відповідає тіло графа, тобто фігура, яка отримується із скінченного числа відрізків ототожненням декількох кінців у відповідності із графом . Одновимірні поліедри є бієктивними з фігурами, які є топологічно еквівалентними тілу деякого графа. Наприклад, фігури та є топологічно еквівалентними лише у випадку, якщо графи та є гомеоморфними.
У категорній логіці Граф складається з класу стрілок (орієнтованих ребер), класу об'єктів (вершин) та двох відображень
Вираз означає, що є стрілкою із початком й кінцем таке відношення можна назвати типом .
Замість того, щоб писати
пишуть або
Дедуктивна система є графом, який може мати наступні операції на стрілках: для кожного об'єкта існує стрілка тотожності (ідемпотентна):
та бінарна часткова операція на стрілках (композиція), яка, застосована до стрілок та породжує стрілку Спеціальні стрілки відповідають аксіоматичним секвенціям й -арним операціям на стрілках із які відповідають правилам виводу. Композиція представляє собою одиничну форму правила перетину
Відношення слідування є узагальненням відношення передпорядку на сукупності і об'єкти (або на дві сукупності об'єктів, коли відношення слідування множинно по обом сторонам, як у випадку генценівських систем класичної логіки). Відношення передпорядку є спеціальним видом дедуктивної системи, коли за кожною парою об'єктів є принамні одна стрілка із початком й кінцем Передвпорядковані графи виконують еквівалентність, яка має місце для кожної дедуктивної системи:
Зправа наліво це дає
а зліва направо дає транзитивність:
Звідси по рефлексивності й транзитивності отримується стрілка тотожності й композиція стрілок.
Дедуктивна категорія є дедуктивною системою, у якій наступні рівняння між доказами мають місце:
для усіх
Перше рівняння стверджує, що композиції, тобто перетини, з одиничними стрілками є усувними, у той час як друге говорить про те, що композиції можуть змінюватися місцями одна з одною. У вільній дедуктивній категорії, яка породжена довільним графом без стрілок, композиція усувна: у цій категорії є лише стрілки тотожності. Існування таких вільних дедуктивних категорій гарантується екваціональною формою категорних аксіом. З більш абстрактної точки зору можна розглядати категорію просто як декотру структуру, коли вона представляє собою сукупність двох різновидів сутностей: об'єктів (а не формул) й стрілок або морфізмів (а не виведень з формул). Самі об'єкти також можуть мати структуру, а морфізми представляють собою відображення, які зберігають цю структуру. Найпопулярніший приклад — категорія , об'єктами якої є довільні множини, а морфізми є довільними відображеннями. Зв'язок між множинами та дедуктивними категоріями описується наступним чином: вільна абстрактна категорія, породжена довільним графом без стрілок (так звана дискретна категорія або дискрет), може розглядатися як категорне поняття множини. У подібній категорії є лише стрілки тотожності.
Сагайдак Сагайдак — це орієнтований граф , де — скінченновимірні множини ( — множина ребер графа — множина його вершин), — відображення та Значення й на ребрі — початок та кінець ребра відповідно. Можна також записати тоді або тобто якщо — ребро з вершини у вершину Часто пишуть просто вважаючи, що задані декотрі позначені відображення для початку та кінця кожного ребра. Можна замість записати
Розгляньмо поле комплексних чисел Тоді є комутативною простою алгеброю із одиницею:
Будь-який -модуль розкладається у пряму суму де На векторах алгебра діє як та навпаки, набір векторних просторів задає представлення алгебри на просторі із цією дією. Зокрема, представлення сагайдака дає представлення
Якщо є скінченновимірним, то усі скінченновимірні. У цьому випадку вектор із компонентами називається розмірністю -модуля. Множина усіх представлень на модулі де узгоджених із структурою -модуля, позначається Щоб задати таке представлення, потрібно узяти довільний набір лінійних операторів з у для кожного ребра таким чином, отримується (добуток по усім ), де — простір лінійних операторів з у (комплексних матриць ).
Нехай — скінченновимірний векторний простір, вільно породжений множиною На ньому існує натуральна структура -бімодуля
Алгебра шляхів сагайдака визначається як де є тензорною алгеброю бімодуля над алгеброю
Лінійний простір вільно породжений елементами виду де є ребрами, які послідово йдуть між вершинами Алгебра шляхів сагайдака є алгеброю із одиницею
де — шлях довжини нуль із початком та кінцем у вершині
Нехай — довільне алгебрично замкнене поле, тоді — алгебра шляхів сагайдака, яка може бути розглянута як градуйована алгебра, -та компонента якої породжується шляхами довжини Якщо — однорідний ідеал алгебри , то на алгебрі успадковується структура градуйованої алгебри
Нехай — алгебра шляхів сагайдака та фроберіусовою формою , Фробеніусова форма називається -формою, якщо існує -бімодуль такий, що Якщо — самоін'єктивна алгебра шляхів сагайдака, — -форма на — відповідний автоморфізм Накаями, — фробеніусовий кодобуток, тоді причому
де — ін'єктивна оболонка бімодулю
Якщо — -модуль, то через позначається -тий член радіального ряду та через -тий член цокольного ряду Для будемо вважати, що та Нехай — однорідний припустимий ідеал алгебри шляхів та Тоді
Якщо алгебра є самоін'єктивною і довжина Леві модулю дорівнює то
Історія виникнення теорії графів Родоначальником теорії графів вважається Леонард Ейлер. У 1736 році в одному зі своїх листів він формулює і пропонує розв'язок задачі про сім мостів Кеніґсберґа, що стала згодом однією з класичних задач теорії графів.
Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа та ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів, наприклад, знаменита проблема чотирьох фарб, інтригуюча математиків і по сей день. Теорія графів швидко розвивається, знаходить все нові додатки і чекає молодих дослідників.
Алгоритми на графах