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