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

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

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

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

Формальная модель матрицы смежности

1. Граф как математический объект
   

   Пусть дан граф

   G = (V, E),

   где:

   • V = {v1, v2, ..., vn} – конечное множество вершин; 

   • E – множество рёбер или дуг. 

   Если граф неориентированный, то ребро есть неупорядоченная пара:

   E ⊆ {{vi, vj} | vi, vj ∈ V}.

   Если граф ориентированный, то дуга есть упорядоченная пара:

   E ⊆ {(vi, vj) | vi, vj ∈ V}.

2. Определение матрицы смежности
   

   Матрица смежности графа G порядка n – это квадратная матрица

   A = (aij),   1 ≤ i, j ≤ n,

   в которой элемент aij кодирует отношение смежности между вершинами vi и vj.

   Для простого невзвешенного графа стандартная формула такова:

   aij = 1, если между vi и vj существует ребро (или дуга);
   aij = 0, если ребра (или дуги) нет.

   Иначе говоря:

   aij = χE(vi, vj),

   где χE – характеристическая функция множества рёбер.

3. Размерность и структура
   

   Если в графе n вершин, то матрица смежности всегда имеет размер:

   n × n.

   Это означает, что объём памяти для хранения такой структуры в общем случае равен:

   Θ(n^2).

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

Виды матриц смежности и их свойства

1. Матрица смежности неориентированного графа
   

   Для неориентированного графа наличие ребра между vi и vj автоматически означает наличие того же ребра между vj и vi. Поэтому:

   aij = aji.

   Следовательно, матрица смежности неориентированного графа симметрична относительно главной диагонали:

   A = A^T.

   Это фундаментальное свойство позволяет:

   • быстро определить тип графа; 

   • уменьшать объём ручного анализа; 

   • проверять корректность построенной матрицы. 

2. Матрица смежности ориентированного графа
   

   Для ориентированного графа наличие дуги vi → vj не означает наличие дуги vj → vi. Поэтому в общем случае:

   aij ≠ aji.

   Матрица ориентированного графа может быть несимметричной.
   При этом:

   • сумма элементов строки i равна полустепени исхода вершины vi; 

   • сумма элементов столбца j равна полустепени захода вершины vj. 

   Формально:

   outdeg(vi) = ∑_{j=1}^{n} aij
   indeg(vj)  = ∑_{i=1}^{n} aij

3. Главная диагональ
   

   Элемент aii описывает отношение вершины vi к самой себе.
   Если в графе нет петель, то:

   aii = 0.

   Если в вершине vi есть петля, то:

   aii = 1

   для булевой матрицы смежности, либо иное значение – при использовании счётной или весовой модели.

Расширенные модели: кратные рёбра, веса, специализированные кодировки

1. Мультиграф и счётная матрица
   

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

   aij = число рёбер (или дуг) между vi и vj.

   Тогда элементы матрицы принимают значения из множества неотрицательных целых:

   aij ∈ {0, 1, 2, ...}.

2. Взвешенный граф
   

   Если каждому ребру приписан вес w(vi, vj), то матрица смежности превращается в матрицу весов:

   aij = w(vi, vj), если ребро существует;
   aij = 0, +∞, −1 или иной специальный маркер, если ребра нет.

   Выбор специального значения зависит от задачи:

   • 0 – удобно, если веса положительны и нулевых рёбер нет; 

   • +∞ – удобно в алгоритмах кратчайших путей; 

   • −1 – удобно при явном разграничении «нет ребра» и «вес 0». 

3. Булева и логическая интерпретация
   

   В булевой интерпретации матрица смежности задаёт бинарное отношение R на множестве вершин:

   vi R vj ⇔ aij = 1.

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

Построение матрицы смежности

1. По списку рёбер
   

   Пусть задан список рёбер:

   (vi1, vj1), (vi2, vj2), ..., (vik, vjk).

   Тогда алгоритм построения матрицы смежности состоит из двух этапов:

   1. Инициализация нулевой матрицы: 

   для i от 1 до n
       для j от 1 до n
           aij ← 0

   1. Обработка каждого ребра: 

   • для ориентированного графа: 

   a[u][v] ← 1

   • для неориентированного: 

   a[u][v] ← 1
   a[v][u] ← 1

2. По списку смежности
   

   Если граф задан списками соседей, то каждая вершина vi имеет набор вершин Adj(vi). Тогда:

   для каждой вершины vi
       для каждого vj из Adj(vi)
           aij ← 1

3. По графическому рисунку
   

   В ручных задачах ЕГЭ граф часто изображён рисунком. В таком случае необходимо:

   1. Пронумеровать вершины. 

   2. Для каждой пары (vi, vj) установить, есть ли ребро. 

   3. Заполнить соответствующую клетку матрицы. 

   4. Проверить симметричность, если граф неориентированный. 

Основные операции над матрицей смежности

1. Проверка наличия ребра
   

   Одно из важнейших преимуществ матрицы смежности – мгновенная проверка смежности:

   есть ли ребро между vi и vj?  ⇔  aij ≠ 0

   Сложность:

   O(1)

2. Подсчёт степени вершины
   

   Для неориентированного простого графа степень вершины vi определяется суммой элементов строки:

   deg(vi) = ∑_{j=1}^{n} aij

   Если допускаются петли, каждая петля учитывается дважды:

   deg(vi) = ∑_{j=1}^{n} aij + aii

   или эквивалентно – с отдельным учётом диагонального элемента.

   Для ориентированного графа:

   outdeg(vi) = ∑_{j=1}^{n} aij
   indeg(vi)  = ∑_{j=1}^{n} aji

3. Поиск соседей вершины
   

   Чтобы найти всех соседей vi, нужно просмотреть строку i:

   если aij ≠ 0, то vj – сосед vi.

   Сложность:

   O(n)

4. Подсчёт числа рёбер
   

   Для неориентированного графа без петель:

   |E| = (1/2) · ∑_{i=1}^{n} ∑_{j=1}^{n} aij

   Для ориентированного графа:

   |E| = ∑_{i=1}^{n} ∑_{j=1}^{n} aij

   если aij – булев индикатор наличия дуги.

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

1. Длина пути и степени матрицы
   

   Одно из важнейших теоретических свойств матрицы смежности состоит в том, что элементы её степеней отражают количество путей.
   Если A – матрица смежности графа, то элемент (i,j) матрицы A^k показывает число путей длины k из вершины vi в вершину vj:

   (A^k)ij = число путей длины k из vi в vj.

   Это свойство чрезвычайно важно как в теории графов, так и в задачах на логику и комбинаторику.

2. Матрица достижимости
   

   Если требуется определить, существует ли путь между вершинами, используют матрицу достижимости.
   Её можно строить:

   • многократным возведением матрицы в степени; 

   • алгоритмом Уоршелла; 

   • обходами DFS/BFS из каждой вершины. 

   Булева версия:

   rij = 1, если существует путь из vi в vj;
   rij = 0, если пути нет.

3. Алгоритм Уоршелла
   

   Для матрицы достижимости можно применять следующий рекуррентный переход:

   R_k[i][j] = R_{k−1}[i][j] OR (R_{k−1}[i][k] AND R_{k−1}[k][j])

   Это означает: путь из i в j существует либо без участия вершины k, либо через неё.
   Сложность:

   O(n^3)

Сравнение матрицы смежности с другими представлениями графа

1. Матрица смежности vs список смежности
   

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

   • память Θ(n^2); 

   • проверка ребра O(1); 

   • перебор соседей O(n). 

   Список смежности:

   • память Θ(n + m), где m – число рёбер; 

   • проверка ребра O(deg(v)) или хуже; 

   • перебор соседей O(deg(v)). 

2. Когда матрица смежности выгодна
   

   Матрица смежности особенно эффективна:

   • в плотных графах, где m близко к n^2; 

   • когда нужно часто проверять наличие ребра; 

   • при реализации алгоритмов на основе матричных операций; 

   • в учебных задачах, где важна наглядность и формальная простота. 

3. Когда лучше использовать список смежности
   

   Список смежности предпочтительнее:

   • в разреженных графах; 

   • при обходах графа с малым средним количеством соседей; 

   • когда память ограничена.

Инженерные правила и практические соглашения

1. Всегда фиксируйте порядок нумерации вершин.
   Ошибки в нумерации делают матрицу бессмысленной. 

2. Указывайте тип графа заранее.
   Неориентированный, ориентированный, взвешенный, с петлями, без петель – это меняет интерпретацию матрицы. 

3. Явно задавайте значение отсутствия ребра.
   Особенно во взвешенных графах. 

4. Проверяйте симметричность, если граф неориентированный.
   Это простой способ контроля корректности. 

5. Не смешивайте булеву и весовую модели.
   Если матрица должна хранить веса, ноль и отсутствие ребра – не одно и то же, если допустимы рёбра нулевого веса. 

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

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

Мини-шпаргалка по теме

1. Определение
   

   aij = 1, если есть ребро (или дуга) между vi и vj;
   aij = 0, если ребра нет.

2. Свойства
   

   • неориентированный граф: 

   aij = aji

   • ориентированный граф: 

   aij и aji независимы

   • петля: 

   aii = 1

3. Формулы
   

   Степень вершины в неориентированном графе:

   deg(vi) = ∑_{j=1}^{n} aij

   Полустепени в ориентированном графе:

   outdeg(vi) = ∑_{j=1}^{n} aij
   indeg(vi)  = ∑_{j=1}^{n} aji

   Число рёбер в неориентированном графе без петель:

   |E| = (1/2) · ∑ aij

   Число путей длины k:

   (A^k)ij

Типичные ошибки и их профилактика

Ошибка 1. Нарушение симметричности
Учащийся строит матрицу неориентированного графа, но забывает поставить симметричное значение.
Профилактика: после заполнения обязательно проверять aij = aji.

Ошибка 2. Путаница с диагональю
Иногда на диагонали ставят 1 автоматически, хотя петель нет.
Профилактика: диагональ заполняется по факту наличия петель, а не по умолчанию.

Ошибка 3. Неправильный подсчёт рёбер
В неориентированном графе каждое ребро учитывается дважды в сумме матрицы.
Профилактика: всегда делить общую сумму на 2.

Ошибка 4. Смешение ориентированного и неориентированного графа
Строка и столбец интерпретируются неверно.
Профилактика: заранее фиксировать: строка – откуда, столбец – куда.

Ошибка 5. Ошибка в модели отсутствия ребра
Во взвешенных графах путают «нулевой вес» и «ребра нет».
Профилактика: использовать специальный маркер ∞, −1 или явно оговорённое значение.

Связь с подготовкой к ЕГЭ по информатике

Матрица смежности играет важную роль в ЕГЭ по информатике, потому что через неё проверяются сразу несколько ключевых навыков:

• умение переводить графическую схему в табличную форму; 
• понимание различия между ориентированным и неориентированным графом; 
• навыки подсчёта степеней вершин и числа рёбер; 
• способность анализировать логические связи между объектами; 
• умение строить алгоритмы обхода и поиска путей. 

Кроме того, матрица смежности – это один из лучших примеров того, как абстрактный объект дискретной математики превращается в конкретную структуру данных, пригодную для программирования.

Пять упражнений 

Упражнение 1. Построение матрицы смежности
Условие. Дан неориентированный граф с вершинами 1,2,3,4 и рёбрами:

(1,2), (1,3), (2,4), (3,4)

Постройте матрицу смежности.

Решение.
Матрица 4 × 4:

     1 2 3 4
1    0 1 1 0
2    1 0 0 1
3    1 0 0 1
4    0 1 1 0

Она симметрична, что подтверждает неориентированность графа. 

Упражнение 2. Определение типа графа
Условие. Дана матрица:

0 1 0
0 0 1
1 0 0

Определите, является ли граф ориентированным.

Решение.
Проверяем симметричность:

• a12 = 1, а a21 = 0; 
• a13 = 0, а a31 = 1. 

Следовательно:

A ≠ A^T

Граф ориентированный. 

Упражнение 3. Подсчёт степеней
Условие. Дана матрица смежности неориентированного графа:

0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

Найдите степени всех вершин.

Решение.
Суммируем строки:

• deg(v1) = 2 
• deg(v2) = 3 
• deg(v3) = 2 
• deg(v4) = 1 

Ответ:

(2, 3, 2, 1) 

Упражнение 4. Число рёбер
Условие. Для матрицы из предыдущего упражнения найдите число рёбер.
Решение.

Сумма всех элементов:

2 + 3 + 2 + 1 = 8

Для неориентированного графа:

|E| = 8 / 2 = 4

Ответ:

4 ребра 

Упражнение 5. Пути длины 2
Условие. Для графа из упражнения 1 найдите число путей длины 2 из вершины 1 в вершину 4.
Решение.

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

A =
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Вычисляем элемент (1,4) матрицы A^2:

(A^2)14 = a11·a14 + a12·a24 + a13·a34 + a14·a44
        = 0·0 + 1·1 + 1·1 + 0·0
        = 2

Значит, существует:

2 пути длины 2 из 1 в 4

Это пути:

1 → 2 → 4
1 → 3 → 4

Практические рекомендации

1. Если задача требует только проверки наличия ребра, матрица смежности удобнее списка смежности. 

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

3. Для ручного анализа всегда сначала проверяйте:  
   

   • размерность; 

   • симметричность; 

   • диагональ; 

   • суммы строк и столбцов.

4. При реализации алгоритмов обхода по матрице смежности используйте вложенный цикл по всем вершинам.

Чек-лист самопроверки

• Матрица квадратная n × n. 
• Вершины правильно пронумерованы. 
• Для неориентированного графа выполнено A = A^T. 
• Диагональ заполнена корректно. 
• Правильно выбрано значение отсутствия ребра. 
• Степени и число рёбер считаются по верным формулам. 
• При анализе ориентированного графа различаются входящие и исходящие связи. 

Заключение

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

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