Mục lục:
Định nghĩa - Acyclic có nghĩa là gì?
Acyclic là một tính từ được sử dụng để mô tả biểu đồ trong đó không có chu trình hoặc đường dẫn khép kín. Nói cách khác, đó là một đường dẫn không có đỉnh lặp lại (các nút tạo thành biểu đồ hoặc liên kết giữa các đỉnh), ngoại trừ các đỉnh bắt đầu và kết thúc.
Trong khoa học máy tính, nó được sử dụng trong cụm từ biểu đồ chu kỳ hướng trực tiếp (DAG). Về mặt kỹ thuật, DAG là một biểu đồ được hình thành bằng cách kết nối các đỉnh khác nhau với các cạnh được định hướng theo cách không cho phép điều hướng qua một chuỗi có thể có một đỉnh đi qua nó hơn hai lần; do đó, không có con đường khép kín.
Techopedia giải thích Acyclic
Khái niệm về DAG được sử dụng để thiết kế các trò chơi chữ như Scrabble và các ứng dụng nghiên cứu khoa học dựa trên sinh học và di truyền học. DAG cũng được sử dụng trong các mô hình xây dựng trong toán học, khoa học máy tính, mạch điện tử, hoạt động biên dịch, tính toán các giá trị liên quan trên các biểu mẫu, v.v … DAG được sử dụng trong các mô hình để minh họa luồng thông tin qua hệ thống. DAG là sự thay thế tốt hơn cho các kỹ thuật khác trong cấu trúc dữ liệu bằng cách cung cấp tối ưu hóa sử dụng bộ nhớ và cải thiện hiệu suất.
Một chu trình là một đường đi qua một chuỗi các đỉnh, sao cho cả hai đỉnh bắt đầu và kết thúc là cùng một điểm. Nếu một đồ thị không có chu kỳ như vậy, thì nó được gọi là chu kỳ. Ví dụ, hãy xem xét ba đỉnh, X, Y và Z được liên kết trong một biểu đồ. Trong khi di chuyển từ bất kỳ một trong ba đỉnh qua cấu trúc của nó theo các cách khác nhau có thể, nếu người ta không thể quay trở lại cùng một đỉnh bắt đầu mà không ghé thăm bất kỳ đỉnh (trừ đỉnh hoặc điểm bắt đầu) hai lần, thì đó là đồ thị Acyclic.
Độ dài của chu kỳ ngắn nhất và chu vi của đồ thị chu kỳ được xác định là vô cùng. Ví dụ về đồ thị theo chu kỳ là Cây và Rừng. Một đồ thị theo chu kỳ và vô hướng với hai đỉnh bất kỳ được kết nối bởi chỉ một đường được gọi là cây. Cây gia đình là một ví dụ điển hình về khái niệm cây tuần hoàn có hướng. Một khu rừng là một đồ thị vô hướng có tập con là cây.
