Связность графа

Определение. Связный граф

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

Путь в графе

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

Цепь и цикл

Цепь — путь, в котором ни одно ребро не проходится дважды. Цикл — цепь, которая начинается и заканчивается в одной и той же вершине, то есть замкнутый маршрут.

Пример 1. Связность графа

Дан граф с вершинами A, B, C, D и рёбрами A–B, B–C. Определить, связный ли он.

Дано: рёбра: A–B, B–C. Вершины: A, B, C, D.

Анализ: из A можно добраться до B и C (через B). Но из D не выходит ни одного ребра — до D нельзя добраться ни из одной вершины.

Ответ: граф несвязный. Вершина D образует отдельную компоненту связности.

Пример 2. Путь между вершинами

Дан граф с рёбрами A–B, B–C, C–D. Найти путь из A в D.

Дано: рёбра: A–B, B–C, C–D.

Формула: путь — последовательность рёбер из начальной вершины в конечную.

Подстановка: из A идём в B (A–B), затем в C (B–C), затем в D (C–D).

Ответ: путь из A в D: A–B–C–D. Вершины A и D связаны.

Пример 3. Цикл в графе

Дан граф с рёбрами A–B, B–C, C–D, D–A. Найти цикл.

Дано: рёбра: A–B, B–C, C–D, D–A.

Анализ: можно пройти A–B–C–D–A, вернувшись в начальную вершину A, не проходя по одному ребру дважды.

Ответ: A–B–C–D–A — цикл. Граф содержит замкнутый маршрут.

Важно!

⚠️ Типичная ошибка — путать цепь и цикл. Цепь — это «открытый» путь из одной вершины в другую (начало и конец разные). Цикл — это «замкнутая» цепь, которая возвращается в начальную вершину. Цикл — это частный случай цепи, у которой начало совпадает с концом.