32. Кругосветное путешествие

В 1859 г. королевский астроном Ирландии сэр ВиЛЛьям Роуэн Гамильтон, известный своими глубокимИ Исследованиями по математической физике, теоретической механике и открытием исчисления кватернионов, придумал игру

«Кругосветное путешествие» и продал свою идею за 25 гиней фабриканту игрушек. Утверждают, что эта сумма была единствеННым заработком, полученным Гамильтоном за свои математические открытия. В ЭТой игре требовалось найти путь, проходящий через все вершиНЫ графа, ИЗображеННого на рис. 10, так, чтобы побывать в каждой ВеРшине лишь одиН раз и вернуться назад (в вершинах былИ написаны названия городоВ). НА рис. 10 ПоказаН ОдиН ИЗ Гамильтоновых путей. Такие пути существуют далеко НЕ для всех графов. Однако в отличие от задачи Эйлера до сих пор неизвестНЫ необходимые и достаточные условия для существования Гамильтонова пути на графе. Необходимым является отсутствие в графе точек, удаление которых привело бы к его распадению на две части — если бы в нем были такие точки, то мы должны были бы при обходе Побывать в НИх по крайНЕй мере дважды. Доказано, что если граф без разбивающих точек НЕ имеет гамильтонова пути, то оН содержит часть, состоящую из ДВух точек и трех соединяющиХ их линий.

< Предыдущая		Следующая >