Аннотация:
В работе рассматриваются нагруженные ориентированные ациклические графы, ребрам которых приписаны веса — целые неотрицательные числа. Исследуется сложность линейной укладки вершин таких графов в порядке топологической сортировки. Получена точная оценка функции Шеннона сложности линейной укладки нагруженных ориентированных ациклических графов.