Задача о покрытии множества. Дано конечное множество U и семейство S его подмножеств. Спрашивается, можно ли выбрать несколько подмножеств из S, так, чтобы U было подмножеством этой выборки, а если можно, то какое минимальное число подмножеств следует выбрать.
Эта задача, насколько я знаю, NP. Как мне кажется, может быть интересной следующая переформулировка задачи:
Интерпретация. Зададим гиперграф на множестве вершин U, ребрами которого будут являться подмножества из S. Каждому подмножеству из S поставим в соответствие по цвету (цвета все разные). Возьмем ребро гиперграфа, теперь построим полный граф на вершинах из этого ребра, причем каждое ребро окрасим в цвет, который был поставлен в соответствие этому ребру гиперграфа. Так проделаем со всеми ребрами. Теперь уберем ребра гиперграфа и получим большой разноцветный граф. Понятно, что чтобы решить задачу, достаточно найти такой остов этого графа, что количество цветов в нём минимально.
Хочется верить, что дальнейшие рассуждения могут привести к какому-нибудь интересному результату. Будут мысли - пишите.
Эта задача, насколько я знаю, NP. Как мне кажется, может быть интересной следующая переформулировка задачи:
Интерпретация. Зададим гиперграф на множестве вершин U, ребрами которого будут являться подмножества из S. Каждому подмножеству из S поставим в соответствие по цвету (цвета все разные). Возьмем ребро гиперграфа, теперь построим полный граф на вершинах из этого ребра, причем каждое ребро окрасим в цвет, который был поставлен в соответствие этому ребру гиперграфа. Так проделаем со всеми ребрами. Теперь уберем ребра гиперграфа и получим большой разноцветный граф. Понятно, что чтобы решить задачу, достаточно найти такой остов этого графа, что количество цветов в нём минимально.
Хочется верить, что дальнейшие рассуждения могут привести к какому-нибудь интересному результату. Будут мысли - пишите.
Комментариев нет:
Отправить комментарий