Золотой билет

«Пути, деревья и цветы» дали нам не только эффективный способ решения задачи о паросочетаниях для случая произвольной схемы. В группе из 100 человек алгоритм Эдмондса находит максимальное паросочетание примерно за 100⁴, т. е. 100000000 (сто миллионов) шагов, что для современного компьютера сущий пустяк. Методичный перебор всех возможных сочетаний вылился бы примерно в два квинвигинтиллиона шагов, а один квинвигинтиллион – это, между прочим, единица и 78 нулей! В работе Эдмондса есть довольно длинное отступление на тему эффективных алгоритмов. Понимая, что для такого, в сущности, интуитивного понятия, как эффективность, подобрать полноценное формальное определение очень сложно, Эдмондс все-таки предлагает некий критерий. Он называет алгоритм эффективным, если тот находит решение за «алгебраическое» время, т. е. время, «алгебраически» зависящее от размера входных данных. Для 100 человек это может быть, к примеру, 100⁴, 100² или 100¹². В дальнейшем класс задач, для которых существуют такие алгоритмы, получил обозначение «P» – от слова «полиномиальный», заменившего эдмондсовское понятие «алгебраический». Таким образом, класс P представляет собой все многообразие задач, которые можно решить относительно быстро. Ну что ж – в споре «P против NP» мы выслушали мнение первой стороны.

Рис. 3.5. Нетрадиционные потенциальные пары

В поисках клики

В рамках проводимого исследования институтскому профессору социологии понадобилось найти 50 жителей Королевства, которые дружили бы между собой. Своими силами справиться с задачей не удалось, и профессор обратилась на факультет компьютерных наук, где один из специалистов рассказал ей о базе дружеских связей и уверенно заявил, что клика из 50 друзей найдется без труда.

На деле выяснилось, что труд здесь требуется совершенно непосильный. Количество различных групп размера 50 оказалось непомерно огромным и выражалось числом из 151 цифры; не было и речи о том, чтобы проверить хотя бы сотую долю вариантов. Круг поиска пытались сузить всеми возможными способами – в частности, отсекли тех жителей, у которых было меньше 49 друзей, поскольку они-то уж точно не могли входить в искомую клику. Однако, несмотря на свою высокую квалификацию, исследователи не набрали и 25 друзей и при этом не смогли представить убедительное доказательство того, что клики размера 50 в Королевстве не существует.

Работа встала. Исследователи опустили руки. Внезапно одного из аспирантов осенило: «Слушайте, у нас же есть „Альфа“!» «Альфой» называлось известное, но при этом полусекретное сообщество, все члены которого, по слухам, дружили между собой. Пятьдесят «альфовцев» удалось найти довольно быстро: ведь, в конце концов, секретным сообщество было лишь наполовину. Оставалось только перебрать 1225 пар, чтобы проверить дружеские связи. К изумлению исследователей (но не самих «альфовцев», разумеется), все пятьдесят действительно оказались друзьями. Клика нашлась.

Передай скипетр

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

Дети в Королевстве любят играть в игру под названием «Передай скипетр», в которой участники по очереди передают друг другу небольшую палку. Передачей считается тот момент, когда палку держат двое – передающий и принимающий.

Правила игры:

1. Палку можно передавать только друзьям.

2. Между любыми двумя друзьями палка должна переместиться ровно один раз.

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

Рис. 3.6. Дети

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

Рис. 3.7. Дети: число друзей у всех четно

Когда у всех участников число друзей четно, в случае успешного исхода палка возвращается к тому, с кого начали.

В данной ситуации решение может быть таким: начинают с Алекса, он передает палку Эрику, Эрик – Дэвиду, Дэвид – Барбаре, Барбара – снова Эрику, Эрик – Кэти, а Кэти – Алексу.

Прообразом игры «Передай скипетр» послужила одна очень известная головоломка XVIII века. В прусском городе Кёнигсберге (а ныне российском Калининграде) через реку Прегель и ее рукава было перекинуто семь мостов (см. карту на рис. 3.8).

Рис. 3.8. Старинная карта мостов Кёнигсберга