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

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

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

Определение

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

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

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

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

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

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

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

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

Примеры

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

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

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

Примечания

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

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

Содержание

Определение

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

Примеры

Примечания

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