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

Для решения этой задачи нам нужно определить, с какой вершины Петр начал обводить граф, зная, что он закончил в вершине 6 и не отрывал карандаш от бумаги, не проводя ни по одному ребру дважды. Это задача на эйлеровы пути. В графе Эйлеров путь существует, если не более двух вершин имеют нечетную степень (количество ребер, выходящих из вершины). Если все вершины имеют четную степень, то Эйлеров цикл существует, и можно начать с любой вершины. Сначала определим степень каждой вершины: - Вершина 1: степень 3 - Вершина 2: степень 2 - Вершина 3: степень 2 - Вершина 4: степень 2 - Вершина 5: степень 2 - Вершина 6: степень 2 - Вершина 7: степень 4 - Вершина 8: степень 3 У нас есть две вершины с нечетной степенью: вершина 1 (степень 3) и вершина 8 (степень 3). Так как Петр закончил обход в вершине 6, значит, он начал обход с вершины, имеющей нечетную степень. У нас только две вершины с нечетной степенью, но только одна из них может быть началом, так как конец пути - вершина 6. Поскольку в графе ровно две вершины с нечетной степенью (1 и 8), путь должен начинаться в одной из них и заканчиваться в другой. Нам известно, что путь заканчивается в вершине 6, и 6 не имеет нечетную степень, следовательно, Петр должен был начать в вершине 1 или 8, но закончил в 6, это значит что изначально граф у нас должен быть с вершинами 1 и 8 как начало и конец соответственно. Значит, путь должен начинаться с вершины 8, чтобы закончиться в вершине 6 (условие). Но подождите, как я мог ошибиться? Все просто: вершина 6 имеет четную степень! Это значит, что нам нужно перепроверить условие и вспомнить, что все пути, где старт и финиш - это вершины с нечетными степенями. Из этого следует, что старт - это вершина 1, финиш - 8! Ответ: Петр начал обводить граф с вершины 8.