Prüfer Dizilimi (Prüfer Sequence)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimleri de dahil olmak üzere pek çok bilim ve mühendislik alanının ortak çalışma konularından birisi olan graf teorisindeki (graph theory) bir hesaplama veya gösterim algoritmasıdır.

Ağaç (tree) yapısındaki graflar için yani dairesel olmayan graflar (acyclic graphs) için kullanılabilir. Daha basit bir ifade ile şeklin (graph) yaprakları (leaf) bulunmalıdır.

Prüfer diziliminin altında yatan sorun bir ağacın bir sayı dizisi ile nasıl gösterileceğidir. Yani bir grafta birbirine bağlı düğümler (nodes) olduğunu ve bu graf yapısını bir şekilde sayılarla göstermek (veya dizi (array) ) istediğimizi düşünelim.

Örneğin aşağıdaki şekli (graph) ele alalım:

prufer

şekildeki grafta toplam 11 düğüm (node) bulunmaktadır ve şekilde graf yönsüz graftır (undirected graph) aynı zamanda da döngü (cycle) bulundurmaz.

Bu durumda yukarıdaki şekli prüfer dizilimi olarak göstermek mümkündür.

Algoritmamız son iki düğüm kalana kadar çalışır. Bu durumda önce yapraklardan başlanarak işlem yapıyoruz. Yukarıdaki grafı yapraklardan köke doğru artan sayılar ile bu yüzden numaralandırdık.

Sırasıyla her düğümün bağlı olduğu diğer üst düğümü yazıyoruz.

Bu durumda aşağıdaki düğümler yapraklardır ve bağlı oldukları üst düğümler yanlarında verilmiştir:

1 → 6

2 → 4

3 → 5

Yukarıdaki yapraklardan başlayarak bu dizilimi not ediyoruz. Yani şimdilik prüfer dizilimimizde 645 bulunuyor. İkinci adımda bu yaprakları şekilden (graph) kaldırıyoruz.

prufer2

Şeklin yeni halindeki yaprakları not edeceğiz ancak son iki düğüm kalınca duracağımız için yeni şekilden sadece bir düğümü alıyoruz. Bu düğümde numara sırasına göre (tamamen tesadüfen) 4 oluyor

4 → 5

şeklinde son sayımızı da not ettikten sonra prüfer dizilimimizdeki sayılar 6455 olarak kaydedilmiş oluyor.

Artık iddia edebiliriz ki 6455 sayı serisinden (sequence) 6 ve 5 düğümlerini bilerek yukarıdaki şekli (graph) geri çizebiliriz.

Bu iddianın tatbiki oldukça basittir. 6 ve 5′ten oluşan bir şekil çizilir ve ardından prüfer dizilimi tersten okunarak sırasıyla yeni düğümler (nodes) şekle eklenir.

« Sıfır Bilgi İspatı (Zero-Knowledge proof) | Malümat İfadesi (Knowledge Representation) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Prüfer Dizilimi (Prüfer Sequence)' isimli yazı 22 Jun 2009 tarihinde, saat: 16:11 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 318 defa okunmuştur.

Benzer yazıları 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