Алгоритм Шамира

Алгоритм Шамира (A. Shamir) — основанный на обратной нумерации линейный алгоритм отыскания минимального разрезающего контуры множества в сводимом управляющем графе, предложенный А. Шамиром в 1979 г.

Пусть заданы управляющий граф [math]\displaystyle{ G=(X,U, p_0) }[/math] и обратная нумерация его вершин N.

Определим функцию ВЕРХ, которая каждой вершине [math]\displaystyle{ p \in X }[/math] сопоставляет число

ВЕРХ (p) = [math]\displaystyle{ \max(0, \{N(q):q \in K(p)\}) }[/math],

где K(p) обозначает множество всех таких вершин [math]\displaystyle{ q \in X }[/math], что существует путь [math]\displaystyle{ P = (p_1 = p, p_2,..., p_{r-1}, p_r = q) }[/math], для которого справедливы следующие два условия:

(1) [math]\displaystyle{ N(p_{i-1}) \lt N(p_i) \neq }[/math] ВЕРХ [math]\displaystyle{ (p_i) }[/math] для всех i, таких, что 1 < i < r,

(2) [math]\displaystyle{ N(p_{r-1}) \geq N(p_r) }[/math].

Справедливо следующее свойство.

Если существует в уграфе G вершина p, для которой ВЕРХ(p) > N(p), то G не является сводимым.

Это условие является достаточным условием несводимости уграфа, но не является необходимым.

Пусть S обозначает множество всех тех вершин [math]\displaystyle{ p \in X }[/math], для которых ВЕРХ(p)=N(p). Тогда, если для любой вершины p графа G выполняется ВЕРХ[math]\displaystyle{ (p) \leq N(p) }[/math], то S является минимальным разрезающим контуры множеством.

Алгоритм состоит из двух частей, первая из которых осуществляет обратную нумерацию N вершин графа G, а вторая приведена ниже. Вычисляется либо минимальное разрезающее контуры множество для G, либо определяется несводимость уграфа G.

функ РАЗРЕЗ =
1.  S : шкала = [math]\displaystyle{ (0^n) }[/math];
2.  ВЕРХ : разметка = [math]\displaystyle{ \{(p,0): p\in X\} }[/math];
3.  для k от n до 1 через - 1 цикл 
4.     p:=[math]\displaystyle{ N^{-1}(k) }[/math]; 
5.     для всех q из ПРЕЕМ(p) цикл 
6.        если N(q)< N(p) то 
7.           ВЕРХ(p): = max(N(q), ВЕРХ(p)) 
8.        иначе если (ВЕРХ [math]\displaystyle{ (p)\neq N(q))\wedge(S[q] = 0 }[/math]) то 
9.                   ВЕРХ(p):= max(ВЕРХ(p), ВЕРХ(q)) 
                все 
          все 
       все; 
10.    если ВЕРХ(p)=N(p) то A[p]:=1 
11.    иначе если ВЕРХ(p)>N(p) то 
12.             возврат G — несводимый уграф 
             все 
       все 
    все; 
13. возврат S 
все 

Нетрудно проверить, что вторая часть алгоритма обрабатывает каждую дугу графа (операторы 5-9) только раз, и таким образом, O(m) — ее временная сложность, где m — число дуг уграфа G. Поскольку обратная нумерация N графа G может быть осуществлена за время O(m) , алгоритм для нахождения минимального разрезающего контуры множества для сводимого уграфа G требует O(m) времени.

Литература

• Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.