В математической дисциплине теории графов линейный граф неориентированного графа G — это другой граф L( G ) , который представляет смежности между ребрами G. L( G ) строится следующим образом: для каждого ребра в G создаём вершину в L( G ) ; для каждых двух ребер в G , имеющих общую вершину, создайте ребро между соответствующими им вершинами в L( G ) .
График линии имени взят из статьи Харари и Нормана (1960), хотя и Уитни (1932), и Крауш (1943) использовали эту конструкцию до этого. [1] Другие термины, используемые для линейного графа, включают покрывающий граф , производную , двойственный ребро к вершине , сопряженный граф , представительный граф и θ-образ , [1] а также граф ребер , граф обмена , присоединенный граф и производный граф . [2]
Хасслер-Уитни (1932) доказал, что за одним исключительным случаем структура связного графа G может быть полностью восстановлена по его линейному графу. [3] Многие другие свойства линейных графов возникают в результате перевода свойств основного графа из вершин в ребра, а по теореме Уитни тот же перевод можно выполнить и в другом направлении. Линейные графы не имеют когтей , а линейные графы двудольных графов совершенны . Линейные графы характеризуются девятью запрещенными подграфами и могут быть распознаны за линейное время .
Были изучены различные расширения концепции линейного графа, включая линейные графы линейных графов, линейные графы мультиграфов, линейные графики гиперграфов и линейные графики взвешенных графов.
Для данного графа G его линейный граф L ( G ) является графом таким, что
То есть это граф пересечений ребер G , представляющий каждое ребро набором двух его конечных точек. [2]
На следующих рисунках показан граф (слева, с синими вершинами) и его линейный график (справа, с зелеными вершинами). Каждая вершина линейного графа помечена парой конечных точек соответствующего ребра исходного графа. Например, зеленая вершина справа, обозначенная 1,3, соответствует ребру слева между синими вершинами 1 и 3. Зеленая вершина 1,3 соседствует с тремя другими зелеными вершинами: 1,4 и 1,2 (соответствующие к ребрам, имеющим общую конечную точку 1 на синем графике) и 4,3 (соответствует ребру, разделяющему конечную точку 3 на синем графике).
Свойства графа G , которые зависят только от смежности между ребрами, можно перевести в эквивалентные свойства в L ( G ) , которые зависят от смежности между вершинами. Например, паросочетание в G — это набор ребер, ни одно из которых не является смежным, и соответствует множеству вершин в L ( G ) , ни одно из которых не является смежным, то есть независимому множеству . [4]
Таким образом,
Если линейные графы двух связных графов изоморфны, то лежащие в их основе графы изоморфны, за исключением случая треугольного графа K 3 и клешни K 1,3 , которые имеют изоморфные линейные графы, но сами не изоморфны. [3]
Помимо K 3 и K 1,3 , существуют еще несколько исключительных маленьких графов, свойство которых состоит в том, что их линейный граф имеет более высокую степень симметрии, чем сам граф. Например, ромбовидный граф K 1,1,2 (два треугольника с общим ребром) имеет четыре автоморфизма графа , а линейный граф K 1,2,2 — восемь. На иллюстрации показанного ромбовидного графика поворот графика на 90 градусов не является симметрией графика, а является симметрией его линейного графика. Однако все такие исключительные случаи имеют не более четырех вершин. Усиленная версия теоремы об изоморфизме Уитни утверждает, что для связных графов с более чем четырьмя вершинами существует взаимно однозначное соответствие между изоморфизмами графов и изоморфизмами их линейных графов. [11]
Аналоги теоремы об изоморфизме Уитни доказаны для линейных графов мультиграфов , но в этом случае они более сложны. [12]
Линейный граф полного графа Kn также известен как треугольный граф , граф Джонсона J ( n ,2) или дополнение к графу Кнезера KGn ,2 . Треугольные графы характеризуются своими спектрами , за исключением n = 8 . [13] Их также можно охарактеризовать (опять же за исключением K 8 ) как сильно регулярные графы с параметрами srg( n ( n – 1)/2, 2( n – 2), n – 2, 4) . [14] Три сильно регулярных графа с теми же параметрами и спектром, что и L ( K8 ) , являются графами Чанга , которые могут быть получены переключением графа с L ( K8 ) .
Линейный график двудольного графа идеален (см. теорему Кенига ), но не обязательно должен быть двудольным, как показывает пример когтевого графа. Линейные графы двудольных графов образуют один из ключевых строительных блоков совершенных графов, используемых в доказательстве сильной теоремы о совершенном графе . [15] Частным случаем этих графов являются ладейные графы , линейные графы полных двудольных графов . Подобно линейным графам полных графов, они, за одним исключением, могут быть охарактеризованы количеством вершин, количеством ребер и количеством общих соседей для смежных и несмежных точек. Единственным исключительным случаем является L ( K 4,4 ) , параметры которого совпадают с графом Шрикханде . Когда обе стороны двуразделения имеют одинаковое количество вершин, эти графы снова становятся строго регулярными. [16]
В более общем смысле, граф G называется линейным совершенным графом, если L ( G ) — совершенный граф . Линейно-совершенные графы — это именно те графы, которые не содержат простых циклов нечетной длины, большей трех. [17] Аналогично, граф является линейно совершенным тогда и только тогда, когда каждый из его двусвязных компонентов либо двудольный, либо имеет форму K 4 (тетраэдр) или K 1,1, n (книга из одного или нескольких треугольников, имеющих общий общий край). [18] Каждый линейный совершенный граф сам по себе совершенен. [19]
Все линейные графы являются графами без клешней , графами без индуцированного подграфа в виде трехлистного дерева. [20] Как и в случае с графами без когтей в более общем смысле, каждый связный линейный граф L ( G ) с четным числом ребер имеет идеальное паросочетание ; [21] эквивалентно, это означает, что если базовый граф G имеет четное количество ребер, его ребра можно разделить на пути с двумя ребрами.
Линейные графы деревьев — это в точности блочные графы без клешней . [22] Эти графы использовались для решения задачи экстремальной теории графов : построения графа с заданным числом ребер и вершин, наибольшее дерево которого, индуцированное как подграф, было бы как можно меньшим. [23]
Все собственные значения матрицы смежности A линейного графа не меньше −2. Причина этого в том, что A можно записать как , где J — беззнаковая матрица инцидентности графа перед строкой, а I — единица. В частности, A + 2 I — матрица Грама системы векторов: все графы с этим свойством называются обобщенными линейными графами. [24]
Для произвольного графа G и произвольной вершины v в G множество ребер, инцидентных v, соответствует клике в линейном графе L ( G ) . Образовавшиеся таким образом клики разбивают ребра L ( G ) . Каждая вершина L ( G ) принадлежит ровно двум из них (двум кликам, соответствующим двум концам соответствующего ребра в G ).
Существование такого разбиения на клики можно использовать для характеристики линейных графов: Граф L является линейным графом некоторого другого графа или мультиграфа тогда и только тогда, когда в L можно найти набор клик (допуская некоторые из клики быть одиночными вершинами), которые разделяют ребра L , так что каждая вершина L принадлежит ровно двум кликам. [20] Это линейный граф графа (а не мультиграф), если этот набор клик удовлетворяет дополнительному условию, согласно которому никакие две вершины L не находятся одновременно в одних и тех же двух кликах. Учитывая такое семейство клик, базовый граф G , для которого L является линейным графом, может быть восстановлен путем создания одной вершины в G для каждой клики и ребра в G для каждой вершины в L , конечными точками которого являются две клики, содержащие вершина в L . Согласно сильной версии теоремы об изоморфизме Уитни, если базовый граф G имеет более четырех вершин, может быть только одно разбиение этого типа.
Например, эту характеристику можно использовать, чтобы показать, что следующий график не является линейным:
В этом примере ребра, идущие вверх, влево и вправо от центральной вершины четвертой степени, не имеют общих клик. Следовательно, любое разделение ребер графа на клики должно иметь по крайней мере одну клику для каждого из этих трех ребер, и все эти три клики будут пересекаться в этой центральной вершине, что нарушает требование, чтобы каждая вершина появлялась ровно в двух кликах. Таким образом, показанный график не является линейным.
Другая характеристика линейных графов была доказана Бейнеке (1970) (и ранее сообщена без доказательства Бейнеке (1968)). Он показал, что существует девять минимальных графов, не являющихся линейными, так что любой граф, не являющийся линейным, имеет один из этих девяти графов в качестве индуцированного подграфа . То есть граф является линейным тогда и только тогда, когда ни одно подмножество его вершин не порождает ни один из этих девяти графов. В приведенном выше примере четыре самые верхние вершины образуют клешню (то есть полный двудольный граф K 1,3 ), показанную в левом верхнем углу иллюстрации запрещенных подграфов. Следовательно, по характеристике Бейнеке, этот пример не может быть линейным графиком. Для графов с минимальной степенью не ниже 5 для характеристики необходимы только шесть подграфов в левом и правом столбцах рисунка. [25]
Руссопулос (1973) и Лехот (1974) описали алгоритмы с линейным временем для распознавания линейных графов и восстановления их исходных графов. Сысло (1982) обобщил эти методы на ориентированные графы . Дегиорджи и Саймон (1995) описали эффективную структуру данных для поддержания динамического графа, допускающего вставку и удаление вершин, а также поддержания представления входных данных в виде линейного графа (если он существует) за время, пропорциональное количеству измененных ребер в точке. каждый шаг.
Алгоритмы Руссопулоса (1973) и Лего (1974) основаны на характеристиках линейных графов, включающих нечетные треугольники (треугольники в линейном графе со свойством, что существует еще одна вершина, смежная с нечетным числом вершин треугольника). Однако алгоритм Дегиорджи и Саймона (1995) использует только теорему об изоморфизме Уитни. Это осложняется необходимостью распознавать удаления, из-за которых оставшийся граф становится линейным, но при специализации на задаче статического распознавания необходимо выполнять только вставки, и алгоритм выполняет следующие шаги:
Каждый шаг либо занимает постоянное время, либо включает в себя поиск вершинного покрытия постоянного размера в графе S , размер которого пропорционален количеству соседей v . Таким образом, общее время всего алгоритма пропорционально сумме чисел соседей всех вершин, которая (по лемме о квитировании ) пропорциональна количеству входных ребер.
ван Рой и Уилф (1965) рассматривают последовательность графов
Они показывают, что, когда G — конечный связный граф , для этой последовательности возможны только четыре поведения:
Если G не связен, эта классификация применяется отдельно к каждому компоненту G.
Для связных графов, которые не являются путями, все достаточно большие числа итераций операции линейного графа создают гамильтоновы графы. [27]
Когда планарный граф G имеет максимальную степень вершины три, его линейный граф является плоским, и каждое плоское вложение G может быть расширено до вложения L ( G ) . Однако существуют планарные графы более высокой степени, линейные графы которых непланарны. К ним относятся, например, 5-звездочка К 1,5 , граф драгоценного камня, образованный сложением двух непересекающихся диагоналей внутри правильного пятиугольника, и все выпуклые многогранники с вершиной четвертой и более степени. [28]
Альтернативная конструкция — медиальный граф — совпадает с линейным графом для планарных графов максимальной степени три, но всегда является планарным. Он имеет те же вершины, что и линейный граф, но потенциально меньше ребер: две вершины медиального графа смежны тогда и только тогда, когда соответствующие два ребра последовательны на некоторой грани плоского вложения. Медиальный граф двойственного графа плоского графа такой же, как медиальный граф исходного плоского графа. [29]
Для правильных многогранников или простых многогранников операцию медиального графа можно представить геометрически операцией отсечения каждой вершины многогранника плоскостью через середины всех его инцидентных ребер. [30] Эта операция известна по-разному как второе усечение, [31] вырожденное усечение, [32] или выпрямление . [33]
Полный граф T ( G ) графа G имеет в качестве вершин элементы (вершины или ребра) G и имеет ребро между двумя элементами всякий раз, когда они инцидентны или смежны. Полный граф также может быть получен путем разделения каждого ребра G и последующего возведения квадрата разделенного графа. [34]
Понятие линейного графа G естественным образом может быть распространено на случай, когда G является мультиграфом. В этом случае характеристики этих графов можно упростить: при характеризации в терминах кликовых разбиений больше нет необходимости предотвращать принадлежность двух вершин к одним и тем же кликам, а при характеризации запрещенными графами имеется семь запрещенных графов вместо девяти. [35]
Однако для мультиграфов существует большее количество пар неизоморфных графов, имеющих одинаковые линейные графы. Например, полный двудольный граф K 1, n имеет тот же линейный граф, что и дипольный граф и мультиграф Шеннона с тем же количеством ребер. Тем не менее аналоги теоремы Уитни об изоморфизме и в этом случае все же можно вывести. [12]
Также возможно обобщить линейные графы до ориентированных графов. [36] Если G — ориентированный граф, его ориентированный линейный граф или линейный орграф имеет по одной вершине для каждого ребра G . Две вершины, представляющие направленные ребра от u до v и от w до x в G , соединены ребром от uv до wx в линейном орграфе, когда v = w . То есть каждое ребро в линейном орграфе G представляет собой направленный путь длины два в G . Графы де Брейна могут быть сформированы путем повторения этого процесса формирования ориентированных линейных графов, начиная с полного ориентированного графа . [37]
В линейном графе 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 ) оно будет проходиться O ( k2 ) чаще . Другими словами, теорема об изоморфизме графа Уитни гарантирует, что линейный граф почти всегда точно кодирует топологию исходного графа G , но не гарантирует, что динамика на этих двух графах имеет простую связь. Одним из решений является построение взвешенного линейного графа, то есть линейного графа с взвешенными ребрами . Есть несколько естественных способов сделать это. [38] Например, если ребра d и e в графе G инцидентны вершине v степени k , то в линейном графе L ( G ) ребру, соединяющему две вершины d и e , можно присвоить вес 1/( k − 1) . Таким образом, каждое ребро в G ( при условии, что ни один конец не соединен с вершиной степени 1) будет иметь силу 2 в линейном графе L ( G ) , что соответствует двум концам, которые ребро имеет в G. Это определение взвешенного линейного графа несложно распространить на случаи, когда исходный граф G был направленным или даже взвешенным. [39] Принцип во всех случаях заключается в том, чтобы линейный граф L ( G ) отражал динамику, а также топологию исходного графа G.
Ребра гиперграфа могут образовывать произвольное семейство множеств , поэтому линейный граф гиперграфа совпадает с графом пересечений множеств из семейства.
Граф дизъюнктности графа G , обозначаемый D ( G ) , строится следующим образом: для каждого ребра в G создаём вершину в D ( G ) ; для каждых двух ребер в G , не имеющих общей вершины, создайте ребро между соответствующими им вершинами в D ( G ) . [40] Другими словами, D ( G ) является графом дополнений L ( G ) . Клика в D ( G ) соответствует независимому множеству в L ( G ) , и наоборот.
, что существует взаимно однозначное соответствие между паросочетаниями графа и независимыми множествами его линейного графа.