Свойства матриц смежности и инцидентности

1. Пусть G=(V, X) – мультиграф (V={v₁, …, v_n}). Тогда сумма элементов матрицы A(G) по i-ой строке (или по i-му столбцу) равна .

2. Пусть Д=(V, X) – ориентированный псевдограф (V={v₁, …, v_n}). Сумма элементов матрицы A(Д) по i-ой строке равна , сумма элементов по i-му столбцу равна .

3. Пусть Д=(V, X) – ориентированный мультиграф. Тогда

а) сумма строк матрицы B(Д) является нулевой строкой;

б) любая строка матрицы B(Д) является линейной комбинацией остальных строк;

в) rang B(Д) n(Д)-1 (n(Д) – кол-во вершин);

г) для любого контура в Д сумма столбцов матрицы В(Д), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

4. Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:

а) сумма строк матрицы В(G) является нулевой строкой;

б) любая строка матрицы B(G) является суммой остальных строк;

в) для любого цикла в G сумма столбцов матрицы B(G), соответствующих рёбрам, входящим в этот цикл, равна нулевому столбцу.

Обозначим через A^k=[a_ij^(k)] – k-тую степень матрицы смежности A.

Утверждение 1. Элемент a_ij^(k) матрицы A^(k) ориентированного псевдографа Д=(V, X) (псевдографа G=(V, X)), где V={v₁, …, v_n} равен числу всех путей (маршрутов длины k) из v_i в v_j.

Утверждение 2. Для того, чтобы n-вершинный орграф Д с матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица K=A²+A³+…+Aⁿ имела ненулевые диагональные элементы.

Утверждение 3. Для того, чтобы n-вершинный ориентированный псевдограф Д с матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица K=A+A²+…+Aⁿ имела ненулевые диагональные элементы.