Псевдограф

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

Определение и формальное описание

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

• \( V \) — непустое множество вершин (узлов);
• \( E \) — множество рёбер, каждое из которых представляет собой неупорядоченную пару вершин, не обязательно различных. Если ребро соединяет вершину \( v \) с самой собой, оно называется петлёй. Если две вершины соединены более чем одним ребром, такие рёбра называются кратными (или параллельными).

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

Связь с другими типами графов

Псевдограф является наиболее общим случаем в иерархии неориентированных графов:

• Простой граф: не содержит ни петель, ни кратных рёбер.
• Мультиграф: допускает кратные рёбра, но не петли.
• Псевдограф: допускает и петли, и кратные рёбра.

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

История и происхождение термина

Термин «псевдограф» (от греч. ψευδής — ложный, и γράφω — пишу) был введён в математический обиход в середине XX века для обозначения структур, которые не удовлетворяют строгим аксиомам простого графа. Первоначально он использовался в контексте теории сетей и комбинаторики, где требовалось моделировать ситуации с множественными связями или самозамкнутыми циклами. В русскоязычной математической литературе термин закрепился благодаря работам таких учёных, как Фрэнк Харари и Клод Берж, которые в своих книгах по теории графов (например, «Теория графов» Ф. Харари, 1969) чётко разграничили понятия графа, мультиграфа и псевдографа.

Классификация и виды псевдографов

Псевдографы можно классифицировать по различным признакам:

По типу рёбер

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

По наличию весов

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

По связности

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

Характеристики и свойства

Основные характеристики псевдографа включают:

• Степень вершины \( \deg(v) \) — число рёбер, инцидентных данной вершине. В псевдографе петля учитывается дважды (так как она соединяет вершину саму с собой). Например, если у вершины есть одна петля и одно обычное ребро, её степень равна 3.
• Порядок графа — количество вершин \( |V| \).
• Размер графа — количество рёбер \( |E| \).
• Цикломатическое число — \( \mu = |E| — |V| + k \), где \( k \) — число компонент связности. Для псевдографа это число может быть больше, чем для простого графа с тем же числом вершин, из-за наличия петель и кратных рёбер.

Особенности матричного представления

Псевдограф можно представить в виде:

• Матрицы смежности: квадратная матрица \( A \) размера \( |V| \times |V| \), где элемент \( a_{ij} \) равен числу рёбер между вершинами \( v_i \) и \( v_j \). Для петли \( a_{ii} \) равно удвоенному числу петель (в некоторых конвенциях — просто числу петель, но для согласования со степенью вершины обычно берут 2).
• Матрицы инцидентности: матрица размера \( |V| \times |E| \), где элемент равен 1, если вершина инцидентна ребру, и 0 в противном случае. Для петли ставится 2 (так как вершина инцидентна ребру дважды).

Применение псевдографов

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

В компьютерных науках

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

В химии

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

В социальных науках

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

В транспортной логистике

• Транспортные сети: на картах дорог могут быть участки, где два города соединены несколькими маршрутами (кратные рёбра), а также кольцевые развязки, которые можно рассматривать как петли.

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

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

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

Несмотря на широкую применимость, псевдографы имеют и недостатки:

• Усложнение анализа: наличие петель и кратных рёбер делает многие алгоритмы (например, поиск кратчайшего пути или проверку на двудольность) более сложными или неоднозначными.
• Избыточность: в некоторых задачах петли и кратные рёбра не несут полезной информации и только загромождают модель.
• Терминологическая путаница: в разных источниках термины «мультиграф», «псевдограф» и «обобщённый граф» могут использоваться по-разному, что требует уточнения в каждом конкретном случае.

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

Источники

1. Харари Ф. Теория графов. — М.: Мир, 1973.
2. Берж К. Теория графов и её применения. — М.: Иностранная литература, 1962.
3. Оре О. Теория графов. — М.: Наука, 1980.
4. Diestel R. Graph Theory. — Springer, 2017.
5. Bondy J. A., Murty U. S. R. Graph Theory with Applications. — Elsevier, 1976.