Здравствуйте, SergASh, Вы писали:

SAS>Из всех таких разбиений нужно выбрать то, при котом во множество A попадает наименьшее количество вершин.

Соответственно, нужно чтобы во множество B попало наибольшее количество вершин.

SAS>Есть ненаправленный граф. Требуется разбить множество его вершин на две части A и B так, чтобы вершины из B соединялись только с вершинами из A, но не между собой.
SAS>Какие будут соображения?

Можно рассмотреть дополнение графа. Т.е. если между двумя вершинами есть дуга — убрать, если нет — добавить. Потом в этом графе искать клику.

Когда мы опять вернёмся к исходному графу, вершины в клике не будут соединены между собой. Только надо проверить, что эти преобразования корректны, и мы ничего не потеряем.