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:

bipartite11

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.

Yorumlar

  1. emre

    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

  2. Şadi Evren ŞEKER Article Author

    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

  3. banu demet

    peki laplacian matrix te özdeğerlerden biri daima sıfırdır neden? bunun ispatını bilen bana ulaşırsa çok sevinicem

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir