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

Матрица смежности — один из способов представления графа в виде матрицы.

Определение 
Матрица смежности графа  с конечным числом вершин  (пронумерованных числами от 1 до ) — это квадратная целочисленная матрица  размера , в которой значение элемента  равно числу рёбер из -й вершины графа в -ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента  в этом случае равно удвоенному числу петель вокруг -й вершины.

Матрица смежности простого графа (не содержащего петель и кратных рёбер) является бинарной матрицей и содержит нули на главной диагонали.

Матрица смежности двудольного графа 
Матрица смежности  двудольного графа, доли которого имеют   и  вершин, может быть записана в следующем виде 
 
где  является  матрицей, а  и  представляют  и  нулевые матрицы. В этом случае меньшая матрица  единственным образом представляет граф, а оставшиеся части матрицы  можно отбросить.  иногда называется матрицей бисмежности.

Формально, пусть  будет двудольным графом с долями  и . Бисопряжённая матрица является  0–1 матрицей , в которой  тогда и только тогда, когда . 

Если  является двудольным мультиграфом или взвешенным графом, то элементами  будет число рёбер между вершинами или веса рёбер  соответственно.

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

{|class="wikitable" style="text-align:center"
!Граф
!Матрица смежности
|-
|
|
|}

 — число рёбер, связывающих вершины  и , причём в некоторых приложениях каждая петля (ребро  при некотором ) учитывается дважды.

 Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

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

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

Из этого следует, что матрицы  и  подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица  не является перестановочной, например, матрицы  и  являются подобными, но соответствующие им графы не изоморфны).

Степени матрицы 
Если  — матрица смежности графа , то матрица  обладает следующим свойством: элемент в -й строке, -м столбце равен числу путей из -й вершины в -ю, состоящих из ровно  ребер.

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

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

В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (), зависящее от решаемой задачи, обычно 0 или .

См. также 
Список рёбер
Матрица инцидентности

Литература

Ссылки 
 Матрица смежности графа. Код программ на Паскаль и C++

Теория графов
Типы матриц
Графы (структуры данных)
Алгебраическая теория графов