Алгоритм Шамира: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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)'' времени.


==Литература==
==Литература==

Текущая версия от 14:35, 9 октября 2019

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

Литература

  • Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.
Источник — http://pco.iis.nsk.su/grapp/index.php?title=Алгоритм_Шамира&oldid=10973