Граф без петель и кратных рёбер

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

Определение и формализация

Формально, граф без петель и кратных рёбер определяется как упорядоченная пара \(G = (V, E)\), где:

• \(V\) — конечное (в большинстве случаев) или счётное множество, элементы которого называются вершинами;
• \(E \subseteq \binom{V}{2}\) — множество неупорядоченных пар \(\{u, v\}\), где \(u, v \in V\) и \(u \neq v\). Каждая такая пара называется ребром.

Из определения следует, что:

• Ни одно ребро не может соединять вершину саму с собой (отсутствие петель).
• Между любой парой вершин может существовать не более одного ребра (отсутствие кратных рёбер).

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

История возникновения

Понятие простого графа восходит к работам Леонарда Эйлера, который в 1736 году решил задачу о кёнигсбергских мостах. В этой задаче Эйлер рассматривал схему, состоящую из четырёх участков суши (вершин) и семи мостов (рёбер). Хотя в оригинальной задаче между некоторыми парами вершин было несколько мостов (кратные рёбра), Эйлер ввёл понятие «графа» как абстрактной структуры, где рёбра представляют связи. Однако формальное определение простого графа было дано позже, в XIX—XX веках, в трудах таких математиков, как Артур Кэли (изучал деревья как простые графы) и Денеш Кёниг, который в 1936 году опубликовал первую монографию по теории графов. Именно Кёниг систематизировал понятия, отделив простые графы от более общих структур.

Классификация простых графов

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

По связности

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

По наличию циклов

• Дерево: связный граф без циклов (ациклический). Любое дерево с \(n\) вершинами имеет ровно \(n-1\) ребро.
• Лес: несвязный граф, каждая компонента которого является деревом.
• Циклический граф: содержит хотя бы один цикл (замкнутый путь, в котором все вершины, кроме первой и последней, различны).

По регулярности

• Регулярный граф: все вершины имеют одинаковую степень (количество инцидентных рёбер). Например, \(k\)-регулярный граф — граф, где степень каждой вершины равна \(k\).
• Полный граф \(K_n\): частный случай регулярного графа, где каждая из \(n\) вершин соединена со всеми остальными. Количество рёбер в \(K_n\) равно \(\frac{n(n-1)}{2}\).

По двудольности

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

По планарности

• Планарный граф: может быть изображён на плоскости без пересечения рёбер (кроме вершин). Классический пример — графы многогранников (например, куба или тетраэдра).
• Непланарный граф: любое его изображение на плоскости содержит пересечения рёбер. Минимальные непланарные графы — \(K_5\) (полный граф на 5 вершинах) и \(K_{3,3}\) (полный двудольный граф с тремя вершинами в каждой доле).

Основные характеристики и параметры

Для описания простого графа используются следующие числовые характеристики:

• Порядок графа: количество вершин \(|V| = n\).
• Размер графа: количество рёбер \(|E| = m\).
• Степень вершины \(deg(v)\): количество рёбер, инцидентных вершине \(v\). Для простого графа \(0 \leq deg(v) \leq n-1\).
• Минимальная степень \(\delta(G)\) и максимальная степень \(\Delta(G)\).
• Диаметр графа: максимальное расстояние (длина кратчайшего пути) между двумя вершинами.
• Радиус графа: минимальное из максимальных расстояний от данной вершины до всех остальных.
• Обхват графа: длина кратчайшего цикла (если циклы есть).

Применение в науке и технике

Простые графы служат моделью для множества реальных систем, где важны только факт наличия связи и её уникальность.

Компьютерные сети

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

Социальные сети

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

Химия

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

Транспортные системы

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

Теория кодирования

В теории кодирования простые графы используются для построения кодов, исправляющих ошибки. Например, графы Кэли и графы-решётки применяются при создании кодов с низкой плотностью проверок на чётность (LDPC-коды), используемых в современных системах связи (Wi-Fi, 5G).

Примеры простых графов

1. Граф-путь \(P_n\): \(n\) вершин, расположенных в линию, рёбра между соседними вершинами. Пример: маршрут автобуса с остановками.
2. Граф-цикл \(C_n\): \(n\) вершин, образующих кольцо. Пример: кольцевая линия метро.
3. Звезда \(S_n\): одна центральная вершина соединена с \(n-1\) периферийными вершинами, которые не соединены между собой. Пример: сеть Wi-Fi с одной точкой доступа.
4. Полный граф \(K_n\): все вершины соединены попарно. Пример: сеть из нескольких компьютеров, где каждый соединён с каждым напрямую.
5. Граф Петерсена: известный пример небольшого (10 вершин, 15 рёбер) кубического (3-регулярного) графа, который является непланарным и используется в качестве контрпримера во многих задачах теории графов.

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

• В любом простом графе с \(n \geq 2\) вершинами существуют по крайней мере две вершины с одинаковой степенью (принцип Дирихле для степеней).
• Простой граф является деревом тогда и только тогда, когда он связен и \(m = n - 1\).
• Задача раскраски вершин простого графа (раскрасить вершины так, чтобы смежные вершины имели разные цвета) является одной из центральных в теории графов. Минимальное количество цветов называется хроматическим числом. Для полного графа \(K_n\) оно равно \(n\), для двудольного графа — 2.
• Теорема Куратовского (1930) даёт критерий планарности простого графа: граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных \(K_5\) или \(K_{3,3}\).
• В 1976 году Кеннет Аппель и Вольфганг Хакен доказали теорему о четырёх красках, используя компьютерный перебор: любой планарный простой граф может быть раскрашен в четыре цвета. Это была первая крупная математическая теорема, доказанная с помощью компьютера.

Критика и ограничения модели

Несмотря на широкое применение, модель простого графа имеет ограничения:

• Отсутствие весов: в реальных задачах рёбра часто имеют вес (длина, стоимость, пропускная способность). Для таких случаев используются взвешенные графы, которые не являются простыми в строгом смысле, хотя могут не содержать петель и кратных рёбер.
• Однородность связей: модель не различает типы связей (например, дружба и родство в социальной сети). Для этого применяются графы с раскрашенными рёбрами или гиперграфы.
• Статичность: простой граф фиксирует связи на момент времени, не учитывая их динамику (например, добавление или удаление друзей в соцсети). Для анализа изменений используются динамические графы.
• Неприменимость к мультисвязям: если между объектами может быть несколько разных связей (например, несколько дорог между городами), простая модель теряет информацию. В таких случаях требуется мультиграф.

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

Источники

• Оре О. «Теория графов». — М.: Наука, 1980.
• Харари Ф. «Теория графов». — М.: Мир, 1973.
• Кёниг Д. «Теория конечных и бесконечных графов». — М.: ГИЗ, 1936.
• Дистель Р. «Теория графов». — Новосибирск: МЦНМО, 2002.
• Уилсон Р. «Введение в теорию графов». — М.: Мир, 1977.