Графовая задачка

Vlad128

Вот задача: в неориентированном графе помечено некоторое подмножество вершин. Необходимо найти минимальный по количеству вершин связный подграф, содержащий все помеченные вершины. Не NP ли полная? Жадный алгоритм: берем одну помеченную, добавляем все вершины, лежащие на кратчайшем пути в смысле количества непомеченных вершин до другой помеченной в подграф. повторяем, пока не получим связный граф (аналогия с алгоритмом Прима не работает.

antcatt77

а чем это отличается от задачи коммивояжера?

kiritsev

Не NP ли полная?
вполне возможно.
я бы попробовал свести задачу о клике к ней инвертировав граф и возможно превратив рёбра в вершины.

Vlad128

Можешь свести? Пиши — интересно.

nely25

а чем это отличается от задачи коммивояжера?
Примерно тем же, чем дерево Штейнера отличается от задачи комивояжера

nely25

О, в Garey&Johnson написано, что дерево Штейнера NP-полно, даже если все веса одинаковы. А оно сильно смахивает на задачу опа.

Vlad128

задачу о клике
кстати, вот можно рассмотреть модификацию исходной задачи, где известно, что граф планарный, тоже будет интересно. Но клик там хороших уже точно не будет.

antcatt77

мне казалось, что путь и связный граф - это одно и тоже, но сейчас уже не уверен (вернее, уверен только - что путь есть связный граф, а вот обратное...)

nely25

вот можно рассмотреть модификацию исходной задачи
Ты уж определяйся с задачей сперва. Планарное дерево Ш. тоже NP-полно, если что, правда хз что с весами, статью лень люркать.

Vlad128

ну начать точно стоит с исходной :)

nely25

про исходную я тебе сказал.
В ответ можешь либо согласиться с моим постом выше, либо спорить с тем, что дерево с наименьшим числом вершин и дерево с наименьшим числом рёбер - одно и то же.

Vlad128

либо спорить с тем, что дерево с наименьшим числом вершин и дерево с наименьшим числом рёбер - одно и то же.
Либо согласиться с "похожа", либо спорить с истиной?
я вот на википедии прочитал, что задача штейнера ставится для метрических пространств (ну там неравенства треугольника всякие). Это как-то легко обходится?

nely25

Если ты ещё не убедился в NP-полноте, то, да, легко обходится: ты веришь (википедия, лол что метричесая steiner tree NP-полная. Тогда произвольная steiner tree тоже NP-полная, так как через неё можно решать метрическую
Если же вопрос был про использованию в общем случае приближённого алгоритма для решения metric steiner tree (через нахождения minimum spanning tree на редуцированном подграфе то ответ хз, не помню о таком.

Vlad128

А, ок, нашел другую постанову steiner tree, частным случаем которой является моя задача. Поищу доказательство NP-полноты. Спасибо.
Хотя надо искать доказательство именно того варианта с ребрами 1 либо бесконечность. Кинь ссылку на то, где ты это прочитал, плз.

Vlad128

а хотя я все понял. Спасибо :D

nely25

Кинь ссылку на то, где ты это прочитал, плз.
Garey, Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness, Appendix 2, problem ND12. Страница 208 в варианте, гуляющем в сети.
Там про это только сказано как факт, но возможно референсы помогут.

Vlad128

ладно, не настолько важно, чтобы по референсам ходить. Поверим типам, книга красиво выглядит :D
Оставить комментарий
Имя или ник:
Комментарий: