Максимальная заданная обложка графика
У меня есть универсальный набор и количество наборов S. Мне нужно найти максимальное количество наборов из S, чтобы между любыми двумя выбранными наборами не было общего элемента.
Мой подход --- Я рассмотрел каждый набор в S как узел, и если между двумя наборами есть какой-либо общий элемент, то между этими двумя наборами будет ребро. Этот подход работает хорошо, если построенный граф является двудольным. Трудность решить, если построенный граф не является двудольным.
PS-выбранные наборы не обязательно должны охватывать все элементы из универсального набора. он должен возвращать максимальное количество наборов, которые не являются смежными.
Спасибо