Накрывающий граф

Пусть ${\displaystyle G=(V_{1},E_{1})}$ и ${\displaystyle C=(V_{2},E_{2})}$ будут два графа и пусть функция ${\displaystyle f\colon V_{2}\to V_{1}}$ сюръективна. Тогда f является накрывающим отображением из C в G, если для каждого ${\displaystyle v\in V_{2}}$ сужение f на окрестность вершины v является биекцией в окрестность вершины f(v) в G. Иначе говоря, f отображает рёбра, инцидентные v один-в-один в рёбра в инцидентные f(v).

Если существует накрывающее отображение из C в G, то C является накрывающим графом или подъёмом графа G, а G — факторграфом C. h-Подъём — это подъём, такой, что накрывающее отображение f имеет свойство, что для любой вершины v графа G, его расслоение ${\displaystyle 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. Здесь H является 2-кратным накрытием или двойным накрытием графа C.

Для любого графа G можно построить двойное покрытие двудольным графом графа G, которое является и двудольным графом и двойным накрытием графа G одновременно. Двойное покрытие двудольным графом графа G является тензорным произведением ${\displaystyle G\times K_{2}}$:

Если граф G уже двудолен, его двойное покрытие двудольным графом состоит из двух непересекающихся копий графа G. Граф может иметь много различных двойных покрытий, отличных от двойного покрытия двудольным графом.

Для любого связного графа G можно построить его граф универсального накрытия[2]. Это частный случай более общей концепции универсального накрытия из топологии. Топологическое требование, чтобы универсальное накрытие было односвязным, преобразуется в терминах теории графов в требовании, чтобы граф был связен и не имел циклов, то есть был деревом. Граф универсального накрытия единственен (с точностью до изоморфизма). Если граф G является деревом, то G сам по себе является графом универсального накрытия графа G. Для любого другого конечного связного графа G граф универсального накрытия графа G является счётно бесконечным (но локально конечным) деревом.

Граф универсального накрытия T связного графа G можно построить следующим образом. Выбираем произвольную вершину r графа G в качестве начальной точки. Каждая вершина накрытия T является проходом без возврата, который начинается в r, то есть последовательность ${\displaystyle w=(r,v_{1},v_{2},\dots ,v_{n})}$ вершин графа G, такая, что

• v_i и v_i+1 смежны в G для всех i, то есть w является проходом
• ${\displaystyle v_{i-1}\neq v_{i+1}}$ для всех i, то есть без возврата.

Тогда две вершины T смежны, если одна является простым расширением другой — вершина ${\displaystyle (r,v_{1},v_{2},\dots ,v_{n})}$ смежна вершине ${\displaystyle (r,v_{1},v_{2},\dots ,v_{n-1})}$. С точностью до изоморфизма то же самое дерево T получается независимо от выбора начальной точки r.

Накрывающее отображение f отображает вершину (r) из T в вершину r в G, а вершину ${\displaystyle (r,v_{1},v_{2},\dots ,v_{n})}$ из T в вершину v_n в G.

Бесконечнократный абелев накрывающий граф конечного (мульти)графа называется топологическим кристаллом, абстракцией кристаллической структуры, и является периодическим графом. Например, кристалл алмаза как граф представляет собой максимальный абелев накрывающий граф диполя с четырьмя рёбрами. Эта точка зрения, комбинированная с идеей «стандартных реализаций», оказывается полезной в систематическом построении (гипотетических) кристаллов[1].

Планарное накрытие графа — это конечное накрытие графа планарным графом. Свойство иметь планарное накрытие может быть описано запрещёнными минорами, однако точное описание такого вида остаётся неизвестным. Любой граф с вложением в проективную плоскость имеет планарное накрытие, получаемое из ориентируемого двойного накрытия проективной плоскости. В 1988 году Сэйю Нагами высказал предположение, что только эти графы и имеют планарные накрытия, но гипотеза остаётся недоказанной[3].

Общий способ получения накрывающих графов использует графы напряжений, в которых «дротики» данного графа G (то есть пары ориентированных рёбер, соответствующих неориентированным рёбрам G) помечены парами противоположных элементов (то есть элементом и ему обратного) из некоторой группы. Полученный из графа напряжений граф (производный граф) имеет в качестве вершин пары (v,x), где v — вершина графа G, а x является элементом группы. Дротик из v в w помечается элементом группы y из G соответствует ребру из (v,x) в (w,xy) в производном графе.

Универсальное накрытие можно рассматривать при таком подходе как производный граф графа напряжений, в котором рёбра остовного дерева графа помечены единичным элементом группы, а каждая оставшаяся пара дротиков помечена различными элементами свободной группы. Двудольное двойное накрытие можно рассматривать тогда как производный граф графа напряжений, в котором каждый дротик помечен ненулевым элементом группы порядка два.