Контрольные задания > 5. На рисунке изображён граф. Наташа обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Наташа могла начать обводить граф.
Вопрос:
5. На рисунке изображён граф. Наташа обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Наташа могла начать обводить граф.
Для графа, чтобы его можно было обвести, не отрывая карандаша и не проводя ни по одному ребру дважды, нужно, чтобы в графе было не более двух вершин с нечетной степенью. В противном случае это невозможно. Если таких вершин нет, то начать можно с любой вершины. Если есть две вершины, то начать можно только с них. В графе вершины D и E имеют степень 3, а вершины C и A имеют степень 3, B имеет степень 2. У нас 4 вершины нечетной степени.
В данном графе невозможно обвести граф, не отрывая карандаш от листа бумаги и не проводя ни по одному ребру дважды.
**Ответ: Невозможно**