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

В теории графов рёберным графом 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)

Хордальные графы

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

Рёберные графы выпуклых многогранников

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

Если многогранник не простой (то есть имеет больше трёх граней на вершину), рёберный граф не будет плоским.

Срединный граф
Основная статья: Срединный граф

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

Свойства

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

Итак,

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

Характеристики и распознавание
Девять минимальных нерёберных графов, из характеристик Байнеке (Beineke) запрещённых подграфов рёберных графов. Граф является рёберным тогда и только тогда, когда он не содержит ни один из этих девяти графов в качестве порождённого подграфа.

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

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

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

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

Повторение операции построения рёберного графа

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

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

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

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

Связь с другими семействами графов

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

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

Обобщения

Мультиграфы

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

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

Можно также обобщить рёберные графы для ориентированных графов[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(k2) чаще в рёберном графе L(G). Таким образом, хотя теорема Уитни[10] гарантирует, что рёберный граф почти всегда содержит в себе закодированную топологию графа G, это не гарантирует, что эти два графа имеют простые динамические связи. Одно из решений этой проблемы — создать взвешенный рёберный граф, то есть, рёберный граф, у которого рёбра снабжены весом. Имеется несколько естественных путей сделать это[19]. Например, если рёбра d и e в графе G сопряжены в вершине v, имеющей степень k, то в рёберном графе L(G) ребру, соединяющему две вершины d и e, можно приписать вес 1/(k-1). Таким же образом любое ребро графа G (если только оно не соединено с вершиной степени 1) будет иметь вес 2 в рёберном графе L(G), что соответствует двум концам ребра в G.

Рёберные графы гиперграфов

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

Примечания
  1. O. Ore. Hamilton connected graphs // J. Math. Pures Appl. — 1963. — Т. 42. — С. 21—27.
  2. G. Sabidussi. Graphs with given group and given praph-theoretical properties // Canad. J. Math. — 1957. — Т. 9. — С. 515—525.
  3. L. W. Beineke. Beiträge zur Graphentheorie. — Leipzig: Teubner, 1968.
  4. Сешу С., Рид М. Линейные графы и электрические цепи. — М.: Высшая школа, 1971. — Т. 42. — С. 21—27.
  5. Kasteleyn P. W. A soluble self-avoiding walk problem // Physica. — 1968. — Т. 23. — С. 85—89.
  6. Menon V. On repeated interchange graphs // Amer Math Monthly. — 1966. — Т. 13. — С. 986—989.
  7. Ф. Харари. Теория графов = Graph Theory / Перевод с английского и предисловие В.П. Козырева. — 2. — М.: Едиториал УРСС, 2003. — 296 с.
  8. Balakrishnan V. K. Schaum's Outline of Graph Theory. — 1st. — McGraw-Hill, 1997. — ISBN 0-07-005489-4.
  9. R. L. Hemminger, L. W. Beineke. Selected Topics in Graph Theory. — Academic Press Inc., 1978. — С. 271—305.
  10. H. Whitney. Congruent graphs and the connectivity of graphs // American Journal of Mathematics. — 1932. — Т. 54, вып. 1. — С. 150—168. — doi:10.2307/2371086. — .
  11. J. Krausz. Démonstration nouvelle d'un théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. — 1943. — Т. 50. — С. 75—85.
  12. N. D. Roussopoulos. A max {m,n} algorithm for determining the graph H from its line graph G // Information Processing Letters. — 1973. — Т. 2, вып. 4. — С. 108—112. — doi:10.1016/0020-0190(73)90029-X.
  13. L. W. Beineke. Characterizations of derived graphs // Journal of Combinatorial Theory. — 1970. — Vol. 9. — С. 129—135. — doi:10.1016/S0021-9800(70)80019-9.
  14. Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Т. 25, вып. 4. — С. 243—251. — doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
  15. Weisstein, Eric W. Line Graph (англ.) на сайте Wolfram MathWorld.
  16. A. C. M. van Rooij, H. S. Wilf. The interchange graph of a finite graph // Acta Mathematica Hungarica. — 1965. — Т. 16, вып. 3—4. — С. 263—269. — doi:10.1007/BF01904834.
  17. Frank Harary, R. Z. Norman. Some properties of line digraphs // Rendiconti del Circolo Matematico di Palermo. — 1960. — Т. 9, вып. 2. — С. 161—169. — doi:10.1007/BF02854581.
  18. Fu Ji Zhang, Guo Ning Lin. On the de Bruijn–Good graphs // Acta Math. Sinica. — 1987. — Т. 30, вып. 2. — С. 195—205.
  19. T. S. Evans, R. Lambiotte. Line Graphs, Link Partitions and Overlapping Communities // Phys.Rev.E. — 2009. — Т. 80. — doi:10.1103/PhysRevE.80.016105.

Ссылки
  • 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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.