Изменения

'''Матрицей Кирхгофа''' [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 def_simple_graph|простого графа]] <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel </tex>, элементы которой определяются равенством: <tex>

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

* Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:: <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 = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.*<tex>0</tex> является собственным значением матрицы, кратность его равна числу связных компонент графа.

''*Асанов М., Баранский В., Расин В.'' — : Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.<br>*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]