Матрица Кирхгофа, также известная как лапласиан графа, является важным инструментом в теории графов и электротехнике. Она используется для анализа свойств графов, таких как связность, и в моделировании электрических цепей.
Определение
Для ненаправленного графа \( G \) с \( n \) вершинами матрица Кирхгофа \( L \) определяется как:
\[ L = D — A \]
где:
— \( D \) — диагональная матрица степеней вершин, где элемент \( D_{ii} \) равен степени вершины \( i \).
— \( A \) — матрица смежности графа, где элемент \( A_{ij} \) равен числу рёбер между вершинами \( i \) и \( j \).
Пример
Рассмотрим простой граф с 4 вершинами, соединенными следующим образом:
— Вершина 1 соединена с вершинами 2 и 3.
— Вершина 2 соединена с вершинами 1 и 4.
— Вершина 3 соединена с вершинами 1 и 4.
— Вершина 4 соединена с вершинами 2 и 3.
Матрица смежности \( A \) будет выглядеть так:
\[ A = \begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
\end{pmatrix} \]
Матрица степеней \( D \) будет:
\[ D = \begin{pmatrix}
2 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 \\
0 & 0 & 0 & 2 \\
\end{pmatrix} \]
Тогда матрица Кирхгофа \( L \) будет:
\[ L = D — A = \begin{pmatrix}
2 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 \\
0 & 0 & 0 & 2 \\
\end{pmatrix} — \begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
\end{pmatrix} = \begin{pmatrix}
2 & -1 & -1 & 0 \\
-1 & 2 & 0 & -1 \\
-1 & 0 & 2 & -1 \\
0 & -1 & -1 & 2 \\
\end{pmatrix} \]
Свойства
1. Сумма строк или столбцов матрицы Кирхгофа равна нулю. Это связано с тем, что каждая строка или столбец представляет собой уравнение баланса токов в вершине.
2. Собственные значения матрицы Кирхгофа. Наименьшее собственное значение \( \lambda_0 \) всегда равно 0. Остальные собственные значения неотрицательны, и их количество показывает количество независимых компонент связности графа.
3. Алгебраическая связность. Второе наименьшее собственное значение матрицы Кирхгофа (также известное как число Фидлера) показывает, насколько граф связан. Чем выше это значение, тем лучше связность графа.
Применения
— Электрические цепи: Используется для анализа и решения уравнений цепей.
— Теория графов: Помогает в изучении связности, разбиений и других свойств графов.
— Машинное обучение и анализ данных: Применяется в спектральной кластеризации и других алгоритмах.
Матрица Кирхгофа является мощным инструментом для математического и прикладного анализа графов и сетей.
