Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

12.5. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Гуиллемина)

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

Теперь обсудим алгоритм, предложенный который использует подход Гуиллемина. Последний, как отмечалось выше, состоит из следующих основных этапов:

1. Получить полюсную конфигурацию дерева Т -полюсной цепи N, реализующей матрицу

2. Получить из дерева Т и матрицы Y матрицу проводимостей короткого замыкания Y я-полюсной цепи, построенной на цепи N, которая имеет полюсную конфигурацию в виде звезды, вершина которой является отрицательно обозначенным зажимом для всех полюсов (разд. 12.2.4).

3. Если матрица Y является гипердоминантной, то можно легко получить искомую цепь (разд. 12.2.2), в противном случае матрица является нереализуемой.

12.5.1. Выделение концевого полюса

Первым важным шагом алгоритма для реализации матриц -узловой резистивной -полюсной цепи является выделение концевого полюса полюсной конфигурации искомой цепи. Легко видеть, что, применяя к матрице алгоритм, описанный в разд. 12.4.2, можно определить такой концевой полюс. В целях полноты приведем далее шаги этого алгоритма.

Шаг 1. Рассмотреть произвольную строку i матрицы Y. Пусть минимум абсолютных величин — элементов этой строки, и пусть S является множеством столбцов, в котором элемент в строке i равен Если 5 содержит только один элемент, то этот элемент соответствует концевому полюсу. В противном случае пусть

Шаг 2. Рассмотреть произвольную другую строку матрицы У, где Если для некоторых содержащихся в S, то удалить из 5. Удалить все такие для строки

Шаг 3. Повторить шаг 2 с некоторой другой строкой k, где k не содержится в сокращенном множестве S. Если повторное применение этого шага не приводит к множеству S, состоящему только из одного элемента, то удалить произвольно любой элемент из множества S на данном этапе и повторить шаги 2 и 3. Окончательно множество S будет содержать только один элемент, который можно идентифицировать как концевой полюс.

12.5.2. Реализация Y-матрицы с ненулевыми элементами

В этом разделе мы рассмотрим реализацию К-матрицы, которые не содержат нулевых элементов. Общий случай, где допускаются и нулевые элементы, рассматривается в работе [12.4]. Цепь N, реализующая К-матрицу с ненулевыми элементами, характеризуется тем, что существует хорда, стягивающая каждую пару полюсов цепи N. Если определить путь в Г от одной конечной вершины к другой, как максимальный, то для каждого такого максимального пути существует хорда в цепи N. Далее, проводимость этой хорды равна величине передаточной проводимости между двумя концевыми

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

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

Пусть является минимальной из абсолютных величин элементов в строке матрицы Y, и пусть передаточная проводимость между другими элементами (если они есть) будет равна . Полюс может быть, а может и не быть концевым полюсом. В случае когда он не является концевым, полюса -множества (разд. 12.4), которое не содержит полюс i и которое имеет в качестве ведущего полюса, образуют линейное поддерево дерева Т и существует только одна хорда в цепи N, которая стягивает i и полюса -множества. Следовательно, независимо от того, является или нет концевым полюсом, в дереве Т существует только один максимальный путь, который содержит как i, так и Пусть положительно (отрицательно) для любого k; если знаки совпадают (различаются), то k находится на максимальном пути, соединяющем (теорема 12.2). Аналогично могут быть определены все полюса, которые содержатся в этом максимальном пути. Пусть этот путь будет где порядок полюсов будет определен позже. Очевидно, что ни один из полюсов в скобках в данном представлении не может быть концевым полюсом в другом максимальном пути, содержащем г. С тем чтобы оставить эти полюса вне рассмотрения, в непосредственно следующих шагах элементы в строке матрицы Y в столбцах обводим кружками. Выберем другой элемент имеющий минимальное по абсолютной величине значение среди не отмеченных кружками элементов в строке, и получим другой максимальный путь, т. е. определим все элементы для которых — положительны. Пусть этим путем является . Теперь обводим кружками элементы Процедуру повторяем до тех пор, пока все элементы матрицы Y в строке, за исключением не будут обведены кружками. Отметим, что каждый из полюсов находится

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

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

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

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

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

Проиллюстрируем приведенную выше процедуру определением конфигурации полюсного дерева, заданного матрицей проводимостей Y, приведенной ниже:

1. Рассматривая первую строку, определяем, что полюс 3 является концевым.

2. В строке 3 минимальным по величине является элемент в 7 столбце, причем отрицательно. Просматривая столбцы 3 и 7 замечаем, что для и 8 только у и 3 и имеют противоположные знаки.

Таким образом 3, (7, 8) является максимальным путем. Отметим кружками элементы в столбцах 7 и 8 третьей строки, которая выглядит теперь следующим образом:

3. Среди неотмеченных элементов в строке 3 элемент имеет минимальное значение и положителен. Просматривая столбцы 3 и 4, замечаем, что для элементы имеют одинаковый знак, является другим максимальным путем. Обводим теперь элементы Аналогично получаем другие максимальные пути 3, (2, 1, 5, 8, 10); (3, 6); и .

4. Рассмотрим путь 3, (2, 1, 5, 8, 10). Располагая полюса в скобках в убывающем порядке значений их передаточных проводимостей по отношению к полюсу 3, получим 3, 8, 1, 5, (2, 10). Рассматривая 5-ю строку матрицы Y, находим, что Таким образом, 3, 8, 1, 5, 10, 2 является упорядоченным максимальным путем.

5. Поскольку другие пути имеют общие ветви с этим путем, то их также легко упорядочить. Другими упорядоченными максимальными путями являются 3, 8, 7; 3, 8, 1, 5, 4; и 3, 8, 1, 9.

6. Теперь легко определить полюсное дерево Т (рис. 12.13, а).

7. Ориентацию любого из полюсов, например полюса 1, можно выбрать произвольно. Ориентации остальных полюсов получают,

Рис. 12.13. а — дерево Т; б — дерево

используя теорему 12.1. Результирующая ориентация полюсов показана на рис. 12.13, а.

8. Пусть звезда Т, имеющая то же множество вершин, что и дерево Т, выбрана такой, как показано на рис. 12.13, б.

Матрица К, связывающая векторы полюсных напряжений приведена ниже. (Отметим, что )

Матрица проводимостей короткого замыкания Y по отношению к Т определяется выражением

Матрица У является гииердоминантной. Проводимости -полюсной цепи, реализующей матрицу Y, можно вычислить из Y, и они определяются следующими соотношениями:

<< Предыдущий параграф Следующий параграф >>
Оглавление