926
правок
KVN (обсуждение | вклад) (Новая страница: «'''Алгоритм Шамира (A. Shamir)''' — основанный на обратной нумерации лине…») |
KVN (обсуждение | вклад) Нет описания правки |
||
Строка 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)'' времени. | |||
==Литература== | ==Литература== |