2004-gre-cs-practice-book.pdf/Q32

Вопрос: Q32-4c9f66

Из следующих задач, касающихся данного неориентированного графа G, о котором в настоящее время известно, что он разрешим за полиномиальное время?

Правильный ответ: Нахождение кратчайшего цикла в G
Нахождение самого длинного простого цикла в G
Нахождение всех остовных деревьев G
Нахождение крупнейшей клики в G
Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов

Исходники — вопрос 32 на 26 странице книги «2004-gre-cs-practice-book.pdf»

«Нахождение самого длинного простого цикла» — наверно можно к этому свести TSP. Неплохо бы расписать.
«Нахождение всех остовных деревьев» — не вижу элементарного сведения от какой-то NPC-задачи разрешения, но звучит очень переборно (не минимальные остовы, а ВСЕ — а их явно экспонента, чисто по построению, только перечислених их любым алгоритмом будет экспоненциальным).
«Нахождение крупнейшей клики» — классическая NPC-задача, надо знать.
«Нахождение раскраски вершин G» — это задача вроде в , но не в P.

(нет элементов)

Войдите, чтобы комментировать.