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.

Bir cevap yazın

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