В математической дисциплине теории графов , граф C представляет собой покрытие графа другого графа G , если существует накрытие из множества вершин C до множества вершин G . Накрытие е является сюръекцией и локальный изоморфизм: окрестность вершинного V в C отображаются уплотняется на окрестность е ( об ) в G .
Термин подъем часто используется как синоним покрывающего графа связного графа.
Хотя это может ввести в заблуждение, нет (очевидной) связи между покрывающим графом и вершинным покрытием или краевым покрытием .
Комбинаторная формулировка покрывающих графов немедленно обобщается на случай мультиграфов . Если мы отождествляем мультиграф с клеточным 1-мерного, покрытие графа не что иное , как особый пример покрытия пространств из топологических пространств , так что терминология в теории накрытий доступна; скажем, накрывающая группа преобразований, универсальное накрытие, абелево накрытие и максимальное абелево покрытие. [1]
Определение [ править ]
Пусть G = ( V 1 , E 1 ) и C = ( V 2 , E 2 ) - два графа, и пусть f : V 2 → V 1 - сюръекция . Тогда F является накрытие от С до G , если для каждого V ∈ V 2 , сужение F на окрестности из V является биекцией на окрестности F (v ) в G . Иначе говоря, f отображает ребра, инцидентные v, взаимно однозначно на ребра, инцидентные f ( v ).
Если существует накрытие от С до G , то C является покрытие графа , или лифт , из G . Ч подъемник лифт таким образом, что накрытие F обладает тем свойством , что для каждой вершины V из G , то его волокна F -1 (V) имеет ровно ч элементы.
Примеры [ править ]
На следующем рисунке, граф С является покрытием графа графа H .
Покрывающая карта f из C в H обозначена цветами. Например, оба синие вершины C отображаются в синей вершины H . Карта F сюръекция: каждая вершина Н имеет прообраз в C . Кроме того, F отображает взаимно однозначно каждые окрестности вершины V в C на окрестности вершины F ( об ) в H .
Например, пусть v будет одной из фиолетовых вершин в C ; у него есть два соседа в C , зеленая вершина u и синяя вершина t . Аналогично, пусть v ′ - пурпурная вершина в H ; у него есть два соседа в H , зеленая вершина u ′ и синяя вершина t ′. Отображение f, ограниченное на { t , u , v }, является биекцией на { t ′, u ′, v ′}. Это показано на следующем рисунке:
Точно так же мы можем проверить, что окрестность синей вершины в C взаимно однозначно отображается на окрестность синей вершины в H :
Двойная обложка [ править ]
В приведенном выше примере, каждая вершина H имеет ровно 2 прообразы в C . Следовательно , С представляет собой 2-кратная крышка или двойная крышка из H .
Для любого графа G , можно построить двудольную двойную крышку из G , который представляет собой двудольный граф и двойной крышка G . Двудольная двойная крышка G представляет собой тензорное произведение графов G × K 2 :
Если G уже двудольный, его двудольная двойная крышка состоит из двух непересекающихся копий G . Граф может иметь много разных двойных покрытий, кроме двудольного двойного покрытия.
Универсальная обложка [ править ]
Для любого связного графа G можно построить его универсальный накрывающий граф . [2] Это пример более общей концепции универсального покрытия из топологии; топологическое требование односвязности универсального покрытия в терминах теории графов переводится в требование, чтобы оно было ацикличным и связным; то есть дерево . Универсальный накрывающий граф единственен (с точностью до изоморфизма). Если G является деревом, то G сама является универсальным накрытием граф G . Для любого другого конечного связного графа G универсальный накрывающий граф графа G является счетно бесконечным (но локально конечным) деревом.
Универсальный накрывающий граф T связного графа G можно построить следующим образом. Выберем произвольную вершину г из G в качестве отправной точки. Каждая вершина T - это обход без возврата, который начинается с r , то есть последовательность w = ( r , v 1 , v 2 , ..., v n ) вершин G такая, что
- v i и v i +1 смежны в G для всех i , т. е. w - прогулка
- v i -1 ≠ v i +1 для всех i , т. е. w не имеет возврата.
Тогда две вершины Т являются смежными , если один является простым расширением другого: вершина ( г , v 1 , v 2 , ..., v п ) примыкает к вершине ( г , V 1 , V 2 ,. .., v n -1 ). С точностью до изоморфизма одно и то же дерево T строится независимо от выбора начальной точки r .
Накрытие F отображает вершину ( г ) в Т к вершине г в G , и вершину ( г , v 1 , v 2 , ..., v п ) в Т к вершине V п в G .
Примеры универсальных обложек [ править ]
На следующем рисунке показан универсальный покрывающий граф T графа H ; цвета обозначают карту покрытия.
Для любых к , все K - регулярные графы имеют одинаковую универсальную крышку: бесконечные К - регулярное дерево.
Топологический кристалл [ править ]
Бесконечнократный абелев накрывающий граф конечного (мульти) графа называется топологическим кристаллом, абстракцией кристаллических структур. Например, кристалл алмаза как граф является максимальным абелевым покрывающим графом четырехреберного дипольного графа . Эта точка зрения в сочетании с идеей «стандартных реализаций» оказывается полезной при систематическом проектировании (гипотетических) кристаллов. [1]
Планарное покрытие [ править ]
Плоская крышка графы является конечным покрытием график , который сам по себе является плоским графом . Свойство иметь плоское покрытие может характеризоваться запрещенными несовершеннолетними , но точная характеристика этой формы остается неизвестной. Каждый граф с вложением в проективную плоскость имеет плоское покрытие, исходящее из ориентируемого двойного покрытия проективной плоскости; В 1988 году Сейя Нагами предположил, что это единственные графы с плоскими покрытиями, но это осталось недоказанным. [3]
Графики напряжения [ править ]
Обычный способ формирования покрывающих графов использует графы напряжения , в которых дротики данного графа G (то есть пары ориентированных ребер, соответствующие неориентированным ребрам графа G ) помечены обратными парами элементов из некоторой группы . Производный граф графа напряжения имеет в качестве вершин пары ( v , x ), где v - вершина G, а x - элемент группы; дротик от v до w, помеченный элементом группы y в G, соответствует ребру от ( v , x ) до (w , xy ) в производном графе.
Таким образом, универсальное покрытие можно рассматривать как производный граф графа напряжений, в котором ребра остовного дерева графа помечены единичным элементом группы, а каждая оставшаяся пара дротиков помечена отдельным порождающим элементом. элемент свободной группы . Таким образом, двудольный двойник можно рассматривать как производный график графика напряжения, в котором каждый дротик помечен ненулевым элементом группы второго порядка.
Заметки [ править ]
- ^ a b Сунада, Тошиказу (2012). «6 топологических кристаллов». Топологическая кристаллография: с точки зрения дискретного геометрического анализа . Springer. С. 73–90. ISBN 978-4-431-54177-6.
- ^ Angluin 1980
- ^ Hliněný, Петр (2010), "20 лет плоской крышки гипотезы Негами в" (PDF) , Графы и комбинаторика , 26 (4): 525-536, CiteSeerX 10.1.1.605.4932 , DOI : 10.1007 / s00373-010-0934 -9 , Руководство по ремонту 2669457 .
Ссылки [ править ]
- Годсил, Крис ; Ройл, Гордон Ф. (2001). «§6.8 Складки и обложки» . Алгебраическая теория графов . Тексты для выпускников по математике. 207 . Springer. С. 114–6. ISBN 978-0-387-95220-8.
- Амит, Алон; Линиал, Натан ; Матушек, Иржи ; Розенман, Эяль (2001). «Случайные подъемы графов» . Материалы двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '01) . Общество промышленной и прикладной математики. С. 883–894. CiteSeerX 10.1.1.719.3508 . ISBN 978-0-89871-490-6.
- Англуин, Дана (1980). «Локальные и глобальные свойства в сетях процессоров (Расширенная аннотация)». Материалы двенадцатого ежегодного симпозиума ACM по теории вычислений (STOC '80) . Ассоциация вычислительной техники. С. 82–93. DOI : 10.1145 / 800141.804655 . ISBN 978-0-89791-017-0.
