| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| VERTEX_COVER http://mathhelpplanet.com/viewtopic.php?f=62&t=45844 |
Страница 1 из 1 |
| Автор: | fura89 [ 16 дек 2015, 20:07 ] |
| Заголовок сообщения: | VERTEX_COVER |
Нужно доказать что задача VERTEX Cover является NP полной сведя её к задаче о КЛИКЕ |
|
| Автор: | 3D Homer [ 16 дек 2015, 23:29 ] |
| Заголовок сообщения: | Re: VERTEX_COVER |
fura89 писал(а): Нужно доказать что задача VERTEX Cover является NP полной сведя её к задаче о КЛИКЕ Так NP-полноту задачи Vertex Cover вы не докажете.
|
|
| Автор: | fura89 [ 18 дек 2015, 21:47 ] |
| Заголовок сообщения: | Re: VERTEX_COVER |
А к какой по вашему лучше свести VERTEX cover ? |
|
| Автор: | 3D Homer [ 18 дек 2015, 22:45 ] |
| Заголовок сообщения: | Re: VERTEX_COVER |
Сводить задачу, NP-полноту которой вы собираетесь доказать, не имеет смысл. Сведя вашу задачу к другой NP-полной задаче вы докажете, что ваша задача более простая. Таким образом, сложность вашей задачи лежит в интервале от тривиальной (например, разрешить пустое множество) до NP-полноты. Сводить нужно заведомо NP-полную задачу к вашей. Тем самым вы покажете, что ваша задача не менее сложная. Дополнительно нужно доказать, что она и не более сложная, то есть лежит в NP. Чтобы свести Clique к Vertex Cover, рассмотрите граф, имеющий ребра в точности там, где исходный граф не имеет ребра. Также возьмите дополнение к клике (по отношению к множеству вершин). Должно получиться вершинное покрытие в новом графе. Чтобы свести Independent Set к Vertex Cover, достаточно рассмотреть только дополнение к множеству вершин, являющемся независимым множеством. |
|
| Автор: | fura89 [ 19 дек 2015, 17:01 ] |
| Заголовок сообщения: | Re: VERTEX_COVER |
Cпасибо , разобрался . Решил сведением к задаче IND_SET , но ваш вариант тоже хорош .
|
|
| Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|