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

Решение:

Чтобы обойти граф, не отрывая карандаша и не проводя по одному ребру дважды, мы должны использовать теорему Эйлера. Согласно ей, такой обход возможен, если граф связный и имеет либо 0, либо 2 вершины с нечётной степенью.

Если граф имеет 2 вершины с нечётной степенью, то обход начинается в одной из них и заканчивается в другой.

Если граф имеет 0 вершин с нечётной степенью, то обход может начаться и закончиться в любой вершине.

В данной задаче граф имеет 2 вершины с нечётной степенью, и обход заканчивается в вершине 6. Это означает, что начало обхода должно быть в другой вершине с нечётной степенью.

Давайте определим степени всех вершин:

• Вершина 1: степень 3 (соединения с 2, 6, 7)
• Вершина 2: степень 2 (соединения с 1, 3)
• Вершина 3: степень 2 (соединения с 2, 4, 7)
• Вершина 4: степень 2 (соединения с 3, 5, 8)
• Вершина 5: степень 2 (соединения с 4, 6, 8)
• Вершина 6: степень 3 (соединения с 1, 5, 7)
• Вершина 7: степень 4 (соединения с 1, 3, 6, 8)
• Вершина 8: степень 4 (соединения с 4, 5, 7)

Вершины с нечётной степенью — это вершины 1 и 6. Поскольку Пётр закончил обводить граф в вершине 6, он должен был начать обход в другой вершине с нечётной степенью, то есть в вершине 1.

Ответ: 1