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

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

Определение

Матрица смежности графа G {displaystyle G} с конечным числом вершин n {displaystyle n} (пронумерованных числами от 1 до n {displaystyle n} ) — это квадратная целочисленная матрица A {displaystyle mathbf {A} } размера n × n {displaystyle n imes n} , в которой значение элемента a i , j {displaystyle a_{i,j}} равно числу рёбер из i {displaystyle i} -й вершины графа в j {displaystyle j} -ю вершину.

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

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

Матрица смежности двудольного графа

Матрица смежности A {displaystyle mathbf {A} } двудольного графа, доли которого имеют r {displaystyle r} и s {displaystyle s} вершин, может быть записана в следующем виде

A = ( 0 r , r B B T 0 s , s ) , {displaystyle mathbf {A} ={egin{pmatrix}mathbf {0} _{r,r}&mathbf {B} mathbf {B} ^{T}&mathbf {0} _{s,s}end{pmatrix}},}

где B {displaystyle mathbf {B} } является r × s {displaystyle r imes s} матрицей, а 0 r , r {displaystyle mathbf {0} _{r,r}} и 0 s , s {displaystyle mathbf {0} _{s,s}} представляют r × r {displaystyle r imes r} и s × s {displaystyle s imes s} нулевые матрицы. В этом случае меньшая матрица B {displaystyle mathbf {B} } единственным образом представляет граф, а оставшиеся части матрицы A {displaystyle mathbf {A} } можно отбросить. B {displaystyle mathbf {B} } иногда называется матрицей бисмежности.

Формально, пусть G = ( U , V , E ) {displaystyle G=(U,V,E)} будет двудольным графом с долями U = { u 1 , … , u r } {displaystyle U={u_{1},dots ,u_{r}}} и V = { v 1 , … , v s } {displaystyle V={v_{1},dots ,v_{s}}} . Бисопряжённая матрица является r × s {displaystyle r imes s} 0–1 матрицей B {displaystyle mathbf {B} } , в которой b i , j = 1 {displaystyle b_{i,j}=1} тогда и только тогда, когда ( u i , v j ) ∈ E {displaystyle (u_{i},v_{j})in E} .

Если G {displaystyle G} является двудольным мультиграфом или взвешенным графом, то элементами b i , j {displaystyle b_{i,j}} будет число рёбер между вершинами или веса рёбер ( u i , v j ) {displaystyle (u_{i},v_{j})} соответственно.

Примеры

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

• a i , j {displaystyle a_{i,j}} — число рёбер, связывающих вершины v i {displaystyle v_{i}} и v j {displaystyle v_{j}} , причём в некоторых приложениях каждая петля (ребро { v i , v i } {displaystyle {v_{i},v_{i}}} при некотором i {displaystyle i} ) учитывается дважды.

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

Свойства

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

Два графа G 1 {displaystyle G_{1}} и G 2 {displaystyle G_{2}} с матрицами смежности A 1 {displaystyle mathbf {A} _{1}} и A 2 {displaystyle mathbf {A} _{2}} являются изоморфными тогда и только тогда, когда существует перестановочная матрица P {displaystyle mathbf {P} } , такая что

P A 1 P − 1 = A 2 {displaystyle mathbf {P} mathbf {A} _{1}mathbf {P} ^{-1}=mathbf {A} _{2}} .

Из этого следует, что матрицы A 1 {displaystyle mathbf {A} _{1}} и A 2 {displaystyle mathbf {A} _{2}} подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица P {displaystyle mathbf {P} } не является перестановочной, например, матрицы ( 0 1 0 0 ) {displaystyle {egin{pmatrix}0&1&0end{pmatrix}}} и ( 0 2 0 0 ) {displaystyle {egin{pmatrix}0&2&0end{pmatrix}}} являются подобными, но соответствующие им графы не изоморфны).

Степени матрицы

Если A {displaystyle mathbf {A} } — матрица смежности графа G {displaystyle G} , то матрица A m {displaystyle mathbf {A} ^{m}} обладает следующим свойством: элемент в i {displaystyle i} -й строке, j {displaystyle j} -м столбце равен числу путей из i {displaystyle i} -й вершины в j {displaystyle j} -ю, состоящих из ровно m {displaystyle m} ребер.

Структура данных

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

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

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