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

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

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

Построение

Двудольное двойное покрытие графа G имеет две вершины u_i и w_i для каждой вершины v_i графа G. Две вершины u_i и w_j связаны ребром в двойном покрытии тогда и только тогда, когда v_i и v_j связаны ребром в G. Например, ниже приведен рисунок двудольного двойного покрытия недвудольного графа H. На иллюстрации каждая вершина в тензорном произведении показана цветом из первого множителя (H), а форма вершины взята из второго множителя (K₂). Таким образом, вершины u_i в двойном покрытии показаны кружками, а вершины w_i показаны квадратиками.

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

Примеры

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

Двудольным двойным покрытием полного графа K_n является корона (полный двудольный граф K_n,n минус совершенное паросочетание). В частности, двудольным двойным покрытием графа тетраэдра, K₄, является граф куба.

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

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

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

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

а матрицей бисмежности^[англ.] двойного покрытия G является сама матрица A. То есть преобразование графа в его двойное покрытие может быть осуществлено просто путём толкования A как матрицы бисмежности, а не матрицы смежности. Более обще, толкование матриц смежности ориентированных графов как бисмежных матриц даёт комбинаторную эквивалентность между ориентированными графами и сбалансированными двудольными графами[1][2].

Свойства

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

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

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

Два различных графа могут иметь изоморфные двудольные двойные покрытия. Например, граф Дезарга является не только двудольным двойным покрытием графа Петерсена, но и также двудольным двойным покрытием другого графа, не изоморфного графу Петерсена[5]. Не любой двудольный граф является двудольным двойным покрытием другого графа. Чтобы двудольный граф G был двудольным покрытием другого графа, необходимо и достаточно, чтобы автоморфизмы графа G включали инволюцию, которая отображает каждую вершину в другую несмежную вершину[5]. Например, граф с двумя вершинами и одним ребром является двудольным, но не является двудольным двойным покрытием, поскольку он не содержит несмежных пар вершин, которые могут быть отображены друг друга такой инволюцией. С другой стороны, граф куба является двудольным двойным покрытием и имеет инволюцию, которая отображает каждую вершину в диаметрально противоположную вершину. Альтернативное описание двудольных графов, которые могут быть образованы построением двудольного двойного покрытия, были получены Сампаткумаром[6].

Другие двойные покрытия

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

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

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

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

В качестве другого примера граф икосаэдра является двойным покрытием полного графа K₆. Чтобы получить покрывающее отображение из графа икосаэдра в K₆, отобразим каждую пару противоположных вершин икосаэдра в одну вершину графа K₆. Однако икосаэдр не является двудольным, так что граф икосаэдра не является двудольным двойным покрытием графа K₆. Вместо этого двудольное двойное покрытие может быть получено как ориентируемое двойное покрытие^[англ.] вложения графа K₆ в проективную плоскость.

Примечания

1. Dulmage, Mendelsohn, 1958.
2. Brualdi, Harary, Miller, 1980.
3. Brualdi, Harary, Miller, 1980, с. Theorem 3.4.
4. Feng, Kutnar, Malnič, Marušic, 2008.
5. Imrich, Pisanski, 2008.
6. Sampathkumar, 1975.
7. Waller, 1976.

Литература

• Richard A. Brualdi, Frank Harary, Zevi Miller. Bigraphs versus digraphs via matrices // Journal of Graph Theory. — 1980. — Т. 4, вып. 1. — С. 51–73. — doi:10.1002/jgt.3190040107.
• A. L. Dulmage, N. S. Mendelsohn. Coverings of bipartite graphs // Canadian Journal of Mathematics. — 1958. — Т. 10. — С. 517–534. — doi:10.4153/CJM-1958-052-0.. «Coverings» в заглавии статьи относится к задаче о вершинном покрытии, а не к двудольному двойному покрытию. Однко, Бруалди, Харари и Миллер (Brualdi, Harary, Miller 1980)цитируют эту статью как источник идеи интерпретации матрицы смежности как матрицы бисмежности.
• Yan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, Dragan Marušic. On 2-fold covers of graphs // Journal of Combinatorial Theory, Series B. — 2008. — Т. 98, вып. 2. — С. 324–341. — doi:10.1016/j.jctb.2007.07.001. — arXiv:math.CO/0701722.
• Wilfried Imrich, Tomaž Pisanski. Multiple Kronecker covering graphs // European Journal of Combinatorics. — 2008. — Т. 29, вып. 5. — С. 1116–1122. — doi:10.1016/j.ejc.2007.07.001.
• E. Sampathkumar. On tensor product graphs // Journal of the Australian Mathematical Society, Series A, Pure Mathematics and Statistics. — 1975. — Т. 20, вып. 3. — С. 268–273. — doi:10.1017/S1446788700020619.
• Derek A. Waller. Double covers of graphs // Bulletin of the Australian Mathematical Society. — 1976. — Т. 14, вып. 2. — С. 233–248. — doi:10.1017/S0004972700025053.

Ссылки

• Weisstein, Eric W. Bipartite Double Graph (англ.) на сайте Wolfram MathWorld.