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