Гамильтонова линия
«ТОЛЬКО ЗАБАВЛЯЯСЬ И УЧАТСЯ», — считал Анатоль Франс. Известный ирландский ученый сэр Уильям Роуэн Гамильтон в 1859 году занялся математическим бизнесом: выпустил в продажу головоломку, состоящую из деревянного додекаэдра, в каждую из двадцати вершин которого вбит гвоздь с большой шляпкой, чтобы не соскакивала обернутая вокруг него веревка. Под каждым гвоздем стояло название крупного города — Дели, Филадельфия, Брюссель... Надо было продолжить веревочный маршрут, проходящий через все центры цивилизации точно по одному разу.
Очевидно, новый товар не вызвал ажиотажа на рынке, а изготовлять правильный двенадцатигранник не так просто, и потому Гамильтон предложил другой вариант игры — технологически намного упрощенный. Роль додекаэдра, пространственного тела, играло его плоское изображение — так называемый граф, то есть фигура, составленная из вершин, соединенных ребрами. (Все многоугольники, все мозаики, что мы рассматривали и еще только будем рассматривать, — это, несмотря на свой простецкий вид, типичные графы.)
Граф, заменяющий собой многогранник, повторяет его архитектуру — столько же вершин, столько же ребер и граней, тот же способ соединения их друг с другом. (Потому формула Эйлера, справедливая для многогранников, верна также и для графов.) Вот один из способов получить такой граф: надо спроецировать весь многогранник на плоскость одной из его граней, а центр проекции выбрать недалеко от ее середины. Тогда для пяти Платоновых тел получаются графы (первая страница книги). Они называются «диаграммой Шлегеля». Таким нам увиделся бы гигантский многогранник, если бы мы удалили одну его грань, забрались в образовавшуюся дыру и стали рассматривать его изнутри. Диаграммы эти очень удобны — они позволяют на листе бумаги производить манипуляции с объемным телом, чем и воспользовался Гамильтон, чтобы упростить свою нерентабельную головоломку.
Математика сохранила память о его поучительной игрушке — до сих пор линия, проходящая по одному разу через все вершины графа, называется гамильтоновой. Но и сейчас никто не может сказать, существует ли для того или иного графа гамильтонова линия или нет. А это весьма обидно, ибо жизнь часто требует ответа на подобный вопрос. Например, знаменитая «задача о странствующем торговце» состоит в том, что он должен посетить несколько городов и как можно скорее вернуться домой. В общем виде эта транспортная проблема не решена.
Можно, конечно, перебрать все варианты и выбрать наилучший порядок обхода городов, но если их много, за дело без мощных вычислительных машин лучше не браться. Впрочем, кое-какие задачи подобного типа все-таки решены — например, найдена кратчайшая авиалиния, проходящая по всем главным городам Америки.