6. Другие задачи распределения

Рассмотрим теперь задачу распределения нагрузок в параллельно-последовательных схемах. Докажем следующую теорему.

Теорема 9. Любая функция может быть реализована параллельно-последовательной схемой с распределением

в терминах переключающих элементов.

Докажем это утверждение по индукции. Оно верно для так как любая функция трех переменных может быть представлена следующим образом:

и каждая из функций может быть реализована с одним переключающим элементом переменной и одним — переменной Таким образом, может быть реализована с распределением 1, 2, 2. Теперь, предполагая, что теорема верна для имеем

и

Простое применение леммы дает нужный результат.

Возможны также многие другие распределения, кроме устанавливаемых теоремой 9, но еще не найдены простые критерии для их описания. Ничего нельзя сказать о любом распределении

(во всяком случае, на основании нашего анализа), так как, например, последовательность

не может быть разложена в две последовательности

и

Однако, по-видимому, допустимо почти равномерное распределение.

В качестве последнего примера распределения нагрузок рассмотрим случай схемы, состоящей из нескольких деревьев от одних и тех же переменных. Большое число таких случаев будет рассмотрено позднее. Справедливость следующего утверждения достаточно очевидна из того, что уже доказано.

Теорема 10. Можно построить различных деревьев от одних и тех же переменных со следующим распределением.

Интересно отметить, что при этих условиях исключается случай единицы при Можно уравнять нагрузку на всех переменных, а не только на из них.