Граф (математика)¶

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

¶История

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

Термин «граф» ввёл Джеймс Джозеф Сильвестр в 1878 году в статье о химических структурах, где он провёл аналогию между математическими структурами и химическими диаграммами. В XX веке теория графов оформилась в самостоятельную дисциплину благодаря работам Денеша Кёнига, который в 1936 году опубликовал первую монографию по этому предмету. Развитие вычислительной техники во второй половине XX века привело к бурному росту прикладных алгоритмов на графах.

¶Основные понятия и классификация

¶Виды графов

Графы классифицируются по множеству признаков. Неориентированный граф — рёбра не имеют направления, то есть связь симметрична (например, отношение «быть знакомым»). Ориентированный граф (орграф) — каждое ребро имеет направление от одной вершины к другой (например, отношение «подписан на» в социальной сети). Смешанный граф содержит как ориентированные, так и неориентированные рёбра.

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

¶Способы представления

На практике графы хранят и обрабатывают в виде матрицы смежности (квадратная таблица, где элемент \(a_{ij}\) равен 1 или весу ребра, если вершины \(i\) и \(j\) соединены) или списков смежности (для каждой вершины хранится список соседних вершин). Матрица смежности удобна для плотных графов и быстрой проверки наличия ребра, но требует \(O(n^2)\) памяти. Списки смежности экономичнее для разреженных графов и удобнее для обходов.

¶Свойства и характеристики

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

Путь — последовательность вершин, в которой каждая следующая соединена с предыдущей ребром. Цикл — путь, начинающийся и заканчивающийся в одной вершине. Граф называется связным, если между любой парой его вершин существует путь. Дерево — связный граф без циклов; деревья играют особую роль как минимальные связные структуры. Расстояние между вершинами — длина кратчайшего пути; максимум расстояний между всеми парами вершин называется диаметром графа.

¶Алгоритмы на графах

Теория графов тесно связана с алгоритмами. Поиск в глубину (DFS) и поиск в ширину (BFS) — базовые методы обхода, лежащие в основе многих более сложных алгоритмов. Для нахождения кратчайших путей во взвешенном графе применяются алгоритм Дейкстры (для неотрицательных весов), алгоритм Беллмана — Форда (допускает отрицательные веса) и алгоритм Флойда — Уоршелла (для всех пар вершин).

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

¶Применение

¶Компьютерные науки и интернет

Графы — фундамент структур данных и алгоритмов. Всемирная паутина моделируется как ориентированный граф, где страницы — вершины, а гиперссылки — рёбра; алгоритм PageRank, использовавшийся поисковой системой Google, вычисляет важность страниц на основе структуры этого графа. Социальные сети описываются графами, где пользователи — вершины, а дружеские связи или подписки — рёбра; анализ таких графов позволяет выявлять сообщества и влиятельных лиц. Компьютерные сети и интернет-маршрутизация используют графы для поиска оптимальных маршрутов передачи данных.

¶Транспорт и логистика

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

¶Другие области

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

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

• Теорема о четырёх красках, утверждающая, что любую плоскую карту можно раскрасить четырьмя цветами так, чтобы соседние области имели разные цвета, была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном с использованием компьютера — это стало первым крупным доказательством, выполненным машинным способом.
• Граф Петерсена — знаменитый граф с 10 вершинами и 15 рёбрами, служащий контрпримером для многих гипотез в теории графов.
• Проблема изоморфизма графов (определение, являются ли два графа структурно одинаковыми) долгое время оставалась одной из ключевых нерешённых задач; в 2015 году Ласло Бабай предложил алгоритм с квазиполиномиальной сложностью, но полного решения до сих пор нет.
• В 2020-х годах графовые нейронные сети стали активно применяться в машинном обучении для анализа данных, представленных в виде графов (например, молекулярных структур или социальных взаимодействий).