Название: алгоритмизированное расчетно-графическое задание (В.А. Аксютин)

Жанр: Информатика

Просмотров: 1617


4.9.2. [q] – матрица главных сечений

 

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

Сечение называют независимым или главным, если оно содержит ветви связи и только одну ветвь дерева. Следовательно, каждая ветвь дерева позволяет построить только одно независимое сечение, поэтому полное число главных сечений n = q – 1 – числу ветвей дерева.

На рис. 18 изображен граф электрической цепи, содержащий дерево с ветвями 1, 2, 3 и ветви связи 4, 5, 6. Пунктирными линиями на графе нанесены сечения. Каждое сечение содержит только одну ветвь дерева и, следовательно, является независимым.

 

Рис. 18

 

[Q] – матрица сечений представляет собой таблицу, строки которой соответствуют сечениям графа, а столбцы — его ветвям.

Элементы матрицы имеют следующие значения:

+ 1 – если ветвь i входит в сечение  j;

− 1 – если ветвь i выходит из сечения  j;

0 − если же ветвь i не связана с сечением  j.

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

Матрица сечений [Q], построенная для графа, изображенного на рис. 16, имеет вид табл. 3.

 

Таблица 3

сечения

ветви

1

2

3

4

5

6

1

0

+1

0

–1

+1

–1

2

–1

0

0

0

+1

–1

3

0

0

+1

+1

–1

0

4.9.3. [B] – матрица главных контуров

 

Контурная матрица – [B] представляет собой таблицу, строки которой соответствуют контурам графа, а столбцы − его ветвям.

Элементы матрицы имеют следующие значения:

+1 – если контур i содержит ветвь j и направление обхода контура совпадает с направлением ветви;

−1 – если контур i содержит ветвь j и направление обхода контура противоположно направлению ветви;

0 – если же контур i не содержит ветви j.

Таким образом, элементы строки матрицы [В] показывают, какие ветви входят в контуры и как они направлены.

Контурная матрица может быть составлена как для всех контуров цепи, так и для независимых контуров. Если контурную матрицу составляют для всех контуров цепи, то ее называют неопределенной. При этом один из контуров считают базисным или опорным, и он не входит в матрицу [В]. Полное число контуров определяют из условия, что каждая ветвь графа входит в два противоположно направленных контура.

Независимая система контуров составляется так, чтобы в каждый контур входили ветви дерева графа и одна из хорд. Число главных (независимых) контуров, которое равно числу хорд, можно определить как .

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

Рис. 19

Определенная контурная матрица, составленная для графа рис. 19, имеет вид табл. 4.

 

Таблица 4

контуры

ветви

1

2

3

4

5

6

1

−1

+1

0

0

0

+1

2

0

−1

+1

−1

0

0

3

−1

+1

−1

0

0

−1