Просмотр исходного текста страницы 2004-gre-cs-practice-book.pdf/Q32

== Вопрос: Q32-4c9f66 ==

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

=== Ответы ===
* Правильный ответ: Нахождение кратчайшего цикла в ''G''
* Нахождение самого длинного простого цикла в ''G''
* Нахождение всех [https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE остовных деревьев] ''G''
* Нахождение крупнейшей клики в ''G''
* Нахождение раскраски вершин ''G'' (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов

=== Объяснение ===
{{cstest-source|2004-gre-cs-practice-book.pdf|26|32}}

* «Нахождение самого длинного простого цикла» — наверно можно к этому свести TSP. Неплохо бы расписать.
* «Нахождение всех [https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE остовных деревьев]» — не вижу элементарного сведения от какой-то NPC-задачи разрешения, но звучит очень переборно (не минимальные остовы, а ВСЕ — а их явно экспонента, чисто по построению, только перечислених их любым алгоритмом будет экспоненциальным).
* «Нахождение крупнейшей клики» — классическая NPC-задача, надо знать.
* «[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Нахождение раскраски вершин] ''G''» — это задача вроде в <m>NP \cup coNP</m>, но не в P.

{{question-ok|[[Участник:StasFomin|StasFomin]] 16:20, 14 декабря 2024 (UTC)}}

[[Категория:Алгоритмы на графах]]
[[Категория:Теория сложности]]