Зміст:
Визначення - Що означає Acyclic?
Ациклічний - прикметник, що використовується для опису графа, в якому немає циклу чи замкнутого шляху. Іншими словами, це шлях без повторних вершин (вузлів, що утворюють графік, або зв’язків між вершинами), виключаючи початкові та кінцеві вершини.
У інформатиці він використовується у фразі "спрямований ациклічний графік" (DAG). Технічно DAG - це графік, сформований шляхом з'єднання різних вершин з ребрами, які спрямовані таким чином, що не дозволяє переходити через послідовність, яка може мати вершину, що проходить через неї більше ніж удвічі; отже, закритого шляху немає.
Техопедія пояснює Acyclic
Концепція DAG використовується для розробки ігор на слова, такі як Scrabble та науково-дослідницькі програми на основі біології та генетики. DAG також використовується для побудови моделей з математики, інформатики, електронних схем, операцій компіляції, обчислення пов'язаних значень на формах тощо. DAG використовуються в моделях для ілюстрації потоку інформації через систему. DAG є кращою альтернативою іншим методам структури даних, забезпечуючи оптимізацію використання пам'яті та підвищення продуктивності.
Цикл - це шлях, пройдений через послідовність вершин, таким, що і початкова, і кінцева вершини є однаковою точкою. Якщо в графіку немає таких циклів, його називають ациклічним. Наприклад, розглянемо три вершини, X, Y і Z, пов'язані в графі. Під час руху з будь-якої з трьох вершин через його структуру різними можливими способами, якщо неможливо повернутися до тієї самої початкової вершини, не відвідуючи жодної вершини (виключаючи початкову вершину чи точку) двічі, то це ациклічний графік.
Довжина найкоротшого циклу і окружність ациклічного графіка визначаються як нескінченність. Прикладами ациклічних графіків є Дерева та Ліси. Ациклічний і непрямий графік з будь-якими двома вершинами, з'єднаними лише одним шляхом, називається деревом. Родинне дерево - хороший приклад концепції спрямованого ациклічного дерева. Ліс - це непрямий графік, підмножини якого - дерева.
