Automorfizm grafu - Graph automorphism

W zakresie matematycznym teorii wykres An automorfizmem wykresu jest formą symetrii, w którym wykres jest mapowany na siebie przy zachowaniu połączenia krawędzi wierzchołek.

Formalnie automorfizm grafu G  = ( V , E ) jest permutacją σ zbioru wierzchołków V , tak że para wierzchołków ( u , v ) tworzy krawędź wtedy i tylko wtedy, gdy para (σ( u ), σ( v )) również tworzą krawędź. Oznacza to, że jest to izomorfizm grafu od G do samego siebie. W ten sposób można zdefiniować automorfizmy zarówno dla grafów skierowanych, jak i dla grafów nieskierowanych . Skład dwóch automorfizmy inny automorfizmem i zestaw automorfizmy danego wykresu, w ramach działania kompozycji tworzy grupę , z grupy automorfizm wykresu. W przeciwnym kierunku, według twierdzenia Fruchta , wszystkie grupy można przedstawić jako grupę automorfizmu grafu spójnego – a właściwie grafu sześciennego .

Złożoność obliczeniowa

Skonstruowanie grupy automorfizmu jest co najmniej tak samo trudne (pod względem jej złożoności obliczeniowej ) jak rozwiązanie problemu izomorfizmu grafu , czyli ustalenie, czy dwa dane grafy odpowiadają wierzchołkowi za wierzchołkiem i krawędzi za krawędzią. Bo G i H są izomorficzne wtedy i tylko wtedy, gdy rozłączony graf utworzony przez rozłączną sumę grafów G i H ma automorfizm, który zamienia te dwie składowe. W rzeczywistości samo liczenie automorfizmów jest równoważne z czasem wielomianowym izomorfizmowi grafu.

Ten rysunek wykresu Petersena przedstawia podgrupę jego symetrii, izomorficzną z dwuścienną grupą D 5 , ale wykres ma dodatkowe symetrie, których nie ma na rysunku. Na przykład, ponieważ wykres jest symetryczny , wszystkie krawędzie są równoważne.

Problemem wykres automorfizmem jest problem testowania czy wykres ma nietrywialne automorfizm. Należy do klasy NP o złożoności obliczeniowej. Podobnie jak w przypadku izomorfizmu grafów, nie wiadomo, czy ma on algorytm wielomianowy , czy jest NP-zupełny . Istnieje wielomianowy algorytm czasu do rozwiązywania problemu automorfizmu grafu dla grafów, w których stopnie wierzchołków są ograniczone stałą. Problem automorfizmu grafu to problem wielomianu wiele jeden sprowadzalny do problemu izomorfizmu grafu, ale odwrotna redukcja jest nieznana. Natomiast twardość jest znana, gdy automorfizmy są ograniczone w określony sposób; na przykład stwierdzenie istnienia automorfizmu bez punktu stałego (automorfizmu, który nie ustala wierzchołka) jest NP-zupełne, a problem zliczania takich automorfizmów to ♯P-zupełny .

Algorytmy, oprogramowanie i aplikacje

Chociaż dla ogólnego problemu automorfizmu grafów nie są znane najgorsze algorytmy czasu wielomianowego, znalezienie grupy automorfizmu (i wydrukowanie zbędnego zestawu generatorów) dla wielu dużych grafów powstających w aplikacjach jest raczej łatwe. Do tego zadania dostępnych jest kilka narzędzi oprogramowania typu open source, w tym NAUTY , BLISS i SAUCY . SAUCY i BLISS są szczególnie wydajne w przypadku rzadkich grafów, np. SAUCY przetwarza niektóre grafy z milionami wierzchołków w zaledwie kilka sekund. Jednak BLISS i NAUTY mogą również tworzyć etykietowanie kanoniczne , podczas gdy SAUCY jest obecnie zoptymalizowany pod kątem rozwiązywania automorfizmu wykresów. Ważną obserwacją jest to, że dla grafu na n wierzchołkach grupa automorfizmu może być określona przez nie więcej niż n-1 generatorów, a powyższe pakiety oprogramowania gwarantują spełnienie tego ograniczenia jako efekt uboczny ich algorytmów (minimalne zestawy generatory są trudniejsze do znalezienia i nie są szczególnie przydatne w praktyce). Wydaje się również, że całkowite wsparcie (tj. liczba przesuniętych wierzchołków) wszystkich generatorów jest ograniczona funkcją liniową n , co jest ważne w analizie w czasie wykonywania tych algorytmów. Jednak nie zostało to ustalone na marzec 2012 r.

Praktyczne zastosowania automorfizmu grafów obejmują rysowanie grafów i inne zadania wizualizacyjne, rozwiązywanie ustrukturyzowanych instancji Boolean Satisfiability powstających w kontekście weryfikacji formalnej i logistyki . Symetria molekularna może przewidywać lub wyjaśniać właściwości chemiczne.

Wyświetlacz symetrii

Kilka wykresie rysunku naukowcy badali algorytmy do rysowania wykresów w taki sposób, że Automorfizmy na wykresie widoczne jest w symetrii rysunku. Można to zrobić albo za pomocą metody, która nie jest zaprojektowana wokół symetrii, ale która automatycznie generuje rysunki symetryczne, jeśli to możliwe, lub przez wyraźne zidentyfikowanie symetrii i użycie ich do kierowania umieszczeniem wierzchołków na rysunku. Nie zawsze jest możliwe jednoczesne wyświetlenie wszystkich symetrii wykresu, więc może być konieczne wybranie, które symetrie mają być wyświetlane, a które nie wizualizowane.

Rodziny grafów definiowane przez ich automorfizmy

Kilka rodzin grafów jest zdefiniowanych przez posiadanie pewnych typów automorfizmów:

  • Asymetryczny wykres jest nieukierunkowane wykres tylko trywialny automorfizm.
  • Wierzchołek-przechodni wykres jest nieukierunkowane wykres, w którym każdy wierzchołek może być mapowane automorfizmem na inny wierzchołka.
  • Wykres krawędzi przechodni jest nieukierunkowane wykres, w którym każde ostrze może być odwzorowana przez automorfizmem do dowolnej innej krawędzi.
  • Symetryczny wykres wykres taki sposób, że każda para sąsiadujących ze sobą wierzchołki mogą być odwzorowywane przez automorfizmem do innej pary sąsiednich wierzchołków.
  • Dystansu przechodni wykres jest wykresem, tak że każda para wierzchołków może być mapowane automorfizmem każdą inną parę wierzchołków, które są w takiej samej odległości od siebie.
  • Pół-symetryczny wykres jest wykresem, który jest krawędzi przechodni ale nie wierzchołek-przechodnia.
  • Pół przechodni wykres jest wykresem, który to wierzchołek-przechodni i krawędzi przechodni ale nie symetryczny.
  • Skosu symetryczny wykres jest kierowane wraz z wykresem Ď permutacji na wierzchołkach, która odwzorowuje krawędzi do krawędzi, ale zmienia kierunek każdej krawędzi. Dodatkowo σ musi być inwolucją .

Relacje włączenia między tymi rodzinami przedstawia poniższa tabela:

Szkielet dwunastościanu
Strzałka wschód.svg
Wykres Shrikhande
Strzałka west.svg
Wykres Paley
odległość-przechodnia odległość-regularna mocno regularne
Strzałka południowa.svg
Wykres F26A
Strzałka west.svg
Wykres Nauru
symetryczny (przechodni łukowo) t -przechodni, t ≥ 2
Strzałka południowa.svg
(jeśli podłączony)
Wykres Holta
Strzałka wschód.svg
Wykres Folkman
Strzałka wschód.svg
Kompletny wykres dwudzielny K3,5
wierzchołki i krawędzie przechodnie krawędź przechodnia i regularna krawędź przechodnia
Strzałka południowa.svg
Strzałka południowa.svg
Szkielet ściętego czworościanu
Strzałka wschód.svg
Wykres Fruchta
wierzchołek-przechodni regularny
Strzałka północ.svg
Szkielet trójkątnego pryzmatu
Wykres Cayleya

Zobacz też

Bibliografia

Linki zewnętrzne