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