Том 12, серия 1, номер 2, 2005 г., Стр. 12-55
УДК 519.17
С. В. Сорочан
Характеризация и распознавание орграфов из минимальных по включению наследственных классов с наименьшим положительным значением энтропии
Аннотация:
Рассматривается задача характеризации в терминах запрещенных порожденных подграфов каждого из минимальных по включению наследственных классов орграфов, имеющих наименьшую положительную энтропию, и прослеживается взаимосвязь этой задачи с алгоритмическими и сложностными вопросами распознавания орграфов из указанных классов. Все исследуемые классы, за исключением двух, полностью охарактеризованы запрещенными порожденными подграфами. Для одного из оставшихся классов такая характеризация найдена частично и доказано, что задача распознавания орграфов из этого класса полиномиально разрешима. С другой стороны, установлено, что задача распознавания орграфов из другого класса является NP-полной.
Сорочан С. В. 1
1. Нижегородский государственный университет, фак. вычисл. математики и кибернетики,
пр. Гагарина, 23, корпус 2, 603950 Нижний Новгород, Россия
Статья поступила 29 июня 2004 г.
Исправленный вариант — 8 января 2005 г.
