Граф — понятие теории графов¶
Граф — математическая структура, состоящая из множества вершин (узлов) и множества рёбер (дуг), соединяющих пары вершин. Графы являются фундаментальным объектом теории графов — раздела дискретной математики, а также одним из ключевых понятий информатики, используемым для моделирования отношений и связей между объектами. Графы применяются в компьютерных науках, лингвистике, химии, биологии, социологии, логистике и других областях.
¶Определение и обозначения
Формально граф — это упорядоченная пара $G = (V, E)$, где $V$ — конечное непустое множество вершин, а $E$ — множество рёбер. Ребро, соединяющее вершины $u$ и $v$, записывается как пара $\{u, v\}$ (для неориентированного графа) или упорядоченная пара $(u, v)$ (для ориентированного графа). Число вершин графа обозначают $|V|$ или $n$, число рёбер — $|E|$ или $m$.
Вершины, соединённые ребром, называются смежными, а сами рёбра — инцидентными этим вершинам. Степень вершины — число рёбер, инцидентных ей. Сумма степеней всех вершин графа всегда равна удвоенному числу рёбер (лемма о рукопожатиях).
¶Основные виды графов
Графы классифицируются по нескольким признакам.
¶По наличию направления рёбер
- Неориентированный граф — ребро $\{u, v\}$ не имеет направления и связывает вершины симметрично.
- Ориентированный граф (диграф) — каждое ребро задано упорядоченной парой $(u, v)$ и имеет направление от $u$ к $v$.
- Полуориентированный граф — допускает одновременно и ориентированные, и неориентированные рёбра.
¶По кратности рёбер и петель
- Простой граф — без петель (рёбер, соединяющих вершину с самой собой) и без кратных рёбер (нескольких рёбер между одной парой вершин).
- Мультиграф — допускает кратные рёбра.
- Псевдограф — допускает и кратные рёбра, и петли.
¶По весам
- Невзвешенный граф — рёбра не имеют числовых характеристик.
- Взвешенный граф — каждому ребру приписан вес (число), например расстояние, стоимость или пропускная способность.
¶По связности
- Связный граф — между любыми двумя вершинами существует путь.
- Несвязный граф — состоит из нескольких компонент связности.
- Полный граф $K_n$ — каждый граф из $n$ вершин содержит все возможные рёбра, то есть $|E| = n(n-1)/2$.
- Дерево — связный граф без циклов.
- Лес — граф без циклов, не обязательно связный.
¶Способы представления
Графы можно записывать и хранить несколькими способами.
- Матрица смежности — квадратная матрица размера $n \times n$, в которой элемент $a_{ij}$ равен числу рёбер между вершинами $i$ и $j$. Для взвешенного графа вместо единицы используется вес ребра.
- Матрица инцидентности — матрица размера $n \times m$, где строкам соответствуют вершины, столбцам — рёбра.
- Список смежности — для каждой вершины хранится список вершин, с которыми она соединена. Наиболее экономичное представление для разреженных графов.
- Геометрическое (чертёжное) представление — вершины изображаются точками, рёбра — линиями между ними.
¶Основные задачи теории графов
Теория графов изучает структуру графов и алгоритмы работы с ними. К классическим задачам относятся:
- Поиск пути и кратчайшего пути — алгоритм Дейкстры (1959) для графов с неотрицательными весами, алгоритм Беллмана — Форда для графов с отрицательными весами, алгоритм Флойда — Уоршелла для всех пар вершин.
- Поиск остовного дерева — алгоритмы Краскала и Прима для нахождения минимального остовного дерева.
- Поиск в ширину и в глубину — базовые обходы графа, используемые во многих алгоритмах.
- Топологическая сортировка — линейная упорядочка вершин ориентированного ациклического графа.
- Поиск компонент связности — алгоритмы на основе обхода или системы непересекающихся множеств (union-find).
- Задача коммивояжёра — нахождение кратчайшего маршрута, проходящего через все вершины; классическая NP-полная задача.
- Раскраска графов — минимальное число цветов, необходимых так, чтобы соседние вершины имели разные цветы.
¶Применение
Графы используются для моделирования широкого круга реальных систем:
- Компьютерные сети — вершины — узлы и сервера, рёбра — каналы связи.
- Транспортные системы — вершины — перекрёстки и станции, рёбра — дороги и маршруты.
- Социальные сети — вершины — люди, рёбра — отношения (дружба, подписка).
- Биоинформатика — белковые взаимодействия, генные регуляторные сети.
- Химия — молекулы как графы, где атомы — вершины, химические связи — рёбра.
- Лингвистика — синтаксические деревья и графы зависимостей.
- Интернет — веб-страницы как вершины, гиперссылки как ориентированные рёбра.
¶История
Первым примером использования графов считается задача о семи кёнигсбергских мостах, решённая Леонардом Эйлером в 1736 году. Эйлер показал, что задача о прохождении всех мостов сводится к поиску пути в графе и доказал невозможность такого пути для кёнигсбергской сети. Эта работа считается началом теории графов.
Термин «граф» в современном смысле ввёл Джеймс Сильвестр в 1878 году. Существенный вклад в развитие теории внесли Деннис Кёниг (1936, первая монография по теории графов), Пал Туран, Вольфганг Дейкстра, Роберт Тарьян и многие другие. В XX веке теория графов стала одним из основных инструментов дискретной математики и информатики.
¶Источники
- Бонди А., Мёрти У. «Графы и их приложения»
- Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. «Алгоритмы: построение и анализ»
- Львовский С. Л. «Дискретная математика»
- Львовский С. Л. «Теория графов»
- Оре О. «Графы и их применения»
- Скурихин В. П. «Дискретная математика»
