algorytm wykresu do wykrywania nawet cykli

Question

Mam nieukierunkowany wykres. Jedna krawędź na tym wykresie jest wyjątkowa. Chcę znaleźć wszystkie inne krawędzie, które są częścią równego cyklu zawierającego pierwszą krawędź.

Nie muszę wyliczać wszystkich cykli, które z natury są NP. Po prostu muszę wiedzieć, dla każdej krawędzi, czy spełnia ona powyższe warunki.

Szukanie brutalnej siły działa oczywiście, ale jest zbyt wolne, a ja staram się wymyślić coś lepszego. Każda pomoc doceniona.

Answer 1

Myślę, że mamy odpowiedź (muszę przyznać, że mój kolega z pomysłem). Zasadniczo jego pomysł polega na wykonaniu algorytmu wypełniania powodzi w przestrzeni równych cykli. Działa to, ponieważ jeśli masz duży, równomierny cykl utworzony przez połączenie dwóch mniejszych cykli, mniejsze cykle muszą być równe lub oba nieparzyste. Podobnie połączenie cyklu nieparzystego i parzystego zawsze tworzy większy cykl nieparzysty.

Jest to praktyczna opcja, ponieważ mogę sobie wyobrazić przypadki patologiczne, na które składają się naprzemienne cykle parzyste i nieparzyste. W tym przypadku nigdy nie znajdziemy dwóch sąsiednich nawet cykli, więc algorytm będzie powolny. Ale jestem przekonany, że takie przypadki nie pojawiają się w prawdziwej chemii. Przynajmniej w chemii, jak to jest obecnie znane, 30 lat temu nigdy nie słyszeliśmy o fulerenach.

Answer 2

Jeśli wykres ma mały stopień węzła, można rozważyć zastosowanie innego graficzne przedstawienie:

Niech trzy atomy u,v,w i dwa wiązania chemiczne e=(u,v) i k=(v,w). Typowym sposobem reprezentowania takich danych jest przechowywanie u,v,w jako węzłów i e,k jako krawędzi na wykresie.

Można jednak stanowią e i k jako węzły na wykresie, posiadające krawędzie jak f=(e,k) gdzie f oznacza związek 2-STEP u do w, f=(e,k) lub f=(u,v,w). Uruchomienie dowolnego algorytmu w celu znalezienia cykli na takim wykresie spowoduje zwrócenie wszystkich cykli na oryginalnym wykresie.

Oczywiście jest to efektywne tylko wtedy, gdy oryginalny wykres ma niewielki stopień węzła. Kiedy użytkownik wykonuje edycję, możesz łatwo edytować odpowiednio alternatywną reprezentację.