Laplacen matriisi

Verkkoteoriassa Laplacen matriisi eli Kirchhoffin matriisi on verkon matriisiesitys. Tätä voidaan käyttää verkon virittäjäpuun laskemiseen.

Määritelmä

Verkon G Laplacen matriisi on määritelmän mukaan

$L:=D-A,$

missä D on G:n astematriisi ja A on G:n vierusmatriisi.

Tarkemmin, olkoon G annettu n-solmuinen verkko. Tällöin

$L_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{jos}}\ i=j\\-1&{\mbox{jos}}\ i\neq j\ {\mbox{ja}}\ v_{i}\ {\mbox{ja}}\ v_{j}\ \mathrm {vierekk{\ddot {a}}iset} {\mbox{ solmut}}\\0&{\mbox{muulloin}}\end{matrix}}\right.$

Suunnatuille verkoille voidaan käyttää joko särmien sisä- tai ulkoastetta tilanteesta ja sovelluksesta riippuen.