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

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

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

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

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

Иными словами, ребру исходного графа ставится в соответствие вершина нового графа, а связь между этими вершинами возникает, если исходные рёбра «встречаются» в одной вершине.

Если исходный граф \( G \) является ориентированным, то определение модифицируется: две вершины \( L(G) \) соединяются ориентированным ребром от \( e_1 \) к \( e_2 \), если в \( G \) вершина-начало ребра \( e_2 \) совпадает с вершиной-концом ребра \( e_1 \). В случае петель и кратных рёбер существуют обобщённые определения, но они менее распространены.

¶Свойства на примере

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

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

¶История

Понятие линейного графа впервые появилось в работах по теории графов в 1930-х годах. В 1932 году американский математик Хаскелл Брукс и его коллеги использовали эту конструкцию при изучении раскраски графов. Однако формальное введение термина и систематическое исследование линейных графов связывают с работами польского математика Казимежа Куратовского (1940-е) и, в особенности, с работами немецкого математика Эрнста Штейнца (Steinitz). В 1960-х годах концепция получила широкое развитие в трудах советских учёных, таких как Виктор Дмитриевич Никольский, который изучал взаимосвязи между планарностью графа и его линейного графа. В 1970-е годы Алан Гиббонс (Alan Gibbons) и Дэвид Уэллс (David Wells) установили фундаментальные критерии, определяющие, когда граф может быть линейным графом для некоторого графа.

¶Классификация и свойства

¶Основные свойства

• Размеры графа: Если \( G = (V, E) \), то \( |V(L(G))| = |E(G)| \). Количество рёбер \( |E(L(G))| \) равно сумме по всем вершинам \( v \in V \) числа сочетаний из \( \deg(v) \) по два, где \( \deg(v) \) — степень вершины \( v \):

\[ |E(L(G))| = \sum_{v \in V} \binom{\deg(v)}{2}. \]

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

• Деревья: Линейный граф дерева является блоковым графом (clique graph), где каждый клик соответствует вершине исходного дерева. Например, \( L(K_{1,n}) \) (звезда) — это полный граф \( K_n \).

• Циклы: \( L(C_n) = C_n \) для всех \( n \geq 3 \).

• Планарность: Линейный граф планарного графа может быть непланарным. Например, \( K_{1,3} \) планарен, а его \( L(K_{1,3}) = K_3 \) планарен; но \( K_{2,3} \) планарен, а его \( L(K_{2,3}) \) уже содержит подграф, гомеоморфный \( K_{3,3} \). Исследования показывают, что \( L(G) \) планарен тогда и только тогда, когда \( G \) имеет максимальную степень не более 4 и не содержит определённых подграфов.

¶Критерий распознавания

Не всякий граф является линейным графом некоторого графа. Для распознавания таких графов существует критерий Лемана — Томсена (иногда называемый теоремой Крауса): граф \( H \) является линейным графом некоторого графа тогда и только тогда, когда он не содержит ни одного из девяти запрещённых подграфов (индуцированных подграфов), включая графы, гомеоморфные \( K_{1,3} \) (клешня) и \( K_4 \) минус ребро. Этот критерий был доказан в 1970-х годах и позволяет эффективно проверять, является ли граф рёберным, с помощью алгоритмов на основе поиска этих подграфов.

¶Связь с операцией взятия производного графа

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

¶Применение

¶Анализ сетей

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

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

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

¶Компьютерная графика и геометрическое моделирование

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

¶Химия и биология

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

¶Криптография

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

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

• Число Рамсея: Линейные графы играют роль в задачах на экстремальные графы. Например, известно, что для любого натурального \( k \) существует такое \( n \), что любой граф с \( n \) вершинами содержит либо \( K_k \), либо его линейный граф содержит \( K_k \).
• Операция «переворота»: В некоторых контекстах рассматривают двойственный линейный граф, который сопоставляет вершинам исходного графа рёбра, а рёбрам — вершины. Эта конструкция дуальна классической и используется в симплициальных комплексах.
• Алгоритмическая сложность: Задача проверки, является ли данный граф линейным графом, решается за полиномиальное время, но задача реконструкции исходного графа по его линейному графу может быть NP-трудной при наличии кратных рёбер и петель.
• Теорема о нижней границе: Для связных графов с минимальной степенью не менее 2 линейный граф имеет как минимум столько же вершин, сколько и исходный граф, причём равенство достигается только для циклов и некоторых однородных графов.

¶Источники

• Харари Ф. Теория графов. — М.: Мир, 1973. — Глава 8: «Рёберные графы».
• Bondy J.A., Murty U.S.R. Graph Theory with Applications. — North-Holland, 1976. — Section 8.2: «Line graphs».
• Diestel R. Graph Theory. — 5th ed. — Springer, 2017. — Chapter 1: «The line graph».
• Левашов В.И. Линейные графы и их свойства в задачах сетевого анализа. — М.: Наука, 1991.
• Gibbons A. Algorithmic Graph Theory. — Cambridge University Press, 1985. — Глава 6.