Почему-то кажется, что задача NP-полная, но никаких доводов у меня пока нет. Надо думать...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Максимизировать сумму произведения вершин и ребер |
| Автор: nettby 10.5.2009, 08:23 |
| Всем привет! Знает ли кто небудь как можно решить такую задачу: Есть граф G=(V, E). Каждой вершине v из V присвоена метка l_v из множества A={1, 0, -1}. У каждого ребра e из E есть вес w_e. Выберем все вершины с меткой равной 0 и обозначим это множество V0. Надо так перемаркировать вершины из V0 (присвоить или 1 или -1), чтобы следующая сумма была максимальной: с(G) = СУММА(w_e * l_v * l_u), где e=(u, v) in E Надо найти алгоритм который решит данную задачу за полиномиальное время или доказать что задача (есть параметр k и граф G, можно ли выполнить перемаркировку вершин V0 из G, так что с(G)>=k) является NP-полной. Любые идеи или комментарии приветствуются. |
| Автор: maxdiver 10.5.2009, 13:21 |
| Иными словами, нужно раскрасить вершины графа в два цвета (при том, что он уже частично раскрашен) так, чтобы максимизировать сумму весов рёбер, оба конца которых одного цвета. Почему-то кажется, что задача NP-полная, но никаких доводов у меня пока нет. Надо думать... |
| Автор: maxdiver 10.5.2009, 18:00 |
| А, блин, вот если бы не было никакой предварительной раскраски графа (т.е. если бы V0 = V), то это же в точности задача минимального разреза, которая решается алгоритмом нахождения максимального потока (или специальным алгоритмом, например, Stoer-Wagner) полиномиально. Осталось понять, не ухудшает ли ничего предварительная раскраска... |
| Автор: nettby 10.5.2009, 18:30 | ||
Ага, мне уже тоже подсказали на другом форуме что эта задача сводится к задаче минимального разреза. |
| Автор: maxdiver 10.5.2009, 20:42 | ||||
Можно попробовать ввести две фиктивные вершины для каждого цвета, и соединить каждую из предварительно раскрашенных вершин с фиктивной ребром веса "бесконечность" (чтобы вершины одного цвета уж точно попали в одну группу), а две фиктивные вершины соединить ребром веса "минус бесконечность" (чтобы вершины одного цвета случайно не попали в одну группу). Но тогда возникает проблема, что возникают рёбра отрицательного веса, поэтому многие алгоритмы неприменимы. Поэтому проблема с пред-раскраской остаётся...
По всем форумам рассылку что ли сделал? |
| Автор: nettby 11.5.2009, 01:28 | ||
Неа, в двух спросил. В этом и еще в другом Я думаю что завтра напишу полное решение и напишу сюда, вдруг кому пригодится. |