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

Определение править

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

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

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

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

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

 

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

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

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

Примеры править

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

Свойства править

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

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

  .

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

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

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

Структура данных править

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

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

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

См. также править

Литература править

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

Ссылки править