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

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

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

Примеры

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

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

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

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

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

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

а Шаблон:Не переведено 5 двойного покрытия G является сама матрица A. То есть преобразование графа в его двойное покрытие может быть осуществлено просто путём толкования A как матрицы бисмежности, а не матрицы смежности. Более обще, толкование матриц смежности ориентированных графов как бисмежных матриц даёт комбинаторную эквивалентность между ориентированными графами и сбалансированными двудольными графамиШаблон:SfnШаблон:Sfn.

Свойства

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

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

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

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

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

В общем случае, граф может иметь несколько двойных покрытий, отличных от двудольного двойного покрытияШаблон:Sfn. На рисунке граф 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₆. Вместо этого двудольное двойное покрытие может быть получено как Шаблон:Не переведено 5 вложения графа K₆ в проективную плоскость.

Литература

• Шаблон:Статья
• Шаблон:Статья. «Coverings» в заглавии статьи относится к задаче о вершинном покрытии, а не к двудольному двойному покрытию. Однко, Бруалди, Харари и Миллер Шаблон:Harvцитируют эту статью как источник идеи интерпретации матрицы смежности как матрицы бисмежности.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Mathworld