Cykl (teoria grafów) - Cycle (graph theory)

Wykres z kolorami krawędzi ilustrującymi ścieżkę HAB (zielony), zamkniętą ścieżkę lub spacer z powtórzonym wierzchołkiem BDEFDCB (niebieski) i cyklem bez powtarzającej się krawędzi lub wierzchołka HDGH (czerwony).

W teorii wykres , A cykl w wykresie jest niepusty szlak , w którym tylko powtarzające wierzchołki są pierwszy i ostatni wierzchołków. Skierowane cykl w skierowanej wykresu jest niepusty skierowane szlak , w którym tylko powtarzające wierzchołki są pierwszy i ostatni wierzchołków.

Wykres bez cykli nazywamy grafem acyklicznym . Graf skierowany bez cykli skierowanych nazywany jest grafem acyklicznym skierowanym . Spójny graf bez cykli nazywa się drzewo .

Definicje

Obwód, cykl

  • Obwód jest niepusty szlak , w którym pierwszy wierzchołek jest równy ostatniej wierzchołka ( zamknięte szlak ).
Niech G = ( V , E , ϕ ) będzie wykresem. Obwód to niepusty ślad ( e 1 , e 2 ,…, e n ) z sekwencją wierzchołków ( v 1 , v 2 ,…, v n , v 1 ) .
  • Cyklu lub prosty układ jest układem, w którym powtarza się tylko wierzchołek jest pierwszym / wierzchołek.
  • Długość obwodu lub cykl jest liczbą krawędzi stron.

Obwód sterowany, cykl

  • Skierowane obwód jest niepusty skierowane szlak , w którym pierwszy wierzchołek jest równy ostatniej wierzchołka.
Niech G = ( V , E , ϕ ) będzie grafem skierowanym. Obwód skierowany to niepusty, skierowany ślad ( e 1 , e 2 ,…, e n ) z sekwencją wierzchołków ( v 1 , v 2 ,…, v n , v 1 ) .
  • Skierowane cyklu lub prosty skierowana obwód jest skierowany obwodu, w którym tylko powtarzające się wierzchołek jest pierwszym / wierzchołek.

Cykle bez akordów

Na tym wykresie zielony cykl (ABCDEFA) jest pozbawiony akordów, podczas gdy czerwony cykl (GHIJKLG) nie. Dzieje się tak, ponieważ krawędź KI jest akordem.

Cykl chordless na wykresie, zwany również otworem lub indukowane cykl jest cyklem tak, że żadne dwa wierzchołki cyklu są połączone z krawędzią, która sama w sobie nie należy do tego cyklu. Antyhole jest uzupełnieniem dziury grafowej . Cykle bez cięciwy mogą być używane do scharakteryzowania wykresów doskonałych : zgodnie z mocnym twierdzeniem o grafie doskonałym, wykres jest doskonały wtedy i tylko wtedy, gdy żaden z jego otworów lub przeciwotworków nie ma nieparzystej liczby wierzchołków większej niż trzy. Cięciwy wykres , specjalny rodzaj graf doskonały, ma otwory o dowolnym większym rozmiarze niż trzy.

Obwód wykresu jest długością najkrótszej cyklu; ten cykl jest z konieczności bez akordów. Klatki definiuje się jako najmniejsze regularne wykresy z podanymi kombinacjami stopnia i obwodu.

Cykl obwodowy jest to cykl, w postaci wykresu z właściwości, co dwie krawędzie nie na cykl może być połączony przez ścieżkę, której wnętrze wierzchołki uniknięcia cyklu. Na wykresie, który nie jest tworzony przez dodanie jednej krawędzi do cyklu, cykl peryferyjny musi być cyklem indukowanym.

Przestrzeń rowerowa

Termin cykl może również odnosić się do elementu przestrzeni cykli wykresu. Istnieje wiele przestrzeni cykli, po jednej dla każdego pola współczynników lub pierścienia. Najbardziej powszechna jest binarna przestrzeń cyklu (zwykle nazywana po prostu przestrzenią cyklu ), która składa się z zestawów krawędzi, które mają równy stopień w każdym wierzchołku; tworzy przestrzeń wektorową nad polem dwuelementowym . Zgodnie z twierdzeniem Veblena , każdy element przestrzeni cykli może zostać utworzony jako rozłączny na krawędzi związek prostych cykli. Pełnym cyklu wykresu jest prosty zestaw cykli tworzy podstawę przestrzeni cyklu.

Korzystając z pomysłów z topologii algebraicznej , przestrzeń cykli binarnych uogólnia się na przestrzenie wektorowe lub moduły nad innymi pierścieniami, takimi jak liczby całkowite, liczby wymierne lub rzeczywiste itp.

Wykrywanie cyklu

Istnienie cyklu w grafach ukierunkowanych i nieukierunkowanych można określić na podstawie tego, czy wyszukiwanie w pierwszej kolejności w głąb (DFS) znajduje krawędź wskazującą na przodka bieżącego wierzchołka (zawiera tylną krawędź ). Wszystkie tylne krawędzie, przez które przeskakuje DFS, są częścią cykli. W grafie nieukierunkowanym krawędź do rodzica węzła nie powinna być liczona jako tylna krawędź, ale znalezienie dowolnego innego już odwiedzonego wierzchołka wskaże tylną krawędź. W przypadku grafów nieukierunkowanych, do znalezienia cyklu na wykresie n -vertex potrzebny jest tylko czas O ( n ) , ponieważ co najwyżej n  - 1 krawędzi może być krawędziami drzewa.

Wiele algorytmów sortowania topologicznego wykrywa również cykle, ponieważ są to przeszkody dla istnienia porządku topologicznego. Ponadto, jeśli ukierunkowany wykres został podzielony na silnie powiązane komponenty , cykle istnieją tylko w obrębie komponentów, a nie między nimi, ponieważ cykle są silnie połączone.

W przypadku grafów skierowanych można zastosować algorytmy oparte na wiadomościach rozproszonych. Algorytmy te opierają się na założeniu, że wiadomość wysłana przez wierzchołek w cyklu powróci do siebie. Algorytmy wykrywania cykli rozproszonych są przydatne do przetwarzania wykresów na dużą skalę przy użyciu rozproszonego systemu przetwarzania wykresów w klastrze komputerowym (lub superkomputerze).

Zastosowania wykrywania cykli obejmują wykorzystanie wykresów oczekiwania na wykrycie zakleszczeń w systemach współbieżnych.

Pokrywanie wykresów cyklami

W swojej pracy z 1736 r. na temat Siedmiu Mostów Królewca , powszechnie uważanej za narodziny teorii grafów, Leonhard Euler udowodnił, że aby skończony graf nieskierowany miał zamknięty spacer, który odwiedza każdą krawędź dokładnie raz, jest konieczne i wystarczające, aby być połączone z wyjątkiem izolowanych wierzchołków (to znaczy wszystkie krawędzie są zawarte w jednym komponencie) i mieć równy stopień na każdym wierzchołku. Odpowiednia charakterystyka istnienia zamkniętego spaceru odwiedzającego każdą krawędź dokładnie raz na wykresie skierowanym jest taka, że ​​graf jest silnie połączony i ma równą liczbę krawędzi wchodzących i wychodzących w każdym wierzchołku. W obu przypadkach wynikowy spacer jest znany jako cykl Eulera lub wycieczka Euler. Jeśli skończony graf nie skierowany ma równy stopień na każdym z jego wierzchołków, niezależnie od tego, czy jest połączony, to można znaleźć zestaw prostych cykli, które razem pokrywają każdą krawędź dokładnie raz: to jest twierdzenie Veblena . Gdy połączony wykres nie spełnia warunków twierdzenia Eulera, można mimo wszystko znaleźć w czasie wielomianowym zamknięty spacer o minimalnej długości obejmujący każdą krawędź, rozwiązując problem inspekcji trasy .

Problem znalezienia pojedynczego prostego cyklu, który pokrywa każdy wierzchołek dokładnie raz, zamiast zakrywać krawędzie, jest znacznie trudniejszy. Taki cykl jest nazywany cyklem hamiltonowskim , a ustalenie, czy istnieje, jest NP-zupełne . Opublikowano wiele badań dotyczących klas grafów, w przypadku których można zagwarantować, że zawierają cykle Hamiltona; jednym z przykładów jest twierdzenie Ore'a, że cykl Hamiltona zawsze można znaleźć na grafie, dla którego każda para nie sąsiadujących ze sobą wierzchołków ma stopnie sumujące się co najmniej do całkowitej liczby wierzchołków na wykresie.

W cyklu podwójne pokrywa Conjecture stwierdza, że dla każdego wykresu bezmostkowego , istnieje MultiSet prostych cyklach, które obejmuje każdą krawędź grafu dokładnie dwa razy. Udowodnienie, że to prawda (lub znalezienie kontrprzykładu) pozostaje otwartym problemem.

Klasy wykresów zdefiniowane przez cykle

Kilka ważnych klas grafów można zdefiniować lub scharakteryzować za pomocą ich cykli. Obejmują one:

Zobacz też

Bibliografia