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

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

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) називається порожнім, якщо W = ∅.

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. Циклом є шлях, в якому перша і остання вершини збігаються . Наприклад, через ${\displaystyle S^{1}}$ позначається граф, гомеоморфний циклу (1-поліедр, тобто клас еквівалентності декотрого графу по відношенню гомеоморфності). Одновимірні поліедри є ломаними лініями (причому припускається їх розпадання на шматки, а також галуження: у одній вершині можуть змикатися скільки завгодно відрізків). Іншими словами, у топологічному сенсі граф представляє собою CW-комплекс розмірності 1 (ребра такого графу представляють відкриті підможини, гомеоморфні одиничному інтервалу (див. Шлях (топологія))).

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

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

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

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

13. Графи ${\displaystyle G_{1}}$ та ${\displaystyle G_{2}}$ є ізоморфними, якщо існує бієкція ${\displaystyle f}$ множини ${\displaystyle V_{1}}$ вершини графу ${\displaystyle G_{1}}$ на множину ${\displaystyle V_{2}}$ вершин графу ${\displaystyle G_{2}}$, яке задовільняє умові: вершини ${\displaystyle A,B\in V_{1}}$ є сполученими ребром лише у тому випадку, якщо вершини ${\displaystyle f(A),\,f(B)\in V_{2}}$ сполучені ребром. Задача перевірки ізоморфізму графів належить до класу задач, для яких поки що невідомо, чи є вони поліноміально вирішуваними, чи ні. Тобто поки що не побудований поліноміальний алгоритм перевірки ізоморфізму графів. Ізоморфізм можна розглядати також як перенумерацію вершин графу, тому будь-яка кількісна характеристика структури графу залишається незмінною. Такі характеристики називаються інваріантами графу[1].

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

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

16. Кожному графу ${\displaystyle G}$ відповідає тіло графу, тобто фігура, яка отримується із скінченного числа відрізків ототожненням декількох кінців у відповідності із графом ${\displaystyle G}$. Одновимірні поліедри є бієктивними з фігурами, які є топологічно еквівалентними тілу деякого графу. Наприклад, фігури ${\displaystyle |G_{1}|}$ та ${\displaystyle |G_{2}|}$ є топологічно еквівалентними лише у випадку, якщо графи ${\displaystyle G_{1}}$ та ${\displaystyle G_{2}}$ є гомеоморфними.

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

${\displaystyle {\text{Початок:}}\{{\text{стрілки}}\}\rightarrow \{{\text{об'єкти}}\}}$

${\displaystyle {\text{Кінець}}:\{{\text{стрілки}}\}\rightarrow \{{\text{об'єкти}}\}}$

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

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

${\displaystyle {\text{початок}}(f)=A,\,\,{\text{кінець}}(f)=B}$

пишуть ${\displaystyle f:A\rightarrow B,}$ або ${\displaystyle f:A\vdash B.}$

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

${\displaystyle \mathrm {Id} _{A}:A\vdash A}$

та бінарна часткова операція на стрілках (композиція), яка, застосована до стрілок ${\displaystyle f:A\vdash B}$ та ${\displaystyle g:B\vdash C,}$ породжує стрілку ${\displaystyle gf:A\vdash C.}$ Спеціальні стрілки відповідають аксіоматичним секвенціям й ${\displaystyle n}$-арним операціям на стрілках із ${\displaystyle n\geq 1,}$ які відповідають правилам виводу. Композиція представляє собою одиничну форму правила перетину

${\displaystyle {\frac {f:A\vdash B\quad g:B\vdash C}{gf:A\vdash C}}.}$

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

${\displaystyle \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))).}$

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

${\displaystyle \forall A\exists f(f:A\vdash A),}$

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

${\displaystyle \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).}$
Звідси по рефлексивності й транзитивності отримується стрілка тотожності й композиція стрілок.

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

${\displaystyle f\,\mathrm {Id} _{A}=f,}$

${\displaystyle \mathrm {Id} _{B}\,f=f,}$

${\displaystyle (hg)f=h(gf)}$

для усіх ${\displaystyle f:A\vdash B,\quad g:B\vdash C,\quad h:C\vdash D.}$

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

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

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

${\displaystyle 1=\sum _{i\in I}1_{i}.}$

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

Якщо ${\displaystyle V}$ є скінченновимірним, то усі ${\displaystyle V_{i}}$ скінченновимірні. У цьому випадку вектор ${\displaystyle \alpha =(\alpha _{})_{i\in I}\in \mathbb {Z} _{\geq 0}^{I}}$ із компонентами ${\displaystyle \alpha _{i}=\mathrm {dim} _{\mathbb {C} }V_{i}}$ називається розмірністю ${\displaystyle \mathbb {C} I}$-модуля. Множина усіх представлень на ${\displaystyle \mathbb {C} I}$ модулі ${\displaystyle V=\bigoplus _{i\in I}V_{i},}$ де ${\displaystyle V_{i}=\mathbb {C} ^{\alpha i},}$ узгоджених із структурою ${\displaystyle \mathbb {C} I}$-модуля, позначається ${\displaystyle \mathrm {Rep} (Q,\alpha ).}$ Щоб задати таке представлення, потрібно узяти довільний набір лінійних операторів з ${\displaystyle \mathbb {C} ^{\alpha _{i}}}$ у ${\displaystyle \mathbb {C} ^{\alpha _{j}}}$ для кожного ребра ${\displaystyle a:i\rightarrow j,}$ таким чином, отримується ${\displaystyle \mathrm {Rep} (Q,\alpha )=\prod _{a:i\rightarrow j}\mathrm {Hom} (\mathbb {C} ^{\alpha _{i}},\mathbb {C} ^{\alpha _{j}})}$ (добуток по усім ${\displaystyle a\in Q}$), де ${\displaystyle \mathrm {Hom} (\mathbb {C} ^{\alpha _{i}},\mathbb {C} ^{\alpha _{j}})}$ — простір лінійних операторів з ${\displaystyle \mathbb {C} ^{\alpha _{i}}}$ у ${\displaystyle \mathbb {C} ^{\alpha _{j}}}$ (комплексних матриць ${\displaystyle \alpha _{i}\times \alpha _{j}}$).

Нехай ${\displaystyle \mathbb {C} E}$ — скінченновимірний векторний простір, вільно породжений множиною ${\displaystyle E,}$ ${\displaystyle \mathbb {C} E=\bigoplus _{a\in Q}\mathbb {C} a.}$ На ньому існує натуральна структура ${\displaystyle \mathbb {C} I}$-бімодуля

${\displaystyle 1_{k}\cdot a=\delta _{jk}a,\quad \quad a\cdot 1_{k}=\delta _{ik}a\quad \quad \forall a:i\rightarrow j.}$

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

${\displaystyle \mathbb {C} Q=\bigoplus _{l=0}^{\infty }(\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,...}$

Лінійний простір ${\displaystyle (\mathbb {C} Q)_{l},\,\,l\geq 0,}$ вільно породжений елементами виду ${\displaystyle a_{l},\cdot \cdot \cdot a_{2}a_{2}1_{i_{0}},}$ де ${\displaystyle a_{k}:i_{k-1}\rightarrow i_{k}}$ є ребрами, які послідово йдуть між вершинами ${\displaystyle i_{0},i_{1},...,i_{l}\in I.}$[3] Алгебра шляхів сагайдака є алгеброю із одиницею

${\displaystyle 1=\sum _{i\in I}e_{i},}$

де ${\displaystyle e_{i}}$ — шлях довжини нуль із початком та кінцем у вершині ${\displaystyle i.}$

Нехай ${\displaystyle k}$ — довільне алгебрично замкнене поле, тоді ${\displaystyle kQ}$ — алгебра шляхів сагайдака, яка може бути розглянута як градуйована алгебра, ${\displaystyle l}$-та компонента якої породжується шляхами довжини ${\displaystyle l.}$ Якщо ${\displaystyle {\mathfrak {I}}}$ — однорідний ідеал алгебри ${\displaystyle kQ}$, то на алгебрі ${\displaystyle A=kQ/{\mathfrak {I}}}$ успадковується структура градуйованої алгебри ${\displaystyle A=\bigoplus _{l\geq 0}A_{l}.}$[4]

Нехай ${\displaystyle A=kQ/{\mathfrak {I}}}$ — алгебра шляхів сагайдака та фроберіусовою формою ${\displaystyle \varepsilon :A\rightarrow k}$, Фробеніусова форма ${\displaystyle \varepsilon }$ називається ${\displaystyle Q_{0}}$-формою, якщо існує ${\displaystyle kQ_{0}}$-бімодуль ${\displaystyle T\leq \mathrm {Ker} (\varepsilon )}$ такий, що ${\displaystyle A=\mathrm {soc} (A)\oplus T.}$ Якщо ${\displaystyle A=kQ/I}$ — самоін'єктивна алгебра шляхів сагайдака, ${\displaystyle \varepsilon :A\rightarrow k}$ — ${\displaystyle Q_{0}}$-форма на ${\displaystyle A,}$ ${\displaystyle {\tilde {v}}=A\rightarrow A}$ — відповідний автоморфізм Накаями[5], ${\displaystyle \varrho :A\rightarrow A\otimes A}$ — фробеніусовий кодобуток, тоді ${\displaystyle {\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},}$ причому

${\displaystyle \varrho ':A\rightarrow \bigoplus _{i\in Q_{0}}P_{\nu _{0}(i),i},}$

де ${\displaystyle \varrho '(a)=\varrho (a)}$ — ін'єктивна оболонка бімодулю ${\displaystyle A.}$

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

${\displaystyle \mathrm {rad} ^{k}(P_{i})=\bigoplus _{l\geq k}e_{i}A_{l}.}$

Якщо алгебра ${\displaystyle A}$ є самоін'єктивною і довжина Леві модулю ${\displaystyle P_{i}}$ дорівнює ${\displaystyle m,}$ то[4]

${\displaystyle \mathrm {soc} ^{k}(P_{i})=\mathrm {rad} ^{m-k}(P_{i}).}$

Родоначальником теорії графів вважається Леонард Ейлер. У 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-повна задача.
• Ізоморфізм графів — чи можна шляхом зміни нумерації вершин одного графу отримати інший.
• Планарність графу — чи можна зобразити граф на площині без перетинань ребер (або з мінімальним числом шарів, що знаходить застосування при трасуванні з'єднань елементів друкованих плат або мікросхем).

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

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

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

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

• Основи ідентифікації та систематизації графів (pdf)

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.