Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:
1 - в случае, если связь j «выходит» из вершины i,
−1 - если связь «входит» в вершину,
0 - во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким и неудобным для хранения, но облегчает нахождение циклов в графе.
Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
Обычно в теории графов выделяют некоторые разновидности графов. Среди таких разновидностей выделим следующие:
- полный граф - граф, матрица смежности которого состоит из одних единиц;
- полный обыкновенный граф - граф, у матрицы смежности которого все элементы, за исключением нулевых элементов главной диагонали, равны единице;
- пустой (нулевой) граф - граф, матрица смежности которого нулевая (обыкновенный граф, все вершины которого изолированы, т.е. нет ни одной пары смежных вершин);
- единичный граф - граф, матрица смежности которого единичная (граф, все вершины которого имеют петли и изолированы);
- плоский (планарный) граф - граф, который можно начертить на плоскости так, чтобы его ребра (дуги) пересекались только в его вершинах.