Граф в теории графов¶

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

¶Определение

Формально граф — это упорядоченная пара $G = (V, E)$, где $V$ — множество вершин, а $E$ — множество рёбер. Ребро может быть ориентированным (дуга), если направление связи важно, или неориентированным. Граф, все рёбра которого ориентированы, называется ориентированным (орграфом); если все рёбра неориентированные — неориентированным. Смешанный граф содержит и те, и другие.

В неориентированном графе ребро $e = \{u, v\}$ связывает вершины $u$ и $v$, которые называются его концами. В ориентированном графе ребро $e = (u, v)$ направлено из $u$ в $v$: $u$ — начало, $v$ — конец ребра. Если рёбра могут соединять вершину с самой собой, такие рёбра называются петлями; если между двумя вершинами допускается несколько рёбер — мультиграфом или псевдографом. Граф без петель и кратных рёбер называется простым.

¶Основные понятия

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

¶Классификация

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

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

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

Граф можно задать несколькими эквивалентными способами:

1. Список рёбер — перечень пар вершин.
2. Матрица смежности — квадратная матрица $n \times n$, где элемент $a_{ij}$ равен числу рёбер между вершинами $i$ и $j$.
3. Матрица инцидентности — матрица, строки которой соответствуют вершинам, столбцам — рёбрам.
4. Списки смежности — для каждой вершины хранится перечень соседей; наиболее распространённое представление при реализации алгоритмов.

¶Алгоритмы теории графов

Классические алгоритмы решения задач на графах:

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

¶Применение

Графы используются для моделирования широкого круга объектов:

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

¶История

Первые задачи, решаемые средствами теории графов, связаны с задачей о семи мостах Кёнигсберга, поставленной Леонардом Эйлером в 1736 году. Решение Эйлера заложило основы теории графов. Термин «граф» ввёл в 1878 году Джеймс Сильвестр. Систематическое развитие теория получила в работах Денниса Кёнига (1936), а в 1959 году Поль Эрдёш и Альфред Реньи опубликовали фундаментальный труд по случайным графам. В XXI веке теория графов стала основой анализа больших данных, социальных сетей и алгоритмов машинного обучения.

¶См. также

• Теория графов
• Алгоритмы на графах
• Сетевой анализ
• Комбинаторика

Источники:

• Бонди Э., Мёрти У. Теория графов и её приложения. — М.: Мир, 1974.
• Корнев М. С. Теория графов. — М.: Высшая школа, 1975.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — СПб.: Питер, 2011.
• Оре О. Графы и их применения. — М.: Мир, 1974.