Kanonizacja wykresu - Graph canonization
W teorii grafów , gałęzi matematyki, kanonizacja grafów to problem ze znalezieniem postaci kanonicznej danego grafu G . Postać kanoniczna to graf oznaczony jako Canon( G ), który jest izomorficzny z G , tak że każdy graf, który jest izomorficzny z G ma taką samą formę kanoniczną jak G . Zatem od rozwiązania problemu kanonizacji grafów można również rozwiązać problem izomorfizmu grafów : aby sprawdzić, czy dwa grafy G i H są izomorficzne, obliczyć ich formy kanoniczne Canon( G ) i Canon( H ) i sprawdzić, czy są to dwie formy kanoniczne są identyczne.
Kanoniczna postać grafu jest przykładem kompletnego niezmiennika grafu : każde dwa izomorficzne grafy mają tę samą postać kanoniczną, a każde dwa nieizomorficzne grafy mają różne postacie kanoniczne. I odwrotnie, każdy kompletny niezmiennik grafów może być użyty do skonstruowania postaci kanonicznej. Zbiór wierzchołków grafu n -wierzchołkowego można utożsamiać liczbami całkowitymi od 1 do n , a przy użyciu takiej identyfikacji kanoniczną postać grafu można również opisać jako permutację jego wierzchołków. Kanoniczne formy grafu są również nazywane etykietami kanonicznymi , a kanonizacja grafu jest również czasami znana jako kanonizacja grafu .
Złożoność obliczeniowa
Oczywiście problem kanonizacji grafów jest co najmniej tak trudny obliczeniowo, jak problem izomorfizmu grafów . W rzeczywistości izomorfizm grafu jest nawet AC 0 - sprowadzalny do kanonizacji grafu. Pytaniem otwartym pozostaje jednak, czy te dwa problemy są równoważne w czasie wielomianowym .
Podczas gdy istnienie (deterministycznych) algorytmów wielomianowych dla izomorfizmu grafów jest nadal otwartym problemem w teorii złożoności obliczeniowej , w 1977 László Babai poinformował, że z prawdopodobieństwem co najmniej 1 − exp(−O( n )), prosty algorytm klasyfikacji wierzchołków daje kanoniczne etykietowanie grafu jednolicie losowo wybranego ze zbioru wszystkich n- wierzchołkowych grafów po zaledwie dwóch krokach uściślania. Niewielkie modyfikacje i dodany etap wyszukiwania w głąb umożliwiają kanoniczne oznaczanie tak jednolicie wybranych losowych wykresów w liniowym oczekiwanym czasie. Wynik ten rzuca nieco światła na fakt, dlaczego wiele zgłoszonych algorytmów izomorfizmu grafów zachowuje się dobrze w praktyce. Był to ważny przełom w probabilistycznej teorii złożoności, która stała się szeroko znana w formie rękopisu i która wciąż była cytowana jako „nieopublikowany rękopis” długo po tym, jak została zgłoszona na sympozjum.
Powszechnie znaną formą kanoniczną jest najmniejszy leksykograficznie graf w klasie izomorfizmu , który jest grafem klasy o najmniejszej leksykograficznie macierzy sąsiedztwa traktowanej jako ciąg liniowy. Jednak obliczenie najmniejszego leksykograficznie grafu jest NP-trudne .
W przypadku drzew zwięzły wielomianowy algorytm kanonizacji wymagający przestrzeni O(n) przedstawia Read (1972) . Rozpocznij od oznaczenia każdego wierzchołka łańcuchem 01. Iteracyjnie dla każdego x nie będącego liściem usuń początkowe 0 i końcowe 1 z etykiety x; następnie posortuj etykietę x wraz z etykietami wszystkich sąsiednich kartek w porządku leksykograficznym. Połącz te posortowane etykiety, dodaj z powrotem początkowe 0 i końcowe 1, ustaw nową etykietę x i usuń sąsiednie liście. Jeśli pozostały dwa wierzchołki, połącz ich etykiety w porządku leksykograficznym.
Aplikacje
Kanonizacja grafów jest istotą wielu algorytmów izomorfizmu grafów. Jednym z wiodących narzędzi jest Nauty.
Powszechnym zastosowaniem kanonizacji grafów jest graficzna eksploracja danych , w szczególności w chemicznych bazach danych .
Pewna liczba identyfikatorów dla substancji chemicznych , takich jak Smiles i Inchi etapów zastosowanie w obliczeniach postać kanoniczną, która jest zasadniczo kanonicznej wykresu, który stanowi cząsteczkę. Identyfikatory te mają na celu zapewnienie standardowego (a czasami czytelnego dla człowieka) sposobu kodowania informacji molekularnych oraz ułatwienia wyszukiwania takich informacji w bazach danych i w Internecie.