Характеризация и распознавание орграфов из минимальных по включению наследственных классов с наименьшим положительным значением энтропии

Рассматривается задача характеризации в терминах запрещенных порожденных подграфов каждого из минимальных по включению наследственных классов орграфов, имеющих наименьшую положительную энтропию, и прослеживается взаимосвязь этой задачи с алгоритмическими и сложностными вопросами распознавания орграфов из указанных классов. Все исследуемые классы, за исключением двух, полностью охарактеризованы запрещенными порожденными подграфами. Для одного из оставшихся классов такая характеризация найдена частично и доказано, что задача распознавания орграфов из этого класса полиномиально разрешима. С другой стороны, установлено, что задача распознавания орграфов из другого класса является NP-полной.