Общая формула для передачи направленного (сигнального) графа

В 1956 г. Мэзон предложил общую формулу для определения передачи графа. Эта формула является основной при расчете графов. Прежде чем перейти к ней, познакомимся с некоторыми новыми понятиями.

Прямой путь Р — это путь вдоль стрелок от истока к стоку, при прохождении которого ни один из узлов не встречается более одного раза.

Передача прямого пути равна произведению передач ветвей этого пути.

Между истоком и стоком графа может быть несколько прямых путей. Например, для схемы на рис. П1.5 между истоком (узел 1) и стоком (узел 2) есть два прямых пути. Первый прямой путь — путь по ветвям с передачами а и Ъ. Передача этого пути Р_г = аЪ. Второй прямой путь — путь по ветвям с передачами с, е, Ъ, его передача Р₂ = сеЪ.

Рис. т.5

Ни один из других возможных путей от узла 1 к узлу 2 в этом графе не относится к категории прямых. Например, путь через ветви с,/, g, е, b не является прямым, так как на этом пути узел 3 встречается дважды. В обшей формуле необходимо учитывать также передачи петель обратной связи.

Петля обратной связи представляет собой замкнутый путь, вдоль которого (по кругу) каждый узел может встретиться только один раз.

Передачу петли обратной связи часто обозначают буквой Т с индексом. Передача петли обратной связи равна произведению передач ветвей, образующих эту петлю. В графе на рис. П1.5 три петли обратной связи: первая — с T₁ = h, вторая — с Т₂ =fg, третья — с Т₃ = ed.

Общая формула для определения передачи графа G записывается следующим образом^[1]:

где Р_к — передача к-го прямого пути от истока к стоку; п — число прямых путей.

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

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

Пример 171

Применить формулу (П1.1) к графу на рис. П1.5.

Решение. Для первого прямого пути с передачей Р-ab определитель равен единице минус сумма передач петель обратной связи, взятых поодиночке и не касающихся этого прямого пути Т_г + Т₂, плюс попарное произведение передач петель обратной связи, не касающихся друг друга и выбранного прямого пути.

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

Для второго прямого пути.

Знаменатель, А = 1 — (Т_г + Т₂ + Г₃) + Т_ХТ3; Т₃ — ed. В выражение для, А вошло произведение Т_х и Г₃ двух соприкасающихся петель графа. Таким образом,

• [1] Вывод формулы см.: Бессонов Л. А. ТОЭ. М.: Высшая школа, 1978.