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

(3) — (—2) + (—4) — (1)=0.

Рис. 5.36.

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

Приведем еще одну формулировку циклического правила. Если v1 — фискироваииая вершина, a vi — любая другая вершина, отличная от v1 то алгебраическая сумма напряжений по любой цепи, ориентированной от v1 к vi, не зависит от выбранной цепи. (Здесь предпола­гается, что граф связен и, следовательно, существует, по крайней мере, одна такая цепь.) Используя эту фор­мулировку для каждой вершины vj, мы можем опреде­лить числа Sj следующим образом. Назначим S1 произ­вольно. Полагаем Sj=S1—К, где К есть алгебраическая сумма напряжений по любой цепи, направленной от v1 к vj. Полагая, например, S1 = 3 в предыдущем примере, мы получим значения Sj, показанные на рис. 5.37.

Рис. 5.37.

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

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

Применяя к вершине vi правило вершин, получим

где аij =+1(—1), если i-я вершина положительно (от­рицательно) инцидентна j-й дуге. аij равно нулю в случае отсутствия инцидентности. Другими словами, векторы

Ai= (аi1, …, аim) и Х'=(х1 ,.., хт)

являются ортогональными. Заметим, что Аi есть строка А матрицы инциденций графа. Так как пространство, на­тянутое на строки А, совпадает с пространством, натя­нутым на строки матрицы разрезов К, X' есть линейная комбинация векторов циклов (строк матрицы циклов С). Действительно, А (или К) и С определяют ортого­нальные подпространства, которые вместе образуют пространство размерности т.

и можно записать в виде

при выборе хорд стягивающего дерева в качестве первых т—п+1 столбцов. Здесь I — единичные матрицы. Раз­бивая таким же способом вектор токовых переменных, получим

где Хa и Хь относятся к хордам и ветвям дерева соот­ветственно. Правило вершин означает, что

Следовательно,

(5.1)

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

(5.2)

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

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

где Ωx есть диагональная m×m-матрица, i-й диагональ­ный элемент которой является либо константой, либо дифференциальным или интегральным оператором, a Yg — вектор-столбец, элементы которого равны нулю для позиций, соответствующих пассивным элементам и функциям f(t) для позиций, соответствующих источ­никам. (Соответствующие диагональные элементы Ωx равны 0.) Если токи выражаются как явные функции напряжения, то получим

Предыдущее выражение может быть переписано в виде

Умножение обеих частей уравнения на дает

(5.1)'

где неизвестными являются только напряжения на хор­дах. Последнее выражение может быть переписано:

и, далее,

(5.2)′

где неизвестными являются только токи в ветвях.

Уравнения (5.1) и (5.2) соответствуют формулиров­кам задачи для циклов и вершин (или узлов) соответ­ственно. В случае, когда полученная система урав­нений может быть решена известными математическими методами, оставшиеся неизвестными токи и напряже­ния легко находятся из приведенных выше соотношений. В частности, заметим, что К' и ′ могут быть получены при визуальном анализе графа, после выбора дерева. В случае, если некоторые элементы системы имеют более двух полюсов или если рассматриваются элемен­ты сопряжения, которые служат для согласования раз­личных видов энергии в одной и той же системе, то матрица, характеризующая основные уравнения, имеет более сложную структуру и решение результирующей системы уравнений получается более сложно. Тем не ме­нее, роль графа, представляющего систему, остается по существу той же самой.

5.16. Сети связи

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

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

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

Рис. 5.38.

Матрица вершин этого графа имеет вид

Упражнение 22. Используя матрицу вершии, ответьте на сле­дующие вопросы.

а) Со сколькими пунктами непосредственно связан каждый от­дельный пункт системы?

b) Сколько пунктов непосредственно связано с каждым отдель­ным пунктом системы?

c) Сколькими способами каждый пункт связан с любым другим через один промежуточный пункт?

d) Может ли каждый пункт быть связан непосредственно или косвенно с каждым другим пунктом?

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

Замечание. На сильно связных графах определя­ется мера, называемая индексом централь­ности. Она характеризует степень разброса вершин гра­фа. Если мы определим матрицу отклонений, элементы которой тij задают минимальную длину пути от верши­ны vi до вершины vj и вычислим - то индекс центральности вершины vi есть

Глобальный индекс центральности графа получается суммированием по всем i.

Упражнение 23. Вычислите индексы центральности и глобаль­ный индекс центральности для нескольких графов. Сравните с поня­тием радиуса.

Синтез сети связи

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