Кирхгофын теорем. Тэлэх модны тоог олох¶
Бодлого: Танд adjacency matrix ашиглан илэрхийлсэн холбоост чиглэлгүй граф (олон ирмэгтэй байж болно) өгөгдсөн. Энэ графын ялгаатай тэлэх модны тоог ол.
Дараах томьёог 1847 онд Кирхгоф баталсан.
Кирхгофын матриц-модны теорем¶
$A$ нь графын adjacency matrix байг: $A_{u,v}$ нь $u$ ба $v$-ийн хоорондох ирмэгийн тоо юм. $D$ нь графын зэргийн матриц байг: $D_{u,u}$ нь $u$ оройн зэрэг (олон ирмэг ба гогцоо буюу $u$ оройг өөртэй нь холбох ирмэгүүдийг оруулаад) байх диагональ матриц.
Графын Лапласын матрицыг $L = D - A$ гэж тодорхойлно. Кирхгофын теоремын дагуу энэ матрицын бүх алгебрийн гүйцээлт хоорондоо тэнцүү бөгөөд тэдгээр нь графын тэлэх модны тоотой тэнцүү байна. Матрицын $(i,j)$ алгебрийн гүйцээлт гэдэг нь $i$-р мөр ба $j$-р баганыг хассаны дараа гарах матрицын тодорхойлогчийг $(-1)^{i + j}$-тэй үржүүлсэн үржвэр юм. Тиймээс та жишээ нь $L$ матрицын сүүлийн мөр ба сүүлийн баганыг устгаж болох ба гарсан матрицын тодорхойлогчийн үнэмлэхүй утга танд тэлэх модны тоог өгнө.
Матрицын тодорхойлогчийг Гауссын аргаар $O(N^3)$-д олж болно.
Энэ теоремын баталгаа нэлээд хэцүү бөгөөд энд оруулаагүй; баталгааны тойм ба олон ирмэггүй граф, чиглэлтэй графын хувьд теоремын хувилбаруудыг Википедиагаас үзнэ үү.
Кирхгофын хэлхээний хуультай холбоо¶
Кирхгофын матриц-модны теорем ба цахилгаан хэлхээний Кирхгофын хуулиуд гоё байдлаар холбогддог. (Омын хууль ба Кирхгофын нэгдүгээр хуулийг ашиглан) хэлхээний $i$ ба $j$ гэсэн хоёр цэгийн хоорондох эсэргүүцэл $R_{ij}$ нь дараах болохыг харуулах боломжтой
Энд $L$ матрицыг Кирхгофын матриц-модны теоремд тайлбарласан үйл ажиллагааг ашиглан урвуу эсэргүүцлийн $A$ матрицаас ($A_{i,j}$ нь $i$ ба $j$ цэгүүдийн хоорондох дамжуулагчийн эсэргүүцлийн урвуу) авна. $T^j$ нь $j$ мөр ба баганыг хассан матриц, $T^{(i,j)}$ нь $i$ ба $j$ гэсэн хоёр мөр, хоёр баганыг хассан матриц юм.
Кирхгофын теорем энэ томьёонд геометрийн утга өгдөг.