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

Матрица смежности – это квадратная матрица, строки и столбцы которой – вершины. Заполняется матрица для неориентированного графа следующим образам: ставится 1, если две вершины соединены ребром и 0 – если не соединены.

Пример: по матрице смежности начертить граф:

2

1 3

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

Матрица смежности для ориентированного графа заполняется 1 если ребро выходит из i-ой вершины и входит в j-ю вершину.

Сумма единиц по строке в матрице смежности неориентированного графа дает степень вершины.