Линейный граф

Линейный граф (также рёберный граф, граф смежности рёбер) — это граф, вершины которого соответствуют рёбрам исходного графа, а две вершины соединены ребром, если соответствующие рёбра исходного графа имеют общую вершину (смежны). Формально, для графа \( G = (V, E) \) его линейный граф \( L(G) \) определяется как \( L(G) = (E, F) \), где \( \{e_1, e_2\} \in F \) тогда и только тогда, когда \( e_1 \cap e_2 \neq \varnothing \). Линейные графы широко используются в теории графов, комбинаторике и прикладных задачах, таких как анализ сетей и распознавание структур.

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

Понятие линейного графа впервые было введено в 1930-х годах в контексте изучения свойств графов, связанных с их рёберной структурой. Одним из первых исследователей, систематически изучавших линейные графы, был американский математик Хасслер Уитни, который в 1932 году опубликовал работу, посвящённую их характеристике. Уитни показал, что для связных графов с числом вершин не менее 4 линейный граф однозначно определяет исходный граф (за исключением некоторых тривиальных случаев). Впоследствии понятие было развито в работах по теории матроидов и алгебраической топологии.

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

Основное определение

Пусть дан неориентированный граф \( G = (V, E) \) без петель и кратных рёбер. Линейный граф \( L(G) \) строится следующим образом:

• Множество вершин \( V(L(G)) = E \).
• Две вершины \( e_1 \) и \( e_2 \) в \( L(G) \) соединены ребром, если в \( G \) рёбра \( e_1 \) и \( e_2 \) инцидентны одной и той же вершине (то есть имеют общий конец).

Для ориентированных графов определение аналогично, но с учётом направления рёбер: две вершины \( L(G) \) соединяются, если конец одного ребра совпадает с началом другого.

Свойства

• Число вершин: \( |V(L(G))| = |E(G)| \).
• Число рёбер: \( |E(L(G))| = \sum_{v \in V(G)} \binom{\deg(v)}{2} \), где \( \deg(v) \) — степень вершины \( v \) в \( G \).
• Линейный граф всегда содержит не менее \( |E(G)| \) вершин и может иметь петли, если исходный граф содержит петли (в стандартном определении петли обычно исключаются).

Классификация и примеры

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

• Пустой граф: Если \( G \) не содержит рёбер, то \( L(G) \) — пустой граф (без вершин).
• Цикл \( C_n \): Линейный граф цикла \( C_n \) при \( n \geq 3 \) изоморфен самому циклу \( C_n \). Например, для треугольника \( C_3 \) линейный граф также является треугольником.
• Полный граф \( K_n \): Линейный граф полного графа \( K_n \) — это граф, известный как граф Джонсона \( J(n, 2) \), вершины которого — пары элементов из \( n \), а рёбра соединяют пары с общим элементом. Для \( K_4 \) линейный граф — это октаэдр (граф, изоморфный дополнению к \( C_6 \)).
• Звезда \( K_{1,n} \): Линейный граф звезды — полный граф \( K_n \), так как все рёбра звезды инцидентны центральной вершине и попарно смежны.

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

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

Характеристика линейных графов

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

Теорема Уитни

Для связных графов с числом вершин не менее 4 линейный граф однозначно определяет исходный граф. Исключение составляют графы \( K_3 \) и \( K_{1,3} \), которые имеют одинаковые линейные графы (оба дают \( K_3 \)).

Критерий Бейнеке

Граф \( H \) является линейным графом некоторого графа тогда и только тогда, когда:

1. \( H \) не содержит индуцированных подграфов, изоморфных определённому набору запрещённых графов (например, \( K_{1,3} \) — звезда с тремя листьями, также известная как «клешня»).
2. Все максимальные клики в \( H \) имеют определённую структуру: они могут быть разбиты на два класса, соответствующие вершинам исходного графа.

Более формально, граф \( H \) является линейным графом тогда и только тогда, когда он не содержит индуцированного подграфа, изоморфного одному из девяти запрещённых графов (список впервые приведён Бейнеке в 1970 году). Наиболее известный из них — это \( K_{1,3} \).

Алгоритмическое распознавание

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

Применение

В теории графов

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

В комбинаторике и информатике

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

В физике и биологии

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

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

• Линейный граф полного двудольного графа \( K_{m,n} \) изоморфен графу, известному как произведение двух полных графов \( K_m \) и \( K_n \) (граф Рейли).
• Существует обобщение понятия — линейный граф высшего порядка (k-й линейный граф), который строится итеративно: \( L^k(G) = L(L^{k-1}(G)) \). Для некоторых графов последовательность линейных графов стабилизируется или становится пустой.
• В теории матроидов линейный граф соответствует графу, ассоциированному с графовым матроидом (матроидом циклов).

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

Хотя линейные графы являются мощным инструментом, они имеют ограничения:

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

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