Математический форум 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 , но ваш вариант тоже хорош . :good:

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/