Требуемые условия завершения
Цель урока:
научиться вычислять степень вершин графа, понимать связь суммы степеней с числом рёбер, различать цепи и циклы, познакомиться с ориентированными графами и решать простейшие задачи.
4. Цикл — замкнутая цепь
Определение:
Цикл — это цепь, у которой начальная и конечная вершины совпадают, а все остальные вершины различны.
Длина цикла — количество рёбер в нём.
Пример 4.
В том же графе: A – B – C – A — это цикл длины 3 (треугольник).
A – B – D – … — из D обратно в A нельзя (нет ребра D–A), значит, не цикл.
Цикл длины 3 называется треугольником.
Цикл длины 1 — петля (ребро из вершины в неё саму) — в школьных задачах редко.
Цикл длины 2 — две вершины, соединённые двумя разными рёбрами (мультиграф).
Пример 5 (граф без циклов):
Дерево (например, схема родословной без браков между родственниками) не содержит циклов.