На рисунке изображён граф. Полина обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Полина начала обводить граф, если она закончила его обводить в вершине 3?

Question

Вопрос:

На рисунке изображён граф. Полина обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Полина начала обводить граф, если она закончила его обводить в вершине 3?

Фотография

Ответ ассистента

Accepted Answer

Для того чтобы обвести граф, не отрывая карандаша от бумаги и не проходя по одному ребру дважды, нужно найти Эйлеров путь. Согласно теории графов, такой путь существует, если в графе не более двух вершин с нечётной степенью (количеством выходящих из них линий). 1. Определим степень каждой вершины (посчитаем количество линий, сходящихся в точке): - Вершина 1: 4 линии (чётная); - Вершина 2: 4 линии (чётная); - Вершина 3: 5 линий (нечётная); - Вершина 4: 4 линии (чётная); - Вершина 5: 4 линии (чётная); - Вершина 6: 5 линий (нечётная). 2. В графе ровно две нечётные вершины: 3 и 6. По правилу Эйлера, если в графе есть две нечётные вершины, то любой Эйлеров путь должен начинаться в одной из них и заканчиваться в другой. Так как Полина закончила обводить граф в вершине 3, она обязательно должна была начать в другой нечётной вершине — вершине 6. **Ответ: 6**

Ответ ассистента

Другие решения