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