На рисунке изображён граф. Светлана обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Светлана начала обводить граф
Реши задание на изображении
Сверь числа и знаки с фото.
Упражнение 2 из 12 [Рисунок: квадрат с вершинами C (верхний левый), D (верхняя середина), E (верхний правый), B (левая середина), F (центр), K (правая середина), A (нижний левый), J (нижняя середина), L (нижний правый). Проведены стороны квадрата, отрезки D—F—J и B—F—K, а также диагонали C—F, F—L, D—K, B—J.] На рисунке изображён граф. Светлана обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Светлана начала обводить граф, если она закончила его обводить в вершине L?
Ответ: \(C\).
При обводе одним росчерком без повторного прохода по рёбрам получается эйлерова цепь. В связном графе она возможна тогда и только тогда, когда нечётную степень имеют ровно две вершины: именно в них путь начинается и заканчивается.
Степень вершины — это число выходящих из неё рёбер. По рисунку:
- \(C\): 3 ребра — \(CD\), \(CB\), \(CF\);
- \(L\): 3 ребра — \(LK\), \(LJ\), \(LF\);
- у остальных вершин степени чётные.
Значит, нечётные вершины только \(C\) и \(L\). Так как обход закончился в \(L\), начаться он должен был в \(C\).
Проверка: если бы начали и закончили в \(L\), это был бы замкнутый обход, а тогда все степени должны быть чётными. Но у \(C\) степень 3, поэтому начало — \(C\).
