Связная компонента графа

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

Связной компонентой вершины i называется множество всех тех вершин, в которые можно попасть из i, идя по ребрам графа. (Поскольку граф неориентированный, отношение << j принадлежит связной компоненте i>> является отношением эквивалентности.)

$\scriptstyle{\blacktriangleright}$ 7.4.5. Дан неориентированный граф (для каждой вершины указано число соседей и массив номеров соседей, как в задаче о топологической сортировке). Составить алгоритм, который по заданному i печатает все вершины связной компоненты i по одному разу (и только их). Число действий не должно превосходить $C\cdot{}$ (общее число вершин и ребер в связной компоненте).

Решение. Программа в процессе работы будет << закрашивать>> некоторые вершины графа. Незакрашенной частью графа будем называть то, что останется, если выбросить все закрашенные вершины и ведущие в них ребра. Процедура add(i) закрашивает связную компоненту i в незакрашенной части графа (и не делает ничего, если вершина i уже закрашена).

     procedure  add (i:1..n);
     begin
     | if вершина i закрашена then begin
     | | ничего делать не надо
     | end else begin
     | | закрасить i (напечатать и пометить как закрашенную)
     | | для всех j, соседних с i
     | | | add(j);
     | | end;
     | end;
     end;

Докажем, что эта процедура действует правильно (в предположении, что рекурсивные вызовы работают правильно). В самом деле, ничего, кроме связной компоненты незакрашенного графа, она закрасить не может. Проверим, что вся она будет закрашена. Пусть k -- вершина, доступная из вершины i по пути ${\hbox{\tt i}}\rightarrow{\hbox{\tt j}}\rightarrow\ldots\rightarrow{\hbox{\tt k}}$ ,проходящему только по незакрашенным вершинам. Будем рассматривать только пути, не возвращающиеся снова в i. Из всех таких путей выберем путь с наименьшим j (в порядке просмотра соседей в процедуре). Тогда при рассмотрении предыдущих соседей ни одна из вершин пути ${\hbox{\tt j}}\rightarrow\ldots\rightarrow{\hbox{\tt k}}$ не будет закрашена (иначе j не было бы минимальным) и потому k окажется в связной компоненте незакрашенного графа к моменту вызова add(j). Что и требовалось.

Чтобы установить конечность глубины рекурсии, заметим, что на каждом уровне рекурсии число незакрашенных вершин уменьшается хотя бы на 1.

Оценим число действий. Каждая вершина закрашивается не более одного раза -- при первым вызове add(i) с данным i. Все последующие вызовы происходят при закрашивании соседей -- количество таких вызовов не больше числа соседей -- и сводятся к проверке того, что вершина i уже закрашена. Первый же вызов состоит в просмотре всех соседей и рекурсивных вызовах add(j) для всех них. Таким образом, общее число действий, связанных с вершиной i, не превосходит константы, умноженной на число ее соседей. Отсюда и вытекает требуемая оценка. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 7.4.6. Решить ту же задачу для ориентированного графа (напечатать все вершины, доступные из данной по стрелкам; граф может содержать циклы).

Ответ. Годится по существу та же программа (строку << для всех соседей>> надо заменить на << для всех вершин, куда ведут стрелки>>). $\scriptstyle\blacktriangleleft$

pvv
1/8/1999