Введение

Граф, представляющий рёбра другого графа – математическая концепция.

В математической дисциплине теории графов, линейный граф неориентированного графа G – это другой граф L(G), который представляет смежности между рёбрами G. L(G) строится следующим образом: для каждого ребра в G создаётся вершина в L(G); для любых двух рёбер в G, имеющих общую вершину, создаётся ребро между их соответствующими вершинами в L(G). Название «линейный граф» происходит из статьи, хотя данная конструкция использовалась и ранее. Другие термины, используемые для линейного графа, включают покрывающий граф, производную, двойственный граф «ребро-вершина», сопряжённый граф, репрезентативный граф и θ-образ, а также граф рёбер, граф перестановок, присоединённый граф и производный граф. Доказано, что в одном исключительном случае структуру связного графа G можно полностью восстановить из его линейного графа. Таким образом, линейный граф связного графа является связным. Если G связен, он содержит путь, соединяющий любые два его ребра, что соответствует пути в L(G), соединяющему любые две вершины L(G). Однако граф G, имеющий изолированные вершины и, следовательно, являющийся несвязным, тем не менее может иметь связный линейный граф. Линейный граф имеет точку сочленения тогда и только тогда, когда исходный граф имеет мост, ни один из концов которого не имеет степень 1. Независимое множество в L(G) соответствует полному сопряжению в G. В частности, максимальное независимое множество в L(G) соответствует максимальному полному сопряжению в G. Поскольку максимальные полные сопряжения могут быть найдены за полиномиальное время, то же самое справедливо и для максимальных независимых множеств линейных графов, несмотря на сложность задачи о максимальном независимом множестве для более общих семейств графов. Линейный граф краевого транзитивного графа является вершинно транзитивным. Это свойство можно использовать для генерации семейств графов, которые (как и граф Петерсена) являются вершинно транзитивными, но не являются графами Кейли: если G – краевой транзитивный граф, имеющий по крайней мере пять вершин, не являющийся двудольным и имеющий нечётные степени вершин, то L(G) является вершинно транзитивным графом, не являющимся графом Кейли. Если граф G имеет эйлеров цикл, то есть, если G связен и имеет чётное число рёбер на каждой вершине, то линейный граф G является гамильтоновым. Однако не все гамильтоновы циклы в линейных графах происходят из эйлеровых циклов таким образом; например, линейный граф гамильтонова графа G сам по себе является гамильтоновым, независимо от того, является ли G также эйлеровым. Если два простых графа изоморфны, то их линейные графы также изоморфны. Теорема об изоморфизме графов Уитни предоставляет обратное утверждение для всех пар связных графов, кроме одной. В контексте теории сложных сетей линейный граф случайной сети сохраняет многие свойства сети, такие как свойство малого мира (существование коротких путей между всеми парами вершин) и форму распределения степеней. Следует отметить, что любой метод поиска кластеров вершин в сложной сети может быть применен к линейному графу и использован для кластеризации его рёбер.

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

Если линейные графы двух связанных графов изоморфны, то и исходные графы изоморфны, за исключением треугольного графа и когтя, которые имеют изоморфные линейные графы, но сами не изоморфны. Помимо треугольного графа и когтя, существуют и другие исключительные малые графы, для которых линейный граф обладает большей степенью симметрии, чем сам граф. Например, алмазный граф (два треугольника, имеющих общий край) имеет четыре автоморфизма графа, а его линейный граф — восемь. На иллюстрации алмазного графа, показанной на рисунке, вращение графа на 90 градусов не является симметрией графа, но является симметрией его линейного графа. Однако все такие исключительные случаи содержат не более четырех вершин. Усиленная версия теоремы изоморфизма Уитни утверждает, что для связанных графов с более чем четырьмя вершинами существует взаимно однозначное соответствие между изоморфизмами графов и изоморфизмами их линейных графов. Аналоги теоремы изоморфизма Уитни доказаны для линейных графов мультиграфов, но в этом случае они более сложны. Их также можно охарактеризовать (опять же, за исключением когтя) как сильно регулярные графы с параметрами srg(n(n – 1)/2, 2(n – 2), n – 2, 4). Три сильно регулярных графа с теми же параметрами и спектром, что и графы Чанга, могут быть получены переключением графов. Линейный граф двудольного графа является совершенным (см. теорему Кёнига), но не обязательно двудольным, как показывает пример графа-когтя. Линейные графы двудольных графов образуют один из ключевых строительных блоков совершенных графов, используемых в доказательстве теоремы о сильных совершенных графах. Частным случаем таких графов являются графы ладей, являющиеся линейными графами полных двудольных графов. Как и линейные графы полных графов, они могут быть охарактеризованы, за одним исключением, по числу вершин, числу ребер и числу общих соседей для смежных и несмежных вершин. Единственным исключением является граф Шриханде, который имеет те же параметры. Когда обе стороны двудольного разбиения содержат одинаковое число вершин, эти графы снова являются сильно регулярными. В более общем смысле, граф G называется линейно-совершенным графом, если L(G) является совершенным графом. Линейно-совершенные графы — это графы, не содержащие простых циклов нечетной длины, большей трех. Эквивалентно, граф является линейно-совершенным тогда и только тогда, когда каждый из его двусвязных компонентов является либо двудольным, либо имеет вид тетраэдра, либо представляет собой книгу, состоящую из одного или нескольких треугольников, имеющих общий край. Каждый линейно-совершенный граф сам по себе совершенен.

Другие родственные семейства графиков

Все линейные графы — это графы без когтей, то есть графы, не содержащие индуцированного подграфа в виде дерева с тремя листьями. Эквивалентно, это означает, что если базовый граф G имеет чётное число рёбер, то его рёбра можно разбить на два рёберных пути. Линейные графы деревьев — это как раз блок-графы без когтей. Эти графы использовались для решения задачи в экстремальной теории графов, заключающейся в построении графа с заданным числом рёбер и вершин, у которого наибольшее дерево, индуцированное как подграф, имеет минимально возможный размер. Все собственные значения матрицы смежности A линейного графа не меньше −2. Это объясняется тем, что A можно представить в виде , где J — матрица знаковой инцидентности предлинейного графа, а I — единичная матрица. В частности, A + 2I является матрицей Грама некоторой системы векторов: все графы с этим свойством называются обобщёнными линейными графами.

Запрещенные подграфы

Еще одна характеристика линейных графов была доказана в (и ранее сообщалась без доказательства в). Он показал, что существует девять минимальных графов, не являющихся линейными, таких что любой граф, не являющийся линейным, содержит один из этих девяти графов в качестве индуцированного подграфа. Иными словами, граф является линейным тогда и только тогда, когда ни одно подмножество его вершин не индуцирует один из этих девяти графов. В приведенном выше примере четыре верхние вершины индуцируют структуру, называемую «когтем» (то есть полный двудольный граф K1,3), изображенную в верхнем левом углу иллюстрации запрещенных подграфов. Следовательно, согласно характеристике Бейнеке, этот пример не может быть линейным графом. Для графов с минимальной степенью не менее 5 в характеристике достаточно использовать только шесть подграфов, расположенных в левой и правой колонках рисунка.

Алгоритмы

и описали линейные по времени алгоритмы для распознавания линейных графов и восстановления исходных графов. обобщили эти методы на ориентированные графы. описали эффективную структуру данных для поддержки динамического графа, с учетом вставки и удаления вершин, и поддержания представления входных данных в виде линейного графа (если он существует) за время, пропорциональное количеству измененных ребер на каждом шаге. Алгоритмы и основаны на характеристиках линейных графов, связанных с нечетными треугольниками (треугольниками в линейном графе, обладающими свойством, что существует другая вершина, смежная с нечетным числом вершин треугольника). Однако алгоритм использует только теорему изоморфизма Уитни. Он усложняется необходимостью распознавать удаления, приводящие к тому, что оставшийся граф становится линейным графом, но при специализации на задаче статического распознавания необходимо выполнять только вставки, и алгоритм выполняет следующие шаги: построить входной граф L, добавляя вершины по одной, на каждом шаге выбирая вершину для добавления, смежную хотя бы с одной ранее добавленной вершиной. При добавлении вершин к L поддерживать граф G, для которого 1=L = L(G); если алгоритм когда-либо не сможет найти подходящий граф G, то входные данные не являются линейным графом, и алгоритм завершается. При добавлении вершины v к графу L(G), для которого G имеет четыре или менее вершин, может оказаться, что представление линейного графа не является единственным. Но в этом случае расширенный граф достаточно мал, чтобы его представление в виде линейного графа можно было найти полным перебором за постоянное время. При добавлении вершины v к большему графу L, который равен линейному графу другого графа G, пусть S будет подграфом G, образованным ребрами, соответствующими соседям v в L. Проверить, что у S есть вершинное покрытие, состоящее из одной вершины или двух несмежных вершин. Если в покрытии есть две вершины, расширить G, добавив ребро (соответствующее v), соединяющее эти две вершины. Если в покрытии только одна вершина, то добавить новую вершину к G, смежную с этой вершиной. Каждый шаг занимает постоянное время или включает поиск вершинного покрытия постоянного размера в графе S, размер которого пропорционален количеству соседей v. Таким образом, общее время работы алгоритма пропорционально сумме степеней всех вершин, которая (по лемме о рукопожатиях) пропорциональна количеству входных ребер.

Медиальные графы и выпуклые полиэдры

Когда плоский граф G имеет максимальную степень вершины равной трем, его линейный граф плоский, и любое плоское вложение G можно расширить до вложения L(G). Однако существуют плоские графы с более высокой степенью, линейные графы которых не являются плоскими. К ним относятся, например, 5-луч, граф, образованный добавлением двух непересекающихся диагоналей внутрь правильного пятиугольника, и все выпуклые многогранники с вершиной степени четыре или более. Альтернативная конструкция, медиальный граф, совпадает с линейным графом для плоских графов с максимальной степенью три, но всегда плоский. Он имеет те же вершины, что и линейный граф, но потенциально меньше ребер: две вершины медиального графа смежны тогда и только тогда, когда соответствующие два ребра последовательны на некотором гране плоского вложения. Медиальный граф двойственного графа планарного графа совпадает с медиальным графом исходного планарного графа. Для правильных или простых многогранников операция построения медиального графа может быть геометрически представлена операцией отсечения каждой вершины многогранника плоскостью, проходящей через середины всех его инцидентных ребер. Эта операция известна как вторая усечение, вырожденное усечение или ректификация.

Графики общего количества

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

Мультиграфы

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

Диграфы линий

Также можно обобщить линейные графы на ориентированные графы. Если G — ориентированный граф, то его ориентированный линейный граф, или линейный диграф, имеет одну вершину для каждого ребра G. Две вершины, представляющие ориентированные ребра из u в v и из w в x в G, соединены ребром из uv в wx в линейном диграфе, когда v = w. То есть каждое ребро в линейном диграфе G представляет собой ориентированный путь длины два в G. Графы де Брюйна могут быть сформированы путем повторения этого процесса построения ориентированных линейных графов, начиная с полного ориентированного графа.

Взвешенные линейные графики

В линейном графе L(G) каждая вершина степени k в исходном графе G порождает k(k − 1)/2 ребер в линейном графе. Для многих типов анализа это означает, что вершины высокой степени в G перепредставлены в линейном графе L(G). Например, рассмотрим случайное блуждание по вершинам исходного графа G. Оно будет проходить по некоторому ребру e с некоторой частотой f. С другой стороны, это ребро e отображается в уникальную вершину, скажем v, в линейном графе L(G). Если мы теперь выполним тот же тип случайного блуждания по вершинам линейного графа, частота посещения вершины v может существенно отличаться от f. Если ребро e в G соединено с вершинами степени O(k), то оно будет пересекаться чаще в линейном графе L(G). Иными словами, теорема об изоморфизме графов Уитни гарантирует, что линейный граф почти всегда точно кодирует топологию исходного графа G, но не гарантирует, что динамика на этих двух графах имеет простую взаимосвязь. Одним из решений является построение взвешенного линейного графа, то есть линейного графа с взвешенными ребрами. Существует несколько естественных способов это сделать. Например, если ребра d и e в графе G инцидентны вершине v степени k, то в линейном графе L(G) ребру, соединяющему вершины d и e, можно присвоить вес 1/(k − 1). Таким образом, каждое ребро в G (при условии, что ни один из его концов не соединен с вершиной степени 1) будет иметь вес 2 в линейном графе L(G), соответствующий двум концам этого ребра в G. Это определение взвешенного линейного графа можно легко расширить на случаи, когда исходный граф G ориентированный или даже взвешенный. Принцип во всех случаях заключается в том, чтобы линейный граф L(G) отражал не только топологию, но и динамику исходного графа G.

Линейные графики гиперграфиков

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

График разъединения

Граф разъединения графа G, обозначаемый D(G), строится следующим образом: для каждого ребра в G создаётся вершина в D(G); для любых двух рёбер в G, не имеющих общей вершины, проводится ребро между соответствующими им вершинами в D(G). Иными словами, D(G) является графом дополнений к графу L(G). Клике в D(G) соответствует независимое множество в L(G), и наоборот.