🔀 Дискретка

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

англ. Adjacency matrix

Квадратная таблица n×n, где единица на пересечении i и j означает ребро из вершины i в вершину j; k-я степень матрицы считает маршруты длины k.

Матрица смежности графа с $n$ вершинами — квадратная таблица $n \times n$ : на пересечении строки $i$ и столбца $j$ стоит $1$ , если из вершины $i$ в вершину $j$ идёт ребро; для взвешенных графов пишут вес, для мультиграфов — кратность. У неориентированного графа матрица симметрична, у ориентированного — нет. Это самый удобный формат для линейной алгебры: степени вершин — суммы по строкам, спектры и маршруты считаются матричными операциями. Основы графов — в уроке графы: основы.

Ключевое свойство — сила степеней: элемент $(i, j)$ матрицы $A^{k}$ равен числу маршрутов длины ровно $k$ из вершины $i$ в вершину $j$ . Отсюда мгновенный ответ на вопрос «существует ли путь не длиннее $k$ » — сложить $A + A^{2} + \dots + A^{k}$ и поискать нулевые позиции. Обратная сторона медали: память $Θ (n^{2})$ даже при паре рёбер, поэтому разреженные графы хранят списками смежности. Выбор зависит от плотности и алгоритма: обходы и кратчайшие пути любят списки — подробности в уроке кратчайшие пути.

(A^{k})_{ij} = # {маршрутов длины k из i в j}

умножение матрицы смежности пересчитывает маршруты: каждый сомножитель выбирает очередную промежуточную вершину пути

Частые вопросы

Зачем возводить матрицу смежности в степень?

Чтобы посчитать маршруты фиксированной длины без перебора путей: $(A^{k})_{ij}$ — готовое число маршрутов из $i$ в $j$ ровно за $k$ шагов. Так проверяют достижимость за ограниченное число ходов, считают треугольники в графе через $tr A^{3} /6$ , анализируют случайные блуждания: степени стохастической матрицы переходов дают вероятности попаданий. Быстрое возведение в степень делает всё это за $O (n^{3} lo g k)$ .

Матрица смежности или списки — что выбрать?

Матрица выигрывает на плотных графах и там, где нужен мгновенный ответ «есть ли ребро $i \to j$ », а также в алгебраических задачах: Флойд—Уоршелл, подсчёт маршрутов, спектральный анализ. Списки выигрывают памятью на разреженных графах — $O (n + m)$ против $O (n^{2})$ — и скоростью обходов: BFS и Дейкстра с кучей ходят именно по спискам. Правило простое: алгебра и плотные графы — матрица, обходы и пути — списки.