Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
===== Задача vcover-clique ===== | ===== Задача vcover-clique ===== | ||
| + | <big>Цыганова Светлана, 974 гр.</big> | ||
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач | Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач | ||
| Строка 5: | Строка 6: | ||
* и задачи о вершинном покрытии | * и задачи о вершинном покрытии | ||
| − | [[Category: | + | '''Решение''' |
| − | + | ||
| + | 1) Вершинное покрытие -> максимальный по числу вершин полный подграф. | ||
| + | |||
| + | Заметим, что если есть полный подграф, то все, кроме одной вершины лежат в вершинном покрытии. Воспользуемся этим фактом. | ||
| + | |||
| + | Из вершинного покрытия будем находить полный подграф следующим образом: | ||
| + | |||
| + | a) Найдем все полные подграфы, состоящие из вершин вершинного покрытия | ||
| + | |||
| + | [[Category:На проверку]] | ||
Версия 15:49, 1 декабря 2014
Задача vcover-clique
Цыганова Светлана, 974 гр.
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
- о поиске максимального по числу вершин полного подграфа (клики) в графе
- и задачи о вершинном покрытии
Решение
1) Вершинное покрытие -> максимальный по числу вершин полный подграф.
Заметим, что если есть полный подграф, то все, кроме одной вершины лежат в вершинном покрытии. Воспользуемся этим фактом.
Из вершинного покрытия будем находить полный подграф следующим образом:
a) Найдем все полные подграфы, состоящие из вершин вершинного покрытия