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

Ориентированный граф, ребра которого помечены обратимо элементами группы

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

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

Определение

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

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

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

Полученный граф

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

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

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

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

Примеры

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

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

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

Примечания

1. Ивано и Стейглиц (1987); Косараджу и Салливан (1988); Коэн и Мегиддо (1989).
2. Гросс и Такер (1987), Теорема 2.2.3, стр. 69.
3. Гросс и Такер (1987), Пример 2.1.2, стр.58.

Ссылки

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