Открыть сервисСервис

Граф — понятие теории графов

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

Определение и обозначения

Формально граф — это упорядоченная пара $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 веке теория графов стала одним из основных инструментов дискретной математики и информатики.

Источники

  • Бонди А., Мёрти У. «Графы и их приложения»
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. «Алгоритмы: построение и анализ»
  • Львовский С. Л. «Дискретная математика»
  • Львовский С. Л. «Теория графов»
  • Оре О. «Графы и их применения»
  • Скурихин В. П. «Дискретная математика»
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru