Co oznacza Acykliczny?
Acykliczny to przymiotnik używany do opisu grafu, w którym nie ma cyklu ani zamkniętej ścieżki. Innymi słowy, jest to ścieżka bez powtarzających się wierzchołków (węzłów tworzących graf lub połączeń między wierzchołkami), z wyłączeniem wierzchołków początkowego i końcowego.
W informatyce jest używany w wyrażeniu „kierowany graf acykliczny” (DAG). Technicznie rzecz biorąc, DAG to graf utworzony przez połączenie różnych wierzchołków krawędziami, które są skierowane w sposób, który nie pozwala na nawigację przez sekwencję, w której wierzchołek może przechodzić przez nią więcej niż dwa razy; dlatego nie ma zamkniętej ścieżki.
Techoteka wyjaśnia Graf Acykliczny
Koncepcja DAG jest używana do projektowania gier słownych, takich jak Scrabble, oraz aplikacji do badań naukowych opartych na biologii i genetyce. DAG jest również używany do budowania modeli w matematyce, informatyce, obwodach elektronicznych, operacjach kompilacji, obliczaniu wartości powiązanych na formularzach itp. DAG są używane w modelach do zilustrowania przepływu informacji przez system. DAG jest lepszą alternatywą dla innych technik w strukturach danych, ponieważ zapewnia optymalizację wykorzystania pamięci i poprawę wydajności.
Cykl to ścieżka przechodząca przez sekwencję wierzchołków, tak że zarówno wierzchołki początkowy, jak i końcowy są tym samym punktem. Jeśli graf nie ma takich cykli, to jest nazywany acyklicznym. Na przykład rozważmy trzy wierzchołki, X, Y i Z połączone w grafie. Podczas przechodzenia z dowolnego z trzech wierzchołków przez jego strukturę na różne możliwe sposoby, jeśli nie można powrócić do tego samego wierzchołka początkowego bez odwiedzenia dowolnego wierzchołka (z wyłączeniem wierzchołka początkowego lub punktu) dwa razy, to jest to graf acykliczny.
Długość najkrótszego cyklu i obwód grafu acyklicznego są zdefiniowane jako nieskończone. Przykładami grafów acyklicznych są drzewa i lasy. Acykliczny i niekierunkowy graf z dowolnymi dwoma wierzchołkami połączonymi tylko jedną ścieżką nazywa się drzewem. Drzewo genealogiczne jest dobrym przykładem koncepcji skierowanego drzewa acyklicznego. Las jest grafem niekierunkowym, którego podzbiorami są drzewa.