Предположим, что есть двудольный граф. Тогда могу ли я сказать, что из двух двудольных разбиений V разбиение с максимальной мощностью является максимальным независимым множеством этого графа?
Поскольку все ребра в двудольном графе являются обрезанными ребрами (пересекающими ч/б два раздела), поэтому больше нет ребер для обработки, т. е. больше нет узлов для добавления к разделу максимальной мощности, если обе конечные точки ребра не находятся в то самое разбиение, которое нарушает свойство независимых множеств.
Если мы можем получить максимальное независимое множество таким образом, то для недвудольного графа я могу раскрасить граф в 2 цвета, а затем из двух разделов удалить все плохие ребра (и их 2 конечные точки) и вызвать оставшиеся max- мощность разбивает максимальное независимое множество графа?
