Матрица смежности – это квадратная матрица, строки и столбцы которой – вершины. Заполняется матрица для неориентированного графа следующим образам: ставится 1, если две вершины соединены ребром и 0 – если не соединены.
Пример: по матрице смежности начертить граф:
2
1 3
Матрица смежности для графа у которого нет петель является симметрической.
Матрица смежности для ориентированного графа заполняется 1 если ребро выходит из i-ой вершины и входит в j-ю вершину.
Сумма единиц по строке в матрице смежности неориентированного графа дает степень вершины.