Фамилия Имя Задание 3. Перечеркни в графе вершины, которые нужно удалить, чтобы в графе был возможен эйлеров путь. Класс Дата Это интересно! В последние годы своей жизни Леонард Эйлер ослеп, но продолжил заниматься наукой. Свои труды он диктовал сорому портному Ушо слепой учёный надиктовал более 400 статей и 10 книг. Задание 4. Реши задачу, используя теорему Эйлера. Сможет ли Петя посетить всех своих друзей и вернуться домой, пройдя по каждой дорожке между домами друзей только один раз. Схема расположения домов друзей Пети и дорожек между ними Решение: Петя Ответ: 2 ИНФОУРОК

Ответ: Задание 3: Нужно удалить две вершины графа (любые) степени 3. Задание 4: Да, сможет.

Задание 3

• В графе должны остаться только вершины четной степени (Эйлеров цикл) или две вершины нечетной степени (Эйлеров путь).
• В данном графе есть вершины степени 3.
• Для получения Эйлерова пути нужно удалить две вершины степени 3.

Задание 4

• Эйлеров цикл возможен, если все вершины графа имеют четную степень.
• В данном графе все вершины имеют четную степень (2 или 4).
• Значит, Петя сможет посетить всех своих друзей и вернуться домой, пройдя по каждой дорожке между домами друзей только один раз.

Ответ: Задание 3: Нужно удалить две вершины графа (любые) степени 3. Задание 4: Да, сможет.