вероятность и статистика · 7 класс · урок 18
Путь, цепь и цикл. Связный граф
Путь · цепь · цикл · кратчайший путь · связный граф
Запомни
- Путь — последовательность вершин, в которой соседние соединены ребром. Длина пути — число рёбер.
- Цепь — путь, в котором ни одно ребро не повторяется. Цикл — цепь, которая заканчивается там, где началась.
- Кратчайший путь — тот, где меньше всего рёбер. Таких путей может быть несколько.
- Граф связный, если из любой вершины можно дойти до любой другой. Из k частей — не меньше k − 1 новых рёбер. 2 части: 1 ребро; k частей: k − 1
О чём урок
Сегодня мы пройдёмся по графу: узнаем, что такое путь, цепь и цикл, как найти самый короткий путь и когда граф называют связным.
Задача из урока
Сколько рёбер в самом коротком пути из A в F?
Ответ и решение по шагам: в тренажёре урока после покупки курса. Урок 01 и его тренажёр бесплатные.