Wykres napięcia

W teorii grafów wykres napięcia jest grafem skierowanym , którego krawędzie są oznaczone w sposób odwracalny elementami grupy . Jest formalnie identyczny z wykresem wzmocnienia , ale jest ogólnie używany w teorii grafów topologicznych jako zwięzły sposób określenia innego wykresu zwanego wykresem pochodnym wykresu napięcia.

Typowe wybory grup używanych do wykresów napięcia obejmują dwuelementową grupę ℤ ₂ (do definiowania dwudzielnego podwójnego pokrycia wykresu), wolne grupy (do definiowania uniwersalnego pokrycia wykresu), d - wymiarowe siatki całkowite ℤ ^d ( postrzegana jako grupa z dodawaniem wektorów, do definiowania struktur okresowych w d - wymiarowej przestrzeni euklidesowej ) i skończonych grup cyklicznych ℤ _n dla n > 2 . Kiedy $Π$ jest grupą cykliczną, wykres napięcia można nazwać wykresem cykliczno-napięciowym .

Definicja

Formalna definicja wykresu napięcia $Π$ dla danej grupy $Π$ :

Rozpocznij od dwuznaku G . (Kierunek jest wyłącznie dla wygody w notacji).
Napięcie $Π$ na łuku G jest etykietą łuku przez element x z $Π$ . Na przykład w przypadku, gdy $Π = ℤ n$ , etykietą jest liczba i (mod n ).
Przypisanie $_$ $Π$ funkcja G Π .
Wykres napięcia $Π$ to para taka, że G jest dwuznakiem, a α jest napięciem ${\ Displaystyle (G, \ alfa: E (G) \ rightarrow \ Pi)}$ zadanie.
Grupa napięć wykresu napięcia ${\ Displaystyle (G, \ alfa: E (G) \ rightarrow \ Pi)}$ to grupa $Π$ , z której przypisywane są napięcia.

Zauważ, że napięcia na wykresie napięcia nie muszą spełniać prawa Kirchhoffa napięć , że suma napięć wokół zamkniętej ścieżki wynosi 0 (element tożsamości grupy), chociaż to prawo obowiązuje dla wykresów pochodnych opisanych poniżej. Dlatego nazwa może być nieco myląca. Wynika to z pochodzenia grafów napięciowych jako dualnych względem grafów prądowych teorii grafów topologicznych .

Wykres pochodny

Pochodny wykres wykresu napięcia $G, \ alfa: E (G) \ rightarrow \ mathbb {Z} _ {n})$ ${\ Displaystyle {\ tylda {G}}}$ } , którego zestaw wierzchołków to ${\ Displaystyle {\ tylda {V}} = V \ razy \ mathbb {Z} _ {n}}$ i którego krawędź zestaw to ${\ Displaystyle {\ tylda {E}} = E \ razy \ mathbb {Z} _ {n}}$ , gdzie punkty końcowe krawędzi ( mi , k ) takie, że e ma ogon v i głowę w są ${\ Displaystyle (v, \ k)}$ i ${\ Displaystyle (w, \ k + \ alfa (e))}$ .

Chociaż wykresy napięcia są zdefiniowane dla digrafów, można je rozszerzyć na wykresy nieskierowane , zastępując każdą nieskierowaną krawędź parą przeciwnych krawędzi skierowanych i wymagając, aby krawędzie te miały etykiety, które są do siebie odwrotne w strukturze grupy. W tym przypadku graf pochodny będzie miał również tę właściwość, że jego skierowane krawędzie tworzą pary przeciwnych krawędzi, więc sam graf pochodny może być interpretowany jako graf nieskierowany.

Wykres pochodny jest wykresem pokrywającym dany wykres napięcia. Jeśli żadna etykieta krawędzi wykresu napięcia nie jest elementem tożsamości, to elementy grupowe powiązane z wierzchołkami wykresu pochodnego zapewniają kolorowanie wykresu pochodnego liczbą kolorów równą porządkowi grup. Ważnym przypadkiem szczególnym jest dwudzielna podwójna pokrywa , pochodny wykres wykresu napięcia, w którym wszystkie krawędzie są oznaczone elementem nieidentyfikującym grupy dwuelementowej. Ponieważ rząd grupy wynosi dwa, graf pochodny w tym przypadku jest dwudzielny .

Algorytmy czasu wielomianowego są znane do określania, czy pochodny wykres napięcia $-$ wykres zawiera jakiekolwiek skierowane

Przykłady

Dowolny wykres Cayleya grupy $Π$ , z danym zestawem $Γ$ generatorów, może być zdefiniowany jako wykres pochodny dla wykresu napięcia $Π$ mającego jeden wierzchołek i $Γ$ pętle własne, z których każdy jest oznaczony jednym z generatorów w $Γ$ .

Wykres Petersena jest wykresem pochodnym dla wykresu napięcia ℤ ₅ w kształcie hantli z dwoma wierzchołkami i trzema krawędziami: jedną krawędzią łączącą dwa wierzchołki i jedną pętlą samoczynną na każdym wierzchołku. Jedna pętla własna jest oznaczona jako 1, druga przez 2, a krawędź łącząca dwa wierzchołki jest oznaczona jako 0. Mówiąc bardziej ogólnie, ta sama konstrukcja pozwala na skonstruowanie dowolnego uogólnionego grafu Petersena GP( n , k ) jako pochodnego wykresu ten sam wykres hantli z etykietami 1, 0 i k w grupie ℤ _n .

Wierzchołki i krawędzie dowolnej okresowej teselacji płaszczyzny można utworzyć jako wykres pochodny grafu skończonego z napięciami w ℤ ² .

Notatki

Cohen, Edyta ; Megiddo, Nimrod (1989), „Silnie wielomianowe algorytmy czasu i NC do wykrywania cykli na wykresach dynamicznych”, Proc. 21. doroczne sympozjum ACM na temat teorii informatyki (STOC '89) , s. 523–534, doi : 10.1145/73007.73057 .
Gross, Jonathan L. (1974), „Wykresy napięcia”, Discrete Mathematics , 9 (3): 239–246, doi : 10.1016/0012-365X (74) 90006-5 .
Gross, Jonathan L.; Tucker, Thomas W. (1977), „Generowanie wszystkich pokryć grafów przez przypisania napięcia permutacji”, Discrete Mathematics , 18 (3): 273–283, doi : 10.1016/0012-365X (77) 90131-5 .
Gross, Jonathan L.; Tucker, Thomas W. (1987), Teoria grafów topologicznych , Nowy Jork: Wiley .
Iwano, K.; Steiglitz, K. (1987), „Testowanie cykli w nieskończonych grafach o strukturze okresowej”, Proc. 19. doroczne sympozjum ACM na temat teorii informatyki (STOC '87) , s. 46–55, doi : 10.1145/28395.28401 .
Kosaraju, S. Rao ; Sullivan, Gregory (1988), „Wykrywanie cykli na wykresach dynamicznych w czasie wielomianowym”, Proc. 20. doroczne sympozjum ACM na temat teorii informatyki (STOC '88) , s. 398–406, doi : 10.1145/62212.62251 .