На рисунке изображён граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Николай начал обводить граф
Реши
Сверь числа и знаки с фото.
На рисунке изображён граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Николай начал обводить граф, если он закончил его обводить в вершине A? [Рисунок: граф с вершинами C, D, E в верхнем ряду; B, G, F — в среднем; A, I, K — в нижнем. Рёбра: C-D, D-E, C-B, B-A, E-F, F-K, A-I, I-K, B-G, G-F, D-B, D-F, A-G, G-K.]
Ответ: Николай начал с вершины \(K\).
В обходе без повторения рёбер все промежуточные вершины должны иметь чётную степень: в них «входим» и из них «выходим». Нечётными могут быть только начало и конец.
Считаем степени вершин:
\[ C=2,\quad D=4,\quad E=2,\quad B=4,\quad G=4,\quad F=4,\quad A=3,\quad I=2,\quad K=3. \]
Нечётные только \(A\) и \(K\). По условию обход закончился в \(A\), значит начался в \(K\).
Проверка — возможный маршрут:
\[ K-I-A-B-C-D-E-F-K-G-B-D-F-G-A. \]
Каждое ребро здесь использовано ровно один раз, начало — \(K\), конец — \(A\).
