Графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях ледь чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа та ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів — наприклад, знаменита проблема чотирьох фарб, що інтригує математиків і донині. Теорія графів швидко розвивається, знаходить все нові додатки і чекає на молодих дослідників.
- The Basics (Основи)
- Graphs (Графи)
- The degree of a vertex (Ступінь вершини)
- Paths and cycles (Шляхи та цикли)
- Connectivity (Зв'язність)
- Trees and forests (Дерева та ліси)
- Bipartite graphs (Дводольні графи)
- Contraction and minors (Стягування та мінори)
- Euler tours (Ейлерові обходи)
- Some linear algebra (Елементи лінійної алгебри)
- Other notions of graphs (Інші поняття графів)
- Exercises (Вправи)
- Matching, Covering and Packing (Паросполучення, покриття та пакування)
- Matching in bipartite graphs (Паросполучення у дводольних графах)
- Matching in general graphs (Паросполучення у загальних графах)
- The Erdos-Posa theorem (Теорема Ердеша — Поша)
- Tree packing and arboricity (Пакування дерев та деревність)
- Path covers (Покриття шляхами)
- Exercises (Вправи)
- Connectivity (Зв'язність)
- 2-Connected graphs and subgraphs (2-зв'язні графи та підграфи)
- The structure of 3-connected graphs (Структура 3-зв'язних графів)
- Menger’s theorem (Теорема Менгера)
- Mader’s theorem (Теорема Мадера)
- Linking pairs of vertices (З'єднання пар вершин)
- Exercises (Вправи)
- Planar Graphs (Планарні графи)
- Topological prerequisites (Топологічні передумови)
- Plane graphs (Плоскі графи)
- Drawings (Укладання / Малюнки графів)
- Planar graphs: Kuratowski’s theorem (Планарні графи: теорема Куратовського)
- Algebraic planarity criteria (Алгебраїчні критерії планарності)
- Plane duality (Плоска дуальність)
- Exercises (Вправи)
- Colouring (Розфарбовування)
- Colouring maps and planar graphs (Розфарбовування мап та планарних графів)
- Colouring vertices (Розфарбовування вершин)
- Colouring edges (Розфарбовування ребер)
- List colouring (Списочне розфарбовування)
- Perfect graphs (Досконалі графи)
- Exercises (Вправи)
- Flows (Потоки)
- Circulations (Циркуляції)
- Flows in networks (Потоки в мережах)
- Group-valued flows (Потоки зі значеннями в групах)
- k-Flows for small k (k-потоки для малих значень k)
- Flow-colouring duality (Двоїстість потоків та розфарбовування)
- Tutte’s flow conjectures (Гіпотези Тутте про потоки)
- Exercises (Вправи)
- Extremal Graph Theory (Екстремальна теорія графів)
- Subgraphs (Підграфи)
- Minors (Мінори)
- Hadwiger’s conjecture (Гіпотеза Хадвігера)
- Szemerédi’s regularity lemma (Регулярна лема Семереді)
- Applying the regularity lemma (Застосування регулярної леми)
- Exercises (Вправи)
- Infinite Graphs (Нескінченні графи)
- Basic notions, facts and techniques (Основні поняття, факти та методи)
- Paths, trees, and ends (Шляхи, дерева та кінці)
- Homogeneous and universal graphs (Однорідні та універсальні графи)
- Connectivity and matching (Зв'язність та паросполучення)
- Recursive structures (Рекурсивні структури)
- Graphs with ends: the complete picture (Графи з кінцями: повна картина)
- The topological cycle space (Топологічний простір циклів)
- Infinite graphs as limits of finite ones (Нескінченні графи як границі скінченних)
- Exercises (Вправи)
- Ramsey Theory for Graphs (Теорія Рамсея для графів)
- Ramsey’s original theorems (Оригінальні теореми Рамсея)
- Ramsey numbers (Числа Рамсея)
- Induced Ramsey theorems (Індуковані теореми Рамсея)
- Ramsey properties and connectivity (Властивості Рамсея та зв'язність)
- Exercises (Вправи)
- Hamilton Cycles (Гамільтонові цикли)
- Sufficient conditions (Достатні умови)
- Hamilton cycles and degree sequences (Гамільтонові цикли та послідовності степенів)
- Hamilton cycles in the square of a graph (Гамільтонові цикли у квадраті графа)
- Exercises (Вправи)
- Random Graphs (Випадкові графи)
- The notion of a random graph (Поняття випадкового графа)
- The probabilistic method (Імовірнісний метод)
- Properties of almost all graphs (Властивості майже всіх графів)
- Threshold functions and second moments (Порогові функції та другі моменти)
- Exercises (Вправи)
- Graph Minors (Мінори графів)
- Well-quasi-ordering (Цілком квазівпорядкування)
- The graph minor theorem for trees (Теорема про мінори графів для дерев)
- Tree-decompositions (Деревні розклади)
- Tree-width (Деревна ширина)
- Tangles (Клубки / Сплетіння)
- Tree-decompositions and forbidden minors (Деревні розклади та заборонені мінори)
- The graph minor theorem (Теорема про мінори графів / Теорема Робертсона — Сеймура)
- Exercises (Вправи)
