§3. Цепи и пути в графах.

В этом разделе будем рассматривать только связные неориен­тированные графы. Нетрудно проверить, что и ПВГ-дерево, и ПВШ-дерево действительно являются деревьями, и более того — корневыми деревьями (см. гл.2), причем корнями этих деревьев являются те вершины, с которых начинался поиск (собственно поэтому они и в ПВГ и в ПВШ названы корневыми вершинами).

Ранее, в главе 2, мы условились считать, что если в ориенти­рованном графе имеется дуга (v,w), то v — отец w, a w — сын v. Легко видеть, что даваемые алгоритмами 4.1 и 4.2 значения пе­ременных ОТЕЦ[w] согласуются с ранее введенным понятием, а именно, если v=ОТЕЦ[w], то (v,w)E.

Напомним, что вершина v называется предком вершины w. и, соответственно, w — потомком v, если в корневом дереве суще­ствует путь от v до w. Например, в корневом дереве ПВШ(1) из рис.4.2 вершина 8 является потомком вершины 2. В следующей теореме формулируются полезные свойства ПВГ-деревьев.

Теорема 4.3. Пусть Т — ПВГ-дерево связного неориентиро­ванного графа G=(V,E), и пусть {u,w}E. Тогда либо u — пото­мок w, либо w потомок u в корневом дереве Т.

Предположим без ограничения общности, что вершина и будет просмотрена раньше, чем w. Рассмотрим процесс поиска в глубину, начиная с первого вызова процедуры ПВГ(u) (см. алго­ритм 4.1.), и до первого вызова ПВГ(w). Это означает, что мы прошли по некоторым ребрам из вершины u в w. Но именно эти пройденные ребра мы и относим в ПВГ-дерево Т. Они образуют путь из u в w, следовательно, вершина u является предком вер­шины w в корневом дереве Т.

Понятно, что ПВШ-дерево не обладает свойством, сформули­рованным в теореме 4.3. Например, в ПВШ(1)-дереве, изобра­женном на рис.4.2, ни вершина 3 не является потомком вершины 6, ни вершина 6 не является потомком вершины 3 (говорят, что такие вершины несравнимы в корневом дереве).

Как в ПВГ-дереве, так и в ПВШ-дереве для каждой вершины w, существует единственный путь из корня v в w. Как построить этот путь? Это несложно делается с помощью массива ОТЕЦ. Отметим только, что под путем в орграфе мы договорились по­нимать в зависимости от степени удобства, либо последователь­ность ребер, либо последовательность вершин (см.гл.2). В пред­лагаемом ниже алгоритме 4.3 требуемый путь идентифицируется последовательностью вершин. Предполагается, что перед рабо­той этого алгоритма работала либо процедура ПВГ(v), либо про­цедура ПВШ(v).

АЛГОРИТМ 4.3. ПОСТРОЕНИЕ ПУТИ

Данные: корневая вершина поиска v, вершина w. массив ОТЕЦ.

Р

1. begin

2. СТЕК:=Ø; СТЕК w; u:=w;

3. while u≠v do

4. begin u:=ОТЕЦ[u];

5. CTEKu;

6. end;

7. end.

езультат: СТЕК, содержащий последовательность вершин, об­разующихv-w-путь.

Понятно, что последовательность вершин v=v₀,v₁,...,v_k=w, по­лученная считыванием СТЕКА, образует как v-w-путь в корневом дереве Т (или D), так и v-w-цепь в исходном графе G.

Оказывается, что пути, построенные поиском в ширину, обла­дают очень полезным свойством, а именно, справедлива.

Теорема 4.4. Пусть D — ПВШ-дерево с корнем v связного неориентированного графа G=(V,E). Тогда для любой вершины wV единственный v-w-путь в D определяет кратчайшую по числу ребер цепь среди всех v-w-цепей в графе G.

Пусть кратчайшая по числу ребер v-w-цепь в графе G со­держит t ребер. (Будем говорить, что вершина w находится на расстоянии t от v). Докажем теорему индукцией по расстоянию t.

Пусть t=l. Тогда всякая вершина u, находящаяся на расстоя­нии 1 от v, будет просмотрена из v, то есть для всех таких вершин u справедливо равенство ОТЕЦ[u]=v. Одновременно v — единст­венная вершина связного графа, для которой OTEЦ,[v]=nil. Зна­чит, как это следует из алгоритма 4.3, поиск в ширину правильно определяет кратчайшие цепи до всех вершин, находящихся на расстоянии 1 от вершины v.

Пусть ПВШ-дерево правильно определяет кратчайшие цепи до всех вершин, находящихся на расстоянии t ≤ k от v.

Пусть вершина w находится на расстоянии k+1 от v и путь v=v₀,v₁...,v_k+1=w — кратчайшая v-w-цепь в графе G. Ясно, что цепь v=v₀,v₁,...,v_s является кратчайшей v-v_s-цепью в графе G для всех s=l,...,k. В частности, вершина v_k находится на расстоянии k от v.

Рассмотрим ПВШ(v)-дерево в тот момент, когда просматрива­ется вершина w, и пусть u=OTEЦ[w]. В силу предположения ин­дукции достаточно доказать, что и находится на расстоянии k от v. Если u=v_k то теорема доказана. Пусть u≠v_k. Так как ребро {v_k,w}E, и вершина w просмотрена из вершины u, то это озна­чает, что вершина и просмотрена раньше чем v_k. Следовательно, расстояние от v до и не больше, чем расстояние от v до v_k, и, зна­чит, вершина и находится на расстоянии не больше k от v. По предположению индукции алгоритм правильно определит крат­чайшую цепь до u, и, следовательно, до w.

Заметим, что пути, определяемые поиском в глубину, вообще говоря, не являются кратчайшими. Например, на рис.4.1 путь от вершины 1 до вершины 8 проходит через вершины 2,3,4,7,6 и имеет длину 6, а поиск в ширину (см.рис.4.2) определяет путь, проходящий через вершины 4,7, длиной 3.