Матрица Кирхгофа
Версия от 20:36, 29 декабря 2014; 188.243.62.170 (обсуждение)
Определение: |
Матрицей Кирхгофа простого графа называется матрица , элементы которой определяются равенством: |
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении
-й строки и -го столбца ( ) стоит , если вершины с номерами и смежны, и в противном случае.Пример матрицы Кирхгофа
Граф | Матрица Кирхгофа |
---|---|
Некоторые свойства
Утверждение: |
Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
|
Утверждение: |
Определитель матрицы Кирхгофа равен нулю:
|
Прибавим к первой строке все остальные строки(это не изменит значение определителя):
Так как сумма элементов каждого столбца равна , получим: |
Утверждение: |
Матрица Кирхгофа простого графа симметрична:
|
Утверждение: |
Связь с матрицей смежности:
|
Утверждение: |
Связь с матрицей инцидентности:
|
Утверждение: |
собственным значением матрицы. является |
Собственным значением матрицы называют значения , которые удовлетворяют уравнению:
Прибавим к первой строке все остальные строки(это не изменит значение определителя):
Так как сумма элементов каждого столбца равна , получим:
Следовательно, является собственным значением. |
См. также
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
Источники информации
- Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы. стр. 18
- Википедия, Матрица Кирхгофа