Двусторонняя двойная крышка

В теории графов двудольное двойное покрытие неориентированного графа G является двудольным покрывающим графом G G. с вдвое большим вершин чем , количеством Его можно построить как графов тензорное произведение G × K ₂ . Его также называют накрытием Кронекера , каноническим двойным накрытием просто двудольным двойником G. или двойным

Его не следует путать с циклическим двойным покрытием графа, семейством циклов, включающим каждое ребро дважды.

Строительство

Двудольное двойное покрытие G вершины u _i и w _i для каждой вершины vi _группы G имеет две . Две вершины u _i и w _j соединены ребром в двойном покрытии тогда и только тогда, когда v _j vi и соединены _ребром в G . Например, ниже приведена иллюстрация двудольного двойного покрытия недвудольного графа G . На иллюстрации каждая вершина тензорного произведения показана с использованием цвета первого члена произведения ( G ) и формы второго члена произведения ( K ₂ ); поэтому вершины ui _wi в двойном покрытии показаны кружками, а вершины — _{квадратами} .

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

Примеры

Двудольное двойное покрытие графа Петерсена — это граф Дезарга : K ₂ × G (5,2) = G (10,3) .

Двудольное двудольное покрытие полного графа является _n графом -короной ( полный двудольный граф Kn _{, . Kn} минус совершенное паросочетание ) двудольное двойное покрытие графа тетраэдра В частности , К ₄ является графом куба .

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

Матричная интерпретация

Если неориентированный граф G имеет матрицу A в качестве матрицы смежности , то матрица смежности двойного покрытия G равна

$\left[{\begin{matrix}0&A\\A^{T}&0\end{matrix}}\right],$

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

Характеристики

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

Двудольное двойное покрытие является частным случаем двойного покрытия (двухкратного накрывающего графа ). Двойное накрытие в теории графов можно рассматривать как частный случай топологического двойного накрытия .

Если G — недвудольный симметричный граф , двойное покрытие G также является симметричным графом; несколько известных кубических Таким способом можно получить симметричных графов. Например, двойное покрытие K ₄ является графиком куба; двойное покрытие графа Петерсена — граф Дезарга; а двойное покрытие графа додекаэдра представляет собой симметричный кубический граф с 40 вершинами.

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

Имя

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

Другие двойные обложки

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

1. Граф C является покрывающим графом H , если существует сюръективный локальный изоморфизм f из C в H . На рисунке сюръекция обозначена цветами. Например, f сопоставляет оба синих узла в C с синим узлом H. в Более того, пусть X — окрестность синего узла в C , а Y — окрестность синего узла в H ; ограничение f на X является биекцией X Y на тогда . В частности, степень каждого синего узла одинакова. То же самое касается каждого цвета.
2. Граф C является двойным покрытием (или 2-кратным покрытием , или 2-лифтом ) графа H , если прообраз каждого узла в H имеет размер 2. В этом примере ровно 2 узла в C сопоставлены с синим узлом. в Х. ​

На следующем рисунке граф C является двойным покрытием графа H :

Однако C не является двудольным двойным покрытием H ; или любого другого графа это не двудольный граф.

Если мы заменим один треугольник квадратом в H, то в полученном графе будет четыре различных двойных числа. крышки. Два из них двудольные, но только один из них является кронекеровским покрытием.

Другой пример: граф икосаэдра является двойным покрытием полного графа K ₆ ; Чтобы получить карту покрытия икосаэдра в K ₆ , отобразите каждую пару противоположных вершин икосаэдра в одну вершину K ₆ . Однако икосаэдр не двудольный, поэтому он не является двудольным двойным покрытием К ₆ . можно получить как ориентируемое двойное накрытие K6 вложения на его _{Вместо этого} проективную плоскость .

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

См. также

• Двусторонняя половина

Ссылки

• Бруальди, Ричард А.; Харари, Фрэнк ; Миллер, Цви (1980), «Биграфы против орграфов через матрицы», Журнал теории графов , 4 (1): 51–73, doi : 10.1002/jgt.3190040107 , MR   0558453 .
• Далмейдж, Алабама; Мендельсон, Н.С. (1958), «Покрытия двудольных графов», Canadian Journal of Mathematics , 10 : 517–534, doi : 10.4153/CJM-1958-052-0 , MR   0097069 . «Покрытия» в названии статьи относятся к проблеме вершинного покрытия , а не к двудольным двойным покрытиям. Однако Бруальди, Харари и Миллер (1980) цитируют эту статью как источник идеи переосмысления матрицы смежности как матрицы двусмежности.
• Фэн, Янь-Цюань; Кутнар, Клавдия ; Мальнич, Александр; Марушич, Драган (2008), «О двукратных покрытиях графов», Журнал комбинаторной теории , серия B, 98 (2): 324–341, arXiv : math.CO/0701722 , doi : 10.1016/j.jctb. 2007.07.001 , МР   2389602 , S2CID   8626473 .
• Имрих, Вильфрид; Писански, Томаж (2008), «Множественные покрывающие графы Кронекера», Европейский журнал комбинаторики , 29 (5): 1116–1122, arXiv : math/0505135 , doi : 10.1016/j.ejc.2007.07.001 , MR   2419215 , S2CID   29878870 .
• Писанский, Томаж (2018), «Не всякая двудольная двойная обложка канонична», Бюллетень ICA , 82 : 51–55.
• Сампаткумар, Э. (1975), «О графах тензорных произведений», Журнал Австралийского математического общества , 20 (3): 268–273, doi : 10.1017/S1446788700020619 , MR   0389681 .
• Уоллер, Дерек А. (1976), «Двойные покрытия графов» (PDF) , Бюллетень Австралийского математического общества , 14 (2): 233–248, doi : 10.1017/S0004972700025053 , hdl : 10338.dmlcz/101887 , MR   0406876 .

Внешние ссылки

• Вайсштейн, Эрик В. «Двудольный двойной граф» . Математический мир .