Лекція 7. Основи теорії графів #

Огляд #

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

Тема спирається на дві попередні. Граф ми означимо як пару множин $G=(V,E)$ — отже, уся мова Лекції 1 (множини, підмножини, потужність) працює тут безпосередньо. А ребро $\{u,v\}$ — це, по суті, симетричне відношення на множині вершин, тож властивості відношень із Лекції 2 (рефлексивність, симетричність, транзитивність, класи еквівалентності) знадобляться, коли ми означуватимемо зв’язність. Конкретні алгоритми на графах — пошук найкоротшого шляху (Дейкстра), мінімальне остовне дерево (Прим, Крускал), транспортні мережі — винесено в наступну Лекцію 8; тут ми будуємо лише мову та теорію.

У цьому розділі ми: означуємо граф і орієнтований граф, фіксуємо базову термінологію (суміжність, інцидентність, степінь, петля, кратні ребра); доводимо лему про рукостискання та її наслідок про парність; будуємо два числові подання графа (матриці суміжності й інцидентності); додаємо ваги; формалізуємо рух графом (маршрут, ланцюг, простий ланцюг, цикл) і зв’язність; і, нарешті, розглядаємо три структурні питання — коли два графи однакові (ізоморфізм), коли граф можна намалювати без перетинів (планарність, теорема Понтрягіна–Куратовського) і скільки фарб потрібно для його розфарбування (хроматичне число $\chi(G)$ та хроматичний клас $\chi'(G)$). Завершуємо деревами й лісами.

Про строгість. Майже кожне твердження нижче — лема про рукостискання, наслідок про парність, формула Ейлера, непланарність $K_5$ і $K_{3,3}$, формула $|E|=|V|-1$ для дерев — оформлене як теорема й доведене, а не просто проголошене. Читайте доведення активно: означення — лише абетка, а справжній зміст курсу — навчитися доводити твердження про дискретні структури.

Наскрізь у лекції ми користуємося одним робочим прикладом:

$$G = (V, E), \qquad V = \{a,b,c,d,e\}, \qquad E = \{\, ab,\ ac,\ ad,\ bc,\ ce,\ de \,\}.$$

7.1 Граф: означення та перше знайомство #

Історична довідка (Кенігсберзькі мости). Теорія графів має точну дату народження. 1736 року Леонард Ейлер розв’язав головоломку про пруське місто Кенігсберг (нині Калінінград), розділене річкою Прегель на береги й два острови, з’єднані сімома мостами: чи можна прогулятися так, щоб перейти кожен міст рівно один раз і повернутися додому? Ейлерова ідея — відкинути всю геометрію: кожна ділянка суходолу стає вершиною, кожен міст — ребром. Питання перетворюється на суто комбінаторне. Систематичну відповідь (умову існування такого обходу) ми одержимо в Лекції 8; тут Кенігсберг лише пояснює, чому степені вершин та їхня парність варто вивчати так уважно.

Означення (граф). Граф $G=(V,E)$ складається зі скінченної непорожньої множини $V$, елементи якої називають вершинами (вузлами), і множини $E$, елементи якої називають ребрами. Кожне ребро сполучає невпорядковану пару вершин; ребро між $u$ і $v$ позначають $uv$ або $\{u,v\}$. Оскільки пара невпорядкована, $uv$ і $vu$ — те саме ребро.

Число вершин $|V|$ називають порядком графа, число ребер $|E|$ — його розміром. Увесь граф міститься в парі $(V,E)$; малюнок — лише зручність для людини. Той самий граф має нескінченно багато різних малюнків (це уточнить §7.10, ізоморфізм): важливо чи сполучені дві вершини, а не наскільки довгою чи вигнутою намальовано лінію (доки ми не додамо ваги в §7.7).

Означення (простий граф, мультиграф). Граф простий, якщо він не має ні петель, ні паралельних ребер (обидва поняття означено в §7.2); тоді $E$ — множина двоелементних підмножин $V$. Граф, що допускає паралельні ребра (тобто $E$ — мультимножина), називають мультиграфом. Якщо не вказано інше, під «графом» розуміємо простий граф.

Приклад 7.1. У робочому графі $G$ маємо $|V|=5$ і $|E|=6$. Вершини $a$ і $c$ сполучені ребром ($ac\in E$), а вершини $b$ і $d$ — ні ($bd\notin E$). Граф простий: петель і кратних ребер немає.

7.2 Суміжність, інцидентність та інші базові поняття #

Зафіксуймо граф $G=(V,E)$.

• Суміжність вершин. Дві вершини $u,v$ суміжні (є сусідами), якщо $uv\in E$. Множину сусідів вершини $v$ називають її околом $N(v)$.
• Інцидентність. Вершина $v$ та ребро $e$ інцидентні, якщо $v$ — один із двох кінців ребра $e$. Два ребра суміжні, якщо мають спільний кінець.
• Петля. Петля — це ребро, що сполучає вершину саму з собою (ребро $vv$). У простих графах петель немає.
• Паралельні (кратні) ребра. Два або більше ребер, що сполучають ту саму пару вершин, називають паралельними (кратними). Прості графи їх не мають, мультиграфи можуть.
• Ізольована вершина. Вершина, з якою не інцидентне жодне ребро (сусідів немає).

Приклад 7.2. На рисунку вгорі вершина $1$ має петлю; вершини $1$ і $2$ сполучені двома паралельними ребрами; вершини $2$ і $3$ суміжні (сполучені одним ребром); вершина $4$ — ізольована. Такий об’єкт уже не простий граф, а мультиграф.

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

7.3 Степінь вершини. Лема про рукостискання #

Найважливіша локальна характеристика вершини — скільки ребер із неї виходить.

Означення (степінь вершини). Степінь $\deg(v)$ вершини $v$ — це кількість інцидентних їй ребер, причому петля рахується двічі. Вершину степеня $0$ називають ізольованою, а вершину степеня $1$ — висячою (листком). У простому графі $\deg(v)=|N(v)|$.

Позначають $\Delta(G)=\max_v\deg(v)$ (максимальний степінь) і $\delta(G)=\min_v\deg(v)$ (мінімальний). Граф $r$-регулярний, якщо всі вершини мають однаковий степінь $r$. Список степенів усіх вершин, зазвичай записаний у незростаючому порядку, називають степеневою послідовністю.

Приклад 7.3 (степені в $G$). Порахуймо степені робочого графа:

Степенева послідовність — $(3,3,2,2,2)$; її сума дорівнює $3+3+2+2+2=12=2\cdot 6=2|E|$. Це не випадковість, а вияв фундаментальної теореми.

Теорема 7.4 (лема про рукостискання). У будь-якому графі (простому чи мультиграфі)

$$\sum_{v\in V}\deg(v)=2\,|E|.$$

Доведення (подвійна лічба). Порахуймо двома способами множину інцидентностей

$$I=\{\,(v,e): v\in V,\ e\in E,\ v \text{ інцидентна } e\,\}.$$

Лічба за вершинами. Згрупуймо пари $(v,e)$ за першою координатою. Фіксована вершина $v$ входить рівно у $\deg(v)$ пар — по одній на кожне інцидентне ребро (петля дає дві пари, відповідно до угоди «рахується двічі»). Отже, $|I|=\sum_{v\in V}\deg(v)$. Лічба за ребрами. Згрупуймо пари за другою координатою. Фіксоване ребро $e$ має рівно два кінці, тож входить рівно у дві пари. Отже, $|I|=\sum_{e\in E}2=2|E|$. Прирівнявши два вирази для однієї величини $|I|$, дістаємо $\sum_v\deg(v)=2|E|$. $\blacksquare$

Формулюють це й «за вечіркою»: сумарна кількість потиснутих рук удвічі більша за кількість рукостискань, бо кожне рукостискання задіює дві руки. Найкорисніший наслідок — твердження про парність.

Наслідок 7.5 (про вершини непарного степеня). У будь-якому графі кількість вершин непарного степеня парна.

Доведення. Розіб’ємо вершини за парністю степеня на $V_{\text{н}}=\{v:\deg(v)\text{ непарний}\}$ і $V_{\text{п}}=\{v:\deg(v)\text{ парний}\}$. За Теоремою 7.4

$$\sum_{v\in V_{\text{н}}}\deg(v)+\sum_{v\in V_{\text{п}}}\deg(v)=2|E|.$$

Права частина парна; друга сума ліворуч — сума парних чисел, отже парна. Тоді й перша сума $\sum_{v\in V_{\text{н}}}\deg(v)$ парна. Але це сума $|V_{\text{н}}|$ непарних чисел, а за модулем $2$ кожне непарне $\equiv 1$, тож $\sum_{v\in V_{\text{н}}}\deg(v)\equiv |V_{\text{н}}|\pmod 2$. Отже, $|V_{\text{н}}|$ парне. $\blacksquare$

Приклад 7.6. Чи можуть $7$ осіб потиснути руки так, щоб кожна привіталася рівно з трьома іншими? Ні: це був би граф із $7$ вершинами степеня $3$, тобто $7$ вершин непарного степеня — непарна кількість, що суперечить Наслідку 7.5. (Рівнозначно: сума степенів $7\cdot 3=21$ непарна, а мусить дорівнювати $2|E|$.)

Ще один короткий, але корисний факт спирається на принцип Діріхле.

Твердження 7.7. У кожному простому графі з $n\ge 2$ вершинами знайдуться дві різні вершини однакового степеня.

Доведення. У простому графі степінь кожної вершини лежить у множині $\{0,1,\dots,n-1\}$ ($n$ можливих значень). Припустимо супротивне: усі $n$ степенів різні; тоді кожне значення $0,1,\dots,n-1$ трапляється рівно раз. Зокрема, є вершина степеня $0$ (ні з ким не суміжна) і вершина степеня $n-1$ (суміжна з усіма $n-1$ іншими, отже й з першою) — суперечність. Тож усі $n$ значень одночасно неможливі: різних степенів щонайбільше $n-1$ на $n$ вершин, і за принципом Діріхле два степені збігаються. $\blacksquare$

Особливі сімейства графів #

Кілька графів трапляються так часто, що мають власні назви й формули для розміру. Ми покликатимемося на них у §7.11 (планарність) та §7.12 (розфарбування).

• Порожній граф $N_n$ — $n$ вершин і жодного ребра; кожна вершина ізольована, граф $0$-регулярний.
• Простий ланцюг $P_n$ — $n$ вершин у рядок із ребрами $v_1v_2,\dots,v_{n-1}v_n$; має $n-1$ ребро й дві висячі вершини (кінці).
• Цикл $C_n$ ($n\ge 3$) — $n$ вершин по колу; має $n$ ребер і $2$-регулярний.
• Повний граф $K_n$ — простий граф, у якому кожна пара різних вершин сполучена ребром; він $(n-1)$-регулярний.
• Повний дводольний граф $K_{m,n}$ — вершини поділено на дві частини розмірів $m$ і $n$; кожну вершину однієї частини сполучено з кожною вершиною другої, а всередині частин ребер немає. Граф, вершини якого так розбиваються, називають дводольним.

Теорема 7.7а (розміри повних графів).

$$|E(K_n)|=\binom{n}{2}=\frac{n(n-1)}{2}, \qquad |E(K_{m,n})|=mn.$$

Доведення. У $K_n$ кожна з $n$ вершин має степінь $n-1$, тож за лемою про рукостискання $2|E|=\sum_v\deg(v)=n(n-1)$, звідки $|E|=\frac{n(n-1)}{2}$. У $K_{m,n}$ кожна з $m$ вершин однієї частини сполучена рівно з $n$ вершинами другої, і жодне ребро не лічиться двічі (кожне має рівно один кінець у кожній частині), тож $|E|=mn$. $\blacksquare$

Приклад 7.7б. $K_3$ (трикутник) має $3$ ребра, $K_4$ — $6$, $K_5$ — $10$, $K_6$ — $15$. Дводольний $K_{3,3}$ має $3\cdot 3=9$ ребер. Ці значення знадобляться, коли ми доводитимемо непланарність $K_5$ і $K_{3,3}$ (§7.11).

7.4 Матриця суміжності #

Графи зручно малювати, але комп’ютерові потрібне числове подання. Найпоширеніше — матриця суміжності.

Означення (матриця суміжності). Матрицею суміжності графа на вершинах $v_1,\dots,v_n$ називають $n\times n$ матрицю $A=[a_{ij}]$, де $a_{ij}$ — кількість ребер між $v_i$ і $v_j$. Для простого графа кожен запис — $0$ або $1$.

Ключові властивості для неорієнтованого простого графа: матриця симетрична ($a_{ij}=a_{ji}$); діагональ нульова (немає петель); а сума $i$-го рядка дорівнює $\deg(v_i)$.

Приклад 7.8. Упорядкувавши вершини $a,b,c,d,e$, матриця суміжності робочого графа $G$ така:

Вона симетрична, діагональ нульова, а суми рядків $3,2,3,2,2$ відтворюють знайдену раніше степеневу послідовність.

Зауваження (степені матриці рахують маршрути). Найкорисніша алгебраїчна властивість матриці суміжності: запис $(i,j)$ у степені $A^{k}$ дорівнює кількості маршрутів довжини $k$ з $v_i$ у $v_j$ (доводиться індукцією за $k$). Зокрема діагональ $A^{2}$ дає степені вершин. Ми користуватимемося цим побіжно; докладніше — у контексті алгоритмів Лекції 8.

7.5 Орієнтовані графи #

Досі ребро було симетричним зв’язком. Часто ж зв’язок напрямлений: одностороння вулиця, гіперпосилання зі сторінки $u$ на сторінку $v$, відношення «передує» між задачами.

Означення (орієнтований граф). Орієнтований граф (орграф) $D=(V,A)$ складається з множини вершин $V$ і множини дуг $A$, де кожна дуга — це впорядкована пара $(u,v)$, намальована стрілкою від початку $u$ до кінця $v$. Тепер $(u,v)$ і $(v,u)$ — різні дуги: напрям має значення.

У орграфі степінь розщеплюється на два. Напівстепінь виходу $\deg^{+}(v)$ — кількість дуг із початком у $v$ (стрілки, що виходять); напівстепінь входу $\deg^{-}(v)$ — кількість дуг із кінцем у $v$ (стрілки, що входять).

Приклад 7.9. Зорієнтуймо ребра робочого графа так: $a\to b$, $a\to c$, $a\to d$, $b\to c$, $c\to e$, $d\to e$. Напівстепені виходу й входу зведено в таблицю:

Твердження 7.10 (орієнтована лема про рукостискання). У будь-якому орграфі $D=(V,A)$

$$\sum_{v\in V}\deg^{+}(v)=\sum_{v\in V}\deg^{-}(v)=|A|.$$

Доведення. Кожна дуга $(u,w)$ має рівно один початок $u$ і рівно один кінець $w$. Сума напівстепенів виходу лічить кожну дугу один раз — у її початку; сума напівстепенів входу лічить кожну дугу один раз — у її кінці. Обидві суми тому дорівнюють числу дуг $|A|$. $\blacksquare$

У прикладі 7.9: $\sum\deg^{+}=3+1+1+1+0=6$ і $\sum\deg^{-}=0+1+2+1+2=6=|A|$.

Матриця суміжності орграфа. Означують так само: $a_{ij}=1$, якщо є дуга $(v_i,v_j)$. Тепер матриця не обов’язково симетрична; сума $i$-го рядка дає $\deg^{+}(v_i)$, а сума $j$-го стовпця — $\deg^{-}(v_j)$.

Суми рядків $3,1,1,1,0$ — це напівстепені виходу, суми стовпців $0,1,2,1,2$ — напівстепені входу, як і має бути.

7.6 Матриця інцидентності #

Друге стандартне подання явно фіксує зв’язок «вершина — ребро».

Означення (матриця інцидентності). Матриця інцидентності $M=[m_{ij}]$ має один рядок на вершину й один стовпець на ребро: $m_{ij}=1$, якщо вершина $v_i$ — кінець ребра $e_j$, і $m_{ij}=0$ інакше.

У простому графі кожен стовпець містить рівно дві одиниці (ребро має два кінці), а сума $i$-го рядка знову дорівнює $\deg(v_i)$. Петля — виняток: у її стовпці стоїть одна двійка.

Приклад 7.11. Занумеруймо ребра $e_1=ab,\ e_2=ac,\ e_3=ad,\ e_4=bc,\ e_5=ce,\ e_6=de$. Матриця інцидентності графа $G$:

Кожен стовпець дає в сумі $2$; додавши всі записи, дістаємо $2|E|=12=\sum_v\deg(v)$ — та сама подвійна лічба, тепер за стовпцями. Суми рядків $3,2,3,2,2$ — знову степені.

Зауваження (яке подання обрати). Матриця суміжності компактна ($n\times n$) і за $O(1)$ відповідає на питання «чи суміжні $u,v$?»; матриця інцидентності ($n\times|E|$) явно зберігає структуру «вершина — ребро» й легко узагальнюється на мультиграфи та (із записами $\pm 1$) на орграфи. На практиці великі розріджені графи зберігають списками суміжності — головним поданням для алгоритмів Лекції 8.

7.7 Зважені графи #

Означення (зважений граф). Зважений граф — це граф разом із ваговою функцією $w\colon E\to\mathbb{R}$, що приписує кожному ребру число $w(e)$ — вартість, довжину, пропускну здатність чи час. Вага маршруту — сума ваг його ребер. (Орграфи зважують так само.)

Ваги роблять осмисленими питання на кшталт «найкоротший маршрут» чи «найдешевша мережа». У комп’ютері ваги зберігають, замінивши одиниці матриці суміжності на $w(v_iv_j)$, а «немає ребра» позначають нескінченністю $\infty$.

Приклад 7.12. Нехай на робочому графі ваги (наприклад, довжини кабелю в метрах) такі: $w(ab)=7,\ w(ac)=4,\ w(ad)=2,\ w(bc)=1,\ w(ce)=5,\ w(de)=3$. Маршрут $a\to c\to e$ має вагу $4+5=9$, тоді як $a\to b\to c\to e$ — вагу $7+1+5=13$. Отже, мінімізуємо вагу, а не кількість ребер: це розрізняє «найменше переходів» (незважений випадок) і «найкоротша відстань» (зважений, алгоритм Дейкстри Лекції 8).

7.8 Маршрути, ланцюги та цикли #

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

Означення (маршрут). Маршрут (шлях) довжини $k$ — це послідовність вершин і ребер, що чергуються,

$$v_0,\ e_1,\ v_1,\ e_2,\ v_2,\ \dots,\ e_k,\ v_k,$$

де кожне ребро $e_i$ сполучає $v_{i-1}$ і $v_i$. Його довжина — кількість ребер $k$. Маршрут замкнений, якщо його кінці збігаються ($v_0=v_k$), і незамкнений інакше. У простому графі маршрут визначається списком вершин, тож його записують $v_0\text{–}v_1\text{–}\cdots\text{–}v_k$.

Означення (ланцюг, простий ланцюг, цикл).

• Ланцюг — маршрут, у якому всі ребра різні (вершини можуть повторюватися).
• Простий ланцюг — маршрут, у якому всі вершини різні (а отже, і всі ребра).
• Цикл — замкнений ланцюг. Якщо при цьому не повторюються й внутрішні вершини, його називають простим циклом. Найкоротший простий цикл у простому графі має довжину $3$ (трикутник).

Ієрархія вкладень: кожен простий ланцюг є ланцюгом, а кожен ланцюг — маршрутом; кожен простий цикл є циклом, а кожен цикл — замкненим маршрутом. Обернені включення хибні.

Приклад 7.13 (зі слайдів, на графі $G$).

• $a\text{–}c\text{–}b\text{–}a\text{–}d$ використовує ребра $ac,cb,ba,ad$ — усі різні, тож це ланцюг; але вершина $a$ повторюється, тому це не простий ланцюг. Кінці $a$ і $d$ різні — незамкнений, довжина $4$.
• $a\text{–}c\text{–}e\text{–}d\text{–}a$ використовує ребра $ac,ce,ed,da$ — усі різні й повертається в $a$, отже цикл; внутрішні вершини не повторюються — це простий цикл довжини $4$.
• $a\text{–}b\text{–}c$ не повторює жодної вершини — простий ланцюг (незамкнений, довжина $2$).

Наступна теорема — робочий інструмент усіх міркувань про зв’язність: якщо вершини з’єднано хоч якимось маршрутом, то їх з’єднано й простим ланцюгом.

Теорема 7.14 (маршрут $\Rightarrow$ простий ланцюг). Якщо в графі є маршрут із $u$ у $v$, то є й простий ланцюг із $u$ у $v$.

Доведення. Множина маршрутів із $u$ у $v$ непорожня за умовою, а довжини належать $\{0,1,2,\dots\}$, тож за принципом найменшого числа виберемо маршрут $W:\ u=w_0,w_1,\dots,w_k=v$ найменшої довжини $k$. Стверджуємо, що $W$ не повторює вершин (отже, є простим ланцюгом). Припустимо супротивне: $w_i=w_j$ для деяких $i<j$. Тоді $W':\ w_0,\dots,w_i,w_{j+1},\dots,w_k$ — теж маршрут із $u$ у $v$ (склейка законна, бо $w_i=w_j$ суміжна з $w_{j+1}$), але його довжина $k-(j-i)<k$ суперечить мінімальності $W$. Отже, вершини не повторюються. $\blacksquare$

7.9 Зв’язність та компоненти зв’язності #

Означення (зв’язність). Граф зв’язний, якщо між кожною парою вершин існує маршрут (рівнозначно, за Теоремою 7.14, простий ланцюг). Інакше граф незв’язний і розпадається на максимальні зв’язні частини — компоненти зв’язності.

Щоб уточнити «частини», згадаймо відношення еквівалентності з Лекції 2.

Твердження 7.15 (компоненти як класи еквівалентності). Означимо на $V$ відношення: $u\sim v$, якщо існує маршрут з $u$ у $v$. Тоді $\sim$ — відношення еквівалентності, а його класи — це вершинні множини компонент зв’язності.

Доведення. Перевіримо три аксіоми. Рефлексивність: маршрут довжини $0$ сполучає $u$ із собою, тож $u\sim u$. Симетричність: обернувши маршрут $u$–$v$, дістаємо маршрут $v$–$u$ (ребра неорієнтовані), тож $u\sim v\Rightarrow v\sim u$. Транзитивність: приєднавши маршрут $v$–$w$ до маршруту $u$–$v$, дістаємо маршрут $u$–$w$, тож $u\sim v$ і $v\sim w\Rightarrow u\sim w$. Отже, $\sim$ розбиває $V$ на класи; кожен клас зв’язний і максимальний — це й є компонента. $\blacksquare$

Робочий граф $G$ зв’язний (наприклад, $b$ досягає $e$ через $b\text{–}c\text{–}e$). Якби ми додали ізольовану вершину $f$, граф став би незв’язним із двома компонентами $\{a,b,c,d,e\}$ і $\{f\}$.

Зауваження (мости та орграфи). Ребро, вилучення якого збільшує кількість компонент, називають мостом. У $G$ ребро $ad$ не міст (є обхідний цикл $a\text{–}c\text{–}e\text{–}d\text{–}a$), тоді як у простому ланцюзі кожне ребро — міст. Для орграфів розрізняють сильну зв’язність (є напрямлений шлях і з $u$ у $v$, і з $v$ у $u$) та слабку (зв’язний неорієнтований «кістяк»). Граф посилань у вебі зазвичай лише слабко зв’язний.

7.10 Ізоморфізм графів #

Два малюнки можуть виглядати геть по-різному й водночас зображати той самий граф. Уточнимо «однакова структура».

Означення (ізоморфізм). Графи $G_1=(V_1,E_1)$ і $G_2=(V_2,E_2)$ ізоморфні (пишуть $G_1\cong G_2$), якщо існує бієкція $f\colon V_1\to V_2$, що зберігає суміжність в обидва боки:

$$uv\in E_1\iff f(u)f(v)\in E_2\quad\text{для всіх } u,v\in V_1.$$

Таку $f$ називають ізоморфізмом: вона перейменовує вершини $G_1$, перетворюючи його на $G_2$ без додавання чи вилучення ребер.

Ізоморфізм — відношення еквівалентності на графах, тож він сортує всі графи на класи ізоморфності: «той самий» цикл $C_5$ означає один такий клас.

Як довести ізоморфність: пред’явити явну бієкцію $f$ і перевірити, що кожне ребро $G_1$ переходить у ребро $G_2$ (за рівних $|V_1|=|V_2|$ і $|E_1|=|E_2|$ цього досить).

Як довести неізоморфність: знайти інваріант — величину чи властивість, яку зберігає кожен ізоморфізм, — на якому графи різняться. Досить одного відмінного інваріанта.

Твердження 7.16 (степенева послідовність — інваріант). Якщо $f\colon G_1\to G_2$ — ізоморфізм, то $\deg_{G_1}(v)=\deg_{G_2}(f(v))$ для кожної вершини $v$; отже, $G_1$ і $G_2$ мають однакову степеневу послідовність.

Доведення. Відображення $f$ звужується до бієкції між околами $N(v)$ і $N(f(v))$: якщо $u\in N(v)$, то $uv\in E_1$, звідки $f(u)f(v)\in E_2$, тобто $f(u)\in N(f(v))$; обернене — так само, бо $f$ бієкція. Отже, $|N(v)|=|N(f(v))|$, тобто $\deg(v)=\deg(f(v))$. $\blacksquare$

Інші зручні інваріанти: порядок $|V|$, розмір $|E|$, кількість компонент, довжина найкоротшого циклу, кількість трикутників, дводольність.

Приклад 7.17 (ізоморфні — п’ятикутник і п’ятикутна зірка). Намалюймо $C_5$ раз як правильний п’ятикутник із ребрами $\{12,23,34,45,51\}$, а раз як п’ятикутну зірку (пентаграму) з ребрами $\{13,35,52,24,41\}$. Бієкція

переводить кожне ребро п’ятикутника в ребро зірки ($\{1,2\}\!\to\!\{1,3\}$, $\{2,3\}\!\to\!\{3,5\}$, $\dots$), тож обидва — це $C_5$.

Типова помилка (однакова степенева послідовність $\ne$ ізоморфізм). Інваріанти необхідні, але не достатні. Розгляньмо два $2$-регулярні графи на $6$ вершинах: цикл $C_6$ і незв’язне об’єднання двох трикутників $C_3\cup C_3$. Обидва мають $6$ вершин, $6$ ребер і степеневу послідовність $(2,2,2,2,2,2)$ — усі «локальні» інваріанти збігаються. Проте $C_6$ зв’язний (одна компонента), а $C_3\cup C_3$ — ні (дві), тож вони не ізоморфні. Тому «однакова степенева послідовність» ніколи не доводить ізоморфізму.

7.11 Планарність. Формула Ейлера. Теорема Понтрягіна–Куратовського #

Означення (планарний / плоский граф). Граф планарний, якщо його можна намалювати на площині так, щоб жодні два ребра не перетиналися (ребра сходяться лише у спільних кінцях). Таке зображення без перетинів називають плоским графом. Плоский граф ділить площину на грані (максимальні зв’язні області), зокрема одну необмежену — зовнішню.

Теорема 7.18 (формула Ейлера). Для будь-якого зв’язного плоского графа з $V$ вершинами, $E$ ребрами та $F$ гранями

$$V-E+F=2.$$

Доведення (індукція за $E$, коротко). База $E=0$: зв’язний граф без ребер — це одна вершина, $V=1$, єдина грань $F=1$, і $1-0+1=2$. Крок. Нехай $E\ge 1$. Якщо граф має цикл, вилучимо одне ребро циклу: дві сусідні грані зливаються в одну, тож $F$ і $E$ зменшуються на $1$, а $V$ і зв’язність не змінюються. Якщо ж циклів немає (граф — дерево), у ньому є висяча вершина; вилучимо її разом з інцидентним ребром: $V$ і $E$ зменшуються на $1$, а $F$ не змінюється (це ребро-міст межує з однією гранню з обох боків). В обох випадках величина $V-E+F$ не змінюється, тож за припущенням індукції дорівнює $2$. $\blacksquare$

Приклад 7.19. Граф $K_4$ планарний: намалювавши його без перетинів (трикутник із центральною вершиною, сполученою з усіма трьома), маємо $V=4$, $E=6$ і $F=4$ (три внутрішні трикутні області та зовнішня), і справді $4-6+4=2$.

Справжня сила формули Ейлера — у межах на кількість ребер, які вона нав’язує планарним графам і які дають швидкий тест непланарності.

Наслідок 7.20 (реброва межа). У простому зв’язному планарному графі з $V\ge 3$

$$E\le 3V-6.$$

Доведення. Візьмімо плоске зображення з $F$ гранями. У простому графі з $V\ge 3$ кожна грань обмежена щонайменше трьома ребрами (грань степеня $1$ вимагала б петлі, степеня $2$ — кратних ребер). Сумуючи степені всіх граней, лічимо кожне ребро двічі (воно межує з двома гранями), тож $\sum_F\deg(F)=2E$. Оскільки кожен із $F$ доданків $\ge 3$, маємо $3F\le 2E$, тобто $F\le \tfrac{2E}{3}$. Підставимо $F=E-V+2$ з формули Ейлера: $E-V+2\le\tfrac{2E}{3}$, звідки $E\le 3V-6$. $\blacksquare$

Наслідок 7.21 ($K_5$ непланарний). Повний граф $K_5$ простий і зв’язний, має $V=5$ і $E=\binom{5}{2}=10$. Якби він був планарним, Наслідок 7.20 давав би $10\le 3\cdot 5-6=9$ — хибно. Отже, $K_5$ непланарний. $\blacksquare$

Межа $E\le 3V-6$ не розв’язує випадку $K_{3,3}$ ($V=6$, $E=9$, $3V-6=12\ge 9$). Потрібна гостріша межа, що враховує відсутність трикутників.

Наслідок 7.22 (межа для графів без трикутників, $K_{3,3}$ непланарний). Якщо простий зв’язний планарний граф із $V\ge 3$ не має трикутників, то кожна грань обмежена $\ge 4$ ребрами, звідки $4F\le 2E$ і $E\le 2V-4$. Граф $K_{3,3}$ дводольний, тож без трикутників; при $V=6$, $E=9$ маємо $9\le 2\cdot 6-4=8$ — хибно. Отже, $K_{3,3}$ непланарний. $\blacksquare$

Ці два графи — це відомі задачі: $K_{3,3}$ — «три колодязі» (з’єднати три будинки з газом, водою та електрикою без перетину труб — неможливо), а $K_5$ — «п’ять взаємно сполучених точок». Куратовський (і незалежно Понтрягін) довели, що вони — єдині істотні перешкоди планарності.

Теорема 7.23 (Понтрягіна–Куратовського). Граф планарний тоді й лише тоді, коли він не містить підграфа, який є підрозбиттям $K_5$ або $K_{3,3}$.

Тут підрозбиття графа одержують, багаторазово замінюючи ребро на простий ланцюг через нові вершини степеня $2$ (тобто «розставляючи зайві точки» вздовж ребра). Підрозбиття не змінює можливості намалювати граф без перетинів, тож прихований $K_5$ чи $K_{3,3}$ — навіть «розтягнутий» додатковими вершинами — унеможливлює планарність, а його відсутність її гарантує.

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

7.12 Розфарбування графів #

Означення (правильне розфарбування вершин, хроматичне число). Правильне розфарбування вершин приписує кожній вершині колір так, щоб суміжні вершини мали різні кольори. Хроматичне число $\chi(G)$ — найменша кількість кольорів у правильному розфарбуванні.

Застосування: складання розкладів (кольори — часові слоти, ребра — конфлікти, тож правильне розфарбування — розклад без накладок), призначення частот, розподіл регістрів у компіляторі.

Межі. Якщо граф містить кліку з $k$ вершин (копію $K_k$ — $k$ попарно суміжних вершин), то їм потрібно $k$ різних кольорів, тож $\chi(G)\ge\omega(G)$, де $\omega(G)$ — найбільший розмір кліки. З іншого боку, завжди $\chi(G)\le\Delta(G)+1$ (розфарбовуючи вершини по черзі, для кожної маємо не більш ніж $\Delta$ уже розфарбованих сусідів, тож один із $\Delta+1$ кольорів вільний).

Базові значення. $\chi(K_n)=n$; для парного циклу $\chi(C_{2k})=2$, для непарного $\chi(C_{2k+1})=3$. Загалом $\chi(G)\le 2$ тоді й лише тоді, коли граф дводольний, тобто не має циклів непарної довжини.

Приклад 7.24 (розфарбування $G$). Робочий граф містить трикутник $a\text{–}b\text{–}c$ — кліку розміру $3$, тож $\chi(G)\ge 3$. Трьох кольорів досить: $a=1,\ b=2,\ c=3$, далі $d=2$ (єдиний розфарбований сусід $a=1$) і $e=1$ (сусіди $c=3$ і $d=2$). Кожне ребро тепер сполучає вершини різних кольорів, отже, $\chi(G)=3$.

Кольорувати можна не лише вершини, а й ребра.

Означення (реберне розфарбування, хроматичний клас). Правильне реберне розфарбування приписує кожному ребру колір так, щоб ребра зі спільною вершиною мали різні кольори. Найменшу кількість кольорів називають хроматичним класом (хроматичним індексом) $\chi'(G)$.

Оскільки $\Delta(G)$ ребер, інцидентних вершині максимального степеня, попарно ділять цю вершину, усі вони мусять мати різні кольори, тож $\chi'(G)\ge\Delta(G)$. Ба більше, за теоремою Візинга для простого графа завжди $\chi'(G)\in\{\Delta(G),\ \Delta(G)+1\}$.

Зауваження (хроматичне число проти хроматичного класу). Це різні задачі, і їхні значення можуть не збігатися. Класичний приклад — граф Петерсена ($10$ вершин, $3$-регулярний): у нього $\chi=3$, але $\chi'=4$ (він досягає верхньої межі Візинга $\Delta+1$). Саме таку пару «хроматичне число $3$, хроматичний клас $4$» наведено й на слайдах.

Історична довідка (задача чотирьох фарб). Кожен планарний граф $4$-розфарбовний — славнозвісна теорема про чотири фарби: будь-яку політичну карту можна розфарбувати чотирма кольорами так, щоб сусідні країни різнилися (граф суміжності областей карти планарний). Гіпотезу висловлено 1852 року, а доведено Аппелем і Гакеном 1976-го — це була перша велика теорема, доведена зі суттєвою допомогою комп’ютера.

7.13 Дерева й ліс #

Найважливіша спеціальна структура — дерево: зв’язний граф без циклів. Дерева організують файлові системи (коренева тека, теки, файли й єдиний шлях до кожного файла), дерева розбору виразів, структури пошуку та префіксні коди.

Означення (дерево, ліс). Дерево — це зв’язний неорієнтований граф без циклів (зв’язний ациклічний граф). Ліс — неорієнтований граф без циклів (не обов’язково зв’язний); кожна його компонента є деревом.

Ключова кількісна властивість дерева — жорсткий зв’язок між числами вершин і ребер. Спершу — допоміжний факт про висячі вершини.

Лема 7.25 (про дві висячі вершини). Кожне дерево з $n\ge 2$ вершинами має щонайменше дві висячі вершини (листки).

Доведення. Серед усіх простих ланцюгів дерева виберемо найдовший $P\colon v_0,v_1,\dots,v_k$ (він існує, бо граф скінченний); оскільки дерево має ребро, $k\ge 1$ і $v_0\ne v_k$. Покажемо, що $v_0$ — листок. Якби $v_0$ мала сусіда $w\ne v_1$, то: або $w\notin P$ — і тоді $w,v_0,\dots,v_k$ довший ланцюг, що суперечить максимальності; або $w=v_i$ для деякого $i\ge 2$ — і тоді $v_0,\dots,v_i,v_0$ цикл, що суперечить ациклічності. Отже, $\deg(v_0)=1$. Так само $v_k$ — листок. $\blacksquare$

Теорема 7.26 (кількість ребер дерева). Дерево з $n$ вершинами має рівно $n-1$ ребро: $|E|=|V|-1$.

Доведення (індукція за $n$). База $n=1$: єдина вершина, $0=1-1$ ребро. Крок. Нехай $n\ge 2$ і твердження справджується для всіх дерев із меншою кількістю вершин. За Лемою 7.25 у дереві $T$ є листок $v$ з єдиним сусідом $u$. Вилучимо $v$ разом із ребром $uv$; одержаний граф $T'$ лишається зв’язним (через вершину степеня $1$ жоден простий ланцюг між іншими вершинами не проходив) і ациклічним, тобто є деревом на $n-1$ вершинах. За припущенням індукції $T'$ має $(n-1)-1=n-2$ ребра, а повернувши $v$ та ребро $uv$, додаємо рівно одне ребро — тож $T$ має $n-1$ ребро. $\blacksquare$

Приклад 7.27. Дерево на рисунку має $|V|=7$ вершин і $|E|=6=|V|-1$ ребер; листки — $d,e,f,g$ (степінь $1$), внутрішні вершини — $a,b,c$. Степені такі: $\deg a=2,\ \deg b=3,\ \deg c=3$, а $\deg d=\deg e=\deg f=\deg g=1$; їхня сума $2+3+3+1+1+1+1=12=2\cdot 6=2|E|$, як і має бути за лемою про рукостискання.

Для лісу формула узагальнюється, і саме кількість компонент «псує» рівність.

Твердження 7.28 (ребра лісу). Ліс із $n$ вершинами та $c$ компонентами має рівно $n-c$ ребер.

Доведення. Нехай компоненти — дерева на $n_1,\dots,n_c$ вершинах, $\sum_i n_i=n$. За Теоремою 7.26 компонента $i$ має $n_i-1$ ребро, тож усього $\sum_{i=1}^{c}(n_i-1)=n-c$. $\blacksquare$

Дерево — окремий випадок $c=1$, що повертає $|E|=n-1$. Обернувши рівність, $c=n-|E|$: у лісі кількість компонент дорівнює вершини мінус ребра — крихітний лічильний рушій, на якому тримається структура «система неперетинних множин» в алгоритмі Крускала.

Зауваження (остовне дерево). Для зв’язного графа остовне дерево — це підграф, який є деревом і містить усі вершини (отже, $|V|-1$ ребро). Кожен зв’язний граф має остовне дерево, а для зваженого графа шукають мінімальне остовне дерево — найдешевший «кістяк» мережі. Алгоритми Прима й Крускала для його побудови — тема Лекції 8.

7.14 Ейлерові та гамільтонові цикли. Задача комівояжера #

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

Ейлерові ланцюги та цикли #

Перше питання — це рівно головоломка про кенігсберзькі мости з §7.1.

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

Ейлер помітив, що можливість обходу залежить лише від парності степенів. Уявімо, що ланцюг проходить графом; щоразу, входячи у проміжну вершину одним ребром, ми мусимо вийти з неї іншим, ще не використаним ребром. Тому ребра при кожній проміжній вершині розбиваються на пари «увійшов–вийшов», а її степінь має бути парним. Це спостереження і є ядром критерію.

Теорема 7.29 (критерій Ейлера). Нехай $G$ — зв’язний граф без ізольованих вершин. Тоді:

• $G$ має ейлерів цикл тоді й лише тоді, коли всі вершини мають парний степінь;
• $G$ має ейлерів ланцюг, який не є циклом, тоді й лише тоді, коли рівно дві вершини мають непарний степінь (саме вони й будуть кінцями ланцюга).

Доведення (необхідність). Нехай у $G$ є ейлерів цикл $C$. Пройдімо ним і для кожної вершини $v$ полічимо інцидентні їй ребра, якими скористалися. Кожен прохід «крізь» $v$ задіює рівно два такі ребра — одне на вхід, одне на вихід, — і всі вони різні, бо ланцюг ребер не повторює. Оскільки цикл замкнений, і в початковій вершині є вихід та відповідний йому вхід. Тому ребра при $v$ повністю розбиваються на пари, а отже, $\deg(v)$ парний для кожної вершини. Для ейлерового ланцюга, що не є циклом, той самий підрахунок дає пари скрізь, окрім двох кінців: у початковій вершині лишається непарований вихід, у кінцевій — непарований вхід, тож рівно ці дві вершини мають непарний степінь. Достатність (виконання умови про парність гарантує існування обходу) доводять індукцією за кількістю ребер або алгоритмом Флері, що рухається лише ребрами, які не є мостами; приймаємо її без подробиць. $\blacksquare$

Навпаки, «додатний» приклад — граф, усі степені якого парні. На рисунку нижче центральна вершина $o$ має степінь $4$, а решта — степінь $2$; за Теоремою 7.29 граф ейлерів, і обхід $o\text{–}a\text{–}b\text{–}o\text{–}c\text{–}d\text{–}o$ (номери на ребрах указують порядок проходження) повертається у старт, скориставшись кожним ребром рівно раз.

Приклад 7.30 (мости й робочий граф). У кенігсберзькому мультиграфі степені вершин дорівнюють $5,3,3,3$ — чотири вершини непарного степеня. За Теоремою 7.29 немає ні ейлерового циклу, ні навіть ейлерового ланцюга: обійти всі сім мостів рівно по разу неможливо — така відповідь Ейлера 1736 року. Натомість робочий граф $G$ має степеневу послідовність $(3,2,3,2,2)$, тож непарний степінь мають рівно дві вершини — $a$ і $c$. Отже, ейлерів ланцюг існує; наприклад,

$$a\text{–}b\text{–}c\text{–}e\text{–}d\text{–}a\text{–}c$$

проходить усі шість ребер по разу й веде від $a$ до $c$. Ейлерового циклу в $G$ немає.

Гамільтонові шляхи та цикли #

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

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

Теорема 7.31 (достатня умова Дірака). Якщо в простому графі з $n\ge 3$ вершинами кожна вершина має степінь $\deg v\ge n/2$, то граф має гамільтонів цикл. (наводимо без доведення).

Умова Дірака лише достатня, а не необхідна: граф цілком може бути гамільтоновим і з меншими степенями.

Приклад 7.32 (гамільтонів цикл у $G$). У робочому графі кожна з вершин $b,d,e$ має степінь $2$; тому в будь-який цикл, що проходить через таку вершину, мусять увійти обидва її ребра. Це відразу фіксує ребра $ab,bc$ (через $b$), $ad,de$ (через $d$) та $ce,de$ (через $e$), а разом із ними цикл однозначно замикається:

$$a\text{–}b\text{–}c\text{–}e\text{–}d\text{–}a.$$

Він відвідує всі п’ять вершин по разу, отже, $G$ гамільтонів. Зауважимо, що умова Дірака тут не виконується (при $n=5$ вона вимагає степеня $\ge n/2=2{,}5$, а $b,d,e$ мають степінь $2$) — і все ж цикл існує; це вкотре підкреслює, що Дірак дає лише достатню умову.

Задача комівояжера #

Означення (задача комівояжера). У зваженому повному графі задача комівояжера (англ. travelling salesman problem, TSP) полягає у відшуканні гамільтонового циклу найменшої сумарної ваги: замкненого маршруту, що виходить із початкової вершини, відвідує кожну іншу рівно раз і повертається назад з найменшими сумарними витратами.

Назва походить від образу торгового агента, який мусить об’їхати задані міста найкоротшим замкненим маршрутом. Задача сумнозвісно складна: у повному графі на $n$ вершинах різних гамільтонових циклів аж $\frac{(n-1)!}{2}$, тож повний перебір стає безнадійним уже за кількох десятків міст; TSP теж NP-складна. Тому на практиці застосовують наближені й евристичні методи — жадібний алгоритм «найближчого сусіда» (щоразу переходити в найближче ще не відвідане місто), локальні покращення обміном ребер (2-opt) чи побудову маршруту з мінімального остовного дерева (Лекція 8); вони дають добрий, хоч і не конче оптимальний, тур швидко.

Приклад 7.33 (чотири вузли). Нехай чотири вузли повного графа $K_4$ сполучено з вагами (відстанями)

$$w_{12}=3,\quad w_{23}=5,\quad w_{34}=2,\quad w_{14}=4,\quad w_{13}=6,\quad w_{24}=7.$$

У $K_4$ є рівно $\frac{(4-1)!}{2}=3$ різних гамільтонових цикли; порахуймо їхні ваги:

$$1\text{–}2\text{–}3\text{–}4\text{–}1:\ 3+5+2+4=14; \qquad 1\text{–}2\text{–}4\text{–}3\text{–}1:\ 3+7+2+6=18; \qquad 1\text{–}3\text{–}2\text{–}4\text{–}1:\ 6+5+7+4=22.$$

Найдешевший тур — $1\text{–}2\text{–}3\text{–}4\text{–}1$ вагою $14$ (периметр квадрата, що оминає «дорогі» діагоналі $6$ і $7$). Для чотирьох вузлів перебір тривіальний; уся складність TSP виявляється, коли вузлів десятки й сотні.

Застосування у поліграфії. TSP — не абстракція, а щоденна цехова задача. Хід ножа різака чи плотера: контури, які треба вирізати або надсікти, — це «міста», а мінімізація холостих переміщень різальної головки між ними є прямою задачею комівояжера. Свердління друкованих плат: свердлильна головка мусить пройти всі отвори, і порядок обходу з найменшим сумарним ходом свердла — знову TSP. Обхід елементів макета при автоматизованому контролі чи лакуванні, а також черговість приладки фарбових зон — тієї самої природи. Оскільки точний оптимум задорогий, у виробничих контролерах закладають саме наближені евристики.

7.15 Застосування у видавництві та поліграфії #

Мова графів безпосередньо описує задачі фаху:

• Макет і навігація. Сторінки видання з переходами (посилання, «далі», перехресні відсилання) — це орграф; зв’язність гарантує, що з будь-якої сторінки досяжна будь-яка інша, а напівстепені входу/виходу виявляють «глухі кути» й «вузли-концентратори».
• Трасування друкованих плат і монтажних схем. З’єднання компонентів — граф; можливість розвести провідники в один шар без перетинів — це питання планарності (Наслідки 7.21–7.22 і теорема Понтрягіна–Куратовського).
• Складання розкладів друку. Завдання, що конкурують за спільний ресурс (машину, фарбову секцію, оператора), — вершини; конфлікт — ребро; безконфліктний розклад — це правильне розфарбування вершин, а $\chi(G)$ — мінімальна кількість змін/слотів.
• Кольороподіл і суміжність. Області зображення, що межують, не повинні зливатися в один колір — це розфарбування графа суміжності; теорема про чотири фарби гарантує, що для пласкої карти вистачить чотирьох кольорів.
• Мережі й найкоротші маршрути. Логістика доставки накладу, топологія внутрішньої мережі друкарні — це зважені графи; найдешевший кабельний «кістяк» — мінімальне остовне дерево, а найшвидший маршрут — найкоротший шлях (Лекція 8).

Підсумок #

• Граф $G=(V,E)$ поєднує вершини з невпорядкованими ребрами; орграф використовує впорядковані дуги. Прості графи забороняють петлі й паралельні ребра; порядок $=|V|$, розмір $=|E|$.
• Базові поняття: суміжність вершин, інцидентність вершини й ребра, степінь $\deg(v)$ (для орграфа — напівстепені входу $\deg^{-}$ і виходу $\deg^{+}$), ізольована та висяча вершини, $\Delta$, $\delta$, регулярність.
• Лема про рукостискання (Т. 7.4): $\sum_v\deg(v)=2|E|$ — подвійною лічбою інцидентностей; Наслідок 7.5: кількість вершин непарного степеня парна. Орієнтований варіант (Тв. 7.10): $\sum\deg^{+}=\sum\deg^{-}=|A|$.
• Подання: симетрична матриця суміжності (суми рядків — степені) та матриця інцидентності (суми стовпців $=2$); для орграфа матриця суміжності несиметрична. Зважений граф приписує ребрам ваги $w(e)$.
• Рух: маршрут $\supseteq$ ланцюг (усі ребра різні) $\supseteq$ простий ланцюг (усі вершини різні); замкнений ланцюг — цикл. Т. 7.14: з маршруту дістаємо простий ланцюг.
• Зв’язність: досяжність — відношення еквівалентності, а його класи — компоненти зв’язності (Тв. 7.15).
• Ізоморфізм $\cong$: бієкція вершин, що зберігає суміжність. Доводять пред’явленням бієкції; спростовують відмінним інваріантом (порядок, розмір, степенева послідовність, кількість компонент, дводольність). Однакова степенева послідовність ізоморфізму не гарантує.
• Планарність: малюється без перетинів. Формула Ейлера $V-E+F=2$ (Т. 7.18) дає $E\le 3V-6$ і, без трикутників, $E\le 2V-4$; звідси $K_5$ та $K_{3,3}$ непланарні. Теорема Понтрягіна–Куратовського (Т. 7.23): планарний $\iff$ немає підрозбиття $K_5$ чи $K_{3,3}$.
• Розфарбування: хроматичне число $\chi(G)$ (вершини) з $\omega\le\chi\le\Delta+1$ і хроматичний клас $\chi'(G)$ (ребра) з $\chi'\ge\Delta$, а за Візингом $\chi'\in\{\Delta,\Delta+1\}$; теорема про чотири фарби для планарних графів.
• Дерева й ліс: дерево — зв’язний ациклічний граф, $|E|=|V|-1$ (Т. 7.26); ліс із $c$ компонентами має $n-c$ ребер (Тв. 7.28); остовне дерево — «кістяк» зв’язного графа.