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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Матрицей Кирхгофа''' [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9_%D0%B3%D1%80%D0%B0%D1%84#.D0.BF.D1.80.D0.BE.D1.81.D1.82.D0.BE.D0.B9_.D0.B3.D1.80.D0.B0.D1.84 простого графа] <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}
Строка 10: Строка 10:
 
</tex>
 
</tex>
 
}}
 
}}
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении <tex>i</tex>-й строки и <tex>j</tex>-го столбца (<tex>i \ne j</tex>) стоит -1, если вершины с номерами <tex>i</tex> и <tex>j</tex> смежны, и 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"
 
!Граф
 
!Граф
Строка 30: Строка 31:
 
== Некоторые свойства ==
 
== Некоторые свойства ==
  
*Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).
+
* Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
 +
: <tex>\ \sum_{i=1}^{|V|} k_{i,j} = 0</tex>.
 +
* Определитель матрицы Кирхгофа равен нулю:
 +
: <tex>\det K=0</tex>
 +
* Матрица Кирхгофа простого графа симметрична:
 +
: <tex>\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|</tex>.
  
*Связь с матрицей смежности:  
+
*Связь с [[Матрица смежности графа|матрицей смежности]]:  
  
<tex> K =  
+
:<tex> K =  
 
\begin{pmatrix}
 
\begin{pmatrix}
 
deg(v_1) & 0 & \cdots & 0 \\
 
deg(v_1) & 0 & \cdots & 0 \\
Строка 45: Строка 51:
 
где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
 
где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
  
*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]: <tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
+
*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
 +
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
 +
*<tex>0</tex> является собственным значением матрицы, кратность его равна числу связных компонент графа.
  
  
 
==См. также==
 
==См. также==
 +
 
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
Строка 54: Строка 63:
 
==Источники==
 
==Источники==
  
''Асанов М., Баранский В., Расин В.'' — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.<br>
+
*Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы
[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
+
*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]

Версия 16:27, 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] является собственным значением матрицы, кратность его равна числу связных компонент графа.


См. также

Источники