Книга: Золотой билет

На первый-второй рассчитайсь!

На первый-второй рассчитайсь!

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

Рис. 3.15. Младшеклассники

Наилучшим решением будет поместить Алекса и Кэти в одну группу, а Барбару, Дэвида и Эрика – в другую: так мы разорвем всего две дружеские связи, Алекс-Эрик и Кэти-Эрик. Очевидно, что разбиения, которое разлучило бы лишь одну пару друзей, просто не существует.

Рис. 3.16. Группы младшеклассников

Директор школы обратился за помощью в институт, подчеркнув, что учителя хотят разлучить минимально возможное число друзей. Оказалось, что для решения задачи существует довольно много эффективных алгоритмов, поскольку она эквивалентна задаче о нахождении минимального разреза в графе. Институтские исследователи сумели разбить 500 учеников на две группы, «разрезав» при этом всего 17 дружеских связей.

Все были довольны и счастливы… до тех пор, пока учителя не осознали, что помещать в одну группу врагов – это еще хуже, чем разлучать друзей. И директору снова пришлось идти в институт. Теперь он просил составить группы таким образом, чтобы разделить как можно большее число врагов. Первая задача не вызвала абсолютно никаких затруднений, и директору казалось, что со второй задачей в институте справятся с такой же легкостью… однако он ошибался.

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

В конце концов выход все же нашелся. Применив алгоритм, разработанный в 1995 году Мишелем Гемансом и Дэвидом Уильямсоном, исследователи сумели построить такое разбиение, при котором в разные группы попадала 1321 пара врагов. Максимальный разрез построить не удалось, однако до него оставалось совсем немного: исследователи знали, что не существует такого разбиения, при котором «разрезалось» бы более 1505 вражеских связей. Директор остался несколько разочарован тем, что оптимальное решение так и не нашли, но ему пришлось смириться. Теперь все снова были довольны и счастливы. Надолго ли?..

Оглавление книги