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

Чтобы Катя могла обвести граф, не отрывая карандаша от бумаги и не проводя ни одно ребро дважды (эйлеров путь), необходимо, чтобы количество нечетных вершин было либо 0, либо 2. В данном графе вершины A, B, C, D, E, F имеют следующие степени (количество ребер, выходящих из вершины): A - 3 B - 4 C - 3 D - 3 E - 3 F - 2 Вершины A, C, D, E - нечетные (степень 3), вершина B четная (степень 4), вершина F четная (степень 2). Так как Катя начала в вершине B, то она закончит в одной из нечетных вершин. Если у графа ровно две нечетные вершины, то маршрут начинается в одной из этих вершин и заканчивается в другой. У нас четыре нечетные вершины. При анализе графа видно, что из вершины B можно пройти по следующему маршруту, не отрывая карандаша и не проходя по одному и тому же ребру дважды: B-A-E-D-C-B-F-E-C-D-A В этом случае мы заканчиваем в вершине А. Ответ: A