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

Для решения этой задачи нам нужно определить, какие вершины имеют нечетную степень (количество ребер, выходящих из вершины). Если в графе есть две вершины с нечетной степенью, то обход можно начать в одной из этих вершин и закончить в другой. Если все вершины имеют четную степень, то можно начать в любой вершине и закончить в ней же.

Посмотрим на степени вершин:

* Вершина 1: 3
* Вершина 2: 2
* Вершина 3: 2
* Вершина 4: 3
* Вершина 5: 4
* Вершина 6: 2
* Вершина 7: 3
* Вершина 8: 3

Мы видим, что вершины 1, 4, 7 и 8 имеют нечетную степень. Поскольку Олег начал обводить граф в вершине 7, он должен закончить в одной из вершин с нечетной степенью, отличной от 7. Возможные варианты: 1, 4 или 8.

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

1. 7 -> 6
2. 6 -> 8
3. 8 -> 7
4. 7 -> 1
5. 1 -> 2
6. 2 -> 5
7. 5 -> 3
8. 3 -> 4
9. 4 -> 1
10. 1 -> 5
11. 5 -> 4
12. 4 -> 8

Путь не соответствует условию задачи, так как нужно обойти все ребра ровно по одному разу. Согласно теории графов, если граф имеет две вершины с нечетной степенью, то путь начинается в одной из этих вершин и заканчивается в другой. В данном графе четыре вершины с нечетной степенью (1, 4, 7, 8). Поскольку начинаем в вершине 7, то закончить можно в вершине 1, 4 или 8.

Для нахождения правильного ответа, можно рассмотреть обход, который заканчивается в одной из этих вершин. Допустим, обход начинается в вершине 7 и заканчивается в вершине 4.

Один из возможных путей:

7-6, 6-8, 8-4, 4-3, 3-5, 5-1, 1-2, 2-5, 5-4, 4-1, 1-7, 7-8

В данном случае, конечная вершина это 8.

Ответ: 4