6.18. Переключательные сети (схемы)

Рассмотрим граф без петель каждому ребру которого поставлена в соответствие переменная принимающая только значения или 1. Такой граф может считаться математической моделью множества взаимосвязанных физических устройств, например ключей, каждый из которых может быть в любом из двух состояний: включенном или выключенном Пусть две различные фиксированные вершины Исходный граф вместе с переменными называется переключательной сетью (схемой), и считаются ее конечными точками (терминалами).

Если в сети существует ребер (т. е. ключей) и есть некоторая комбинация значений переменных, то рассматриваемая сеть будет замкнутой относительно X тогда и только тогда, когда множество ребер, для которых образует элементарную цепь,

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

Рис. 6.49.

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

Переключательная функция данной переключательной сети ключами определяется на возможных значениях X следующим образом:

До сих пор мы неявно предполагали, что не зависит от при т. е. что все ключей управляются независимо друг от друга. Если это не так, то не все значений X являются допустимыми. Предположим, что в предыдущем примере

Тогда цепь, определяемая индексами (2, 6, 5), не может быть замкнутой, так как не могут быть одновременно равны 1. Аналогично цепь (1, 3, 7) замкнута всякий раз, когда

так как в этом случае мы обязательно имеем

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

переключательная сеть, реализующая заданную переключательную функцию от независимых переменных

Любая переключательная функция может быть реализована достаточно большой сетью, каждая переменная которой равна одной из независимых переключательных переменных или ее дополнению. Например, если для следующих значений X:

то сеть рис. 6.50, очевидно, реализует заданную переключательную функцию. К сожалению, высокая степень избыточности, возникающая при таком способе построения сети, как правило, недопустима.

Рис. 6.50.

Естественно стремиться использовать наименьшее количество ключей (в лучшем случае В предыдущем примере, при существуют только три различных представляющих интерес конфигурации, которые показаны на рис. 6.51,

Рис. 6.51.

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

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

сравнительно небольшом числе ключей. Например, в работе [64] для решения этой задачи используются свойства фундаментального цикла и матриц разрезов, рассмотренные в главе 5. Показано, что задача реализуемости переключательной функции связана с задачей реализуемости матрицы циклов соответствующего графа с помощью заданной матрицы.