Введение в схемы, автоматы и алгоритмы



             

Сокращенные УБДР - часть 3


Применение алгоритма СОКРАЩЕНИЕ-УБДР

Рис. 3.5.  Применение алгоритма СОКРАЩЕНИЕ-УБДР

На исходной УБДР слева все вершины уже занумерованы. Стрелки разделяют УБДР, получаемые после очередных итераций основного цикла в строках 2 - 19. При первом исполнении цикла i=3, V(3) = {v3}. Для вершины v3 условие в строке 6 выполнено (w= v6), поэтому применяется правило сокращения и эта вершина удаляется, а ее входы направляются в v6. При следующем исполнении цикла i=2, V(2) = {v2, v4}. После цикла в строках 5 - 10 key(v2)= {5, 6} и key(v4)= {5, 6}. После сортировки u1=v2, u2 = v4. В цикле в строках 13-18 для u2 выполнено условие в строке 14. Поэтому применяется правило слияния и вершина v4 удаляется, а ее вход передаeтся вершине v2. При третьем исполнении цикла i=1, V(1) = {v1}. Для вершины v1 условие в строке 6 выполнено (w= v2), поэтому применяется правило сокращения и эта вершина удаляется.

Оказывается, что построенная алгоритмом УБДР является единственной и минимальной для заданного порядка.

Теорема 3.2.

  1. Алгоритм СОКРАЩЕНИЕ-УБДР строит сокращенную УБДР, эквивалентную исходной УБДР D.
  2. Эта сокращенная УБДР является при данном порядке переменных единственной (с точностью до изоморфизма) и минимальной.

Доказательство первого пункта непосредственно следует из выполнения критерия теоремы 3.1, так как к результирующей диаграмме никакое правило сокращения или слияния неприменимо.

Доказательство второго пункта основано на следующем индуктивном утверждении:

Лемма 3.1.

После выполнения i-ой итерации алгоритма в полученной диаграмме для каждой подфункции f(?1, ?2, …, ?_{i-1},xi, …, xn) (?k

{0, 1} при k=1,2,…, i-1), существенно зависящей от xi, имеется ровно одна вершина - корень поддиаграммы, реализующей эту подфункцию.

Напомним, что функция f(x1, x2, …, xi, …, xn) существенно зависит от переменной xi, если существуют такие два набора значений аргументов (?1, …, ?i-1, 0, ?i+1,…, ?n) и (?1, …, ?i-1, 1, ?i+1,…, ?n), различающиеся только значением xi, на которых f принимает разные значения: f(?1, …, ?i-1, 0,?i+1, …, ?n)

f(?1, …, ?i-1, 1,?i+1, …, ?n) .

Доказательство этой леммы и вывод из нее утверждения 2 теоремы 3.2 оставляем в качестве задач 3.2 и 3.3.




Содержание  Назад  Вперед