Цепь и цикл. Путь в графе простыми словами: найти путь, цепь и цикл. Тренажёр 7 класс
← Все тренажёры
Telegram-канал ↗Telegram ↗

Цепь и цикл. Путь в графе

Зачем это нужно: так проверяют любой маршрут. Можно ли пройти, ничего не повторив, и вернуться в начало другой дорогой? Это и учимся проверять.

Графточки (вершины) и линии (рёбра)
Путь из A в C
▬ Маркер полупрозрачный: повтор темнее
Нажимай точки по очереди: маркер пойдёт по линии
Крути пальцем вбок · двумя пальцами ближе · двойное нажатие: вид прямо на экран
Маркер стоит в A. Нажми точку, с которой A соединена линией.
Aдлина 0

Главное правило

Путь: идём по рёбрам от вершины к вершине, повторы можно. Цепь: путь, где ни одна вершина не повторяется. Цикл: путь вернулся в начальную вершину, а рёбра и остальные вершины не повторились.
A-B-C-Bпуть: повторы можно
A-B-Cцепь: вершины разные
A-B-C-Aцикл: вернулись без повторов
длина A-B-C = 2длина: число рёбер

Почему A-B-A не цикл

Вернулись в A, но по ребру AB прошли два раза: туда и обратно. В цикле рёбра не повторяются. Проверка числом: в цикле разных рёбер столько же, сколько вершин. В A-B-C-A вершин 3 и разных рёбер 3, а в A-B-A вершин 2, а разное ребро одно: AB.

Почему цепь не обязана пройти все вершины

Цепь это любой путь без повтора вершин. A-B уже цепь, даже если в графе 6 вершин. Проверка: в цепи A-B вершин 2, рёбер 1, повторов нет.

Как проверить маршрут в тетради

  1. 1. Проверь каждую пару соседних букв: есть ли такое ребро. Если хоть одного нет, это не путь.A-B-F-A: AB, BF, FA есть
  2. 2. Посчитай пары соседних букв: это длина пути. Букв на одну больше.длина 3
  3. 3. Ищи повтор. Вершина встретилась дважды, и это не пара «начало и конец»: путь, но не цепь.A только в начале и в конце
  4. 4. Начало и конец одна вершина, других повторов нет, ни одно ребро не пройдено дважды: цикл. A-B-A не цикл: ребро AB дважды.A-B-F-A цикл
  5. 5. Начало и конец разные, повторов нет: цепь.A-B-F цепь

Соседняя тема: связный граф, в нём из любой вершины есть путь в любую другую.

Как проверить любой маршрут

A-B-D-C

  1. Пары: AB есть, BD?

A-B-C-B-E

  1. Пары AB, BC, CB, BE: все рёбра есть. Это путь, длина 4.

A-B-A

  1. Начали в A и закончили в A. Похоже на цикл?

A-B-C-A

  1. Пары AB, BC, CA: все рёбра есть. Длина 3.

Бесконечный тренажёр

A-B-D-C: все рёбра есть?
Цель дня: 0 из 5Уровень 1
A-B-D-C
Шаг 1 из 2
Все ли соседние вершины маршрута соединены рёбрами?

Где это бывает в жизни

⛷️

Лыжня в зимнем лесу: вернуться на базу

Цикл: вернулись на базу по другой трассе

Как уйти с базы и вернуться, не пройдя ни одну трассу дважды?

Место это вершина, трасса между местами это ребро. На трассе две лыжни: встречные лыжники держатся правой, поэтому туда и обратно едут по соседним лыжням, но трасса та же.

👆 Веди сам: нажми мигающее место
Трасс пройдено: 0
Лыжник на базе. Нажми мигающее место: туда ведёт трасса.

Вернулись на базу по другой трассе, по дороге ничего не повторили: это цикл. Туда и обратно по одной трассе не цикл, даже если обратно ехал по соседней лыжне.

Для мам и пап

Главная ошибка: «вернулся в начало, значит, цикл». Маршрут туда и обратно по одной линии не цикл: ребро пройдено дважды.

3 минуты с бумагой

Нарисуйте точки A, B, C, D, E и 6 линий: AB, BC, CA, CD, DE, EA. Пусть ребёнок карандашом проведёт A-B-C-A, а потом A-B-A. Спросите, где линия обведена дважды.

Что спросить

«Есть линия между этими буквами? Какая буква уже была? Ты вернулся по той же линии?» Не говорите «просто запомни»: пусть проверит по рисунку.

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

В цепи рёбер на одно меньше, чем вершин: A-B-C, 3 вершины, 2 ребра. В цикле разных рёбер столько же, сколько вершин: A-B-C-A, 3 и 3. В A-B-A вершин 2, а разное ребро одно, значит, это не цикл.

Тема понята, когда ребёнок без рисунка, по списку рёбер, говорит про маршрут «путь», «цепь», «цикл» или «не путь» и называет причину.

Какой путь проходит ребёнок
ЭтапДумаетПишетГде в тренажёре
1. Иду по рёбрам«Можно перейти в любую точку, которая рядом».A-D-C назван путём, хотя ребра AD нет (e2).Герой «Путь»: если линии нет, маркер не идёт и пишет почему.
2. Считаю длину«Длина это сколько букв».A-B-C-D: длина 4 (e1).Под моделью счётчик рёбер, вкладка 1 «Путь».
3. Путь или цепь«Повторы запрещены везде» или «главное, чтобы рёбра не повторялись».A-B-C-B-D не путь (e9); A-B-C-A-D цепь (e3).Второй слой маркера темнеет на повторе. Вкладка 2 «Цепь».
4. Узнаю цикл«Вернулся в начало, значит, цикл».A-B-A назван циклом (e4); A-B-C-A не цикл из-за двух A (e6).Герой «Цикл»: назад по той же линии маркер не идёт. Вкладка 3, сцена «Лыжня».
5. Ловушки«Цикл должен обойти всё» или «вернулся, и ладно».A-B-F-A не цикл (e5); восьмёрка названа циклом (e7).Вкладка 4 «Вперемешку».
6. Сам, без рисункаПроверяет пары, повторы и начало с концом.Без рисунка снова путает A-B-A с циклом.Вкладка 5 «Проверка» и задача без рисунка.
Отчёт на языке ошибок: как выглядит, почему, что сделать
Как выглядитПочемуЧто сделать за 2 минуты
A-B-C-D: длина 4считает буквы, а длина пути это число рёберПопросите назвать рёбра пути парами букв (AB, BC, CD) и посчитать пары.
A-D-C назван путём, а ребра AD нетне проверяет каждую пару или считает соседними точки, нарисованные рядомПусть ребёнок ведёт пальцем по рисунку: палец не должен отрываться от линий.
A-B-C-A-D назван цепьюпроверяет только рёбра и не видит, что вершина повториласьПусть ребёнок обведёт каждую букву маршрута: где буква обведена дважды, там повтор.
A-B-A назван цикломдумает: вернулся в начало, значит, циклСпросите: «По какой линии ты вернулся? По той же?» Если по той же, это не цикл.
A-B-F-A не цикл: прошли не все вершиныдумает, что цепь и цикл обходят весь графПокажите треугольник внутри большого рисунка: это уже цикл, остальные вершины не нужны.
A-B-C-A не цикл: A два разасчитает повтором то, что начало и конец совпалиОбъясните: буква в конце показывает, что мы вернулись, а не прошли её второй раз по дороге.
A-B-C-A-D-E-A назван цикломвидит, что вернулись в начало, и не замечает повтор в серединеПопросите найти каждую букву маршрута между первой и последней: повторов там быть не должно.
в цикле A-B-C-A рёбер 4считает рёбра по буквам записиСпросите, сколько линий обвёл маркер, и посчитайте их на рисунке вместе.
A-B-C-B-D не путь: B повториласьпутает путь с цепью и думает, что в пути нельзя повторятьСкажите так: путь это любая прогулка по линиям, цепь это прогулка без повторов.
A-D-C: «нет ребра AD», хотя линия AD естьне находит на рисунке длинное ребро или ребро, которое пересекает другие линииПусть ребёнок проведёт пальцем от первой буквы до второй прямо по линии.
A-B-C-D: «B повторилась»не сверяет каждую букву маршрута с остальнымиПусть ребёнок выпишет буквы маршрута и вычёркивает найденные: повтор, если букву уже вычеркнули.
путь A-B-C: длина 6, потому что в графе 6 вершинсчитает все вершины графа, а не рёбра путиПопросите показать пальцем только те линии, по которым прошёл маршрут, и посчитать их.

Что дальше

Все тренажёры →

Частые вопросы

Чем путь отличается от цепи?

В пути вершины и рёбра могут повторяться. Цепь это путь, в котором ни одна вершина не повторяется: A-B-C цепь, а A-B-C-B-D путь, но не цепь, вершина B встретилась дважды.

Почему A-B-A не цикл?

Вернулись в A, но по ребру AB прошли два раза: туда и обратно. В цикле рёбра и вершины, кроме начальной, не повторяются. В графах этого тренажёра две вершины соединены не больше чем одним ребром, поэтому в цикле хотя бы 3 ребра.

Что такое длина пути?

Число рёбер в пути. У пути A-B-C-D рёбра AB, BC, CD, длина 3. Букв в записи всегда на одну больше, чем рёбер.

Должны ли цепь и цикл проходить через все вершины графа?

Нет. A-B уже цепь, а треугольник A-B-F-A внутри большого графа уже цикл. Обойти все вершины нужно только тогда, когда этого требует задача.

Может ли в цепи рёбер быть больше, чем вершин?

Нет. В цепи рёбер ровно на одно меньше, чем вершин: каждое новое ребро приводит в новую вершину. A-B-C-D: вершин 4, рёбер 3.

Может ли в цикле рёбер быть меньше, чем вершин?

Нет. В цикле рёбер столько же, сколько вершин: последнее ребро возвращает в начало. A-B-C-D-A: вершин 4, рёбер 4.

Тренажёр сделали методисты школы «да, математика». yesmatematika.com
Обновлено 16 ноября 2026