Матрицы инциденций
Для направленного графа могут быть определены:
а) матрица соединений ветвей в узлах (первая матрица инциденций);
б) матрица соединения ветвей в независимые контуры (вторая матрица инциденций).
Эти матрицы служат для обобщенного аналитического представления графа.
Матрица соединений ветвей в узлах MS – это прямоугольная матрица, число строк которой равно числу вершин графа n,а число столбцов – числу ребер m.
При этом номера строк i соответствуют номерам вершин, а номера столбцов j– номерам ребер.
Элементы матрицы MS могут принимать одно из трех значений:
= +1, если узел i является начальной вершиной ветви j ;
= -1, если узел i является конечной вершиной ветви j ;
= 0, если узел i не является вершиной ветви j.
Очевидно, что в каждом столбце матрицы MS может быть только одна положительная и одна отрицательная единицы; остальные элементы матрицы равны нулю.
Так как число уравнений 1-го закона Кирхгофа равно n -1, то в расчетах используется матрица М, которая получается из матрицы MS путем исключения из нее строки, соответствующей балансирующему узлу.
Для направленного графа, показанного на рисунке 5, матрица MS имеет следующий вид:
| |||
 | |||
-1 1 0 0 0 0
0 0 0 1 0 -1
M S = 0 -1 -1 0 -1 1
0 0 1 0 0 0
1 0 0 -1 1 0
|
Выбрав узел eв качестве балансирующего, получим матрицу Mпутем исключения последней строки из матрицыMS :
-1 1 0 0 0 0
|
0 -1 -1 0 -1 1
0 0 1 0 0 0
Матрица соединения ветвей в независимые контуры - это прямоугольная матрица, число строк которой равно числу независимых контуров графа К, а число столбцов – числу ветвей m.При этом номера строк i соответствуют номерам независимых контуров, а номера столбцов j - номерам ветвей. Она
обозначается следующим образом:
N = 
Элементы матрицы N определяются следующим образом:
+1, если ветвь j входит в контур i и их направления совпадают;
-1, если ветвь j входит в контур i и их направления не совпадают;
0, если ветвь j не входит в контур i .
Для направленного графа, приведенного на рисунке 5, матрица Nимеет вид:
|
|
1 1 0 0 -1 0
0 0 0 1 1 1
 |