Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Graph Teorisi’ne giriş yapacağız.
Graph Teorisi – Graph Nedir?
Garph nedir? Garph’a ihtiyacımız var mıdır? Örnek olarak Facebook’u düşünün. Milyonlarca insanın birbirleri ile arkadaşlık bağları kurduğu bir sosyal ortam. Bütün bu ilişkilere çizge deniyor. Her insan bu graph’ın bir düğümü (node) ve her bağlantı bu çizgenin kenarıdır (edge). Bu örnekteki garph çift yönlüdür. Çünkü, eğer A kişisi B kişisiyle arkadaş ise B kişisi A kişisiyle de arkadaştır. Bir graph sonlu bir düğüm (node) dizisinin birleşimi ve sonlu bir kenar (edge) ikililerinin birleşiminden oluşmaktadır. Örneğin (u, v), u düğümünü v düğümüne bağlayan bir kenarı ifade etmektedir. Eğer graph çift yönlü ise (u, v) ile (v, u) aynıdır.
Sık kullanılan kavramların Türkçesini ve İngilizcesini verdikten sonra yazının devamında İngilizce karşılıklarını kullanmanın daha doğru olacağını düşünüyorum. Çünkü bu konu hakkında akademik yazılarda sürekli İngilizce karşılıklarını göreceğimiz için baştan öyle öğrenmek daha sağlıklı. Öbür türlü Türkçesini öğrendiğimizde kafa karışıklığına yol açabiliyor.
Eğer bir graph’ta bir node’dan çıkıp o node’a tekrar geri dönen bir yol var ise buna döngü (loop) deriz.
Yukarıdakı graph örneğinde mesela herhangi bir node’dan başlayıp tekrar aynı node’a gelebileceğimiz için bu bir loop’a örnektir.
Özel Graph’lar
Graph Teorisinde çok fazla özel graph’lar vardır. Bunlar arasından en çok kullanılan ağaç (tree) hakkında konuşalım biraz. Tree’nin tanımı “Eğer bir graph’ta hiç loop yoksa ve her bir node arasında tam olarak bir tane yol var ise buna tree denir.” Biraz karışık gelmiş olabilir ancak kavramların anlamını bildikten sonra o kadar da zor olmadığını göreceksiniz.
Yukarıda ağaç örneği görüyorsunuz. Hiçbir şekilde bir node’dan başlayıp tekrar o node’a gelemiyorsunuz yani loop yok. Aynı zamanda her iki node arasında tam olarak bir yol bulunmakta. Bu iki özellik birçok problemin çözümünde bize çok yardımcı oluyor. Aslında graph’lara böyle özellikler ekleyip onları özelleştirmenin temel amacı problemimizin çözümüne uygun hale getirmek.
Somut bir örnek vermek gerekirse bir kargo aracının izleyeceği güzergah graph şeklinde olursa eğer loop olabileceğinden dolayı gereksiz yakıt harcanımına yol açabilir. O yüzden en verimli şekilde kargo güzergahı planlamak için tree kurallarına uyan graph kullanmamız gerek.
Graphların Gösterimi
1- Komşuluk Matrisi
A[i][j]’yi A matrisinin i. satırnın j. sütunu olarak ifade edelim. Eğer A[i][j] 1 ise i düğümü ile j düğümü arasında bir kenar vardır.
Şimdi bunun komşuluk matrisini hesaplayalım
A B C D E
A 0 1 0 1 1
B 1 0 1 0 0
C 0 1 0 1 0
D 1 0 1 0 0
E 1 0 0 0 0
Bu yönsüz bir graph olduğu için yani A’dan B’ye yol varsa B’den A’ya da yol vardır tanımını sağladığı için matrisimizi simetrik olmuş oldu. Ancak yönsüz graph’larda böyle olmak zorunda değildir.
2. Komşuluk Listesi
Dikkat ettiyseniz matriste çok fazla 0 vardı. Bilgisayarda depolama yaparken hafızayı olabildiğince verimli kullanmamız gerek. Bu nedenle 0’ları tutmak yerine sadece 1’leri tutmak için komşuluk listesi yöntemini kullanıyoruz. Burada ise her bir node için bir vektör’e (dizi olarak düşünebiliriz) komşularını ekliyoruz.
a -> b,e,d
b -> a,c
c -> b,d
d -> a,c
Böylece çok daha az hafıza tutarak graph’ı depolamış oluyoruz.
Bu yazımızda Graph Teorisi‘ne giriş yaparak gösterimi ve bilgisayarda depolanma yöntemlerinden bahsettik. Okuduğunuz için teşekkür ederim umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.
Tüm Algoritma Derslerimiz İçin tıklayınız.
44