Рёберный граф

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

Понятие рёберного графа для данного графа настолько естественно, что независимо было введено многими авторами. Конечно, каждый из них давал своё название: Оре^[1] назвал этот граф «смежностным графом», Сабидусси^[2] — «графом производной», Байнеке^[3] — «производным графом», Сешу и Рид^[4] — «рёберно-вершинно-двойственным», Кастелейн^[5] — «покрывающим графом», Менон^[6] — «присоединённым» («сопряжённым»)^[7][8][9].

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

Формальное определение[править | править код]

Пусть задан граф G, тогда его рёберный граф L(G) — это такой граф, что

• любая вершина графа L(G) представляет ребро графа G
• две вершины графа L(G) смежны тогда и только тогда, когда их соответствующие рёбра имеют общую вершину («смежны») в G.

Примеры[править | править код]

Пример построения[править | править код]

Следующий рисунок показывает граф (слева, с синими вершинами) и его рёберный граф (справа, с зелёными вершинами). Каждая вершина рёберного графа помечена парой номеров вершин соответствующего ребра в исходном графе. Например, зелёная вершина справа с меткой 1,3 соответствует ребру слева между голубыми вершинами 1 и 3. Зелёная вершина 1,3 смежна трём другим зелёным вершинам: 1,4, 1,2 (соответствующей рёбрам с общей вершиной 1 в синем графе) и 4,3 (соответствующей рёбрам с общей вершиной 3 в синем графе).

• 
  Граф G
• 
  Вершины L(G), созданные из ребер графа G
• 
  Добавлены рёбра в L(G)
• 
  Рёберный граф L(G)

Хордальные графы[править | править код]

Рёберный граф полного графа K_n известен как хордальный граф (или триангулированный граф). Важной теоремой о хордальных графах является теорема, утверждающая, что хордальный граф характеризуется спектром, за исключением n = 8, когда имеется три других графа с тем же спектром, что и у L(K₈). Исключения объяснены в переключении графов.

Рёберные графы выпуклых многогранников[править | править код]

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

Срединный граф[править | править код]

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

Свойства[править | править код]

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

Итак,

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

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

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

Характеристики и распознавание[править | править код]

Граф G является рёберным графом какого-либо другого графа в том и только в том случае, когда можно найти набор клик в G, разбивающих дуги графа G так, что каждая вершина G принадлежит в точности двум кликам. Может случиться, что для достижения этого потребуется отдельные вершины выделить в клики. По теореме Уитни ^[10][11], если G не является треугольником, может быть только одно разбиение такого рода. Если разбиение существует, мы можем построить граф, для которого G будет рёберным графом путём создания вершины для каждой клики и соединением полученных вершин ребром, если вершина принадлежит обоим кликам. Таким образом, за исключением ${\displaystyle K_{3}}$ и ${\displaystyle K_{1,3}}$, если два рёберных графа связных графов изоморфны, то и графы изоморфны. Русопоулос (Roussopoulos)^[12] использовал это наблюдение как базис для линейного по времени алгоритма распознавания рёберных графов и реконструкции их исходных графов.

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

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

Другая характеристика графа была доказана Байнеке^[13] (и упомянута без доказательства ранее им же^[3]). Он показал, что имеется девять минимальных графов, не являющихся рёберными, таких, что любой граф, не являющийся рёберным, содержит один из этих девяти графов в качестве порождённого подграфа. Таким образом, граф является рёберным тогда и только тогда, когда никакое подмножество вершин не порождает один из этих девяти. В примере выше четыре верхних вершины порождают клешню (то есть, полный двудольный граф K_1,3), показанный вверху слева иллюстрации запрещённых подграфов. Таким образом, по характеристике Байнеке, этот граф не может быть рёберным. Для графов со степенью вершин не менее 5 только шесть подграфов в левом и правом столбцах рисунка могут порождаться графом^[14]. Этот результат похож на результат для рёберных графов гиперграфа^[15].

Повторение операции построения рёберного графа[править | править код]

Руидж и Вильф^[16] рассмотрели последовательность графов

${\displaystyle G,L(G),L(L(G)),L(L(L(G))),\dots .\ }$

Они показали, что для конечного графа связного графа G возможны только четыре вида поведения этой последовательности:

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

Если G несвязен, то эта классификация применима к каждой отдельной компоненте связности графа G.

Связь с другими семействами графов[править | править код]

Любой рёберный граф не содержит клешней.

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

Обобщения[править | править код]

Мультиграфы[править | править код]

Концепция рёберного графа для графа G может быть естественным образом распространена на случай, когда G является мультиграфом, хотя, в этом случае теорема Уитни о единственности становится неверной. Например, полный двудольный граф K_1,n имеет тот же рёберныё граф, что и дипольный граф^[en] и мультиграф Шеннона с тем же числом рёбер.

Рёберные орграфы[править | править код]

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

Взвешеные рёберные графы[править | править код]

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

Рёберные графы гиперграфов[править | править код]

Рёбра гиперграфа могут формировать любые семейства множеств, так что рёберный граф гиперграфа — это то же самое, что и граф пересечений множеств семейства.

Примечания[править | править код]

Ссылки[править | править код]

• Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X..

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.