На рис. изображен граф. В вершине Маша завершит обводить граф, если начнет обводить его. Вершине К2.

Решение:

На рисунке изображён граф. Вершины графа обозначены буквами (C, A, B, K2, D, T). Стрелки указывают направление рёбер графа. Обведение графа — это проход по всем его вершинам и рёбрам, который начинается и заканчивается в одной и той же вершине.

Чтобы понять, где Маша завершит обводить граф, нужно проанализировать степени вершин (количество рёбер, выходящих из вершины и входящих в неё) и наличие ориентированного цикла.

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

Рассмотрим вершины:

• C: Входит 1 ребро (из A), выходит 1 ребро (в K2). Степень входа = 1, Степень выхода = 1.
• A: Входит 1 ребро (из C), выходит 2 ребра (в B и D). Степень входа = 1, Степень выхода = 2.
• B: Входит 1 ребро (из A), выходит 1 ребро (в K2). Степень входа = 1, Степень выхода = 1.
• K2: Входит 2 ребра (из C и B), выходит 1 ребро (в D). Степень входа = 2, Степень выхода = 1.
• D: Входит 1 ребро (из A), выходит 1 ребро (в T). Степень входа = 1, Степень выхода = 1.
• T: Входит 1 ребро (из D), выходит 1 ребро (в A). Степень входа = 1, Степень выхода = 1.

Из анализа видно, что вершины A и K2 имеют разное число входящих и выходящих рёбер.

Если Маша начнет обводить граф из вершины A, то она может пройти путь A → B → K2 → D → T → A. Но это не полный обход. Если она начнет из A, то, чтобы завершить обход, она должна закончить в вершине, где степень выхода больше степени входа (то есть в A). Но для завершения обхода, она должна будет выйти из K2, придя в нее из C и B.

Если начать обход из вершины, где степень выхода больше степени входа, и закончить в вершине, где степень входа больше степени выхода, то это будет Эйлеров путь.

В данном случае, если Маша начнет из A, то путь может быть такой: A → B → K2 → D → T → A. Но из A выходит два ребра. Если начать из A, то путь может быть A → D → T → A. Но это не полный обход.

Если Маша начнет обход из вершины A, то она может пройти путь: A → B → K2 → D → T → A. Но это не полный обход. Если она начнет обход из вершины A (степень выхода 2, степень входа 1), она может пройти через вершины.

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

Если Маша начнет из вершины A (где выход > вход), она может закончить в вершине K2 (где вход > выход).

Путь: A → B → K2 (тут она пришла из C и B) → D → T → A. Это не полный обход.

Правильный путь, если начать из A: A → D → T → A → B → K2. Это тоже не полный обход.

Если Маша начнет из вершины A, то она может закончить в вершине K2. Например: A → B → K2 (как завершающая вершина). Но это не Эйлеров цикл. Если начать из A, то путь будет A → D → T → A → B → K2. Тут она не сможет пройти из A еще раз.

Единственная вершина, где завершится обход, если начать с нее, — это вершина, где степень входа равна степени выхода. Если такого нет, то это будет вершина, где степень входа больше степени выхода.

Исходя из условия, что Маша начнет обходить граф, и ей нужно его завершить, то если она начнет из вершины A, она может закончить в вершине K2. Путь: A → B → K2. Это не полный обход.

Если начать из A, то путь будет: A → B → K2 → D → T → A. Но из A выходит два ребра. Если начать из A, то путь может быть: A → D → T → A → B → K2. Тогда она завершит в K2.

Таким образом, если Маша начнет из вершины A, она завершит обводку в вершине K2.

Уточнение: Граф является ориентированным. Для существования Эйлерова цикла необходимо, чтобы для каждой вершины степень входа равнялась степени выхода. В данном графе это условие не выполняется. Следовательно, речь может идти об Эйлеровом пути. Эйлеров путь существует, если есть либо 0 вершин, где степень входа равна степени выхода, либо 2 вершины, одна из которых имеет степень выхода на 1 больше степени входа (начальная), а другая — степень входа на 1 больше степени выхода (конечная). В данном случае, вершина A имеет степень выхода на 1 больше степени входа (2 > 1), а вершина K2 имеет степень входа на 1 больше степени выхода (2 > 1). Если Маша начнет из вершины A, она завершит обводку графа в вершине K2.

Ответ: K2