lecture_04

Связность

Граф G называется связным, если имеется путь между любыми двумя его различными вершинами.

Теорема 3. Граф G является связным тогда и только тогда, когда между любыми двумя его вершинами существует простой путь.

Связность

Граф G называется связным, если имеется путь между любыми двумя его различными вершинами.

Теорема 3. Граф G является связным тогда и только тогда, когда между любыми двумя его вершинами существует простой путь.

Для связности графа необходимо и достаточно, чтобы произвольная фиксированная вершина графа соединялась маршрутом с каждой из оставшихся вершин этого графа.

Компонента связности

Отношение связности рефлексивно (вершина всегда связана сама с собой), симметрично (из связности вершины u с вершиной v следует связность вершины v с вершиной u) и транзитивно (если вершины u, v и вершины v, w связаны, то связаны и вершины u, w).

Таким образом, отношение связности для вершин есть отношение эквивалентности. Поэтому существует такое разбиение множества вершин графа на попарно непересекающиеся подмножества (классы эквивалентности).

Каждое такое подмножество вершин графа вместе с ребрами, инцидентными этим вершинам, образует связный подграф, который называется связной компонентой графа.

Поиск в глубину

Поиск в глубину

Выделение компонент связности

Модифицируем алгоритм поиска в глубину

Точка сочленения

Точкой сочленения называется такая вершина, удаление которой делает граф несвязным.

Алгоритм нахождения всех точек сочления

Мост

Мостом называется ребро, удаление которого увеличивает число компонент связности.

Алгоритм нахождения мостов