Kirchoff Teoremi (Kirchoff Theorem)

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 λ₁ , λ₂ , … , λ_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ı = (λ₀ λ₁ λ₂ … λ_n-1)/n

Yukarıdaki bu değer aynı zamanda laplas matrisinin herhangi bir kofaktör (cofactor) değerinin mutlak değerine eşittir.

« Laplas Matrisi (Laplacian Matrix) | Chomsky Normal Şekili (Chomsky Normal Form) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Kirchoff Teoremi (Kirchoff Theorem)' isimli yazı 19 Jun 2009 tarihinde, saat: 00:44 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 435 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, graf teorisi (graph theory, çizge kuramı) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar