Алгоритм Шамира: различия между версиями
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)'' времени. | |||
==Литература== | ==Литература== |
Текущая версия от 11:05, 21 сентября 2019
Алгоритм Шамира (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.