Napěťový graf - Voltage graph - Wikipedia

v teorie grafů, a graf napětí je řízený graf jehož okraje jsou označeny invertibilně prvky a skupina. Je formálně totožný s a získat graf, ale obvykle se používá v teorie topologických grafů jako výstižný způsob, jak určit další graf volal odvozený graf grafu napětí.

Typické volby skupin použitých pro grafy napětí zahrnují skupinu dvou prvků ℤ₂ (pro definování dvojdílný dvojitý kryt grafu), skupiny zdarma (pro definování univerzální kryt grafu), d-dimenzionální celočíselné mřížky ℤ^d (zobrazeno jako skupina pod vektorovým přidáním, pro definování periodických struktur v d-dimenzionální Euklidovský prostor ),^[1] a konečný cyklické skupiny ℤ_n pro n > 2. Kdy Π je cyklická skupina, graf napětí lze nazvat a graf cyklického napětí.

Definice

Formální definice a Π-napěťový graf pro danou skupinu Π:

• Začněte s digraf G. (Směr je pouze pro pohodlí při zápisu.)
• A Π-napětí na oblouku G je označení oblouku prvkem X z Π. Například v případě, kdy Π = ℤ_n, štítek je číslo i (modn).
• A Π- přiřazení napětí je funkce ${ displaystyle alpha: E (G) rightarrow Pi}$ který označuje každý oblouk G s napětím Π.
• A Π- graf napětí je pár ${ displaystyle (G, alpha: E (G) rightarrow Pi)}$ takhle G je digraf a α je přiřazení napětí.
• The napěťová skupina grafu napětí ${ displaystyle (G, alpha: E (G) rightarrow Pi)}$ je skupina Π ze kterého jsou přiřazena napětí.

Všimněte si, že napětí grafu napětí nemusí uspokojit Kirchhoffův zákon napětí, že součet napětí kolem uzavřené cesty je 0 (prvek identity skupiny), i když tento zákon platí pro odvozené grafy popsané níže. Název tedy může být poněkud zavádějící. Vyplývá to z počátku grafů napětí jako duální vůči aktuální grafy z teorie topologických grafů.

Odvozený graf

The odvozený graf grafu napětí ${ displaystyle (G, alpha: E (G) rightarrow mathbb {Z} _ {n})}$ je graf ${ displaystyle { tilde {G}}}$ jehož vrcholová množina je ${ displaystyle { tilde {V}} = V krát mathbb {Z} _ {n}}$ a jehož okrajová sada je ${ displaystyle { tilde {E}} = E times mathbb {Z} _ {n}}$, kde koncové body hrany (E, k) takové, že E má ocas proti a hlavu w jsou ${ displaystyle (v, k)}$ a ${ displaystyle (w, k + alfa (e))}$.

Ačkoli jsou grafy napětí definovány pro digrafy, lze je rozšířit na neorientované grafy nahrazením každé neorientované hrany dvojicí opačně uspořádaných orientovaných hran a požadavkem, aby tyto hrany měly štítky, které jsou ve struktuře skupiny navzájem inverzní. V tomto případě bude mít odvozený graf také vlastnost, že jeho směrované hrany tvoří páry protilehlých hran, takže odvozený graf může být sám interpretován jako neorientovaný graf.

Odvozený graf je a krycí graf daného grafu napětí. Pokud žádný hranový štítek grafu napětí není prvkem identity, pak prvky skupiny spojené s vrcholy odvozeného grafu poskytují a zbarvení odvozeného grafu s počtem barev rovným skupinovému pořadí. Důležitým zvláštním případem je dvojdílný dvojitý kryt, odvozený graf napěťového grafu, ve kterém jsou všechny hrany označeny prvkem neidentity skupiny dvou prvků. Protože pořadí skupiny je dvě, je v tomto případě odvozený graf zaručeně bipartitní.

Polynomiální čas algoritmy jsou známé pro určování, zda je odvozený graf a ${ displaystyle mathbb {Z} ^ {d}}$- graf napětí obsahuje všechny směrované cykly.^[1]

Příklady

Žádný Cayleyův graf skupiny Π, s danou sadou Γ generátorů, lze definovat jako odvozený graf pro a Π- graf napětí s jedním vrcholem a | Γ | vlastní smyčky, každý označený jedním z generátorů v Γ.^[2]

The Petersenův graf je odvozený graf pro ℤ₅- napěťový graf ve tvaru činky se dvěma vrcholy a třemi hranami: jedna hrana spojující dva vrcholy a jedna vlastní smyčka na každém vrcholu. Jedna samostatná smyčka je označena 1, druhá 2 a hrana spojující dva vrcholy je označena 0. Obecněji stejná konstrukce umožňuje libovolné zobecněný Petersenův graf GP (n,k), které mají být konstruovány jako odvozený graf stejného grafu činky s popisky 1, 0 a k ve skupině ℤ_n.^[3]

Vrcholy a hrany jakéhokoli periodika mozaikování roviny může být vytvořen jako odvozený graf konečného grafu s napětím v ℤ².

Poznámky

Reference

• Cohen, Edith; Megiddo, Nimrod (1989), "Silně polynomiální čas a NC algoritmy pro detekci cyklů v dynamických grafech", Proc. 21. výroční sympozium ACM o teorii práce na počítači (STOC '89), str. 523–534, doi:10.1145/73007.73057.
• Gross, Jonathan L. (1974), „Napěťové grafy“, Diskrétní matematika, 9 (3): 239–246, doi:10.1016 / 0012-365X (74) 90006-5.
• Gross, Jonathan L .; Tucker, Thomas W. (1977), „Generování všech pokrytí grafu přiřazením permutačního napětí“, Diskrétní matematika, 18 (3): 273–283, doi:10.1016 / 0012-365X (77) 90131-5.
• Gross, Jonathan L .; Tucker, Thomas W. (1987), Teorie topologického grafu, New York: Wiley.
• Iwano, K .; Steiglitz, K. (1987), "Testování cyklů v nekonečných grafech s periodickou strukturou", Proc. 19. výroční sympozium ACM o teorii práce na počítači (STOC '87), str. 46–55, doi:10.1145/28395.28401.
• Kosaraju, S. Rao; Sullivan, Gregory (1988), „Detekce cyklů v dynamických grafech v polynomiálním čase“, Proc. 20. výroční sympozium ACM o teorii práce na počítači (STOC '88), str. 398–406, doi:10.1145/62212.62251.