#graph-theory #partitioning #connected-components #np-hard
Вопрос:
Существует неориентированный граф с несовместимыми узлами(показан красным цветом на рисунке), узлы, соединенные красными ребрами, несовместимы, то есть, если вы включите один из них в кластер, который вы пытаетесь создать, вы не сможете использовать другой.
Я хочу найти один кластер, который максимизирует его размер и включает только совместимые узлы.
Это похоже на проблему с максимальными счастливыми вершинами (MHV) или Максимальными счастливыми ребрами (MHE), но разные точки моей проблемы заключаются в том, что несчастливые узлы не должны существовать в кластере, и нужно найти только один самый большой кластер.
Существуют ли какие — либо термины, которые относятся к этой проблеме? Есть ли какой-нибудь хороший способ решить эту проблему, кроме проверки всех возможных случаев?