Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и не больше K врагов.

[koshka669]

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

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

Всем, кто ответит или сможет помочь, СПАСИБО!!!!

[terminadoor]

Напиши поконкретнее.А то суть постановки задачи мне неясна. Какие данные надо ввести, а какие - вывести.

[koshka669]

Надо написать программу, решающую эту задачу на любом языке программирования, у меня есть по задаче только это:
Задача может быть сформулирована в графовой постановке следующим образом: найти простой цикл в графе (т.е. без повторяющихся вершин), проходящий через все вершины графа. В общем случае не существует эффективного алгоритма решения этой задачи. Однако в данном случае задачу можно решить эффективно.
Предположим, что уже построен некоторый простой путь (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, построим простой цикл, включающий все вершины.

[Ksardas13]

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