PROFILPELAJAR.COM

Двудольное двойное покрытие неориентированного графа 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 равна

\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:

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

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

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

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

Примечания

↑ Dulmage, Mendelsohn, 1958.
↑ Brualdi, Harary, Miller, 1980.
↑ Brualdi, Harary, Miller, 1980, с. Theorem 3.4.
↑ Feng, Kutnar, Malnič, Marušic, 2008.
↑ ¹ ² Imrich, Pisanski, 2008.
↑ Sampathkumar, 1975.
↑ 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.