Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinin de arasında bulunduğu pek çok bilim ve mühendislik alanında kullanılan graf teorisinde kullanılan bir teoremdir. Bu teorem kirchoff matrisi veya laplas matrisi (laplacian matrix) ismi verilen matrisler ile birlikte kullanıldığında bir grafta bulunan asgari tarama ağacı (minimum spanning tree) sayısını verir.
Bilindiği (veya ilgili yazıdan okunabileceği) üzere laplas matrisleri diyagonda graftaki düğümlerin (nodes), düğüm derecelerini (node order) ve geri kalan elemanlarda da düğümlerin komşuluk listelerini (adjacency list) veren matrislerdir.
Kirchoff teoremine göre bir graftaki n tane düğüm (node) için laplas matrisinden çıkarılan ve sıfırdan farklı olan λ1 , λ2 , … , λn-1 şeklinde özdeğerler (eigen values) bulunsun. Bu durumda bu grafta bulunabilecek asgari tarama ağacı (minimum spanning tree) sayısı aşağıdaki şekilde bulunur:
farklı asgari tarama ağacı sayısı = (λ0 λ1 λ2 … λn-1)/n
Yukarıdaki bu değer aynı zamanda laplas matrisinin herhangi bir kofaktör (cofactor) değerinin mutlak değerine eşittir.