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