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

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

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

Рисунок 19

M =

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

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

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

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

Рисунок 20

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

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

< Предыдущая		Следующая >