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

Материал из DISCOPAL
< 2004-gre-cs-practice-book.pdf
Версия от 16:20, 14 декабря 2024; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Вопрос: Q32-4c9f66

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

Ответы

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

Объяснение

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

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

[ Хронологический вид ]Комментарии

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

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