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

Для того чтобы граф можно было обвести, не отрывая карандаша и не проводя ни одно ребро дважды (то есть построить эйлеров путь), необходимо и достаточно, чтобы в графе было не более двух вершин с нечётной степенью (количеством рёбер, выходящих из вершины). Если таких вершин нет или есть только одна, то можно начать с любой вершины. Если их две, то начинать обвод нужно с одной из них, а закончить – в другой. Посчитаем степени вершин графа: - A: 1 - B: 1 - C: 2 - D: 1 - E: 1 - F: 2 - G: 2 - H: 1 - K: 1 - L: 2 - M: 2 - N: 1 - O: 6 Нечётные степени имеют вершины: A, B, D, E, H, K, N. Так как эйлеров путь должен заканчиваться в вершине C, а начать можно только в вершине с нечётной степенью, то Ваня не мог закончить обвод графа в вершине C, не нарушая условия задачи. Скорее всего, в условии опечатка, и нужно найти, с какой вершины Ваня *мог* начать обвод, чтобы закончить в одной из вершин с нечетной степенью. Если он закончил обвод в вершине С, то в графе должно быть не более двух вершин с нечетной степенью, но их больше, поэтому условие не выполняется. Следовательно, Ваня не мог начать обвод графа, чтобы закончить его в вершине С, не нарушая правил. Если же требуется найти вершину, с которой можно начать обвод, чтобы закончить в вершине с нечётной степенью, то нужно выбрать любую из вершин с нечётной степенью, отличную от C. Например, если бы он закончил в вершине A, то начал бы в любой другой вершине с нечётной степенью.