Laplas Matrisi (Laplacian Matrix)


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.


« Düğüm Derecesi (Order of Node)   |   Kirchoff Teoremi (Kirchoff Theorem) »



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Toplam 4 yorum var.

  1. emre | 28 Jun 2009, 00:00

    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 | 28 Jun 2009, 01:08

    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. Şadi Evren ŞEKER | 28 Jun 2009, 01:56

    İstediğiniz kodları Masfuf (matrix) başlıklı konu altında yazdım.

    Umarım yardımcı olur.
    Başarılar

  4. emre | 28 Jun 2009, 09:04

    yardımcı oldugunuz için teskkr ederim

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Laplas Matrisi (Laplacian Matrix)' isimli yazı 18 Jun 2009 tarihinde, saat: 02:56 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 543 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), 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
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar