Yazan : Şadi Evren ŞEKER
Bu yazının amacı, şekil teorisinde (graph theory) kullanılan sargısız ağaç (unwrapped tree) kavramını açıklamaktır. Şekil teorisi üzerine kurulu pek çok çalışmada sıkça geçmekte olan bu kavram, basitçe şeklin ifade ettiği değerlerin sadeleştirilmesi ve şekildeki döngülerin açılarak şeklin bir ağaca dönüştürülmesinden ibarettir.
Konuyu basit bir döngüyü (cycle) açarak anlamaya başlayalım:
Yukarıdaki şekli sargısız hale getirmek için öncelikle bir düğüm seçilerek işe başlanır. Biz örneğimizde A düğümünü (node) kök düğüm (root) olarak seçerek başlayalım ve bu düğümün komşuluk ilişkisini bir ağaç şeklinde gösterelim:
Şekilde görüldüğü üzere A düğümü ve bu düğümün komşuları ile olan ilişkisi modellenmiştir. Bu ilişkide daha sonra tekrar edecek düğümleri karıştırmamak için düğümlere isimlerinin yanında bir de sayılar ekleyelim:
Şimdi yukarıda, komşuluk ilişkileri henüz işaretlenmemiş olan D1 ve B1 düğümlerinin de komşularını işaretleyelim. Bu işaretleme sırasında dikkat edeceğimiz bir husus, orjinal şeklimizde olan ve D-A ve B-A bağlantılarının geldiğimiz yön itibariyle şeklin son halinde ifade ediliyor olduğudur. Yani zaten D ve B düğümlerine, D-A ve B-A kenarlarını dolaşarak geldik. Bu gelinen kenarlardan bir kere daha geçmiyoruz. Dolayısıyla bu ilişkiler ikinci kere gösterilmez. Bunun yerine henüz gösterilmemiş olan D-C ve B-C ilişkilerini gösteriyoruz.
Şekilde iki farklı C değeri bulunduğu için ikisini de farklı sayılar ile ifade ettik. Zaten bu noktada dikkat edilirse bir şeklin nasıl sargısız hale getirildiği anlaşılır. Yani her farklı komşuluk düğüm kopyalaması ile farklı bir ilişki olarak ifade edilmiştir. Aynı yaklaşımla devam edersek, aşağıdaki şekli elde ederiz:
Şeklin bu son halinde iki yolu sırasıyla yazacak olursak,
A-D-C-B yolu solda
A-B-C-D yolu ise sağda görülmektedir. Devam edelim:
Son halinde şekil yeniden A düğümüne ulaşmıştır. Bu noktada bazı kaynaklar durarak bu sargısız hale getirmenin yeterli olduğunu savunur ve bu açılmış şekil üzerinden işlem yapar. Bazı kaynaklar ise sonsuza kadar giden bir zincir (yol, path, chain) oluştuğunu kabul eder.
Kısacası, şekil, başlangıç düğümüne gelinene kadar iki farklı yönde dönülüyor:
Yukarıdaki şekilde görülen saat yönündeki dönme neticesinde, sargısız düğümün sağ kolu ve bu yönün tam tersi istikametteki dönme neticesinde de sargısız şeklin sol kolundaki yol (path) ortaya çıkmaktadır.
Yukarıdaki açılımı basit bir döngü (single cycle) için yaptık ancak birden fazla döngü bulunması hali de incelemeye değer. Örneğin aşağıdaki şekli ele alalım:
Bu yeni şekilde, tahmin edileceği üzere oldukça büyük bir ağaç çıkacaktır. Bu yüzden bir iki seviye ilerleyerek ağacın nasıl açılıdğını gösterip bırakacağım. Başlangıç düğümü olarak (kök düğüm, root) A seçiyorum. Bu düğümün farklı şekillerde seçilebileceğini hatırlayınız:
Şekli ilerletirsek, aşağıdaki gibi bir durum ile devam ederiz:
Elbette şeklin, bundan sonra da ilerletilmesi mümkündür ancak şekil bir iki seviyede çok hızlı bir şekilde genişlemektedir, konunun anlaşıldığını düşünerek bu seviyede kesiyorum.