Spisu treści:
Definicja - Co oznacza acykliczny?
Acykliczny to przymiotnik używany do opisania wykresu, na którym nie ma cyklu lub zamkniętej ścieżki. Innymi słowy, jest to ścieżka bez powtarzających się wierzchołków (węzłów tworzących wykres lub łączy między wierzchołkami), z wyłączeniem wierzchołków początkowych i końcowych.
W informatyce jest używany w wyrażeniu „ukierunkowany wykres acykliczny” (DAG). Technicznie, DAG jest wykresem utworzonym przez połączenie różnych wierzchołków z krawędziami, które są skierowane w sposób, który nie pozwala na nawigację przez sekwencję, która może przechodzić przez nią ponad dwa razy; dlatego nie ma zamkniętej ścieżki.
Techopedia wyjaśnia Acyclic
Koncepcja DAG służy do projektowania gier słownych, takich jak Scrabble oraz aplikacji do badań naukowych opartych na biologii i genetyki. DAG jest również stosowany w budowaniu modeli w matematyce, informatyce, obwodach elektronicznych, operacjach kompilacji, obliczaniu powiązanych wartości na formularzach itp. DAG są używane w modelach do zilustrowania przepływu informacji przez system. DAG stanowi lepszą alternatywę dla innych technik w strukturach danych, zapewniając optymalizację wykorzystania pamięci i poprawę wydajności.
Cykl jest ścieżką przechodzącą przez sekwencję wierzchołków, tak że wierzchołki początkowy i końcowy są tym samym punktem. Jeśli wykres nie ma takich cykli, określa się go jako acykliczny. Rozważmy na przykład trzy wierzchołki, X, Y i Z połączone na wykresie. Podczas gdy przemierza się którykolwiek 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, nie odwiedzając dwukrotnie wierzchołka (z wyjątkiem wierzchołka lub punktu początkowego), jest to wykres acykliczny.
Długość najkrótszego cyklu i obwód wykresu acyklicznego określa się jako nieskończoność. Przykładami wykresów acyklicznych są Drzewa i Lasy. Acykliczny i niekierowany wykres z dowolnymi dwoma wierzchołkami połączonymi tylko jedną ścieżką nazywa się drzewem. Drzewo genealogiczne jest dobrym przykładem koncepcji ukierunkowanego drzewa acyklicznego. Las to nieukierunkowany wykres, którego podzbiorami są drzewa.
