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