Метод «критического» класса графов

В книге рассматривается проблема определения границы между полиномиальной разрешимостью и NP-полнотой для классических графовых задач в решетке замкнутых относительно удаления вершин классов обыкновенных графов (решетке наследственных классов). Изучение данной границы ведется на основе метода «критического» класса графов – поиска наследственных классов, играющих особую роль при решении упомянутой задачи демаркации. Исследуются два типа таких разделителей – граничные и минимальные сложные классы графов, один из которых (минимальные сложные классы) был введен в рассмотрение автором. В монографии представлены результаты автора по структуре граничных классов для ряда задач на графах. Например, показывается, что для обеих задач о 3-раскраске (вершинного и реберного вариантов) множество граничных классов континуально. В этой книге впервые предъявлены конкретные примеры минимальных сложных классов (ранее не было известно, существуют ли они вообще). С другой стороны, выделяется тип задач, для которых таких не существует. Данная книга предназначена для студентов, аспирантов и научных работников, занимающихся дискретной математикой.