Вероятность и статистика · урок 13

Связность, пути, цепи и циклы в графах

Учимся читать маршруты в графе.

Объяснение темы

Путь в графе — последовательность рёбер, по которым можно пройти от одной вершины к другой. Цепь обычно не повторяет рёбра, а цикл начинается и заканчивается в одной и той же вершине. Граф называется связным, если между любыми двумя вершинами существует путь.

Примеры

Пример 1. Если из любой станции метро можно доехать до любой другой, схема связна.
Пример 2. Маршрут A-B-C-D — путь.
Пример 3. Маршрут A-B-C-A — цикл.

Проверка темы

Решите задания и отправьте ответы на проверку.

Чтобы платформа сохранила результат, войдите или зарегистрируйтесь.

Войти Зарегистрироваться