В математической дисциплине теории графов граф C является покрывающим графом другого графа G , если существует покрывающее отображение из множества вершин C в множество вершин G. Покрывающее отображение f является сюръекцией и локальным изоморфизмом : окрестность вершины v в C отображается биективно на окрестность в G.
Термин «подъем» часто используется как синоним графа покрытия связного графа .
Хотя это может ввести в заблуждение, не существует (очевидной) связи между покрывающим графом и покрытием вершин или ребер .
Комбинаторная формулировка покрывающих графов немедленно обобщается на случай мультиграфов . Покрывающий граф является частным случаем покрывающего комплекса. [1] Как покрывающие комплексы, так и мультиграфы с одномерным клеточным комплексом являются не чем иным, как примерами покрывающих пространств топологических пространств , поэтому терминология в теории покрывающих пространств доступна; скажем, покрывающая группа преобразований, универсальное покрывание, абелево покрывание и максимальное абелево покрывание. [2]
Пусть G = ( V 1 , E 1 ) и C = ( V 2 , E 2 ) — два графа, и пусть f : V 2 → V 1 — сюръекция . Тогда f является накрывающим отображением из C в G , если для каждого v ∈ V 2 ограничение f на окрестность v является биекцией на окрестность f ( v ) в G . Иначе говоря, f отображает ребра, инцидентные v , взаимно однозначно на ребра, инцидентные f ( v ).
Если существует покрывающее отображение из C в G , то C является покрывающим графом или лифтом графа G. H-лифтом называется лифт, при котором покрывающее отображение f обладает тем свойством, что для каждой вершины v графа G его слой f −1 (v) имеет ровно h элементов.
На следующем рисунке граф C является покрывающим графом графа H.
Покрывающее отображение f из C в H обозначено цветами. Например, обе синие вершины C отображаются в синюю вершину H . Отображение f является сюръекцией: каждая вершина H имеет прообраз в C . Более того, f биективно отображает каждую окрестность вершины v в C на окрестность вершины f ( v ) в H .
Например, пусть v будет одной из фиолетовых вершин в C ; у нее есть два соседа в C , зеленая вершина u и синяя вершина t . Аналогично, пусть v ′ будет фиолетовой вершиной в H ; у нее есть два соседа в H , зеленая вершина u ′ и синяя вершина t ′ . Отображение f , ограниченное { t , u , v } , является биекцией на { t ′ , u ′ , v ′ }. Это проиллюстрировано на следующем рисунке:
Аналогично мы можем проверить, что окрестность синей вершины в C отображается один к одному на окрестность синей вершины в H :
В приведенном выше примере каждая вершина H имеет ровно 2 прообраза в C. Следовательно, C является 2 -кратным покрытием или двойным покрытием H.
Для любого графа G можно построить двудольное двойное покрытие графа G , которое является двудольным графом и двойным покрытием графа G. Двудольное двойное покрытие графа G является тензорным произведением графов G × K 2 :
Если G уже двудольный, его двудольное двойное покрытие состоит из двух непересекающихся копий G. Граф может иметь много различных двойных покрытий, отличных от двудольного двойного покрытия.
Для любого связного графа G можно построить его универсальный покрывающий граф . [3] Это пример более общей концепции универсального покрытия из топологии; топологическое требование, чтобы универсальное покрытие было односвязным, в терминах теории графов переводится в требование, чтобы оно было ацикличным и связным; то есть деревом . Универсальный покрывающий граф уникален (с точностью до изоморфизма). Если G является деревом, то сам G является универсальным покрывающим графом G . Для любого другого конечного связного графа G универсальный покрывающий граф G является счетно бесконечным (но локально конечным) деревом.
Универсальный покрывающий граф T связного графа G может быть построен следующим образом. Выберем произвольную вершину r графа G в качестве начальной точки. Каждая вершина T является невозвратным маршрутом, который начинается с r , то есть последовательностью w = ( r , v 1 , v 2 , ..., v n ) вершин графа G такой, что
Тогда две вершины T смежны, если одна из них является простым расширением другой: вершина ( r , v 1 , v 2 , ..., v n ) смежна с вершиной ( r , v 1 , v 2 , ..., v n -1 ). С точностью до изоморфизма строится одно и то же дерево T независимо от выбора начальной точки r .
Покрывающее отображение f отображает вершину ( r ) из T в вершину r из G , а вершину ( r , v 1 , v 2 , ..., v n ) из T в вершину v n из G .
На следующем рисунке показан универсальный покрывающий граф T графа H ; цвета указывают на покрывающую карту.
Для любого k все k - регулярные графы имеют одно и то же универсальное покрытие: бесконечное k -регулярное дерево.
Бесконечнократный абелев покрывающий граф конечного (мульти)графа называется топологическим кристаллом, абстракцией кристаллических структур. Например, алмазный кристалл как граф является максимальным абелевым покрывающим графом четырехреберного дипольного графа . Этот взгляд в сочетании с идеей «стандартных реализаций» оказывается полезным в систематическом проектировании (гипотетических) кристаллов. [2]
Планарное покрытие графа — это конечный покрывающий граф, который сам является планарным графом . Свойство иметь планарное покрытие может быть охарактеризовано запрещенными минорами , но точная характеристика этой формы остается неизвестной. Каждый граф с вложением в проективную плоскость имеет планарное покрытие, происходящее от ориентируемого двойного покрытия проективной плоскости; в 1988 году Сейя Нагами предположил, что это единственные графы с планарными покрытиями, но это остается недоказанным. [4]
Обычный способ формирования покрывающих графов использует графы напряжения , в которых дротики заданного графа G (то есть пары направленных ребер, соответствующих ненаправленным ребрам G ) помечены обратными парами элементов из некоторой группы . Производный граф графа напряжения имеет в качестве своих вершин пары ( v , x ), где v — вершина G , а x — элемент группы; дротик из v в w, помеченный элементом группы y в G, соответствует ребру из ( v , x ) в ( w , xy ) в производном графе.
Универсальное покрытие можно рассматривать таким образом как производный граф графа напряжения, в котором ребра остовного дерева графа помечены единичным элементом группы, а каждая оставшаяся пара дротиков помечена отдельным порождающим элементом свободной группы . Двудольный дубль можно рассматривать таким образом как производный граф графа напряжения, в котором каждый дротик помечен ненулевым элементом группы второго порядка.
