Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinin de içinde bulunduğu pekçok bilim ve mühendislik alanında kullanılan graf teorisi (graph theory) açısından önemli bir matristir. Laplas matrisinin özelliği her düğümün derecesini (node order) ve diğer düğümlerle olan komşuluk ilişkisini (adjacency list) tutmasıdır.
Laplas matrisine giriş matrisi (admittance matrix) veya Kirchhoff matirisi ( Kirchhoff matrix ) isimleri de verilmektedir. Kirchhoff teorsi ( Kirchhoff theory ) ile birlikte kullanılınca bir graftaki birbirinden farklı asgari tarama ağacı (minimum spanning tree) sayısını elde etmekte kullanılabilir.
Laplas matrisinin tanımı
Laplas matrisi bir grafta bulunan düğüm sayısı kadar boyutlara sahip kare matristir. Düğüm sayısı n olan bir graf için nxn boyutlarında bir matris aşağıdaki şartlara göre üretilir.
i=j -> düğümün derecesi (node order)
i≠j -> i. düğümün j. düğümle olan komşuluğu (komşuluk varsa -1 yoksa 0)
Yukarıdaki kurallardan anlaşılacağı üzere matrisin köşegeninde (diagon) düğüm dereceleri ve matrisin geri kalanında ise -1 ve 0’dan oluşan komşuluk matrisi bulunacaktır.
Laplas matrisine örnek
Örneğin aşağıdaki grafın laplas matrisini oluşturmak isteyelim:
Yukarıdaki şekilde 11 düğüm bulunmaktadır. Bu durumda 11×11 boyutlarında bir matris (masfuf) oluşturarak tanımımızda verilen kurallara uygun bir şekilde matrisin değerlerini dolduralım:
| A | B | C | D | E | F | G | H | I | J | K | |
| A | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
| B | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
| C | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
| D | 0 | 0 | 0 | 1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| E | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | -1 | -1 | 5 | 0 | 0 | -1 | 0 | -1 |
| G | 0 | 0 | 0 | 0 | 0 | -1 | 2 | -1 | 0 | 0 | 0 |
| H | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 |
| I | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 2 | -1 | 0 |
| J | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 |
| K | -1 | -1 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 4 |
Yukarıdaki tablodan açıkça görülebileceği üzere laplas matrisinin bir özelliğide satır bazında ve sütün bazında toplamların 0 olmasıdır.
Laplas matrisinin özellikleri
G ismindeki bir graf ve L ismindeki bir Laplas matrisinin λ0 ≤ λ1 ≤ λ2 ≤ … ≤ λn-1 koşullarını sağlayan özdeğerleri (eigen values) için aşağıaki özellikler sayılabilir:
Şayet laplas matrisinin bütün özdeğerleri (eigenvalues) sıfırdan büyükse bu matris için Hermitian matris denilebilir
λ0 her zaman 0’dır.
λ1 matematiksel bağlılığı (algebraic connectivity) gösterir
Özdeğerlerin 0 olma sayısı G grafındaki bağlı düğüm sayısını verir.
c ++ builder da matris işlemleri (toplma çıkarma birim matris işlemlerinin) kodlarını yazmak istiyorum araştırdım bi türlü bulamıyorum yardımcı olabilirmisiniz
Elbette oluruz ancak yorum buraya çok uygun değil o yüzden matrisler diye yeni bir başlık yazıp onun altında açıklayayım (sanırım 1 saate kadar yayınlamış olurum)
başarılar
İstediğiniz kodları Masfuf (matrix) başlıklı konu altında yazdım.
Umarım yardımcı olur.
Başarılar
yardımcı oldugunuz için teskkr ederim
peki laplacian matrix te özdeğerlerden biri daima sıfırdır neden? bunun ispatını bilen bana ulaşırsa çok sevinicem
Çünkü satır toplamı 0 her satır için o halde 0 özdeğer olur.