2.7 Матрица смежности и инцидентности

Пусть G = (V, Е) — ориентированный граф без параллельных дуг, в котором V={v₁,v₂,...,v_n}. Матрицей смежности M=[m_ij] графа G называется матрица порядка n×n, элементы которой m_ij определяются следующим образом:

Например, граф, изображенный на рис. 19, имеет следующую матрицу смежности:

Рисунок 19

M =

В случае неориентированного графа m_ij=1 тогда и только тогда, когда существует ребро, соединяющее вершины v_i и v_j. Перейдем к изучению результатов, связанных с матрицей смежности.

Матрица инциденций. Рассмотрим граф G без петель на n вершинах и m ребрах. Матрица инциденций А_c = [a_ij] графа G имеет n строк (по одной на каждую вершину) и m столбцов (по одному на каждую дугу). Элемент a_ij матрицы A_с определяется следующим образом:

Если граф G ориентированный a_ij=

Если граф G ориентированный a_ij=

Строки матрицы А_с называют векторами инциденций графа G. На рис. 20, а и б представлены два графа со своими матрицами инциденций.

Рисунок 20

Из определения очевидно, что всякий столбец матрицы А_с содержит точно два ненулевых элемента: +1 и -1. Поэтому любую строку этой матрицы можно определить по остальным n-1 строкам. Таким образом, произвольные n-1 строк матрицы А_с содержат всю информацию об этой матрице. Другими словами, строки матрицы А_с линейно - зависимы.

Подматрицу А матрицы Ас на n-1 строке называют усеченной матрицей инциденций. Если вершина соответствует строке матрицы Aс, отсутствующей в подматрице А, то говорят, что А — матрица инциденций, усеченная по строке— соответствует данной вершине.