Оглавление:
Определение - Что означает Acyclic?
Acyclic - это прилагательное, используемое для описания графа, в котором нет цикла или замкнутого пути. Другими словами, это путь без повторяющихся вершин (узлов, образующих граф, или связей между вершинами), за исключением начальной и конечной вершин.
В информатике он используется во фразе «направленный ациклический граф» (DAG). Технически, DAG - это граф, образованный путем соединения разных вершин с ребрами, которые направлены таким образом, что не позволяют перемещаться по последовательности, в которой вершина может проходить через нее более двух раз; следовательно, нет закрытого пути.
Техопедия объясняет ациклический
Концепция DAG используется для разработки игр в слова, таких как Scrabble, и приложений для научных исследований на основе биологии и генетики. DAG также используется при построении моделей в математике, информатике, электронных схемах, операциях компиляции, вычислении связанных значений в формах и т. Д. DAG используются в моделях для иллюстрации потока информации через систему. DAG является лучшей альтернативой другим методам в структурах данных, обеспечивая оптимизацию использования памяти и повышение производительности.
Цикл - это путь, пройденный через последовательность вершин, так что и начальная, и конечная вершины находятся в одной точке. Если граф не имеет таких циклов, то он называется ациклическим. Например, рассмотрим три вершины, X, Y и Z, связанные в графе. При прохождении из любой из трех вершин через ее структуру различными возможными способами, если нельзя вернуться обратно к одной и той же начальной вершине, не посетив ни одну вершину (исключая начальную вершину или точку) дважды, тогда это ациклический граф.
Длина кратчайшего цикла и окружность ациклического графа определяются как бесконечность. Примерами ациклических графов являются деревья и леса. Ациклический и ненаправленный граф с любыми двумя вершинами, связанными только одним путем, называется деревом. Семейное древо является хорошим примером концепции направленного ациклического дерева. Лес - это неориентированный граф, подмножества которого являются деревьями.
