В теории графов двудольное двойное покрытие неориентированного графа G — это двудольный покрывающий граф графа G с вдвое большим числом вершин , чем у G. Его можно построить как тензорное произведение графов , G × K 2 . Его также называют двойным покрытием Кронекера , каноническим двойным покрытием или просто двудольным двойным покрытием графа G.
Его не следует путать с двойным циклическим покрытием графа — семейством циклов, которое включает каждое ребро дважды.
Двудольное двойное покрытие графа G имеет две вершины u i и w i для каждой вершины v i графа G . Две вершины u i и w j соединены ребром в двойном покрытии тогда и только тогда, когда v i и v j соединены ребром в G . Например, ниже приведена иллюстрация двудольного двойного покрытия недвудольного графа G . На иллюстрации каждая вершина в тензорном произведении показана с использованием цвета из первого члена произведения ( G ) и формы из второго члена произведения ( K 2 ); поэтому вершины u i в двойном покрытии показаны в виде кругов, а вершины w i показаны в виде квадратов.
Двудольное двойное покрытие может быть также построено с использованием матриц смежности (как описано ниже) или как производный граф графа напряжения , в котором каждое ребро G помечено ненулевым элементом двухэлементной группы .
Двудольное двойное покрытие графа Петерсена — это граф Дезарга : K2 × G ( 5,2) = G (10,3) .
Двудольное двойное покрытие полного графа K n является графом короны ( полный двудольный граф K n , n минус совершенное паросочетание ). В частности, двудольное двойное покрытие графа тетраэдра , K 4 , является графом куба .
Двудольное двойное покрытие графа-цикла нечетной длины представляет собой цикл удвоенной длины, в то время как двудольное двойное покрытие любого двудольного графа (например, цикла четной длины, показанного в следующем примере) образовано двумя непересекающимися копиями исходного графа.
Если неориентированный граф G имеет матрицу A в качестве матрицы смежности , то матрица смежности двойного покрытия графа G имеет вид
и матрица бисмежности двойного покрытия G — это просто A. То есть, преобразование из графа в его двойное покрытие может быть выполнено просто путем переинтерпретации A как матрицы бисмежности вместо матрицы смежности. В более общем смысле, переинтерпретация матриц смежности ориентированных графов как матриц бисмежности обеспечивает комбинаторную эквивалентность между ориентированными графами и сбалансированными двудольными графами. [1]
Двудольное двойное покрытие любого графа G является двудольным графом ; обе части двудольного графа имеют по одной вершине для каждой вершины графа G. Двудольное двойное покрытие связно тогда и только тогда, когда граф G связен и не является двудольным. [2]
Двудольное двойное покрытие является частным случаем двойного покрытия (графа 2-кратного покрытия ). Двойное покрытие в теории графов можно рассматривать как частный случай топологического двойного покрытия .
Если G — недвудольный симметричный граф , то двойное покрытие G также является симметричным графом; таким образом можно получить несколько известных кубических симметричных графов. Например, двойное покрытие K 4 является графом куба; двойное покрытие графа Петерсена является графом Дезарга; а двойное покрытие графа додекаэдра является 40-вершинным симметричным кубическим графом. [3]
Два различных графа могут иметь изоморфные двудольные двойные покрытия. Например, граф Дезарга является не только двудольным двойным покрытием графа Петерсена, но также двудольным двойным покрытием другого графа, который не изоморфен графу Петерсена. [4] Не каждый двудольный граф является двудольным двойным покрытием другого графа; для того чтобы двудольный граф G был двудольным покрытием другого графа, необходимо и достаточно, чтобы автоморфизмы графа G включали инволюцию , которая отображает каждую вершину в отличную и несмежную вершину. [ 4] Например, граф с двумя вершинами и одним ребром является двудольным, но не является двудольным двойным покрытием, поскольку у него нет несмежных пар вершин, которые можно было бы отобразить друг в друга такой инволюцией; с другой стороны, граф куба является двудольным двойным покрытием и имеет инволюцию, которая отображает каждую вершину в диаметрально противоположную вершину. Альтернативная характеристика двудольных графов, которые могут быть образованы с помощью конструкции двудольного двойного покрытия, была получена Сампаткумаром (1975).
В связном графе , который не является двудольным, только одно двойное покрытие является двудольным, но когда граф двудольный или несвязный, их может быть больше одного. По этой причине Томаж Писански утверждал, что название «двудольное двойное покрытие» следует заменить на «каноническое двойное покрытие» или «покрытие Кронекера», названия которых недвусмысленны. [5]
В общем случае граф может иметь несколько двойных покрытий, отличных от двудольного двойного покрытия. [6]
На следующем рисунке граф C является двойным покрытием графа H :
Однако C не является двудольным двойным покрытием H или любого другого графа; он не является двудольным графом .
Если заменить один треугольник квадратом в H, то полученный граф будет иметь четыре различных двойных покрытия. Два из них двудольные, но только одно из них является покрытием Кронекера.
В качестве другого примера, граф икосаэдра является двойным покрытием полного графа K 6 ; чтобы получить отображение покрытия из икосаэдра в K 6 , отобразите каждую пару противоположных вершин икосаэдра в одну вершину K 6 . Однако икосаэдр не является двудольным, поэтому он не является двудольным двойным покрытием K 6 . Вместо этого его можно получить как ориентируемое двойное покрытие вложения K 6 в проективную плоскость .
Двойные покрытия графа соответствуют различным способам подписи ребер графа.
![{\displaystyle \left[{\begin{matrix}0&A\\A^{T}&0\end{matrix}}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b04896754d39fbfcb50519550c82e74d77be67a)