Podstawa cyklu

Symetryczna różnica dwóch cykli to podgraf Eulera

W teorii grafów , gałęzi matematyki, podstawą cyklu nieskierowanego wykresu jest zestaw prostych cykli , który stanowi podstawę przestrzeni cykli grafu. Oznacza to, że jest to minimalny zestaw cykli, który pozwala na wyrażenie każdego podwykresu parzystego stopnia jako symetrycznej różnicy cykli bazowych.

Podstawową podstawę cyklu można utworzyć z dowolnego drzewa rozpinającego lub lasu rozpinającego danego grafu, wybierając cykle utworzone przez połączenie ścieżki w drzewie i pojedynczej krawędzi na zewnątrz drzewa. Alternatywnie, jeśli krawędzie wykresu mają dodatnie wagi, podstawa minimalnego cyklu wagowego może być skonstruowana w czasie wielomianowym .

W grafach planarnych podstawą cyklu jest zbiór ograniczonych cykli osadzania grafu. Podstawa minimalnego cyklu wagowego wykresu planarnego odpowiada drzewu Gomory-Hu wykresu dualnego .

Definicje

Rozpinający podgraf danego grafu G ma taki sam zestaw wierzchołków jak sam G , ale prawdopodobnie mniej krawędzi. Mówimy, że graf G lub jeden z jego podgrafów jest eulerowski , jeśli każdy z jego wierzchołków ma parzysty stopień (liczbę krawędzi padających). Każdy prosty cykl w grafie jest podgrafem Eulera, ale mogą istnieć inne. Przestrzeń cyklu grafu to zbiór jego podgrafów Eulera. Tworzy przestrzeń wektorową nad dwuelementowym ciałem skończonym . Operacja dodawania wektorów to symetryczna różnica dwóch lub więcej podgrafów, która tworzy kolejny podgraf składający się z krawędzi, które pojawiają się nieparzystą liczbę razy w argumentach symetrycznej operacji różnicowej.

Podstawa cyklu jest bazą tej przestrzeni wektorowej, w której każdy wektor bazowy reprezentuje prosty cykl. Składa się z zestawu cykli, które można łączyć za pomocą różnic symetrycznych, tworząc każdy podgraf Eulera, i jest to minimalne przy tej właściwości. Każda podstawa cykliczna danego grafu ma taką samą liczbę cykli, co jest równe wymiarowi jej przestrzeni cykli. Liczba ta nazywana jest $do$ obwodu wykresu i jest równa gdzie jest liczbą krawędzi na wykresie, $displaystyle$$m-n}$$to$ to liczba wierzchołków, a liczba połączonych komponentów .

Specjalne podstawy rowerowe

Zbadano kilka specjalnych typów podstaw cykli, w tym podstawowe podstawy cykli, słabo fundamentalne podstawy cykli, rzadkie (lub 2-) podstawy cykli i integralne podstawy cykli.

Cykle indukowane

Każdy wykres ma podstawę cykliczną, w której każdy cykl jest cyklem indukowanym . W grafie spójnym z 3 wierzchołkami zawsze istnieje baza składająca się z cykli peryferyjnych , czyli cykli, których usunięcie nie rozdziela pozostałego grafu. W każdym grafie innym niż utworzony przez dodanie jednej krawędzi do cyklu, cykl peryferyjny musi być cyklem indukowanym.

Podstawowe cykle

Jeśli jest drzewem rozpinającym $lub$ lasem rozpinającym danego wykresu $displaystyle$ jest $T$ , która nie należy do $T}, to podstawowa T {\ displaystyle$ } cykl zdefiniowany przez ${\ displaystyle e}$$jest$ cyklem składającym się ze ścieżki w $T$$}$ łączącej punkty końcowe mi ${\ displaystyle$ . Istnieją dokładnie $jednym dla każdej$ , która nie należy do $T}$ . Każdy z nich jest $liniowo$ niezależny od pozostałych cykli, ponieważ zawiera krawędź której nie ma w żadnym innym podstawowym cyklu. Dlatego podstawowe cykle tworzą podstawę dla przestrzeni cykli. Tak skonstruowana baza cykliczna nazywana jest fundamentalną bazą cykliczną lub silnie fundamentalną bazą cykliczną .

Możliwe jest również scharakteryzowanie podstawowych baz cykli bez określania drzewa, dla którego są one fundamentalne. Istnieje drzewo, dla którego dana baza cyklu jest fundamentalna wtedy i tylko wtedy, gdy każdy cykl zawiera krawędź, która nie jest zawarta w żadnym innym cyklu bazowym, to znaczy każdy cykl jest niezależny od innych. Wynika z tego, że zbiór cykli jest podstawową podstawą cyklu $i$$,$ gdy ma właściwość niezależności i ma odpowiednią liczbę cykli, aby być podstawą .

Słabo fundamentalne cykle

Podstawę cyklu nazywamy słabo fundamentalną , jeśli jej cykle można uporządkować liniowo w taki sposób, że każdy cykl zawiera co najmniej jedną krawędź, która nie jest zawarta w żadnym wcześniejszym cyklu. Podstawowa podstawa cyklu jest automatycznie słabo fundamentalna (dla dowolnego uporządkowania krawędzi). Jeśli każda podstawa cyklu wykresu jest słabo fundamentalna, to samo dotyczy każdej mniejszej części wykresu. W oparciu o tę właściwość, klasę grafów (i multigrafów ), dla których każda baza cyklu jest słabo fundamentalna, można scharakteryzować za pomocą pięciu zabronionych drugorzędnych : wykres piramidy kwadratowej , multigraf utworzony przez podwojenie wszystkich krawędzi cyklu o czterech wierzchołkach, dwa multigrafy utworzone przez podwojenie dwóch krawędzi czworościanu oraz multigraf utworzony przez potrojenie krawędzi trójkąta.

Cykle twarzy

Jeśli spójny skończony graf planarny jest osadzony w płaszczyźnie, każda ściana osadzania jest ograniczona cyklem krawędzi. Jedna ściana jest z konieczności nieograniczona (zawiera punkty dowolnie oddalone od wierzchołków grafu), a pozostałe ściany są ograniczone. Zgodnie ze $wzorem$ Eulera dla istnieją ograniczone Symetryczna różnica dowolnego zestawu cykli ścian jest granicą odpowiedniego zestawu ścian, a różne zestawy ograniczonych ścian mają różne granice, więc nie jest możliwe przedstawienie tego samego zestawu jako symetrycznej różnicy cykli ścian w więcej niż jednym sposób; oznacza to, że zbiór cykli twarzy jest liniowo niezależny. Jako liniowo niezależny zbiór wystarczającej liczby cykli, koniecznie tworzy podstawę cyklu. Jest to zawsze słabo fundamentalna podstawa cyklu i jest fundamentalna wtedy i tylko wtedy, gdy osadzanie grafu jest na płaszczyźnie zewnętrznej .

W przypadku grafów prawidłowo osadzonych na innych powierzchniach, tak że wszystkie ściany osadzania są dyskami topologicznymi, generalnie nie jest prawdą, że istnieje podstawa cykli wykorzystująca tylko cykle ścian. Cykle twarzy tych zanurzeń generują odpowiedni podzbiór wszystkich podgrafów Eulera. H ${\ Displaystyle H_ {2} (S \ mathbb {Z} _ {2})}$$powierzchni$ charakteryzuje podgrafy Eulera, których nie można jako granica zbioru ścian. Kryterium planarności Mac Lane'a wykorzystuje tę ideę do scharakteryzowania grafów planarnych pod względem podstaw cykli: skończony graf nieskierowany jest planarny wtedy i tylko wtedy, gdy ma rzadką podstawę cykliczną lub 2-podstawową , w której uczestniczy każda krawędź grafu w co najwyżej dwóch cyklach bazowych. W grafie planarnym podstawa cyklu utworzona przez zbiór ograniczonych ścian jest z konieczności rzadka i odwrotnie, rzadka podstawa cyklu dowolnego grafu z konieczności tworzy zbiór ograniczonych ścian płaskiego osadzania jego wykresu.

Integralne podstawy

Przestrzeń cykli wykresu można interpretować za pomocą teorii homologii jako grupy homologii uproszczonego $)}$ H_ {1} (G, \ mathbb {Z} _ {2} złożony z punktem dla każdego wierzchołka wykresu i odcinkiem linii dla każdej krawędzi wykresu. $konstrukcję$ można na nad $_$ _ Ważnym przypadkiem $,$ jest pierścień liczb całkowitych którego grupa wolną abelową wolnej grupa abelowa generowana przez krawędzie grafu. Mniej abstrakcyjnie, tę grupę można skonstruować, przypisując dowolną orientację krawędziom danego wykresu; wtedy elementy $oznaczeniami$ krawędzi wykresu liczbami całkowitymi z przychodzące etykiety krawędzi są równe sumie wychodzących etykiet krawędzi. Operacja grupowa polega na dodawaniu tych wektorów etykiet. Podstawa cyklu całkowego to zbiór cykli prostych, który generuje tę grupę.

Minimalna waga

Jeśli krawędziom grafu przypisano rzeczywiste wagi, wagę podgrafu można obliczyć jako sumę wag jego krawędzi. Podstawa minimalnej wagi przestrzeni cyklu jest z konieczności podstawą cyklu: zgodnie z twierdzeniem Veblena każdy podgraf Eulera, który sam w sobie nie jest cyklem prostym, można rozłożyć na wiele cykli prostych, które z konieczności mają mniejszą wagę.

Dzięki standardowym właściwościom baz w przestrzeniach wektorowych i matroidach podstawa cyklu minimalnej wagi nie tylko minimalizuje sumę wag swoich cykli, ale także minimalizuje każdą inną monotoniczną kombinację wag cykli. Na przykład podstawa cyklu minimalizuje wagę najdłuższego cyklu.

Algorytmy czasu wielomianowego

W dowolnej przestrzeni wektorowej, a bardziej ogólnie w dowolnej matroidie , minimalną podstawę wagi można znaleźć za pomocą zachłannego algorytmu , który rozważa potencjalne elementy bazy pojedynczo, w porządku posortowanym według ich wag, i który zawiera element w bazie, gdy jest jest liniowo niezależna od wcześniej wybranych elementów bazowych. Testowanie liniowej niezależności można przeprowadzić za pomocą eliminacji Gaussa . Jednak nieskierowany graf może mieć wykładniczo duży zestaw prostych cykli, więc wygenerowanie i przetestowanie wszystkich takich cykli byłoby obliczeniowo niewykonalne.

Horton (1987) dostarczył pierwszego algorytmu czasu wielomianowego do znajdowania minimalnej podstawy wagi na wykresach, dla których każda waga krawędzi jest dodatnia. Jego $polegające na$ generowane cykle do małego zestawu cykli, zwanych cyklami Hortona . Cykl Hortona jest podstawowym cyklem drzewa najkrótszych ścieżek danego grafu. Istnieje co najwyżej n różnych najkrótszych drzew ścieżek (po jednym dla każdego wierzchołka początkowego), a każde z nich ma mniej niż m podstawowych cykli, co daje granicę całkowitej liczby cykli Hortona. Jak pokazał Horton, każdy cykl w podstawie cyklu minimalnej wagi jest cyklem Hortona. Użycie algorytmu Dijkstry do znalezienia każdego najkrótszego drzewa ścieżek, a następnie użycie eliminacji Gaussa do wykonania kroków testowych algorytmu zachłannej podstawy prowadzi do algorytmu czasu wielomianowego dla podstawy minimalnego cyklu wagowego. Kolejni badacze opracowali ulepszone algorytmy dla tego problemu, zmniejszając $krawędziami$ czasową najgorszego przypadku w celu $znalezienia$ podstawy minimalnego cyklu wagowego na wykresie z i do ${\ Displaystyle O (m ^ {2} n / \ log n)}$ .

NP-twardość

Znalezienie podstawowej bazy o minimalnej możliwej wadze jest ściśle związane z problemem znalezienia drzewa rozpinającego, które minimalizuje średnią odległości parami; oba są NP-trudne . Znalezienie słabo fundamentalnej podstawy minimalnej wagi jest również NP-trudne, a przybliżenie jej jest MAXSNP-trudne . Jeśli dopuszczalne są ujemne wagi i ujemnie ważone cykle, to znalezienie minimalnej podstawy cyklu (bez ograniczeń) jest również NP-trudne, ponieważ można jej użyć do znalezienia cyklu Hamiltona: jeśli wykres jest hamiltonowski, a wszystkie krawędzie mają wagę - 1, wówczas minimalna podstawa cyklu wagowego koniecznie obejmuje co najmniej jeden cykl Hamiltona.

W grafach planarnych

Podstawa minimalnego cyklu wagowego dla wykresu planarnego niekoniecznie jest taka sama, jak podstawa utworzona przez jego ograniczone ściany: może zawierać cykle, które nie są ścianami, a niektóre ściany mogą nie być uwzględnione jako cykle w podstawie minimalnego cyklu wagowego. Istnieje jednak podstawa cyklu minimalnej wagi, w której żadne dwa cykle się nie przecinają: na każde dwa cykle w bazie albo cykle obejmują rozłączne podzbiory ograniczonych ścian, albo jeden z dwóch cykli obejmuje drugi. Ten zestaw cykli odpowiada, na wykresie dualnym danego wykresu planarnego, zbiorowi cięć , które tworzą drzewo Gomory-Hu wykresu dualnego, podstawę minimalnej wagi jego przestrzeni cięcia . W oparciu o tę dwoistość można skonstruować niejawną reprezentację podstawy minimalnego cyklu wagowego na grafie planarnym w czasie. ${\ Displaystyle O (n \ log ^ {3} n)}$ .

Aplikacje

Podstawy cykli zostały wykorzystane do rozwiązywania okresowych problemów harmonogramowania, takich jak problem określania rozkładu jazdy dla systemu transportu publicznego. W tej aplikacji cykle podstawy cyklu odpowiadają zmiennym w programie całkowitoliczbowym do rozwiązania problemu.

W teorii sztywności strukturalnej i kinematyki podstawy cykli są wykorzystywane do kierowania procesem tworzenia układu nieredundantnych równań, które można rozwiązać w celu przewidywania sztywności lub ruchu konstrukcji. W tym zastosowaniu minimalne lub prawie minimalne podstawy cyklu wagowego prowadzą do prostszych układów równań.

W obliczeniach rozproszonych podstawy cykli zostały wykorzystane do analizy liczby kroków potrzebnych do ustabilizowania się algorytmu.

W bioinformatyce podstawy cykli zostały wykorzystane do określenia informacji o haplotypie na podstawie danych dotyczących sekwencji genomu. Zasady cykli zostały również wykorzystane do analizy trzeciorzędowej struktury RNA .

Podstawa minimalnego cyklu wagowego wykresu najbliższego sąsiada punktów pobranych z trójwymiarowej powierzchni może być wykorzystana do uzyskania rekonstrukcji powierzchni.

W cheminformatyce podstawa minimalnego cyklu wykresu molekularnego jest nazywana najmniejszym zestawem najmniejszych pierścieni .