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

Матрицей смежности -графа называется квадратная матрица размера , которая определяется следующим образом:

Для графа, изображенного на рис. 4, матрица смежности имеет вид:

Матрица смежности полностью определяет структуру графа. Например,

, ,

Множество столбцов, имеющих 1 в -ой строке, есть множество , а множество строк, которые имеют 1 в -ом столбце, совпадает с множеством .

Для неориентированного графа без кратных ребер и петель матрица смежности симметрична и имеет нули по главной диагонали. Для такого графа

,

Возведем матрицу смежности в квадрат. Элемент матрицы определяется по формуле

.

Слагаемое в этом уравнении равно 1 тогда и только тогда, когда оба числа равны 1, в противном случае оно равно 0. Поскольку из равенства следует существование пути длины 2 из вершины в вершину , проходящего через вершину , то равно числу путей длины 2, идущих из в .

Аналогично если является элементом матрицы , то равно числу путей длины , идущих от к .

Матрицей инциденций -графа называется прямоугольная матрица размерности , определяемая следующим образом:

Для графа, приведенного на рис. 4, матрица инциденций имеет вид:

Поскольку каждая дуга (ребро) инцидентна двум различным вершинам, за исключением того случая, когда дуга (ребро) образует петлю (в этом случае элементы соответствующего столбца равны 0), то в каждом столбце матрицы – два ненулевых элемента.

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