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

Решение:

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

Рассмотрим степени вершин на графе:

• Степень вершины A: 2 (рёбра AB, AJ)
• Степень вершины B: 4 (рёбра BA, BC, BF, BJ)
• Степень вершины C: 2 (рёбра CB, CD)
• Степень вершины D: 3 (рёбра DC, DB, DE)
• Степень вершины E: 2 (рёбра ED, EK)
• Степень вершины F: 2 (рёбра FB, FK)
• Степень вершины J: 2 (рёбра JB, JA)
• Степень вершины K: 2 (рёбра KE, KF)

В данном графе вершины D имеет нечётную степень (3). Все остальные вершины имеют чётную степень. Если в графе есть две вершины с нечётной степенью, то обход начинается с одной из них и заканчивается в другой. Если же в графе только одна вершина имеет нечётную степень, то такой обход невозможен. В нашем случае, если бы это был полный обход, то должна была бы быть либо 0, либо 2 вершины с нечётной степенью. Однако, поскольку мы знаем, что обход возможен (и он закончен в вершине А), то это означает, что в графе должна быть ровно одна вершина с нечётной степенью, если мы рассматриваем граф как путь. В данной задаче, мы имеем одну вершину с нечетной степенью (D), и Светлана закончила обводить в вершине А. Так как вершина D имеет нечетную степень, а вершина А имеет четную степень, то начало обхода могло быть только из вершины D.

Однако, если рассматривать задачу как обход Эйлера, который начинается и заканчивается в одной и той же вершине, то все вершины должны иметь четную степень. Если же начало и конец обхода разные, то ровно две вершины должны иметь нечетную степень. В данном графе только вершина D имеет нечетную степень, что противоречит условию возможности полного обхода. Но так как в условии сказано, что Светлана обвела граф, мы предполагаем, что обход возможен.

Если Светлана закончила обводить в вершине А, а в графе есть ровно одна вершина с нечётной степенью (D), то начало обхода должно быть из вершины D.

Вернемся к степеням вершин:

• A: 2
• B: 4
• C: 2
• D: 3
• E: 2
• F: 2
• J: 2
• K: 2

Есть одна вершина с нечетной степенью (D). Если обход заканчивается в точке А, то он должен начинаться в точке D.

Пояснение:

Для того чтобы обойти граф, не отрывая карандаша и не проводя ни по одному ребру дважды:

1. Если все вершины имеют чётную степень, то можно начать из любой вершины и закончить в той же вершине (Эйлеров цикл).

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

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

В данном графе только одна вершина (D) имеет нечётную степень (3). Это означает, что строгого Эйлерова пути или цикла нет. Однако, если предположить, что обход возможен и закончен в вершине А, то начало обхода должно быть в вершине с нечётной степенью. В данном случае это вершина D. Таким образом, Светлана начала обводить граф с вершины D.

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

• A: 2
• B: 4
• C: 2
• D: 3
• E: 2
• F: 2
• J: 2
• K: 2

Так как вершина D имеет нечетную степень, а Светлана закончила в А, то начало пути должно быть в D.

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

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

Это условие подразумевает, что такой обход существует.

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

• A: 2 (AB, AJ)
• B: 4 (BA, BC, BF, BJ)
• C: 2 (CB, CD)
• D: 3 (DC, DB, DE)
• E: 2 (ED, EK)
• F: 2 (FB, FK)
• J: 2 (JB, JA)
• K: 2 (KE, KF)

Вершина D имеет нечетную степень. Все остальные вершины имеют четную степень.

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

Итак, если в графе только одна вершина с нечетной степенью, то обход возможен, если он начинается с этой вершины и заканчивается в какой-либо другой вершине. В данном случае, Светлана закончила в А, а единственная вершина с нечетной степенью - D. Следовательно, она начала обводить граф с вершины D.

Ответ: D