График напряжения - Voltage graph

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

Типичный выбор групп, используемых для графиков напряжения, включает двухэлементную группу ℤ₂ (для определения двусторонняя двойная обложка графика), бесплатные группы (для определения универсальный чехол графика), d-размерный целочисленные решетки ℤ^d (рассматривается как группа при векторном сложении для определения периодических структур в d-размерный Евклидово пространство ),^[1] и конечный циклические группы ℤ_п за п > 2. Когда Π циклическая группа, график напряжений можно назвать график циклического напряжения.

Определение

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

• Начните с диграф грамм. (Направление предназначено исключительно для удобства обозначений.)
• А Π-напряжение на дуге грамм метка дуги элементом Икс из Π. Например, в случае, когда Π = ℤ_п, метка - это число я (модп).
• А Π- назначение напряжения - функция ${\displaystyle \alpha :E(G)\rightarrow \Pi }$ который маркирует каждую дугу грамм с-напряжением.
• А Πграфик напряжений - пара ${\displaystyle (G,\alpha :E(G)\rightarrow \Pi )}$ такой, что грамм - орграф, а - задание напряжения.
• В группа напряжения графика напряжения ${\displaystyle (G,\alpha :E(G)\rightarrow \Pi )}$ это группа Π откуда назначаются напряжения.

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

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

В производный график графика напряжения ${\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}}$, где концы ребра (е, k) такие, что е имеет хвост v и голова ш находятся ${\displaystyle (v,\ k)}$ и ${\displaystyle (w,\ k+\alpha (e))}$.

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

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

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

Примеры

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

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

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

Примечания

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

Рекомендации

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