Обходы графов

Одной из особенностей теории графов, которая способствовала ее популяризации, является ее использование в решении головоломок и игр. Часто головоломку можно сформулировать как графовую задачу: определить, существует ли в графе «эйлерова цепь» или «гамильтонов цикл». Как уже упоминалось, понятие эйлерова графа появилось, когда Эйлер решал задачу о кёнигсбергских мостах. В настоящей главе даны две характеризации эйлеровых графов. Затем рассматриваются гамильтоновы графы, для которых приведены некоторые необходимые и некоторые достаточные условия их существования. Однако остается еще нерешенной задача нахождения простого и эффективного описания гамильтоновых графов, которое бы отличалось от завуалированной перефразировки определения.