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

Question

Вопрос:

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

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

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

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

Вершина A: степень 2
Вершина B: степень 4
Вершина C: степень 2
Вершина K: степень 4
Вершина D: степень 2
Вершина N: степень 2

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

Посчитаем количество ребер:

AC
AK
AB
BC
BK
BN
KD
KN
DN

Всего 9 ребер. Если Марина начала обводить в вершине A, то закончит в вершине N.

Ответ: N