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

Блочную группу графа определим следующим образом:

2Ап = = [bn-1an]

где Ап-1 — блочная группа графа без последнего модуля Г(п).

Поскольку таблица порядков

P=

не содернчит идентичных столбцов, то

Число Тп деревьев графа Г равно

где — число деревьев графа без последнего модуля Г(п), замкнутого со стороны выхода; Т(п)— число деревьев последнего модуля Г(п); Тп-1 — число деревьев графа без последнего модуля Г(п); — число деревьев модуля Г(п), замкнутого на входе.

Предполагая структуру всех модуля (подграфов) одинаковой, приведенная формула примет вид

(а)

где Т — число деревьев каждого модуля, Та — число деревьев каждого модуля, замкнутого на входе (рис. 8.17, б).

Аналогично получим выражение числа деревьев графа, замкну­того на выходе:

(б)

а также выражение для числа деревьев графа Г с замкнутым входом

(в)

где Т b — число деревьев каждого модуля, замкнутого на выходе; Таb — число деревьев каждого модуля, замкнутого на входе и на выходе (рис. 8.17, б).

Раскрывая рекуррентные формулы (а) — (в), получим выраже­ние для числа деревьев Тп, а также 2-деревьев и цеп­ного графа Г, состоящего из п изоморфных подграфов

где п — k≥0; Т — число деревьев одного подграфа; Та — число 2-деревьев подграфа относительно пути а (или число деревьев подграфа с замкнутым путем а); Тb — число 2-деревьев подгра­фа относительно пути b (или число деревьев подграфа с замкну­тым путем b); Таb — число 3-деревьев подграфа относительно путей а и b (или число деревьев подграфа с замкнутыми путями а и b); — число 2-деревьев графа Г относительно пути bп (или число деревьев графа с замкнутым выходом); — число 2-деревьев графа Г относительно пути a1(или число деревьев графа, замкнутого на входе).

Пусть, например, подграфы графа Г имеют Т-образный вид, тогда Т = 1, Та = 2, Тb = 2, Т аb = 3. Следовательно, для п = 2, 3, 4, 5 имеем

Т 2 = 2 + 2=4,

= 22 + 3 = 7,

Т 3 = 22 + 2•2 + 7 = 15,

= 23 + 3(2 + 4) = 26,

T4 = 23 + 22•2+2•7 + 26 = 56,

= 24 + 3(22 + 2•4 + 15) = 97,

Т 5 = 24 + 23•2 + 22•7 + 2•26 + 97 = 209,

= 25 + 3 (23 + 22 • 4 + 2 • 15 + 56) = 362.

Из приведенных примеров расчетов числа деревьев графа очевидны преимущества алгебры полных блочных групп. Также очевидно, что при расчете блочных групп графов, содержащих большое число вершин и ребер, деление графов на подграфы и применение методов расчета блочных групп модуль-графов значительно упрощают расчеты. При большом коли­честве деревьев графа (т. е. столбцов блочной группы) оты­скание идентичных столбцов — очень трудоемкая задача (это операция сортировки на ЭВМ), которая в значительной степени облегчается при расчете полных блочных групп модуль - графов.

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

Рассмотрим методы анализа структур средствами блочных групп и модуль-графами на примерах структур электрическим цепей.

Анализ пассивных и активных структур цепей можно проводить классическим мето­дом с помощью определителей и матриц, с помощью графов сигна­лов или сетевых графов (метод деревьев) или с использованием унистора. В данном разделе анализ пассивных активных структур цепей будет производиться методом, который использует средства блочных групп и модуль-графов. Топологические методы анализа, а именно метод графов сигна­лов и метод деревьев, значительно облегчают анализ электрических цепей. Однако их существенный недостаток заключается в невоз­можности определения алгоритма расчетов чисто алгебраическим путем. Кроме того, к недостаткам этих методов следует отнести многозначность способов решения данной задачи; особенно при использовании графов сигналов. В зависимости от выбора базис­ных узлов конечный результат в случае метода графов сигналов может быть представлен в совершенно различных формах. Поэто­му возникают большие трудности для программирования на ЭЦВМ.

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

9.1. Анализ структур, представленных пассивными цепями

9.1.1. Анализ пассивного четырехполюсника

Рассмотри структуру цепи в виде четырехполюсника (рис. 1).

Рис. 1. Структура цепи в виде четырехполюсника.

Для него можно написать следующие характеристические функции:

(1)

где Ки и Kі называются передаточными функциями (коэффи­циентами передачи) напряжения и тока; Z1, Zвх и Zвых — первичным, входным и выходным импедансами; Гs — рабочим зату­ханием.

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

(2)

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

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

Передаточную функцию тока Кi для четырехполюсника можно представить в виде

(3)

где I2v — токи контуров четырехполюсника, содержащих одина­ково ориентированные ребра α=1 и β=2; I2v — токи контуров четырехполюсника, содержащих противоположно ориентирован­ные ребра α=1 и β=2.

Так как столбцы блочной группы А определяют все дополнения деревьев цепи, то столбцы блочных групп дА/дα и дА/дβ определяют те ветви цепи, исключение которых преобразует ее в один контур. Поэтому одинаковые столбцы блочных групп дА/дα и дА/дβ определяют все ветви, исключение которых приводит к образованию контуров, содер­жащих ребра α и β, т. е. контуров с токами I2v и I2μ. Кроме того, на основании уравнений контурных токов имеем

(4)

Отсюда следует, что

(5)

где ∆11 и ∆12 — соответствующие миноры определителя урав­нений (4).

Минор ∆11 представляет собой сумму всех величин дополне­ний деревьев цепи с исключенной ветвью α = 1. Поэтому

(6)

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

Минор ∆11 есть линейная комбинация с коэффициентами +1 и

—1 величин таких дополнений деревьев цепи с исключенной ветвью α или β, при удалении которых Kі ≠ 0. Поэтому