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

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

Определение

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

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

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

Примеры

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

Граф	Матрица смежности
	<math>\begin{pmatrix} 1 & 1 & 0 & 0 & 1& 0\\ 1 & 0& 1&0&1&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&1\\ 1&1&0&1&0&0\\ 0&0&0&1&0&0 \end{pmatrix}</math>

• a_ij — число рёбер, связывающих вершины <math>v_i</math> и <math>v_j</math>, причем в некоторых приложениях каждая петля (ребро <math>\{v_i, v_i\}</math> при некотором <math>i</math>) учитывается дважды.

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

Свойства

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

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

PA₁P^-1 = A₂.

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

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

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

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

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

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

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

См. также

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

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Ссылки

• [kvodo.ru/adjacency-matrix.html Матрица смежности графа. Код программ на Паскаль и C++]
• [ideone.com/FDCtT0 Реализация формирования матрицы смежности для случайно сгенерированных графов/связей между графами на языке программирования C#]

Отрывок, характеризующий Матрица смежности

– Мы здесь в Москве больше заняты обедами и сплетнями, чем политикой, – сказал он своим спокойным, насмешливым тоном. – Я ничего про это не знаю и не думаю. Москва занята сплетнями больше всего, – продолжал он. – Теперь говорят про вас и про графа.
Пьер улыбнулся своей доброю улыбкой, как будто боясь за своего собеседника, как бы он не сказал чего нибудь такого, в чем стал бы раскаиваться. Но Борис говорил отчетливо, ясно и сухо, прямо глядя в глаза Пьеру.
– Москве больше делать нечего, как сплетничать, – продолжал он. – Все заняты тем, кому оставит граф свое состояние, хотя, может быть, он переживет всех нас, чего я от души желаю…
– Да, это всё очень тяжело, – подхватил Пьер, – очень тяжело. – Пьер всё боялся, что этот офицер нечаянно вдастся в неловкий для самого себя разговор.
– А вам должно казаться, – говорил Борис, слегка краснея, но не изменяя голоса и позы, – вам должно казаться, что все заняты только тем, чтобы получить что нибудь от богача.
«Так и есть», подумал Пьер.
– А я именно хочу сказать вам, чтоб избежать недоразумений, что вы очень ошибетесь, ежели причтете меня и мою мать к числу этих людей. Мы очень бедны, но я, по крайней мере, за себя говорю: именно потому, что отец ваш богат, я не считаю себя его родственником, и ни я, ни мать никогда ничего не будем просить и не примем от него.
Пьер долго не мог понять, но когда понял, вскочил с дивана, ухватил Бориса за руку снизу с свойственною ему быстротой и неловкостью и, раскрасневшись гораздо более, чем Борис, начал говорить с смешанным чувством стыда и досады.
– Вот это странно! Я разве… да и кто ж мог думать… Я очень знаю…
Но Борис опять перебил его:
– Я рад, что высказал всё. Может быть, вам неприятно, вы меня извините, – сказал он, успокоивая Пьера, вместо того чтоб быть успокоиваемым им, – но я надеюсь, что не оскорбил вас. Я имею правило говорить всё прямо… Как же мне передать? Вы приедете обедать к Ростовым?
И Борис, видимо свалив с себя тяжелую обязанность, сам выйдя из неловкого положения и поставив в него другого, сделался опять совершенно приятен.
– Нет, послушайте, – сказал Пьер, успокоиваясь. – Вы удивительный человек. То, что вы сейчас сказали, очень хорошо, очень хорошо. Разумеется, вы меня не знаете. Мы так давно не видались…детьми еще… Вы можете предполагать во мне… Я вас понимаю, очень понимаю. Я бы этого не сделал, у меня недостало бы духу, но это прекрасно. Я очень рад, что познакомился с вами. Странно, – прибавил он, помолчав и улыбаясь, – что вы во мне предполагали! – Он засмеялся. – Ну, да что ж? Мы познакомимся с вами лучше. Пожалуйста. – Он пожал руку Борису. – Вы знаете ли, я ни разу не был у графа. Он меня не звал… Мне его жалко, как человека… Но что же делать?
– И вы думаете, что Наполеон успеет переправить армию? – спросил Борис, улыбаясь.
Пьер понял, что Борис хотел переменить разговор, и, соглашаясь с ним, начал излагать выгоды и невыгоды булонского предприятия.
Лакей пришел вызвать Бориса к княгине. Княгиня уезжала. Пьер обещался приехать обедать затем, чтобы ближе сойтись с Борисом, крепко жал его руку, ласково глядя ему в глаза через очки… По уходе его Пьер долго еще ходил по комнате, уже не пронзая невидимого врага шпагой, а улыбаясь при воспоминании об этом милом, умном и твердом молодом человеке.
Как это бывает в первой молодости и особенно в одиноком положении, он почувствовал беспричинную нежность к этому молодому человеку и обещал себе непременно подружиться с ним.
Князь Василий провожал княгиню. Княгиня держала платок у глаз, и лицо ее было в слезах.
– Это ужасно! ужасно! – говорила она, – но чего бы мне ни стоило, я исполню свой долг. Я приеду ночевать. Его нельзя так оставить. Каждая минута дорога. Я не понимаю, чего мешкают княжны. Может, Бог поможет мне найти средство его приготовить!… Adieu, mon prince, que le bon Dieu vous soutienne… [Прощайте, князь, да поддержит вас Бог.]
– Adieu, ma bonne, [Прощайте, моя милая,] – отвечал князь Василий, повертываясь от нее.
– Ах, он в ужасном положении, – сказала мать сыну, когда они опять садились в карету. – Он почти никого не узнает.