Когда порядок переменных зафиксирован, то достаточно просто можно по произвольной УБДР для функции построить минимальную УБДР, реализующую данную функцию.
Определение 3.3. УБДР называется сокращенной, если
Смысл этого определения понятен: если из некоторой вершины v оба ребра ведут в одну вершину, то такая вершина v не нужна, а если имеются две вершины с одинаковыми поддиаграммами, то их можно слить. Определим два типа эквивалентных преобразований УБДР.
Правило сокращения: если 0-сын и 1-сын вершины v совпадают и равны w, то удалить v, перенаправив все входящие в нее ребра в вершину w.
Правило слияния: если вершины v и w помечены одной переменной и имеют одинаковых 0-сыновей и 1-сыновей, то удалить вершину v, перенаправив все входящие в нее ребра в вершину w.
На следующем рисунке показаны преобразования по этим правилам.
Следующая простая теорема показывает, что применимость этих двух правил является критерием несокращаемости УБДР.
Теорема 3.1.
УБДР D является сокращенной тогда и только тогда, когда к ней не применимо ни правило слияния, ни правило сокращения.
Доказательство.
? Пусть к УБДР D нельзя применить правило сокращения. Тогда в ней нет вершин с совпадающими 0- и 1-сыновьями и выполнено условие (1). Пусть к УБДР D нельзя применить правило слияния. Тогда из следующей леммы можно заключить, что в D нет пары вершин, поддиаграммы которых являются изоморфными, и следовательно, выполнено условие (2).
Лемма 3.2. Если в D есть такая пара вершин u и v, для которых поддиаграммы с корнями v и w являются изоморфными, то в D имеется и пара вершин v', w' с попарно одинаковыми 0- и 1-сыновьями и, следовательно, к D применимо правило слияния.