ukierunkowany Graf acykliczny (dag) to rodzaj grafu, w którym niemożliwe jest powrót do tego samego węzła przez przemierzanie krawędzi.

w teorii grafów Graf to struktura składająca się z węzłów połączonych krawędziami. Możesz myśleć o węzłach jako punktach, a krawędziach jako liniach ciągniętych od punktu do punktu.

„skierowane” oznacza, że krawędzie grafu poruszają się tylko w jednym kierunku, gdzie przyszłe krawędzie zależą od poprzednich. Na przykład, jeśli miałbyś narysować proces gotowania i jedzenia posiłku składającego się z ryżu i kurczaka, zadania związane z tym musiałyby być uporządkowane topologicznie (lub uporządkowane topologicznie). Zanim będziesz mógł zjeść posiłek, musisz przygotować jedzenie, więc krawędź musiałaby być skierowana od przygotowania do jedzenia. Ale zanim będziesz mógł przygotować jedzenie, musisz kupić składniki, więc ponownie krawędź musi przejść od wcześniejszego wydarzenia do późniejszego wydarzenia. Przypuśćmy, że ryż został kupiony w oddzielnym wydarzeniu od kurczaka, byłyby dwie oddzielne krawędzie dla wydarzeń związanych z zakupami spożywczymi, które nie są ze sobą połączone, ale które zbiegają się w przypadku przygotowywania jedzenia.

„acykliczny” oznacza, że nie można rozpocząć w jednym punkcie grafu i wrócić do niego podążając za krawędziami. Podczas gdy cykl wraca do pierwotnego punktu początkowego jak okrąg, Wykres acykliczny nadal porusza się w kierunku liniowym i nigdy nie wraca do punktu początkowego. Kontynuując wcześniejszy przykład kolacji z kurczakiem i ryżem, nie można poruszać się po wykresie od zakupu ryżu do przygotowania jedzenia do zakupu kurczaka, ponieważ wymagałoby to cofnięcia się po wykresie. Niemożliwe jest przygotowanie kurczaka, jeśli jeszcze go nie kupiłeś.

dag są probabilistycznymi graficznymi reprezentacjami sieci bayesowskich, które mają na celu modelowanie zależności warunkowej (np. zjedzenie posiłku zależy od jego przygotowania).

kilka kryptowalut używa dag zamiast struktur danych blockchain w celu przetwarzania i walidacji transakcji. W przypadku sieci blockchain wszystkie węzły w sieci opierają się na tym samym pojedynczym łańcuchu bloków, a każdy blok odnosi się do tego, który był przed nim. Możliwą wadą tej struktury jest to, że nakłada ona ograniczenie przepustowości transakcji w sieci, ponieważ istnieje tylko tak wiele transakcji, które mogą zmieścić się w jednym bloku i tylko tak wiele bloków, które można zweryfikować w danym czasie. W sieci DAG transakcje są bezpośrednio powiązane ze sobą, a nie grupowane w bloki, a transakcje mogą być przetwarzane jednocześnie z innymi. Rezultatem jest zmniejszone wąskie gardło przepustowości transakcji.