Издательство: | Книга по требованию |
Дата выхода: | май 2011 |
ISBN: | 978-3-8433-0142-8 |
Объём: | 88 страниц |
Масса: | 153 г |
Размеры(В x Ш x Т), см: | 23 x 16 x 1 |
В книге рассматривается проблема определения границы между полиномиальной разрешимостью и NP-полнотой для классических графовых задач в решетке замкнутых относительно удаления вершин классов обыкновенных графов (решетке наследственных классов). Изучение данной границы ведется на основе метода «критического» класса графов – поиска наследственных классов, играющих особую роль при решении упомянутой задачи демаркации. Исследуются два типа таких разделителей – граничные и минимальные сложные классы графов, один из которых (минимальные сложные классы) был введен в рассмотрение автором. В монографии представлены результаты автора по структуре граничных классов для ряда задач на графах. Например, показывается, что для обеих задач о 3-раскраске (вершинного и реберного вариантов) множество граничных классов континуально. В этой книге впервые предъявлены конкретные примеры минимальных сложных классов (ранее не было известно, существуют ли они вообще). С другой стороны, выделяется тип задач, для которых таких не существует. Данная книга предназначена для студентов, аспирантов и научных работников, занимающихся дискретной математикой.
Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.