Введение в схемы, автоматы и алгоритмы
Сокращенные УБДР - часть 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.
- Алгоритм СОКРАЩЕНИЕ-УБДР строит сокращенную УБДР, эквивалентную исходной УБДР D.
- Эта сокращенная УБДР является при данном порядке переменных единственной (с точностью до изоморфизма) и минимальной.
Доказательство первого пункта непосредственно следует из выполнения критерия теоремы 3.1, так как к результирующей диаграмме никакое правило сокращения или слияния неприменимо.
Доказательство второго пункта основано на следующем индуктивном утверждении:
Лемма 3.1.
После выполнения i-ой итерации алгоритма в полученной диаграмме для каждой подфункции f(?1, ?2, …, ?_{i-1},xi, …, xn) (?k
Напомним, что функция 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)
Доказательство этой леммы и вывод из нее утверждения 2 теоремы 3.2 оставляем в качестве задач 3.2 и 3.3.