Всем привет!

Знает ли кто небудь как можно решить такую задачу:

Есть граф 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-полной.

Любые идеи или комментарии приветствуются.

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

Почему-то кажется, что задача NP-полная, но никаких доводов у меня пока нет. Надо думать... 

А, блин, вот если бы не было никакой предварительной раскраски графа (т.е. если бы V0 = V), то это же в точности задача минимального разреза, которая решается алгоритмом нахождения максимального потока (или специальным алгоритмом, например, Stoer-Wagner) полиномиально.

Осталось понять, не ухудшает ли ничего предварительная раскраска...

Ага, мне уже тоже подсказали на другом форуме что эта задача сводится к задаче минимального разреза.

Можно попробовать ввести две фиктивные вершины для каждого цвета, и соединить каждую из предварительно раскрашенных вершин с фиктивной ребром веса "бесконечность" (чтобы вершины одного цвета уж точно попали в одну группу), а две фиктивные вершины соединить ребром веса "минус бесконечность" (чтобы вершины одного цвета случайно не попали в одну группу). Но тогда возникает проблема, что возникают рёбра отрицательного веса, поэтому многие алгоритмы неприменимы. Поэтому проблема с пред-раскраской остаётся...


По всем форумам рассылку что ли сделал? 

Это сообщение отредактировал(а) maxdiver - 10.5.2009, 20:44

Неа, в двух спросил. В этом и еще в другом 

Я думаю что завтра напишу полное решение и напишу сюда, вдруг кому пригодится.