Теория графов¶

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

¶Основные определения

Граф формально определяется как упорядоченная пара \( G = (V, E) \), где \( V \) — непустое множество вершин, а \( E \) — множество рёбер, каждое из которых соединяет пару вершин. В зависимости от типа связей различают:

Неориентированный граф: рёбра не имеют направления, то есть связь между вершинами \( u \) и \( v \) симметрична.
Ориентированный граф (орграф): рёбра (дуги) имеют направление от одной вершины к другой.
Смешанный граф: содержит как ориентированные, так и неориентированные рёбра.

Ключевые характеристики графа включают:

Степень вершины: количество рёбер, инцидентных данной вершине. Для орграфов различают полустепень исхода (количество исходящих дуг) и полустепень захода (количество входящих дуг).
Петля: ребро, соединяющее вершину с самой собой.
Кратные рёбра: несколько рёбер, соединяющих одну и ту же пару вершин.
Путь: последовательность вершин, в которой каждая следующая вершина соединена ребром с предыдущей.
Цикл: замкнутый путь, в котором первая и последняя вершины совпадают.
Связность: свойство графа, при котором между любой парой вершин существует путь.

¶История развития

Первые задачи, связанные с графами, решались ещё в XVIII веке. Основоположником теории графов считается Леонард Эйлер, который в 1736 году опубликовал решение задачи о кёнигсбергских мостах. Эйлер доказал, что невозможно пройти по всем семи мостам города Кёнигсберг (ныне Калининград) ровно один раз и вернуться в исходную точку, если граф мостов не удовлетворяет определённым условиям. Это положило начало теории эйлеровых графов.

В XIX веке теория графов развивалась в основном в связи с задачами электротехники и химии. В 1847 году Густав Кирхгоф применил графы для анализа электрических цепей, а в 1857 году Артур Кэли использовал деревья (частный случай графов) для подсчёта числа изомеров алканов. В 1852 году возникла проблема четырёх красок, которая стимулировала развитие теории раскраски графов.

В XX веке теория графов стала активно применяться в информатике и исследовании операций. В 1930-е годы Денеш Кёниг написал первую монографию по теории графов. Во второй половине века развитие вычислительной техники привело к появлению алгоритмов на графах (поиск кратчайшего пути, минимального остовного дерева, максимального потока). В 1976 году проблема четырёх красок была решена с помощью компьютерного перебора Кеннетом Аппелем и Вольфгангом Хакеном.

¶Классификация графов

Графы классифицируют по различным признакам:

¶По структуре

Простой граф: не содержит петель и кратных рёбер.
Мультиграф: допускает кратные рёбра.
Псевдограф: допускает петли и кратные рёбра.
Полный граф: каждая пара вершин соединена ребром. Обозначается \( K_n \), где \( n \) — число вершин.
Двудольный граф: вершины можно разделить на два непересекающихся множества так, что каждое ребро соединяет вершины из разных множеств.
Планарный граф: может быть изображён на плоскости без пересечения рёбер.
Дерево: связный граф без циклов.

¶По свойствам связности

Связный граф: существует путь между любой парой вершин.
Сильно связный орграф: существует путь в обоих направлениях между любой парой вершин.
Компонента связности: максимальный связный подграф.

¶По весам

Взвешенный граф: каждому ребру (или вершине) приписан числовой вес (стоимость, длина, пропускная способность).
Невзвешенный граф: все рёбра равнозначны.

¶Основные задачи и алгоритмы

Теория графов решает широкий круг задач, многие из которых имеют практическое значение.

¶Поиск кратчайшего пути

Одна из классических задач — нахождение пути минимальной длины (или стоимости) между двумя вершинами во взвешенном графе. Основные алгоритмы:

Алгоритм Дейкстры (1959): находит кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными весами.
Алгоритм Беллмана — Форда: работает с графами, содержащими рёбра отрицательного веса, и обнаруживает отрицательные циклы.
Алгоритм Флойда — Уоршелла: находит кратчайшие пути между всеми парами вершин.

¶Минимальное остовное дерево

Задача построения дерева, соединяющего все вершины графа с минимальной суммарной стоимостью рёбер. Решается алгоритмами:

Алгоритм Прима (1957): строит дерево, последовательно добавляя ближайшую вершину.
Алгоритм Краскала (1956): сортирует рёбра по весу и добавляет их, если они не образуют цикл.

¶Задача о максимальном потоке

В транспортных сетях (ориентированных графах с пропускными способностями рёбер) требуется найти максимальный поток от источника к стоку. Классический алгоритм — алгоритм Форда — Фалкерсона (1956), который использует поиск увеличивающих путей.

¶Раскраска графов

Раскраска вершин или рёбер графа с минимальным числом цветов так, чтобы смежные элементы имели разные цвета. Задача раскраски вершин связана с проблемой четырёх красок: любой планарный граф можно раскрасить в четыре цвета так, чтобы смежные вершины были разного цвета. Раскраска рёбер применяется при составлении расписаний.

¶Эйлеровы и гамильтоновы циклы

Эйлеров цикл: замкнутый путь, проходящий по каждому ребру ровно один раз. Существует в связном графе, если все вершины имеют чётную степень (теорема Эйлера).
Гамильтонов цикл: замкнутый путь, проходящий через каждую вершину ровно один раз. Задача его нахождения является NP-полной.

¶Изоморфизм графов

Определение, являются ли два графа одинаковыми с точностью до переименования вершин. Эта задача имеет важное значение в химии (идентификация молекул) и информатике. В 2015 году Ласло Бабай предложил алгоритм с квазиполиномиальной сложностью, но общее решение остаётся открытым.

¶Применение

Теория графов широко используется в различных сферах:

Информатика: графы лежат в основе структур данных (списки смежности, матрицы смежности), алгоритмов поиска (DFS, BFS), анализа социальных сетей, построения рекомендательных систем, маршрутизации в компьютерных сетях.
Транспорт и логистика: моделирование дорожных сетей, задача коммивояжёра (поиск кратчайшего гамильтонова цикла), оптимизация цепочек поставок.
Электротехника: анализ электрических цепей с помощью графов (метод узловых потенциалов).
Химия: представление молекул в виде графов (атомы — вершины, химические связи — рёбра), предсказание свойств веществ.
Социология: изучение социальных сетей, распространение информации, выявление сообществ.
Биология: моделирование метаболических путей, нейронных сетей, филогенетических деревьев.
Лингвистика: синтаксический анализ предложений с помощью деревьев зависимостей.

¶Интересные факты

Теория графов тесно связана с теорией вероятностей: случайные графы (модель Эрдёша — Реньи) изучают свойства графов, возникающих с заданной вероятностью появления рёбер.
Проблема четырёх красок стала первой крупной математической теоремой, доказанной с помощью компьютера.
Графы используются в криптографии: например, в схеме электронной подписи на основе изоморфизма графов.
В 2024 году исследователи из Массачусетского технологического института предложили новый алгоритм для задачи о максимальном потоке, работающий за почти линейное время.

¶Источники

Оре О. Теория графов. — М.: Наука, 1980.
Харари Ф. Теория графов. — М.: Мир, 1973.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
Эйлер Л. Solutio problematis ad geometriam situs pertinentis. — Commentarii Academiae Scientiarum Imperialis Petropolitanae, 1736.
Кирхгоф Г. О решении уравнений, к которым приводятся исследования линейного распределения гальванических токов. — 1847.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →