Доказательство леммы проведем индукцией по высоте h поддиаграмм Dv и Dw с корнями v и w, соответственно (так как Dv и Dw изоморфны, то их высоты, т.е. длины максимальных путей из корней до стоков, одинаковы).
Базис: h=1. В этом случае 0- и 1-сыновьями вершин v и w являются одинаковые стоки.
Шаг индукции. Предположим, что утверждение верно для h=k. Пусть Dv и Dw - поддиаграммы высоты h=k+1. Пусть v0 и w0 - это 0-сыновья вершин v и w, соответственно, а v1 и w1 - их 1-сыновья. Если v0=w0 и v1=w1, то в качестве v', w' подходят сами v и w. Если же для некоторого i
Из теоремы 3.1 непосредственно следует, что, применяя к произвольной УБДР правила сокращения и слияния, мы, в конце концов, получим сокращенную УБДР. Чтобы эта процедура работала эффективо, нужно применять правила в порядке "снизу-вверх". Мы опишем этот алгоритм для "естественного" порядка переменных: x1, … , xn.
Алгоритм СОКРАЩЕНИЕ-УБДР
Вход: УБДР D для функции f(x1, … , xn).
Выход: сокращенная УБДР для
1. Занумеруем множество вершин D: V = {v1, v2, …, vm}; 2. ДЛЯ i = n, n-1, …, 1 ВЫПОЛНЯТЬ 3. { 4. V(i) = { v | v помечена переменной xi }; /* Применение правила сокращения: 5. ДЛЯ КАЖДОЙ v
Пример 3.1. Рассмотрим пример применения алгоритма СОКРАЩЕНИЕ-УБДР, показанный на следующем рисунке.