Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ 1 сообщение ] |
|
Автор | Сообщение | |
---|---|---|
akipol |
|
|
Вторая задача: существует ли в заданном неориентированном графе (без весов) разрез, размер которого не менее заданного числа? Докажите, что первая задача полиномиально сводима ко второй. Для доказательства NP-полноты можно использовать NP-полноту следующих задач: 1) выполнимость булевой формулы (SAT); 2) выполнимость 3-КНФ; 3) существование клики заданного размера в графе; 4) существование вершинного покрытия заданного размера в графе; 5) наличие гамильтонова пути в ориентированном графе. |
||
Вернуться к началу | ||
[ 1 сообщение ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задача на полиномиальные события
в форуме Теория вероятностей |
7 |
536 |
18 ноя 2020, 15:18 |
|
Полиномиальные уравнения степени 3
в форуме Алгебра |
2 |
349 |
14 май 2015, 07:04 |
|
Решить с помощью сведения к дифф. уравнению
в форуме Интегральное исчисление |
1 |
335 |
10 фев 2016, 20:00 |
|
Полные системы | 2 |
177 |
13 сен 2021, 21:08 |
|
Про частные и полные производные
в форуме Дифференциальное исчисление |
1 |
418 |
01 июн 2017, 19:45 |
|
Найти полные дифференциалы функций
в форуме Дифференциальное исчисление |
9 |
600 |
14 фев 2018, 10:12 |
|
Найти полные дифференциалы функций
в форуме Дифференциальное исчисление |
1 |
298 |
22 фев 2018, 14:10 |
|
Тем, кто сразу дает полные решения
в форуме Размышления по поводу и без |
100 |
2413 |
06 апр 2019, 19:45 |
|
Найти все полные свертки тензора
в форуме Линейная и Абстрактная алгебра |
2 |
194 |
03 июн 2023, 16:19 |
|
Полные решетки. Теорема о неподвижной точке | 2 |
171 |
21 ноя 2022, 14:17 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |