748
правок
Изменения
→Задача о минимизации контактной схемы
{{Определение
|definition =
'''Дерево конъюнктов для <tex>n</tex> переменных''' {{---}} двоичное ориентированное дерево глубиной <tex>n</tex>, такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной <tex>x_k (k<=\leqslant n)</tex>, а правое помечено символом отрицания переменной <tex>x_k</tex>.
}}
[[Файл:tree_for_two.png | 250px | thumb | Дерево конъюнктов для 2-х переменных]]
Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной <tex>v</tex> контактами, над которыми написана <tex>1</tex>. От этого в схему добавится не более, чем <tex>2^n</tex> ребер и тогда сложность останется <tex>O(2^n)</tex>.
