2004-gre-cs-practice-book.pdf/Q32 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q32-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q32-4c9f66 == | == Вопрос: 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:// | + | * «Нахождение всех [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)}} | |
| − | + | [[Категория:Алгоритмы на графах]] | |
| + | [[Категория:Теория сложности]] | ||
Текущая версия на 16:20, 14 декабря 2024
Вопрос: Q32-4c9f66
Из следующих задач, касающихся данного неориентированного графа G, о котором в настоящее время известно, что он разрешим за полиномиальное время?
Ответы
- Правильный ответ: Нахождение кратчайшего цикла в G
- Нахождение самого длинного простого цикла в G
- Нахождение всех остовных деревьев G
- Нахождение крупнейшей клики в G
- Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов
Объяснение
Исходники — вопрос 32 на 26 странице книги «2004-gre-cs-practice-book.pdf»
- «Нахождение самого длинного простого цикла» — наверно можно к этому свести TSP. Неплохо бы расписать.
- «Нахождение всех остовных деревьев» — не вижу элементарного сведения от какой-то NPC-задачи разрешения, но звучит очень переборно (не минимальные остовы, а ВСЕ — а их явно экспонента, чисто по построению, только перечислених их любым алгоритмом будет экспоненциальным).
- «Нахождение крупнейшей клики» — классическая NPC-задача, надо знать.
- «Нахождение раскраски вершин G» — это задача вроде в , но не в P.