Граф для двудольного графа путем удаления ребер (не более чем ребер /2) - алгоритм?

Question

Скажем, у нас есть график, и вам разрешено удалять ребра (не более (ребра исходного графа)/2) до тех пор, пока это не будет двудольный граф.

Допустим, нам дали:

E={ (4, 1),( 1 ,2), (2 ,3),( 7, 2),( 1 ,5),( 8 ,4), (5 ,8),( 8, 9)}

и множество вершин:

V= { 1,2,3,4,5,6,7,8}

Как решить эту проблему? Есть ли какой-нибудь алгоритм, который это делает? Любое объяснение будет оценено.

Answer 1

Выберите произвольный узел в качестве первого члена набора A. Если с ним связан какой-либо узел, выберите один в качестве первого члена набора B. Если нет, выберите любой другой узел в качестве первого члена набора B.

Теперь у вас есть два набора узлов, A и B. Повторно выбирайте узел, не входящий ни в один из этих наборов. Подсчитайте количество ребер, связывающих этот узел с узлами в A и B. Если имеется больше ребер, связывающих его с набором A, удалите ребра, связывающие его с узлами в наборе B, и поместите его в набор B. В противном случае сотрите ребра, связывающие его с узлы в наборе A и поместите его в множество A. Обратите внимание, что вы стираете не более половины ребер, связанных с этим узлом.