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

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

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

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

Дано простий граф с https://wikimedia.org/api/rest_v1/media/math/render/svg/17ef9be2521922a6d96ccc19e0b0ea3a5a974f07 з вершинами. Тоді матриця Кірхгофа даного графа буде визначатися наступним чином:

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

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

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

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

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

Позначений граф Матриця Кірхгофа
6n-graf.svg

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

  • Визначник матриці Кірхгофа дорівнює нулю:
  • Всі алгебраїчні доповнення симетричної матриці Кірхгофа рівні між собою — постійна матриці Кірхгофа. Для простого графа значення даної постійної збігається з числом всіх можливих кістяків графа.
  • Якщо зважений граф являє собою електричну мережу, де вага кожного ребра відповідає його провідності, то мінори матриці Кірхгофа дозволяють обчислити резистивні відстані (resistance distance) між точками і даної мережі:
    https://wikimedia.org/api/rest_v1/media/math/render/svg/41db983dbe868a923fcb6f95ca5548bdffe50a54,
тут — постійна (алгебраїчне доповнення) матриці Кірхгофа, а — алгебраїчне доповнення 2-го порядку, тобто визначник матриці, отримуваної з матриці Кірхгофа викреслюванням двох рядків і двох стовпців.
  • Існує алгоритм відновлення матриці Кірхгофа по матриці опорів .
    • 0 є власним значенням матриці (відповідний власний вектор — всі одиниці), кратність його дорівнює числу зв'язних компонент графа.
    • Інші власні значення позитивні. Друге за малості значення Фідлер назвав індексом зв'язності графа, відповідний власний вектор — вектор Фиддлера.

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