Двусторонняя двойная обложка

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

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

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

Строительство [ править ]

Двудольная двойная крышка G имеет две вершины ˙U _I и ш _I для каждой вершины V _я из G . Две вершины ¯u _я и ш _J соединены ребром в двойной крышкой , если и только если v _я и v _J соединены ребром в G . Например, ниже является иллюстрацией двудольной двойной крышки без двудольного графа G . На иллюстрации каждая вершина в тензорном произведении показана с использованием цвета из первого члена произведения ( G) и форма из второго члена продукта ( 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 как матрицы двойного сопряжения, а не как матрицы смежности. В более общем смысле, переинтерпретация матриц смежности ориентированных графов как матриц двойного сопряжения обеспечивает комбинаторную эквивалентность между ориентированными графами и сбалансированными двудольными графами. ^[2]

Свойства [ править ]

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

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

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

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

Другие двойные обложки [ править ]

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

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

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

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

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

См. Также [ править ]

• Двудольная половина

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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