Линейный граф. Основные определения и понятия.

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

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

 

 

Рис 3.1

На рис.3.1 приведен типовой граф, содержащий пять узлов и девять ветвей.

Каждый i-й – узел характеризуется величиной, называемой узловым сигналом Xi . Отдельные узлы соединены направленными ветвями, каждая ветвь характеризуется

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

Условимся, что каждая ветвь с передачей ţ_јк переносит информацию от узла Х_j к узлу Х_к , причем эта информация равна узловому сигналу Х_ј , умноженному на передачу ветви t_јк._. К узлу Х₁ никакая ветвь не подходит, что свидетельствует о том, что сигнал не является функцией других сигналов, т.е. является независимым. Такие узлы в дальнейшем будем называть узлами-источниками. К узлу Х₂ подходят ветви с передачами t₁₂ , t₄₂, t₃₂ соответственно от узлов X₁, X₄, X₃ и от него уходит ветвь t₂₄ к узлу X₄. Условимся, что в этом и подобных случаях сигнал определяется как сумма информаций, поступающих в узел по всем подходящим к нему ветвям, тогда как выходящие из узла ветви никак на его сигнал не влияют.

 

X₂=t₁₂X₁+t₄₂X₄+t₃₂X₃

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

Х₄=t₁₄Х₁ +t₂₄Х₂

К узлу Х₃ подходит ветвь t₄₃ от четвертого узла и ветвь t₃₃, начинающаяся в том же третьем узле.

Х₃=t₃₃Х₃+t₄₃Х₄

Для дальнейшего изучения графов очень важно усвоить следующие понятия: путь, передача пути, контур, передача контура.

Путем между двумя различными узлами называется непрерывная последовательность одинаково направленных ветвей, в которой каждый узел встречается не более одного раза. Так, путем от узла Х₁ к узлу Х₅ в графе на рис.3.1. является любая из последовательностей t₁₄ – t₄₅, t₁₄ – t₄₃ – t_35, не является путем последовательность t₁₂ – t₄₂ – t₄₅, так как в ней одна из ветвей (t₄₂) направлена в обратную сторону.. Путем не является так же последовательность t₁₄ – t₄₂ – t₂₄ – t₄₅ , так как в ней узел Х₄ встречается дважды.

Передача пути Рјі от узла Хік узлу Хј является произведение передач ветвей, образующих путь. Так, указанные выше пути имеют следующие передачи.

Р₁₅₍₁₎ =t₁₄t₄₅, Р₁₅₍₂₎=t₁₄t₄₃t₃₅.

Р₁₅(₃₎=t₁₂t₂₄t₄₅, Р₁₅₍₄₎=t₁₂t₂₄t₄₃t₃₅

Если произведение сомножителей записывать в том же порядке, в котором следуют ветви, с учетом принятой выше индексации передач ветвей первый индекс каждого последующего сомножителя будет равен второму индексу предыдущего. Будем называть такую последовательность индексов упорядоченной. Первый индекс последовательности соответствует номеру узла, в котором начинается путь, а последний – номер узла, в котором путь заканчивается.

Контуромназывается замкнутый путь, начинающийся и заканчивающийся в одном и том же узле.

Передачей контура называется произведение передач ветвей, образующих этот контур. Так, в графе на рис. 3.1. есть три контура с передачами: L₁=t₂₄t₄₂, L₂=t₂₄t₄₃t₃₂, L₃=t₃₃. Последовательность индексов здесь также будет упорядоченной, если сомножители записывать в том порядке, в каком следуют ветви при обходе контура. Так как контур – это путь, начинающийся и заканчивающийся в одном и том же узле, первый индекс последовательности равен последнему. Такие последовательности будут называться замкнутыми. В противоположность контуру последовательность индексов передачи пути между двумя узлами будет разомкнутой.