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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации)
(не показаны 24 промежуточные версии 6 участников)
Строка 1: Строка 1:
== Определение матрицы Кирхгофа ==
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Матрицей Кирхгофа''' простого графа <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel  </tex>, элементы которой определяются равенством: <tex>
+
'''Матрицей Кирхгофа''' [[Основные определения теории графов#def_simple_graph|простого графа]] <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel  </tex>, элементы которой определяются равенством: <tex>
 
k_{i,j} =  
 
k_{i,j} =  
 
\begin{cases}
 
\begin{cases}
 
\deg(v_i), \ i = j \\
 
\deg(v_i), \ i = j \\
 
-1, \ (v_i,v_j) \in E \\
 
-1, \ (v_i,v_j) \in E \\
0, \mbox{ else}.
+
0, \mbox{ otherwise}.
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
 
}}
 
}}
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца (<tex>i \ne j</tex>) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае.
+
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении <tex>i</tex>-й строки и <tex>j</tex>-го столбца (<tex>i \ne j</tex>) стоит <tex>-1</tex>, если вершины с номерами <tex>i</tex> и <tex>j</tex> смежны, и <tex>0</tex> в противном случае.
  
 
== Пример матрицы Кирхгофа==
 
== Пример матрицы Кирхгофа==
Пример матрицы Кирхгофа простого графа.
+
 
 
{|class="wikitable"
 
{|class="wikitable"
![[Помеченный граф]]
+
!Граф
 
!Матрица Кирхгофа
 
!Матрица Кирхгофа
 
|-
 
|-
|[[image:6n-graf.svg|175px]]
+
|[[Файл:Kirhgof_matrix_1.png|200px]]
|<math>\left(\begin{array}{rrrrrr}
+
|<tex>\left(\begin{array}{rrrrrr}
 
  2 & -1 &  0 &  0 & -1 &  0\\
 
  2 & -1 &  0 &  0 & -1 &  0\\
 
-1 &  3 & -1 &  0 & -1 &  0\\
 
-1 &  3 & -1 &  0 & -1 &  0\\
Строка 28: Строка 26:
 
-1 & -1 &  0 & -1 &  3 &  0\\
 
-1 & -1 &  0 & -1 &  3 &  0\\
 
  0 &  0 &  0 & -1 &  0 &  1\\
 
  0 &  0 &  0 & -1 &  0 &  1\\
\end{array}\right)</math>
+
\end{array}\right)</tex>
 
|}
 
|}
  
 +
== Некоторые свойства ==
 +
 +
{{Утверждение
 +
|statement=Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
 +
: <tex>\ \sum_{i=1}^{|V|} k_{i,j} = 0</tex>.
 +
}}
  
== Некоторые свойства ==
+
{{Утверждение
 +
|statement=Определитель матрицы Кирхгофа равен нулю:
 +
: <tex>\det K=0</tex>
 +
|proof=<tex>  \det K =  
 +
\begin{vmatrix}
 +
k_{1, 1} & k_{1, 2} & \cdots & k_{1, |V|} \\
 +
k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}
 +
\end{vmatrix}
 +
</tex>
 +
 
 +
Прибавим к первой строке все остальные строки (это не изменит значение определителя):
 +
 
 +
<tex>\begin{vmatrix}
 +
k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} \\
 +
k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}
 +
\end{vmatrix}
 +
</tex>
 +
 
 +
Так как сумма элементов каждого столбца равна <tex>0</tex>, получим:
  
1) Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).
+
<tex>\det K = \begin{vmatrix}
 +
0 & 0 & \cdots & 0 \\
 +
k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}
 +
\end{vmatrix} = 0
 +
</tex>
 +
}}
  
2) Связь с матрицей смежности:  
+
{{Утверждение
 +
|statement=Матрица Кирхгофа простого графа симметрична:
 +
: <tex>\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|</tex>.
 +
}}
  
<tex> K =  
+
{{Утверждение
 +
|statement=Связь с [[Матрица смежности графа|матрицей смежности]]:
 +
:<tex> K =  
 
\begin{pmatrix}
 
\begin{pmatrix}
deg(v_1) & 0 & \cdots & 0 \\
+
\mathrm{deg}(v_1) & 0 & \cdots & 0 \\
0 & deg(v_2) & \cdots & 0 \\         
+
0 & \mathrm{deg}(v_2) & \cdots & 0 \\         
 
\vdots & \vdots & \ddots & \vdots \\
 
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & deg(v_n)
+
0 & 0 & \cdots & \mathrm{deg}(v_n)
 
\end{pmatrix} - A,
 
\end{pmatrix} - A,
 
</tex>  
 
</tex>  
 +
где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
 +
}}
 +
 +
{{Утверждение
 +
|statement=[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
 +
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
 +
}}
 +
 +
{{Утверждение
 +
|statement=<tex>0</tex> является [[Собственные векторы и собственные значения|собственным значением]] матрицы, кратность его равна числу [[Отношение связности, компоненты связности|компонент связности]] графа.
 +
|proof=Собственным значением матрицы называют значения <tex>\lambda</tex>, которые удовлетворяют уравнению:
 +
 +
<tex>\begin{vmatrix}
 +
k_{1, 1} - \lambda &k_{1, 2} & \cdots & k_{1, |V|} \\
 +
k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V| - \lambda}
 +
\end{vmatrix} = 0
 +
</tex>
 +
 +
Прибавим к первой строке все остальные строки (это не изменит значение определителя):
 +
 +
<tex>\begin{vmatrix}
 +
k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} - \lambda & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} - \lambda & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} - \lambda \\
 +
k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda
 +
\end{vmatrix}
 +
</tex>
 +
 +
Так как сумма элементов каждого столбца равна <tex>0</tex>, получим:
 +
 +
<tex>\begin{vmatrix}
 +
- \lambda &-\lambda & \cdots & - \lambda \\
 +
k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda
 +
\end{vmatrix} = 0
 +
</tex>
 +
 +
<tex>- \lambda
 +
\begin{vmatrix}
 +
1 & 1 & \cdots & 1 \\
 +
k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\       
 +
\vdots & \vdots & \ddots & \vdots \\
 +
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda
 +
\end{vmatrix}= 0.
 +
</tex>
 +
 +
Следовательно, <tex>0</tex> является собственным значением.
 +
 +
'''Доказательство кратности:'''
 +
 +
Пусть дан граф <tex>G</tex> c <tex>n</tex> компонентами связности. Перенумеруем его вершины так, чтобы сначала шли вершины первой компоненты связности, затем второй и т.д. Тогда матрица Кирхгофа примет блочно-диагональный вид, и <tex>i</tex>-тый блок этой матрицы будет являтся матрицей Кирхгофа для <tex>i</tex>-той компоненты связности.
 +
 +
Из свойства блочно-диагональной матрицы <tex>\det K = \det K_{1} \cdot \det K_{2} \cdot \ldots \cdot \det K_{n}</tex>, где <tex>K_{i}</tex> — матрица Кирхгофа для <tex>i</tex>-той компоненты связности, и свойства, доказанного выше,
 +
 +
<tex>\det K_{i} = - \lambda \cdot det X_{i} \quad \Rightarrow \quad \det K = (-1)^{n} \cdot \lambda^{n} \cdot \det X_{1} \cdot \det X_{2} \cdot \ldots \cdot \det X_{n}</tex>
 +
}}
  
где <tex>A</tex> - матрица смежности графа <tex>G</tex>.
+
==См. также==
  
3) [[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]: <tex> K = I \cdot I^T, </tex> где <tex>I</tex> - матрица инцидентности с некоторой ориентацией.
+
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 +
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
  
==Источники==
+
==Источники информации==
  
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
+
*Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы. стр. 18
 +
*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия — Матрица Кирхгофа]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
+
[[Категория: Остовные деревья]]
 +
[[Категория: Свойства остовных деревьев ]]

Версия 21:00, 7 сентября 2015

Определение:
Матрицей Кирхгофа простого графа [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]\triangleright[/math]

[math] \det K = \begin{vmatrix} k_{1, 1} & k_{1, 2} & \cdots & k_{1, |V|} \\ k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} \end{vmatrix} [/math]

Прибавим к первой строке все остальные строки (это не изменит значение определителя):

[math]\begin{vmatrix} k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} \\ k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} \end{vmatrix} [/math]

Так как сумма элементов каждого столбца равна [math]0[/math], получим:

[math]\det K = \begin{vmatrix} 0 & 0 & \cdots & 0 \\ k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} \end{vmatrix} = 0 [/math]
[math]\triangleleft[/math]
Утверждение:
Матрица Кирхгофа простого графа симметрична:
[math]\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|[/math].
Утверждение:
Связь с матрицей смежности:
[math] K = \begin{pmatrix} \mathrm{deg}(v_1) & 0 & \cdots & 0 \\ 0 & \mathrm{deg}(v_2) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathrm{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] является собственным значением матрицы, кратность его равна числу компонент связности графа.
[math]\triangleright[/math]

Собственным значением матрицы называют значения [math]\lambda[/math], которые удовлетворяют уравнению:

[math]\begin{vmatrix} k_{1, 1} - \lambda &k_{1, 2} & \cdots & k_{1, |V|} \\ k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V| - \lambda} \end{vmatrix} = 0 [/math]

Прибавим к первой строке все остальные строки (это не изменит значение определителя):

[math]\begin{vmatrix} k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} - \lambda & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} - \lambda & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} - \lambda \\ k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda \end{vmatrix} [/math]

Так как сумма элементов каждого столбца равна [math]0[/math], получим:

[math]\begin{vmatrix} - \lambda &-\lambda & \cdots & - \lambda \\ k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda \end{vmatrix} = 0 [/math]

[math]- \lambda \begin{vmatrix} 1 & 1 & \cdots & 1 \\ k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\ k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda \end{vmatrix}= 0. [/math]

Следовательно, [math]0[/math] является собственным значением.

Доказательство кратности:

Пусть дан граф [math]G[/math] c [math]n[/math] компонентами связности. Перенумеруем его вершины так, чтобы сначала шли вершины первой компоненты связности, затем второй и т.д. Тогда матрица Кирхгофа примет блочно-диагональный вид, и [math]i[/math]-тый блок этой матрицы будет являтся матрицей Кирхгофа для [math]i[/math]-той компоненты связности.

Из свойства блочно-диагональной матрицы [math]\det K = \det K_{1} \cdot \det K_{2} \cdot \ldots \cdot \det K_{n}[/math], где [math]K_{i}[/math] — матрица Кирхгофа для [math]i[/math]-той компоненты связности, и свойства, доказанного выше,

[math]\det K_{i} = - \lambda \cdot det X_{i} \quad \Rightarrow \quad \det K = (-1)^{n} \cdot \lambda^{n} \cdot \det X_{1} \cdot \det X_{2} \cdot \ldots \cdot \det X_{n}[/math]
[math]\triangleleft[/math]

См. также

Источники информации