Задание, где нужно обвести граф одной линией, часто вызывает панику у школьников. На самом деле это просто головоломка с чёткими правилами. Давайте разберём её спокойно и шаг за шагом.
Условие задачи
На рисунке изображён граф из 13 вершин. Ваня обвёл его одним росчерком — не отрывая карандаша и не проводя по одному ребру дважды. Известно, что закончил он в вершине C. Требуется определить, с какой вершины он начал.
Что важно знать: степень вершины
Первое, что нужно сделать — посчитать, сколько линий выходит из каждой точки. В математике это называется «степень вершины». Посмотрим на наш граф:
• Степень 2 (две линии): вершины A, N, D, E, H, K
• Степень 4 (четыре линии): вершины M, B, C, F, G, L
• Степень 6 (шесть линий): вершина O
Все степени чётные — 2, 4, 6. Это ключевой момент.
Правило Эйлера: как рисовать граф одной линией
Существует классическая теорема Эйлера. Если объяснять просто:
• В каждой вершине, кроме начала и конца, сколько раз карандаш заходит, столько же выходит. Значит, у всех «промежуточных» вершин число линий должно быть чётным.
• Если в графе все вершины чётные, то начать можно где угодно, но закончить придётся в той же точке (получается замкнутый маршрут).
• Если в графе ровно две нечётные вершины, то начать нужно в одной из них, а закончить — в другой.
• Если нечётных вершин больше двух — нарисовать граф одной линией вообще невозможно.
Применяем к нашей задаче
В нашем графе все вершины чётные (2, 4, 6). Значит, работает первый случай: начало и конец совпадают.
По условию Ваня закончил обводить в вершине C. Следовательно, начал он тоже в вершине C.
Ответ: C.
Коротко для родителей
Если ребёнок увидит такое задание в ВПР, алгоритм прост: считаем линии у каждой вершины. Если все числа чётные — ищем конец пути, он же будет началом. Если есть ровно две нечётные — они и есть старт и финиш.