Дискретно-непрерывная математика (стр. 80 )

Рис. 5.43

Подстановка дает

т. е. сеть не может быть упрощена.

Вернемся теперь к линейным системам, в которых все f являются линейными функциями аргументов х. Предположим, что сигнал, полученный в любой верши­не, есть сумма произведений коэффициентов усиления дуг, заканчивающихся в данной вершине, на веса их начальных вершин. Таким образом, для рис. 5.44,а мы имеем x3=c1xI+c2x2, а для рис. 5.44, b х3=с2х2, х2= c1xI и, следовательно,

x3= c1 с2xI.

Рис. 5.44.

Таким образом, когда дуги образуют последовательность, их коэффициенты усиле­ния перемножаются, а сами дуги могут быть заменены одной дугой (в нашем случае между v1 и v3) с коэффи­циентом усиления с1с2. В случае параллельных дуг меж­ду двумя вершинами их коэффициенты усиления скла­дываются, а сами дуги можно заменить одной дугой с суммарным коэффициентом усиления.

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

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

Пусть v — вершина с весом х, имеющая петлю с ко­эффициентом усиления С. Так как общий сигнал, вхо­дящий в v, должен быть равен х, а петля дает входной сигнал сх, сигнал по другим дугам, входящим в v, дол­жен быть равен (1—c)x. В этом случае действие петли можно заменить действием дуги с коэффициентом уси­ления 1/(1—с). Так, например, вес вершины v3 в сети, изображенной на рис. 5.45, записывается как

Рис. 5.45.

Аналогичные преобразования могут быть выполнены при наличии нескольких петель.

Упражнение 24. Показать, что вес вершины v4 в сети на рис. 5.46 определяется выражением

Рис. 5.46.

Для того чтобы рассмотренные операции на сети со­ответствовали решению системы совместных линейных уравнений, можно соста­вить уравнения потока в сети, как показано ниже, и выполнить операции на сети так, чтобы они соответ­ствовали операциям, используемым при решении урав­нений. Рассмотрим сеть рис. 5.47 с соответствующими ей уравнениями

x3=4x1—х4, х2= x1, x4= 6x3—2х2,

где x1 считается заданным.

Рис. 5.47.

Если нам требуется, напри­мер, определить коэффициент усиления в x3, то путем исключения получим x3=6/7 x1. С другой стороны, при­ведение можно осуществить также с помощью конструи­рования остаточного графа, показанного на рис. 5.48, используя v3 в качестве вершины, определяющей индекс.

Рис. 5.48

Так как v3 желательно иметь в качестве стока, добавим фиктивную вершину v′3 с единичным коэффициентом усиления по дуге v3 v′3. При этом обе вершины будут иметь вес х3. Две параллельные дуги

v1 v3 образуют новую дугу с коэффициентом усиления 6. После замены петли с коэффициентом усиления 6 на дугу с коэффициентом усиления 1/[1 — (—6)] и объединения результатов для получения коэффициента в v3 получим x3=6/7x1. В действительности можно установить соответствие между последовательными этапами процесса исключе­ния при решении системы уравнений и процесса приве­дения графа. Например, если х2 всюду заменяется на x1, то исходный граф приводится к другому графу, в кото­ром коэффициенты усиления дуг, проходящих через х2, умножаются на единичный коэффициент усиления дуги v1v2 и т. д. Таким образом, указанное соответствие дей­ствительно имеет место.

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

Рассмотрим граф без петель G=(V, E), каждому ребру ei которого поставлена в соответствие переменная хi, принимающая только значения 0 или 1. Такой граф может считаться математической моделью множества взаимосвязанных физических устройств, например клю­чей, каждый из которых может быть в любом из двух состояний: включенном (хi= 1) или выключенном (хi= 0). Пусть v1 и v2 — две различные фиксированные вершины G. Исходный граф вместе с переменными {xi} называется переключательной сетью (схемой), a v1 и v2 считаются ее конечными точками (терминалами).

Если в сети существует п ребер (т. е. ключей) и X= = (х1, х2,...,хп) есть некоторая комбинация значений переменных, то рассматриваемая сеть будет замкнутой относительно X тогда и только тогда, когда множество ребер, для которых хi=1, образует элементарную цепь, соединяющую v1 и v2. В противном случае говорят, что сеть разомкнута относительно X. (Другими словами, сеть замкнута относительнно X тогда и только тогда, когда v1 и v2 лежат в одной и той же компоненте подграфа, определенного ребрами, для которых хi=1.)

Рассмотрим, например, переключательную сеть рис. 5.49.

Pис. 5.49

Множество пе­ременных переключения, соответствующих элемен­тарным цепям, соединя­ ющим v1 и v2, есть ((1. 4, 5), (1,4,6,7), (1,3,6,5), (1, 3, 7), (2, 7), (2, 6, 5), (2, 3, 4, 5)), где цифры совпада­ют с индексами переменных. Векторы X= = (х1, х2,...,х7), для которых сеть замкнута, являются в точности теми векторами, которые имеют 1 в каждой позиции, соответ­ствующей одной из элементарных цепей, и произвольные значения в других позициях.

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

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

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

x1 = x3 =1

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

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

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

то сеть рис. 5.50, очевидно, реализует заданную пере­ключательную функцию.

Рис. 5.50.

К сожалению, высокая степень избыточности, возникающая при таком способе построе­ния сети, как правило, недопустима. Естественно стре­миться использовать наименьшее количество ключей (в лучшем случае т). В предыдущем примере, при т=3, существуют только три различных представляющих ин­терес конфигурации, которые показаны на рис. 5.51.

Рис. 5.51.

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

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

5.19. Объединение электростанций в энергосистему