Производный граф

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

История

Понятие производного графа впервые было введено в 1932 году американским математиком Хасслером Уитни в его работе «Congruent Graphs and the Connectivity of Graphs». Уитни исследовал связь между изоморфизмом графов и их производных, доказав, что для связных графов, за исключением треугольника \(K_3\), производный граф однозначно определяет исходный. Впоследствии, в 1960-х годах, концепция была развита в работах Фрэнка Харари и других учёных, которые систематизировали свойства производных графов и их применение в теории графов и комбинаторике.

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

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

В случае ориентированного графа \( \vec{G} = (V, \vec{E}) \) производный граф \( L(\vec{G}) \) строится аналогично, но смежность рёбер определяется направлением: вершины \( \vec{e}_1 \) и \( \vec{e}_2 \) соединяются ребром, если конечная вершина \( \vec{e}_1 \) совпадает с начальной вершиной \( \vec{e}_2 \). Таким образом, производный граф для ориентированного графа также является ориентированным.

Пример

Рассмотрим простой граф \( G \) с вершинами \( \{1, 2, 3\} \) и рёбрами \( \{a = (1,2), b = (2,3), c = (1,3)\} \). Рёбра \( a \) и \( b \) имеют общую вершину \( 2 \), \( a \) и \( c \) — вершину \( 1 \), \( b \) и \( c \) — вершину \( 3 \). Следовательно, производный граф \( L(G) \) будет полным графом \( K_3 \) с вершинами \( a, b, c \), где каждая пара вершин соединена ребром.

Свойства производных графов

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

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

• Число вершин и рёбер: Если исходный граф \( G \) имеет \( n \) вершин и \( m \) рёбер, то \( L(G) \) содержит ровно \( m \) вершин. Число рёбер в \( L(G) \) равно \( \sum_{v \in V} \binom{\deg(v)}{2} \), где \( \deg(v) \) — степень вершины \( v \) в \( G \). Это следует из того, что каждая вершина степени \( d \) в \( G \) порождает \( \binom{d}{2} \) пар смежных рёбер.
• Степени вершин: Степень вершины \( e = (u, v) \) в \( L(G) \) равна \( \deg(u) + \deg(v) - 2 \), так как ребро \( e \) смежно с \( \deg(u) - 1 \) другими рёбрами, инцидентными \( u \), и \( \deg(v) - 1 \) рёбрами, инцидентными \( v \).
• Связность: Если \( G \) связен и не является изолированной вершиной, то \( L(G) \) также связен. Однако обратное неверно: производный граф может быть связным, даже если \( G \) несвязен, при условии, что рёбра из разных компонент соединены через общие вершины (что невозможно для простых графов).
• Клики: Каждая вершина степени \( d \) в \( G \) порождает клику размера \( d \) в \( L(G) \), состоящую из всех рёбер, инцидентных этой вершине. Эти клики могут пересекаться по вершинам, соответствующим рёбрам, соединяющим две вершины высокой степени.
• Изоморфизм: Теорема Уитни утверждает, что для связных графов, за исключением треугольника \( K_3 \), изоморфизм производных графов \( L(G) \cong L(H) \) влечёт изоморфизм исходных графов \( G \cong H \). Исключение составляет случай, когда \( G \) и \( H \) — это \( K_3 \) и \( K_{1,3} \) (звезда с тремя листьями), так как оба имеют производный граф \( K_3 \).

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

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

Классификация и распознавание

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

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

Один из наиболее известных критериев был предложен Лоуренсом Байнеке в 1968 году. Граф \( H \) является производным графом некоторого графа \( G \) тогда и только тогда, когда \( H \) не содержит в качестве порождённого подграфа ни один из девяти запрещённых графов (так называемых «запрещённых подграфов Байнеке»). Эти графы включают, например, звезду \( K_{1,3} \) (клешню) и некоторые другие небольшие графы с 4–6 вершинами.

Алгоритмы распознавания

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

Применение

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

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

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

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

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

В биологии и химии

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

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

• Производный граф полного графа \( K_n \) является графом Джонсона \( J(n, 2) \), вершины которого — все 2-элементные подмножества множества из \( n \) элементов, а рёбра соединяют подмножества с непустым пересечением.
• Для дерева \( T \) производный граф \( L(T) \) является хордальным графом, то есть не содержит индуцированных циклов длины больше 3.
• Существует обобщение понятия производного графа на гиперграфы, где рёбра могут соединять более двух вершин. В этом случае производный граф строится на основе пересечений гиперрёбер.

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

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

Источники

• Уитни, Х. (1932). «Congruent Graphs and the Connectivity of Graphs». American Journal of Mathematics.
• Харари, Ф. (1969). «Теория графов». Мир.
• Байнеке, Л. (1968). «Characterizations of Derived Graphs». Journal of Combinatorial Theory.
• Дистель, Р. (2000). «Теория графов». Новосибирск: Издательство Института математики.
• Уэст, Д. (2001). «Введение в теорию графов». Вильямс.