Перегляд вихідного коду сторінки Теорія графів

[[Файл:Graph.gif|right|frame|Граф зі шістьма вершинами та сімома ребрами]]
'''Теорія графів'''&nbsp;— розділ [[математика|математики]], що вивчає властивості [[Граф (математика)|графів]]. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок ([[Вершина (теорія графів)|вершини]]) сполучених лініями ([[Словник термінів теорії графів#Р|ребрами]]). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E&nbsp;— підмножина V × V.

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

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

== Формальні означення ==
{{section-stub|дата=березень 2020}}

Нехай X = { x<sub>1</sub>,…,x<sub>n</sub>}&nbsp;— деяка скінченна множина (множина вершин), M<sub>2</sub>&nbsp;— множина всіх невпорядкованих пар елементів з X,

<center>'''M<sub>2</sub> = { (x<sub>i</sub>,x<sub>j</sub>): x<sub>i</sub> ∈ X, x<sub>j</sub> ∈ X, i ≠ j}'''</center>


'''1.''' Граф G(V, E)&nbsp;— пара множин V, E ⊂ M<sub>2</sub>. Множина V&nbsp;— це множина вершин, множина E&nbsp;— це множина ребер. Якщо (x<sub>i</sub>,x<sub>j</sub>) ∈ E, то ми говоримо, що ребро (x<sub>i</sub>,x<sub>j</sub>) сполучає вершину x<sub>i</sub> з вершиною x<sub>j</sub>; інша термінологія&nbsp;— ребро (x<sub>i</sub>,x<sub>j</sub>) і вершини x<sub>i</sub> та x<sub>j</sub> інцидентні.

'''2.''' Граф G(V, E) називається [[Повний граф|повним]], якщо E = M<sub>2</sub>.

Якщо множина V містить n вершин, то, очевидно, число ребер повного графа дорівнює C<sub>n</sub><sup>2</sup>. Повний граф з n вершинами позначається K<sub>n</sub>.

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

'''4.''' Вершини x<sub>i</sub> та x<sub>j</sub> графа G(V, E) інцидентні, якщо (x<sub>i</sub>,x<sub>j</sub>) ∈ E.

'''5.''' Степенем d(x<sub>i</sub>) вершини x<sub>i</sub> графа G(V, E) називається число вершин x<sub>j</sub>, які інцидентні вершині x<sub>i</sub> (число відрізків, які виходять з вершини x<sub>i</sub>).

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

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

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

'''9'''. Гомологічний цикл у графі&nbsp;— набір його ребер, для якого з кожної вершини виходить парне число ребер набору. Вживають також термін «замкнена крива» у графі. Наприклад, об'єднання ребер прямокутників, на які робивається пляшка Клейна на один багатокутник, є вісьміркою, тому у цьому графі є чотири цикли. Цикли у <math>G</math> утворюють групу із рангом, який є [[Цикломатичне число|цикломатичним числом]], <math>\lambda(G)=|E(G)|-|V(G)|+v,</math> де <math>v</math> чисельність компонент зв'язності графа <math>G</math>.

'''10'''. Група <math>H_{1}(G)</math> усіх циклів у графі <math>G</math> із операцією суми по модулю 2 називається групою гомологій графа <math>G</math> (одновимірною із коефіцієнтами <math>\mathbb{Z}_{2}</math>). Наприклад, <math>H_{1}(G)\cong \mathbb{Z}^{E-V+1}_{2}</math> для зв'язного графа <math>G</math> із <math>V</math> вершинами та <math>E</math> ребрами. Це слідує з того, що сума будь-якого елемента із собою дорівнює нулю, однак це є невірним для <math>|H_{1}(G)|=2^{E-V+1}.</math>

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

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

'''13'''. Графи <math>G_{1}</math> та <math>G_{2}</math> є ізоморфними, якщо існує бієкція <math>f</math> множини <math>V_{1}</math> вершини графа <math>G_{1}</math> на множину <math>V_{2}</math> вершин графа <math>G_{2}</math>, яке задовільняє умові: вершини <math>A,B\in V_{1}</math> є сполученими ребром лише у тому випадку, якщо вершини <math>f(A),\,f(B)\in V_{2}</math> сполучені ребром. Задача перевірки ізоморфізму графів належить до класу задач, для яких поки що невідомо, чи є вони поліноміально вирішуваними, чи ні. Тобто поки що не побудований поліноміальний алгоритм перевірки ізоморфізму графів. Ізоморфізм можна розглядати також як перенумерацію вершин графа, тому будь-яка кількісна характеристика структури графа залишається незмінною. Такі характеристики називаються інваріантами графа<ref>{{Cite book|title=А. C. Белозеров, Б. Ф. Мельников, Н. П. Чурикова - Алгоритмы локального поиска в задаче исследования инвариантов графа.|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref>.

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

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

'''16'''. Кожному графу <math>G</math> відповідає тіло графа, тобто фігура, яка отримується із скінченного числа відрізків ототожненням декількох кінців у відповідності із графом <math>G</math>. Одновимірні поліедри є бієктивними з фігурами, які є топологічно еквівалентними тілу деякого графа. Наприклад, фігури <math>|G_{1}|</math> та <math>|G_{2}|</math> є топологічно еквівалентними лише у випадку, якщо графи <math>G_{1}</math> та <math>G_{2}</math> є [[Гомеоморфізм графів|гомеоморфними]].

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

<math>\text{Початок:}\{\text{стрілки}\}\rightarrow\{\text{об'єкти}\}</math>

<math>\text{Кінець}:\{\text{стрілки}\}\rightarrow\{\text{об'єкти}\}</math>

Вираз <math>f:A\vdash B</math> означає, що <math>f</math> є стрілкою із початком <math>A</math> й кінцем <math>B;</math> таке відношення <math>A\vdash B</math> можна назвати типом <math>f</math>.

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

<math>\text{початок}(f)=A,\,\,\text{кінець}(f)=B</math>

пишуть <math>f:A\rightarrow B, </math> або <math>f:A\vdash B.</math>

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

<math>\mathrm{Id}_{A}:A\vdash A</math>

та бінарна часткова операція на стрілках (композиція), яка, застосована до стрілок <math>f:A\vdash B</math> та <math>g:B\vdash C,</math> породжує стрілку <math>gf:A\vdash C.</math> Спеціальні стрілки відповідають аксіоматичним секвенціям й <math>n</math>-[[Алгебрична операція|арним операціям]] на стрілках із <math>n\geq1,</math> які відповідають правилам виводу. Композиція представляє собою одиничну форму правила перетину

<math>\frac{f:A\vdash B \quad g:B\vdash C}{gf:A\vdash C}.</math>

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

<math>\forall A\forall B(\exists f(f:A\vdash B)\Leftrightarrow \forall C(\exists g(g:B\vdash C)\Rightarrow \exists h(h:A\vdash C))).</math>

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

<math>\forall A\exists f(f:A\vdash A),</math>

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

<math>\forall A\forall B\forall C\forall f\forall g(\exists h((f:A\vdash B)\And g:B\vdash C)\Rightarrow h:A\vdash C).</math><br/>Звідси по рефлексивності й транзитивності отримується стрілка тотожності й композиція стрілок.

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

<math>f\,\mathrm{Id}_{A}=f,</math>

<math>\mathrm{Id}_{B}\,f=f,</math>

<math>(hg)f=h(gf)</math>

для усіх <math>f:A\vdash B,\quad g:B\vdash C,\quad h:C\vdash D.</math>

Перше рівняння стверджує, що композиції, тобто перетини, з одиничними стрілками є усувними, у той час як друге говорить про те, що композиції можуть змінюватися місцями одна з одною. У вільній дедуктивній категорії, яка породжена довільним графом без стрілок, композиція усувна: у цій категорії є лише стрілки тотожності. Існування таких вільних дедуктивних категорій гарантується екваціональною формою категорних аксіом. З більш абстрактної точки зору можна розглядати категорію просто як декотру структуру, коли вона представляє собою сукупність двох різновидів сутностей: об'єктів (а не формул) й стрілок або морфізмів (а не виведень з формул). Самі об'єкти також можуть мати структуру, а морфізми представляють собою відображення, які зберігають цю структуру. Найпопулярніший приклад&nbsp;— [[Категорія множин|категорія <math>\mathrm{Set}</math>]], об'єктами якої є довільні множини, а морфізми є довільними відображеннями. Зв'язок між множинами та дедуктивними категоріями описується наступним чином: вільна абстрактна категорія, породжена довільним графом без стрілок (так звана дискретна категорія або дискрет), може розглядатися як категорне поняття множини. У подібній категорії є лише стрілки тотожності<ref>{{Cite book|title=В.Л.Васюков - Категорная логика.|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref>.

== Сагайдак ==
Сагайдак <math>Q</math>&nbsp;— це орієнтований граф <math>(I,E,t,h)</math>, де <math>I,E</math>&nbsp;— скінченновимірні множини (<math>E</math>&nbsp;— множина ребер графа <math>I</math>&nbsp;— множина його вершин), <math>t,h</math>&nbsp;— відображення <math>t:E\rightarrow I</math> та <math>h:E\rightarrow I.</math> Значення <math>t(a)</math> й <math>h(a)</math> на ребрі <math>a\in E</math>&nbsp;— початок та кінець ребра <math>a</math> відповідно. Можна також записати <math>t(a)=i,\,\, h(a)=j,</math> тоді <math>a:i\rightarrow j</math> або <math>i\overset{a}{\rightarrow}j,</math> тобто якщо <math>a\in E</math>&nbsp;— ребро з вершини <math>i\in I</math> у вершину <math>j\in I.</math> Часто пишуть просто <math>Q=(I,E),</math> вважаючи, що задані декотрі позначені відображення для початку та кінця кожного ребра. Можна замість <math>a\in E</math> записати <math>a\in Q.</math>

Розгляньмо поле комплексних чисел <math>\mathbb{C}.</math> Тоді <math>\mathbb{C}I</math> є комутативною простою алгеброю із одиницею:

<math>1=\sum_{i\in I}1_{i}.</math>

Будь-який <math>\mathbb{C}I</math>-модуль <math>V</math> розкладається у пряму суму <math>V=\bigoplus_{i\in I}V_{i},</math> де <math>V_{i}=1_{j}V.</math> На векторах <math>v=(v_{i})_{i\in I}\in V,\,\, v_{i}\in V_{i},</math> алгебра <math>\mathbb{C}I</math> діє як <math>1_{j}v=(\delta_{ij}v_{i})_{i\in I},</math> та навпаки, набір векторних просторів <math>(V_{i})_{i\in I}</math> задає представлення алгебри <math>\mathbb{C}I</math> на просторі <math>V=\bigoplus_{i\in I}V_{i}</math> із цією дією. Зокрема, представлення сагайдака <math>Q=(I,E)</math> дає представлення <math>\mathbb{C}I.</math>

Якщо <math>V</math> є [[Скінченновимірний простір|скінченновимірним]], то усі <math>V_{i}</math> скінченновимірні. У цьому випадку вектор <math>\alpha=(\alpha_{})_{i\in I}\in\mathbb{Z}^{I}_{\geq0}</math> із компонентами <math>\alpha_{i}=\mathrm{dim}_{\mathbb{C}}V_{i}</math> називається розмірністю <math>\mathbb{C}I</math>-модуля. Множина усіх представлень на <math>\mathbb{C}I</math> модулі <math>V=\bigoplus_{i\in I}V_{i},</math> де <math>V_{i}=\mathbb{C}^{\alpha i},</math> узгоджених із структурою <math>\mathbb{C}I</math>-модуля, позначається <math>\mathrm{Rep}(Q,\alpha).</math> Щоб задати таке представлення, потрібно узяти довільний набір лінійних операторів з <math>\mathbb{C}^{\alpha_{i}}</math> у <math>\mathbb{C}^{\alpha_{j}}</math> для кожного ребра <math>a:i\rightarrow j,</math> таким чином, отримується <math>\mathrm{Rep}(Q,\alpha)=\prod_{a:i\rightarrow j}\mathrm{Hom}(\mathbb{C}^{\alpha_{i}},\mathbb{C}^{\alpha_{j}})</math> (добуток по усім <math>a\in Q</math>), де <math>\mathrm{Hom}(\mathbb{C}^{\alpha_{i}},\mathbb{C}^{\alpha_{j}})</math>&nbsp;— простір лінійних операторів з <math>\mathbb{C}^{\alpha_{i}}</math> у <math>\mathbb{C}^{\alpha_{j}}</math> (комплексних матриць <math>\alpha_{i}\times\alpha_{j}</math>).

Нехай <math>\mathbb{C}E</math>&nbsp;— скінченновимірний векторний простір, вільно породжений множиною <math>E,</math> <math>\mathbb{C}E=\bigoplus_{a\in Q}\mathbb{C}a.</math> На ньому існує натуральна структура <math>\mathbb{C}I</math>-бімодуля

<math>1_{k}\cdot a=\delta_{jk}a,\quad\quad a\cdot 1_{k}=\delta_{ik}a\quad\quad \forall a:i\rightarrow j.</math>

Алгебра шляхів сагайдака <math>Q(I,E)</math> визначається як <math>\mathbb{C}Q=T_{\mathbb{C}I}\mathbb{C}E,</math> де <math>T_{A}M</math> є тензорною алгеброю бімодуля <math>M</math> над алгеброю <math>A,</math>

<math>\mathbb{C}Q=\bigoplus^{\infty}_{l=0}(\mathbb{C}Q)_{l},\quad \quad (\mathbb{C}Q)_{0}=\mathbb{C}I,\quad\quad (\mathbb{C}Q)_{1}=\mathbb{C}E,\quad\quad (\mathbb{C}Q)_{2}=\mathbb{C}E\otimes_{\mathbb{C}I}\mathbb{C}E,\quad\quad (\mathbb{C}Q)_{3}=\mathbb{C}E\otimes_{\mathbb{C}I}\mathbb{C}E\otimes_{\mathbb{C}I}\mathbb{C}E,...</math>

Лінійний простір <math>(\mathbb{C}Q)_{l},\,\,l\geq0,</math> вільно породжений елементами виду <math>a_{l},\cdot\cdot\cdot a_{2}a_{2}1_{i_{0}},</math> де <math>a_{k}:i_{k-1}\rightarrow i_{k}</math> є ребрами, які послідово йдуть між вершинами <math>i_{0},i_{1},...,i_{l}\in I.</math><ref>{{Cite book|title=А.В.Силантьев - Функтор отражения в теории представлений алгебр для колчанов и интегрируемые системы. Физика элементарных частиц и атомного ядра, 2018, т.49, вып.3, с.710-775.|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref> Алгебра шляхів сагайдака є алгеброю із одиницею

<math>1=\sum_{i\in I}e_{i},</math>

де <math>e_{i}</math>&nbsp;— шлях довжини нуль із початком та кінцем у вершині <math>i.</math>

Нехай <math>k</math>&nbsp;— довільне алгебрично замкнене поле, тоді <math>kQ</math>&nbsp;— алгебра шляхів сагайдака, яка може бути розглянута як градуйована алгебра, <math>l</math>-та компонента якої породжується шляхами довжини <math>l.</math> Якщо <math>\mathfrak{I}</math>&nbsp;— однорідний ідеал алгебри <math>kQ</math>, то на алгебрі <math>A=kQ/\mathfrak{I}</math> успадковується структура градуйованої алгебри <math>A=\bigoplus_{l\geq0}A_{l}.</math><ref name=":0">{{Cite book|title=С. О. Иванов, Стабильная Калаби–Яу размерность препроективных алгебр типа Ln, Алгебра и анализ, 2012, том 24, выпуск 3, 148–162|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref>

Нехай <math>A=kQ/\mathfrak{I}</math>&nbsp;— алгебра шляхів сагайдака та фроберіусовою формою <math>\varepsilon:A\rightarrow k</math>, Фробеніусова форма <math>\varepsilon</math> називається <math>Q_{0}</math>-формою, якщо існує <math>kQ_{0}</math>-бімодуль <math>T\leq \mathrm{Ker}(\varepsilon)</math> такий, що <math>A=\mathrm{soc}(A)\oplus T.</math> Якщо <math>A=kQ/I</math>&nbsp;— самоін'єктивна алгебра шляхів сагайдака, <math>\varepsilon:A\rightarrow k</math>&nbsp;— <math>Q_{0}</math>-форма на <math>A,</math> <math>\tilde{v}=A\rightarrow A</math>&nbsp;— відповідний автоморфізм Накаями<ref>{{Cite book|title=K. Yamagata, Frobenius algebras, in Handbook of algebra, Vol. 1, 841–887, Elsevier, Amsterdam, 1996.|last=|first=|year=|publisher=|location=|pages=|language=|isbn=}}</ref>, <math>\varrho:A\rightarrow A\otimes A</math>&nbsp;— фробеніусовий кодобуток, тоді <math>\tilde{\nu}(e_{i})=e_{\nu_{0}(i)}\,\,\, \forall i\in Q_{0},\,\,\mathrm{Im}(\varrho)\leq \bigoplus_{i\in Q_{0}}P_{\nu_{0}(i),i},</math> причому

<math>\varrho':A\rightarrow\bigoplus_{i\in Q_{0}}P_{\nu_{0}(i),i},</math>

де <math>\varrho'(a)=\varrho(a)</math>&nbsp;— [[ін'єктивна оболонка]] бімодулю <math>A.</math>

Якщо <math>M</math>&nbsp;— <math>A</math>-модуль, то через <math>\mathrm{rad}^{k}(M)</math> позначається <math>k</math>-тий член радіального ряду <math>M=\mathrm{rad}^{0}(M)\supseteq\mathrm{rad}^{1}(M)\supseteq...</math> та через <math>\mathrm{soc}^{k}(M)\,\,\,k</math>-тий член цокольного ряду <math>0=\mathrm{soc}^{0}(M)\subseteq \mathrm{soc}^{1}(M)\subseteq...</math> Для <math>k<0</math> будемо вважати, що <math>\mathrm{soc}^{k}(M)=0</math> та <math>\mathrm{rad}^{k}(M)=M.</math> Нехай <math>\mathfrak{I}</math>&nbsp;— однорідний припустимий ідеал алгебри шляхів <math>kQ,\,\,A=kQ/\mathfrak{I}</math> та <math>P_{i}=e_{i}A.</math> Тоді

<math>\mathrm{rad}^{k}(P_{i})=\bigoplus_{l\geq k}e_{i}A_{l}.</math>

Якщо алгебра <math>A</math> є самоін'єктивною і довжина Леві модулю <math>P_{i}</math> дорівнює <math>m,</math> то<ref name=":0" />

<math>\mathrm{soc}^{k}(P_{i})=\mathrm{rad}^{m-k}(P_{i}).</math>

== Історія виникнення теорії графів ==
Родоначальником теорії графів вважається [[Леонард Ейлер]]. У 1736 році в одному зі своїх листів він формулює і пропонує розв'язок задачі про сім Кенігсберзьких мостів, що стала згодом однією з класичних задач теорії графів.
 
Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.

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

== Алгоритми на графах ==
# [[Пошук в глибину]].
# [[Пошук в ширину]].
# [[Топологічне сортування]].
# [[Фундаментальна множина циклів]].
# [[Ейлерів ланцюг|Ейлерів цикл]]. [[Ейлерів ланцюг|Теорема Ейлера]].
# [[Гамільтонів цикл]].
# [[Задача про гамільтонів шлях]]
# [[Алгоритм Беллмана—Форда|Алгоритм Беллмана-Форда]].
# [[Алгоритм Дейкстри]].
# [[Алгоритм Флойда — Воршелла]].
# [[Транзитивне замикання]] графа.
# [[Системи неперетинаючих множин]].
# [[Зв'язний граф|Зв'язність]]. Алгоритми [[Алгоритм Прима|Прима]] та [[Алгоритм Крускала|Крускала]]. [[Кістякове дерево]]
# [[Коди Прюфера]].
# [[Матрична теорема про дерева]].
# Знаходження [[точка сполучення|точок сполучення]] та [[Міст (теорія графів)|мостів]] у графі.
# [[Алгоритм Едмондса-Карпа]].
# [[Пошук максимального паросполучення]]
# Знаходження [[Найменший спільний предок|найменшого спільного предку]] в дереві.

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

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

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

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

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

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

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

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

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

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

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

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

== Деякі задачі теорії графів ==
* [[Сім мостів Кенігсберга|Проблема семи мостів Кенігсберга]]&nbsp;— один з перших результатів у теорії графів, опублікований Ейлером в 1736.
* [[Проблема чотирьох фарб]]&nbsp;— була сформульована в 1852, але некласичне доведення отримано лише в 1976 (достатньо 4-х фарб для карти на сфері (площині).
* [[Задача комівояжера|Завдання комівояжера]]&nbsp;— одна з найбільш відомих NP-повних задач.
* [[Задача про кліку]]&nbsp;— ще одна NP-повна задача.
* Знаходження [[Мінімальне кістякове дерево|мінімального стягуючого]] ([[Кістякове дерево|кістякового]]) дерева.
* Знаходження [[Задача Штейнера|мінімального дерева Штейнера]]&nbsp;— найкоротшої мережі, що з'єднує заданий кінцевий набір точок площини, при умові, що дозволяється додавати до мережі нові точки. NP-повна задача.
* [[Ізоморфізм графів]]&nbsp;— чи можна шляхом зміни нумерації вершин одного графа отримати інший.
* [[Задача пошуку ізоморфного підграфа|Пошук ізоморфного підграфа]]&nbsp;— чи містить граф <math>G</math> підграф, ізоморфний графу <math>H</math>.
* [[Планарний граф|Планарність графа]]&nbsp;— чи можна зобразити граф на площині без перетинань ребер (або з мінімальним числом шарів, що знаходить застосування при трасуванні з'єднань елементів друкованих плат або мікросхем).

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

== Застосування теорії графів ==
* В [[хімія|хімії]] (для опису структур, шляхів складних реакцій, [[правило фаз]] також може бути інтерпретоване як задача теорії графів); [[комп'ютерна хімія]]&nbsp;— порівняно молода галузь хімії, заснована на застосуванні теорії графів. Теорія графів являє собою математичну основу [[хемоінформатика]]. Теорія графів дозволяє точно визначити число теоретично можливих [[Ізомери|ізомерів]] у [[вуглеводні]]в та інших органічних сполук.
* В [[Інформатика|інформатиці]] та [[Програмування|програмуванні]] (граф-схема алгоритму)
* У комунікаційних і транспортних системах. Зокрема, для [[Маршрутизація|маршрутизації]] даних в [[Інтернет]]і.
* В [[Економіка|економіці]]
* В [[Логістика|логістиці]]
* У [[Схемотехніка|схемотехніці]] (топологія з'єднання елементів на [[Друкована плата|друкованій платі]] або [[Мікросхема|мікросхемі]] являє собою [[граф]] або [[гіперграф]]).

== Див. також ==
{{Портал|Математика}}
* [[Словник термінів теорії графів]]
* [[Дерево (теорія графів)|Дерево]]
* [[Теорема Турана]]
* [[Бондграф]]
* [[Алгебрична теорія графів]]
* [[Спектральна теорія графів]]
* [[Хімічна теорія графів]]

== Примітки ==
{{примітки|2}}

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

== Посилання ==
* [http://www.graphs.ee/Fundamentals.pdf Основи ідентифікації та систематизації графів] {{Webarchive|url=https://web.archive.org/web/20190711171039/http://www.graphs.ee/Fundamentals.pdf |date=11 липня 2019 }} (pdf)

{{refimprove|дата=березень 2020}}
{{стиль|дата=березень 2020}}

{{Математика-footer}}
{{Інформатика}}


{{Math-stub}}

[[Категорія:Теорія графів| ]]
[[Категорія:Теоретична інформатика]]
[[Категорія:Розділи математики]]