- •Часть 1
- •Часть 1
- •Введение
- •1. Основные понятия теории графов
- •Задачи теории графов
- •1.2. Основные определения
- •1.3. Степени вершин графа
- •1.4. Изоморфизм графов
- •2. Представление графов в эвм и операции над ними
- •2.1. Матричные способы задания графов
- •2.2. Список ребер (луг) и структура смежности графа
- •2.3. Части графов
- •2.4. Основные операции над графами
- •3. Маршруты в графах
- •3.1. Понятие маршрута
- •Маршруты в неориентированных графах
- •Маршруты в ориентированных графах
- •3.2. Связность в графах.
- •В примере 3 граф имеет две сильно связных компоненты.
- •3.3. Связность и матрица смежности графа
- •3.4. Матрица взаимодостижимости
- •4. Деревья
- •4.1. Свободные деревья
- •4.2. Ориентированные, упорядоченные и бинарные деревья
- •Эквивалентное определение ориентированного дерева
- •5. Эйлеровы и гамильтоновы графы.
- •5.1. Эйлеровы графы.
- •5. 2. Алгоритм построения эйлерова цикла в эйлеровом графе
- •5.3. Гамильтоновы графы
- •5.4. Оценки числа эйлеровых и гамильтоновых графов
- •6. Фундаментальные циклы и разрезы
- •6.1. Фундаментальные циклы
- •6.2. Разрезы
- •7. Связь теории графов с бинарными отношениями и векторными пространствами
- •7.1. Отношения на множествах и графы
- •7.2. Векторные пространства, связанные с графами
- •8. Планарность и раскраска графов
- •8.1. Планарные графы
- •8.2. Раскраска графов
- •8.3. Алгоритм последовательной раскраски
- •9. Покрытия и независимость
- •9.1. Покрывающие множества вершин и ребер
- •9.2. Независимые множества вершин и ребер
- •9.3. Доминирующие множества
- •10. Кратчайшие маршруты в графах
- •10.1. Расстояния в графах
- •10.2. Алгоритм Форда-Беллмана
- •11. Задача коммивояжера
- •11.1. Постановка задачи
- •11.2. Обходы вершин графа по глубине и ширине
- •11.3. Решение задачи коммивояжера
- •12. Потоки в сетях
- •12.1. Основные определения
- •12.2. Теорема Форда и Фалкерсона
- •12.3. Алгоритм построения максимального потока
- •13. Сетевое планирование и управление
- •13.1. Элементы сетевого графика
- •13.2. Временные параметры сетевого графика
- •13.3. Распределение ограниченных ресурсов
- •14. Анализ технических систем (на примере электрической цепи)
- •14.1 Закон Кирхгофа
- •14.2. Основные уравнения
- •15. Сигнальные графы
- •15.1. Общие представления о сигнальных графах
- •15.2. Преобразования сигнальных графов
- •15.3. Формула Мэзона
- •16. Переключательные сети (схемы)
- •17. Математические машины и цепи маркова
- •Библиографический список
- •Оглавление
- •Часть 1
- •394026 Воронеж, Московский просп., 14
14. Анализ технических систем (на примере электрической цепи)
14.1 Закон Кирхгофа
В данной теме рассматривается поведение технических систем. Исходной информацией для анализа любой системы является:
1) поведение ее составных частей и элементов
2) способы связи между ними
Метод, который здесь изложен, используется для анализа электрических цепей. Однако его можно применить к любым другим системам.
Имеется набор из m двухполосных элементов E1,…,Em. Двухполюсники соединены в n узлах P1,…,Pn. Каждый элемент системы Ei характеризуется уравнением, связывающим ток xi и напряжение yj.
Пассивные элементы, не являющимися источниками энергии, характеризуются уравнениями :
yi=kxi – сопротивлением
yi=k xi – индуктивность
yi=k - емкость, где t – время.
Активные элементы (источники энергии) характеризуются уравнениями:
xi=f(t) – источник тока
yi=g(t) – источник напряжения
В простейшем случае f и g константы. Каждому элементу Ei соответствует дуга ai, а каждому узлу Pj – вершина Vj. Полученный ориентированный граф называется топологическим (структурным) графом реальной технической системы.
В каждой вершине поведение токов подчиняется правилу вершин (1-ый закон Кирхгофа для тока).
Алгебраическая сумма токов, соответствующих дугам, инцидентны любой вершине, равны нулю.
В случае не электрических систем в качестве одной из базисных переменных тока следует выбирать такую переменную, для которой обеспечивается выполнение условий вершинного постулата.
Циклическое правило (2-ой закон Кирхгофа для напряжений): алгебраическая сумма напряжений, соответствующих дугам любого цикла равна нулю.
Предполагается, что циклу задается некоторая ориентация и каждое напряжение добавляется или вычитается, в зависимости от того, совпадает или не совпадает напряжение соответствующей дуги с выбранной ориентацией цикла.
Циклическое правило может быть переформулировано следующим образом. Если V1 – фиксированная вершина, а Vi – любая другая вершина, отличная от V1, то алгебраическая сумма напряжений по любой цепи, ориентированной от V1 к Vi не зависит от выбранной цепи. Так как граф связен, то существует по крайней мере одна такая цепь. В результате для каждой вершины Vj можно определить число Sj=S1-K, где K – алгебраическая сумма напряжений по любой цепи, направленной от V1 к Vj , а значение S1 – произвольно. В качестве V1 можно выбрать любую вершину.
Таким образом, величины напряжений будут соответствовать разностям потенциалов.
14.2. Основные уравнения
Процесс получения уравнений, характеризующих состояние системы в целом, на основе уравнений ее элементов и заданной структуры проводиться в два этапа.
Сначала с помощью вершинного и циклического правил уменьшается количество переменных, соответствующих токам и напряжениям. В результате выделяется множество переменных, через которые можно выразить все переменные системы. Затем выписывается уравнение связи переменных тока и напряжения.
Рассмотрим первый этап процесса. Применяя к вершине Vi правило вершин, получим: , где
т.е. векторы Ai=(ai1,ai2,…,aim) и X`=(x1,…,xm) являются ортогональными.
Здесь Ai есть строки матрицы A инциденций графа. Так как пространство натянутое на строке A совпадает с пространством, натянутым на строки матрицы разрезов K, X` есть линейная комбинация векторов циклов (строк матрицы циклов С). Таким образом, A (или K) и C определяют ортогональные подпространства, которые вместе образуют подпространство размерности m.
Используя материалы темы 6 K и C можно записать в виде K=(K1|I) C=(I|C2), где I – единичная матрица.
При выборе хорд стягивающего дерева в качестве первых m-n+1 столбцов. Разбивая таким же образом вектор токовых переменных, получим: X=( ) где Xc и Xb относятся к хордам и ветвям дерева.
Правило вершин означает, что KX(K1|I)( )=0 следовательно
Xb= – K1Xc=CT2Xc, т.е. (X=CTXc) (1)
Таким образом, токи в ветвях выражаются через токи в хордах.
Аналогично, циклическое правило приводит к матричным
уравнениям CY=(±|C)( )=0 Yc=-C2Yb=KT1Yb (Y=KTYb) (2)
Это уравнение выражает напряжение на хордах через напряжение на ветвях. Применение соотношений (1) и (2) составляет первый этап анализа.
Основные уравнения элементов удобно записать в матричной форме. Если напряжения заданны в виде явных функций от токов, то при этом получаем Y=ΩxX-Yg где Ωx- диагональная m×m матрица, i – диагональный элемент который является либо константой, либо дифференциальным или интегральным оператором; Yg – вектор столбец, элементы которого равны нулю, для позиций, соответствующих пассивным элементам и функциям g(t) для позиций, соответствующим источникам. Заметим, что соответствующие диагональные элементы Ωx равны нулю.
Если токи выражаются как явные функции напряжения, то получим
X= ΩyY-Xg (*)
Предыдущее выражение, с учетом (1), может быть переписано в виде :
ΩxСTXc=Y+Yg
Умножение обеих частей уравнения на C дает
C ΩxCTXc=CY+CYg=CYg (3)
В этом выражении неизвестными являются лишь токи в хордах.
Выражение (*) может быть переписано
ΩyKTYb=X+Xg
и затем
K ΩyKTYb=KX+KXg=KXg (4)
где неизвестными являются только напряжения в ветвях.
Уравнения (3) и (4) соответствуют формулировкам задачи для циклов и вершин (узлов) соответственно. В случае, когда полученная система уравнений может быть решена известными математическими методами, оставшиеся неизвестными токи и напряжения легко находятся с приведенных выше соотношений.
В частности заметим, что KT и CT могут быть получены при визуальном анализе графа, после выбора дерева.
В случае, если некоторые элементы системы имеют более двух полюсов или если рассматриваются элементы согласования различных видов энергии в одной и той же системе, то матрица характеризующая основные уравнения, имеет более сложную структуру и решение результирующей системы уравнений получается более сложным. Тем не менее, роль графа, представляющего систему, остается по существу той же самой.