Домашнее задание: 1. Какими цифрами обозначены Эйлеровы графы? ① 2. Пять участков отделены друг от друга заборами (см. план). Можно ли побывать на каждом участке, но при этом перелезть через каждый забор ровно один раз? Почему? 3. В Изумрудном городе шесть площадей. Каждая площадь соединена улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. а) Начертите возможный план Изумрудного города. 6) Можно ли устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды?

Решение:

1. Задание 1:

   Эйлеров граф - это граф, в котором существует Эйлеров цикл (путь, проходящий через каждое ребро графа ровно один раз) или Эйлеров путь (путь, проходящий через каждое ребро графа ровно один раз, но не обязательно начинающийся и заканчивающийся в одной и той же вершине).

   Граф является Эйлеровым, если он связный и все его вершины имеют четную степень (для Эйлерова цикла) или ровно две вершины имеют нечетную степень (для Эйлерова пути).

   Среди представленных графов Эйлеровым является граф под цифрой ①, так как он имеет две вершины с нечетной степенью.

2. Задание 2:

   Если бы существовала возможность побывать на каждом участке, перелезая через забор ровно один раз, то это означало бы, что существует Эйлеров путь или цикл в графе, где участки - это вершины, а заборы - ребра.

   Для существования Эйлерова пути необходимо, чтобы не более двух вершин имели нечетную степень (нечетное количество заборов). Для существования Эйлерова цикла все вершины должны иметь четную степень.

   Если на плане есть участки с нечетным количеством заборов, то нельзя перелезть через каждый забор ровно один раз, посетив все участки.

3. Задание 3:

   а) Возможный план Изумрудного города:

   

   б) В Изумрудном городе шесть площадей, каждая из которых соединена с тремя другими площадями. Это означает, что каждая вершина (площадь) имеет степень 3 (нечетная степень). Так как все шесть площадей имеют нечетную степень, невозможно построить экскурсию, проходя по каждой улице ровно один раз.

Result Card:

Твой статус: Цифровой атлет

Минус 15 минут нудной домашки. Потрать их на катку или новый рилс

Не будь NPC — кинь ссылку бро, который всё еще тупит над этой задачей