Упражнения

8.1. Выяснить, имеются ли в графах эйлеровы цепи, циклы. Если да, то выделить их, используя алгоритмы.

а) б) в)

8.2. Нарисовать восьмивершинный граф, который:

а) имеет эйлеров цикл;

б) имеет эйлерову цепь;

в) не имеет ни эйлерова цикла, ни эйлеровой цепи;

г) имеет гамильтонов цикл;

д) имеет гамильтонову цепь;

е) не имеет ни гамильтона цикла, ни гамильтоновой цепи;

ж) имеет гамильтонов цикл, но не имеет эйлерова цикла;

з) имеет эйлеров цикл, но не имеет гамильтонова цикла.

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

М

8.4. На рисунке изображена схема зоопарка (вершины графа – вход, выход, перекрестки, повороты, тупики; ребра – дорожки, вдоль которых расположены клетки). Найти маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути.

ВХОД

ВЫХОД

8.5. Сможет ли экскурсовод провести посетителей по выставке так, чтобы они побывали в каждом зале ровно один раз? Соответствующий граф приведен на рисунке. Вершины графа – это вход, выход, двери, соединяющие залы, перекрестки, а ребра – залы и коридоры.

8.6. На рисунке изображен план подземелья, в одной из комнат которого скрыты богатства рыцаря. После смерти рыцаря его наследники нашли завещание, в котором было сказано, что для отыскания сокровищ достаточно войти в одну из крайних комнат подземелья, пройти через все двери, причем в точности по одному разу через каждую; сокровища скрыты за той дверью, которая будут пройдена последней. В какой комнате были скрыты сокровища?