Матриця Кірхгофа

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Матриця Лапласа)
Перейти до навігації Перейти до пошуку

Матриця Кірхгофа (англ. Laplacian matrix) — один з методів подання графа за допомогою матриці. Матриця Кірхгофа використовується для підрахунку кістякових дерев графа, а також у спектральній теорії графів.

Визначення[ред. | ред. код]

Дано простий граф з вершинами. Тоді матриця Кірхгофа цього графа буде визначатися так:

Також матрицю Кірхгофа можна визначити як різницю матриць де  — це матриця суміжності цього графа, а  — матриця, на головній діагоналі якої степені вершин графа, а решта елементів — нулі:

Якщо граф є зваженим, то визначення матриці Кірхгофа узагальнюється. У цьому випадку елементами головної діагоналі матриці Кірхгофа будуть суми ваг ребер, інцидентних відповідній вершині. Для суміжних (пов'язаних) вершин , де  — це вага (провідність) ребра. Для різних не суміжних (не пов'язаних) вершин покладається .

Для зваженого графа матриця суміжності записується з урахуванням провідностей ребер, а на головній діагоналі матриці будуть суми провідностей ребер, інцидентних відповідним вершинам.

Приклад[ред. | ред. код]

Приклад матриці Кірхгофа простого графа.

Розмічений граф Матриця Кірхгофа

Властивості[ред. | ред. код]

  • Сума елементів кожного рядка (стовпця) матриці Кірхгофа дорівнює нулю:
    .
  • Визначник матриці Кірхгофа дорівнює нулю:
  • Матриця Кірхгофа простого графа симетрична:
    .
  • Всі алгебраїчні доповнення симетричної матриці Кірхгофа рівні між собою — стала матриці Кірхгофа. Для простого графа значення цієї сталої збігається з числом всіх можливих кістяків графа.
  • Якщо зважений граф являє собою електричну мережу, де вага кожного ребра відповідає його провідності, то мінори матриці Кірхгофа дозволяють обчислити резистивні відстані  між точками і даної мережі:
    ,
тут  — стала (алгебраїчне доповнення) матриці Кірхгофа, а  — алгебраїчне доповнення 2-го порядку, тобто визначник матриці, отримуваної з матриці Кірхгофа викреслюванням двох рядків і двох стовпців.
  • Існує алгоритм відновлення матриці Кірхгофа за матрицею опорів .

Див. також[ред. | ред. код]