Задача 32993

Темы:    [ Обход графов ] [ Степень вершины ] [ Четность и нечетность ]

Сложность: 2+ Классы: 8

Условие

Гуляя по Кенигсбергу, Леонард Эйлер захотел обойти город, пройдя по каждому мосту ровно один раз (см. рис.). Как ему это сделать?

Решение

В соответствующем графе (см. рис.) четыре нечётные вершины. Поэтому обойти его невозможно (см. задачу 31095 а).

Ответ

Это невозможно.

Источники и прецеденты использования

Кружок
Название	ВМШ 57 школы
класс
Класс	8
год
Год	1997/98
Место проведения	57 школа
занятие
Номер	9
Название	Графы
Тема	Неизвестная тема
задача
Номер	03