Вопрос:

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

Фотография

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

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

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

Что ещё задавали пользователи