|
|
| Строка 1: |
Строка 1: |
| '''Алгоритм Шамира (A. Shamir)''' — основанный на [[обратная нумерация|обратной нумерации]] линейный [[алгоритм]] отыскания [[Множество вершин, разрезающих контуры|''минимального разрезающего контуры множества'']] в [[сводимый управляющий граф|сводимом управляющем графе]], предложенный А. Шамиром в 1979 г. | | '''Алгоритм Шамира (A. Shamir)''' — основанный на [[обратная нумерация|обратной нумерации]] линейный [[алгоритм]] отыскания [[Множество вершин, разрезающих контуры|''минимального разрезающего контуры множества'']] в [[сводимый управляющий граф|сводимом управляющем графе]], предложенный А. Шамиром в 1979 г. |
|
| |
| Пусть заданы [[управляющий граф]] <math> G=(X,U, p_0)</math> и [[обратная нумерация]] его вершин N.
| |
|
| |
| Определим функцию ВЕРХ, которая каждой вершине <math> p \in X</math> сопоставляет число
| |
|
| |
| ВЕРХ (p) = <math> \max(0, \{N(q):q \in K(p)\}) </math>,
| |
|
| |
| где K(p) обозначает множество всех таких вершин <math> q \in X</math>, что существует путь
| |
| <math>P = (p_1 = p, p_2,..., p_{r-1}, p_r = q)</math>,
| |
| для которого справедливы следующие два условия:
| |
|
| |
| (1) <math> N(p_{i-1}) < N(p_i) \neq </math> ВЕРХ <math> (p_i) </math> для всех i, таких, что 1 < i < r,
| |
|
| |
| (2) <math> N(p_{r-1}) \geq N(p_r) </math>.
| |
|
| |
| Справедливо следующее свойство.
| |
|
| |
| ''Если существует в уграфе G вершина p, для которой ВЕРХ(p) > N(p), то G не является сводимым''.
| |
|
| |
| Это условие является достаточным условием несводимости уграфа, но не является необходимым.
| |
|
| |
| Пусть S обозначает множество всех тех вершин <math> p \in X</math>, для которых ВЕРХ(p)=N(p). Тогда, ''если для любой вершины p графа G выполняется ВЕРХ<math>(p) \leq N(p)</math>, то S является минимальным разрезающим контуры множеством''.
| |
|
| |
| Алгоритм состоит из двух частей, первая из которых осуществляет обратную нумерацию N вершин графа G, а вторая приведена ниже. Вычисляется либо минимальное разрезающее контуры множество для G, либо определяется несводимость уграфа G.
| |
|
| |
| '''функ''' РАЗРЕЗ =
| |
| 1. S : '''шкала''' = <math>(0^n)</math>;
| |
| 2. ВЕРХ : '''разметка''' = <math>\{(p,0): p\in X\}</math>;
| |
| 3. '''для''' k '''от''' n '''до''' 1 '''через''' - 1 '''цикл'''
| |
| 4. p:=<math>N^{-1}(k)</math>;
| |
| 5. '''для всех''' q '''из''' ПРЕЕМ(p) '''цикл'''
| |
| 6. '''если''' N(q)< N(p) '''то'''
| |
| 7. ВЕРХ(p): = max(N(q), ВЕРХ(p))
| |
| 8. '''иначе если''' (ВЕРХ <math>(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)'' времени.
| |
|
| |
|
| |
|
| ==Литература== | | ==Литература== |
