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

Вот одна из них — старая задача о пере­возчике, волке, козе и капусте. Перевозчику нужно переправить через реку волка, козу и капусту. У него есть лодка, но она очень ма­ла и может вместить кроме перевозчика еще что-нибудь одно: или волка, или козу, или ка­пусту. Как же перевезти их через реку? Вол­ка нельзя оставить вместе с козой — задерет, а козу нельзя оставить с капустой — съест. Поэтому в первый рейс через реку должна от­правиться коза, а на первом берегу остаются волк и капуста. Возвращаться обратно вместе с козой перевозчику нет резона — это возвра­щение в начальное положение. Значит, козу следует оставить на втором берегу, где мирно дожидаются волк и капуста.

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

Решение этой головоломки можно пред­ставить в виде графа (рис. 1), каждая из вер­шин которого представляет набор действую­щих лиц, находящихся на первом берегу. Буква П означает перевозчика, В — волка, К — козу, а М — мешок с капустой.