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

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

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

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

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

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

Привет всем!

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

Какие будут соображения?

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

SAS>Привет всем!

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

SAS>Какие будут соображения?

Прошлым летом я делал что-то аналогичное для орграфа:
https://sites.google.com/site/alex0shkotin/grafy/wikipedia-category-graph
может пригодится

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

SAS>Привет всем!

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

SAS>Какие будут соображения?

Это задача о максимальном независимом множестве. Собственно, вершины из B — это и есть независимое множество вершин. Задача NP-полна (если граф не является деревом).

Можно попробовать жадный алгоритм (если не требуется оптимальность):
1. выбрать в графе вершину максимальной степени, пометить ее как А
2. удалить выбранную вершину из графа, а также удалить все инцидентные ребра
2. повторять п.1 и 2 пока не останутся только вершины со степенью ноль (ни с кем не связанные)
3. все оставшиеся вершины = множество B