График напряжения

В теории графов граф напряжения — это ориентированный граф , ребра которого обратимо помечены элементами группы . Формально он идентичен графику усиления , но обычно используется в топологической теории графов как краткий способ задания другого графа, называемого производным графиком графика напряжения.

Типичный выбор групп, используемых для графиков напряжения, включает группу из двух элементов. $\mathbb {Z} _{2}$ (для определения двудольного двойного покрытия графа), свободные группы (для определения универсального покрытия графа), d -мерные целочисленные решетки $\mathbb {Z} ^{d}$ (рассматривается как группа при сложении векторов для определения периодических структур в d -мерном евклидовом пространстве ), и конечные циклические группы $\mathbb {Z_{n}}$ для n > 2. Когда Π — циклическая группа, график напряжения можно назвать графом циклического напряжения .

Определение

Формальное определение графика Π -напряжения для данной группы Π :

• с орграфа G. Начните (Направление указано исключительно для удобства обозначений.)
• П - напряжение на дуге графа G — это метка дуги элементом $x\in \Pi$. Например, в случае, когда $\Pi =\mathbb {Z} _{n}$, метка представляет собой число i (mod n ).
• Назначение Π -напряжения — это функция $\alpha :E(G)\rightarrow \Pi$ который помечает каждую дугу G Π-напряжением.
• График Π -напряжения представляет собой пару $(G,\alpha :E(G)\rightarrow \Pi )$ такой, что G — орграф, а α — присвоение напряжения.
• Группа напряжений графика напряжения $(G,\alpha :E(G)\rightarrow \Pi )$ – группа П, из которой назначаются напряжения.

Обратите внимание, что напряжения на графике напряжения не обязательно должны удовлетворять закону напряжения Кирхгофа , согласно которому сумма напряжений на замкнутом пути равна 0 (единичный элемент группы), хотя этот закон справедлив для полученных графиков, описанных ниже. Таким образом, название может вводить в заблуждение. Это происходит из-за того, что графики напряжения двойственны современным графикам топологической теории графов .

Производный граф

графика Производный график напряжения $(G,\alpha :E(G)\rightarrow \mathbb {Z} _{n})$ это график ${\tilde {G}}$ чье множество вершин ${\tilde {V}}=V\times \mathbb {Z} _{n}$ и чей набор ребер равен ${\tilde {E}}=E\times \mathbb {Z} _{n}$, где концы ребра ( e , k ) такого, что e имеет хвост v и начало w, равны $(v,\ k)$ и $(w,\ k+\alpha (e))$.

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

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

с полиномиальным временем Известны алгоритмы , позволяющие определить, является ли полученный граф $\mathbb {Z} ^{d}$-график напряжения содержит любые направленные циклы.

Примеры

Любой граф Кэли группы Π с заданным набором Γ образующих может быть определен как производный граф для Π -графа напряжения, имеющего одну вершину и Γ самопетли, каждая из которых помечена одним из генераторов в Γ .

Граф Петерсена — это производный граф для $\mathbb {Z} _{5}$-график напряжения в форме гантели с двумя вершинами и тремя ребрами: одно ребро, соединяющее две вершины, и по одному витку на каждой вершине. Одна петля помечена цифрой 1, другая — 2, а ребро, соединяющее две вершины, помечено 0. В более общем смысле, та же конструкция позволяет любой обобщенный граф Петерсена GP( n , k построить ) как производный граф тот же гантельный граф с метками 1, 0 и k в группе $\mathbb {Z} _{n}$.

Вершины и ребра любой периодической мозаики плоскости могут быть сформированы как производный граф конечного графа с напряжениями в $\mathbb {Z} ^{2}$.

Ссылки

• Коэн, Эдит ; Мегиддо, Нимрод (1989), «Строго полиномиальное время и NC-алгоритмы для обнаружения циклов в динамических графах», Proc. 21-й ежегодный симпозиум ACM по теории вычислений (STOC '89) , стр. 523–534, doi : 10.1145/73007.73057 , ISBN  0-89791-307-8 .
• Гросс, Джонатан Л. (1974), «Графики напряжения», Discrete Mathematics , 9 (3): 239–246, doi : 10.1016/0012-365X(74)90006-5 .
• Гросс, Джонатан Л.; Такер, Томас В. (1977), «Генерация всех покрытий графа путем назначения перестановочного напряжения», Discrete Mathematics , 18 (3): 273–283, doi : 10.1016/0012-365X(77)90131-5 .
• Гросс, Джонатан Л.; Такер, Томас В. (1987), Топологическая теория графов , Нью-Йорк: Wiley .
• Ивано, К.; Стейглиц, К. (1987), "Проверка циклов в бесконечных графах с периодической структурой", Proc. 19-й ежегодный симпозиум ACM по теории вычислений (STOC '87) , стр. 46–55, doi : 10.1145/28395.28401 , ISBN  0-89791-221-7 , S2CID   37934099 .
• Косараджу, С. Рао ; Салливан, Грегори (1988), «Обнаружение циклов в динамических графах за полиномиальное время», Proc. 20-й ежегодный симпозиум ACM по теории вычислений (STOC '88) , стр. 398–406, doi : 10.1145/62212.62251 , ISBN  0-89791-264-0 , S2CID   14290312 .