Матрица Кирхгофа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 53: Строка 53:
 
*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:  
 
*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:  
 
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
 
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
*<tex>0</tex> является собственным значением матрицы, кратность его равна числу связных компонент графа.
+
*<tex>0</tex> является собственным значением матрицы, кратность его равна числу компонент связности графа.
  
  

Версия 16:32, 29 декабря 2014

Определение:
Матрицей Кирхгофа простого графа [math]G = (V,E) [/math] называется матрица [math] K (|V| \times |V|) = \parallel k_{i,j} \parallel [/math], элементы которой определяются равенством: [math] k_{i,j} = \begin{cases} \deg(v_i), \ i = j \\ -1, \ (v_i,v_j) \in E \\ 0, \mbox{ otherwise}. \end{cases} [/math]

Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении [math]i[/math]-й строки и [math]j[/math]-го столбца ([math]i \ne j[/math]) стоит [math]-1[/math], если вершины с номерами [math]i[/math] и [math]j[/math] смежны, и [math]0[/math] в противном случае.

Пример матрицы Кирхгофа

Граф Матрица Кирхгофа
Kirhgof matrix 1.png [math]\left(\begin{array}{rrrrrr} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\\ \end{array}\right)[/math]

Некоторые свойства

  • Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
[math]\ \sum_{i=1}^{|V|} k_{i,j} = 0[/math].
  • Определитель матрицы Кирхгофа равен нулю:
[math]\det K=0[/math]
  • Матрица Кирхгофа простого графа симметрична:
[math]\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|[/math].
[math] K = \begin{pmatrix} deg(v_1) & 0 & \cdots & 0 \\ 0 & deg(v_2) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & deg(v_n) \end{pmatrix} - A, [/math]

где [math]A[/math] — матрица смежности графа [math]G[/math].

[math] K = I \cdot I^T, [/math] где [math]I[/math] — матрица инцидентности некоторой ориентации графа.
  • [math]0[/math] является собственным значением матрицы, кратность его равна числу компонент связности графа.


См. также

Источники