[Koshka669]

Помогите, пожалуйста решить задачу на любом из языков программирования!!!!!

Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и не больше K врагов. У одного из них есть книга, которую все хотели бы прочитать и потом обсудить с некоторыми из остальных.
Написать программу, которая разбивает людей на S групп, где будет обсуждаться книга, таким образом, чтобы вместе с каждым человеком в ту же самую группу вошло не более P его врагов.
Примечание: предполагается, что S*P>=K.

Всем, кто ответит и сможет помочь, заранее СПАСИБО)))

[lmikle]

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

А то задача сводится к элементарному перебору и граф тут нафиг не нужен. Он граф, только если расссматривать информацию о друзьях/врагах, а для нахождения групп достаточно простого перебора.

[Koshka669]

Точно в задании ничего не указывется.
По решению задачи есть только это:
Математическая постановка задачи 3.
Задача может быть сформулирована в графовой постановке следующим образом: найти простой цикл в графе (т.е. без повторяющихся вершин), проходящий через все вершины графа. В общем случае не существует эффективного алгоритма решения этой задачи. Однако в данном случае задачу можно решить эффективно.
Предположим, что уже построен некоторый простой путь (x[1],x[2],...x[k]) Множество вершин, вошедших в путь, будем считать пройденными, остальные не пройденные. Возможны 3 ситуации.
1. Одна из вершин x[1],x[k] смежна одной из не пройденных еще вершин. В этом случае путь можно очевидным образом удлинить на одну вершину.
2. Ни одна из вершин x[1],x[k] не смежна одной из не пройденных еще вершин, а вершины x[1] и x[k] смежны. В этом случае понятно, что k>N/2, так как вершины x[1] и x[k] смежны N/2 вершинам. Следовательно количество не пройденных вершин не больше N/2. Следовательно любая вершина у из них смежна одной из пройденных вершин, например x[i]. Но тогда можно получить более длинный путь (у,x[i],x[i+1],...,x[k],x[1],x[2],...x[i-1]).
3. В этом случае степеней вершин нетрудно показать, что в пути (x[1],x[2],...x[k]) существует такой индекс i, что x[1] смежна x[i], а x[i-1] смежна x[k]. Следовательно, рассмотрев путь (x[i],x[i+1],...,x[k],x[i-1],x[i-2],...x[1]) мы имеем ситуацию 2., поэтому можно получить более длинный путь.
Применяя описанный выше способ начиная с пути длины 1, построим простой цикл, включающий все вершины.

[voron_paa]

Вроде бы нужно решать алгоритмом китайского почтальона ...
Если мне память не изменяет ..