Здравствуйте, SergASh, Вы писали:
SAS>Из всех таких разбиений нужно выбрать то, при котом во множество A попадает наименьшее количество вершин.
Соответственно, нужно чтобы во множество B попало наибольшее количество вершин.
SAS>Есть ненаправленный граф. Требуется разбить множество его вершин на две части A и B так, чтобы вершины из B соединялись только с вершинами из A, но не между собой.
SAS>Какие будут соображения?
Можно рассмотреть дополнение графа. Т.е. если между двумя вершинами есть дуга — убрать, если нет — добавить. Потом в этом графе
искать клику.
Когда мы опять вернёмся к исходному графу, вершины в клике не будут соединены между собой. Только надо проверить, что эти преобразования корректны, и мы ничего не потеряем.
Здравствуйте, 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
... << RSDN@Home (RF) 1.2.0 alpha 5 rev. 17>>
