Graph Theory Nedir?

Graph theory (çizgi kuramı), en basit ifadesiyle nesnesel yapıların aralarında bulunan ilişkiyi doğrusal ve noktasal formlarda modelleyen ve bu modellemeleri inceleyen matematik biliminin grafiklerle ilgilenen alt dalı olarak ifade edilebilir.

Graph theory, bahsedildiği üzere noktasal ve doğrusal formlarda bulunan matematiksel ifadeleri görsel diyagramlara dönüştürme sanatıdır. Bu teoride, evrensel olarak kenarların(edges) ve köşelerin(vertices) birbirleriyle olan ilişkileri incelenir ve çıkan ilişki sonucuna göre nesneler arasında ilişki çıkarımları yapılmaktadır. Şekilsel olarak çizgi kuramı grafikleri "E" ve "V" ifadelerinden oluşmaktadır.

"E" ifadesi edges (kenarlar) kelimesinin baş harfinden gelmektedir ve sonlu kenarlar kümesini ifade etmektedir.

"V" ifadesi vertices 'in (köşeler) kelimesinin baş harfinden gelmektedir ve sonlu köşeler kümesini ifade etmektedir.

Yukarıdaki resimde görüldüğü üzere 4 farklı bireyin birbirleri arasındaki ilişkiler bağlantıların belirgin olmasıyla grafikleştirilmiştir. Günümüzde bu grafikleşme genel olarak "ağ" yapıları olarak ifade edilmektedir. Bu bilgilden hareketle bazı bireylerin birbirleri arasında ağ bağlantıları mevcuttur. Bu bağlantılar sayesinde kişilerin birbirleri ile bağlantıları oldukça basit bir şekilde ifade edilmektedir. Örneğin; bu grafiğe göre Ahmet ile Ayşe arasında bir ilişkinin olduğu, ancak Ayşe ile Ali arasında direkt olarak bir ilişki olmadığı görülmektedir. Yani, buradan da anlaşılacağı üzere graph theory kullanılarak canlı veya cansız nesnelerin aralarındaki bağlantılar oldukça anlaşılır bir şekilde resmedilmektedir. 

Yukarıda bahsedildiği üzere standart olarak graph theory grafikleri "E" ve "V" ifadelerinden oluşmaktadır. Bu bağlamda "E" kenarları ve  "V" köşeleri ifade etmektedir ve bu resim üzerinde bu ifadelere bakıldığı zaman;

• Köşeler (vertices, vertex veya node): Grafikte yer alan canlı veya cansız nesneleri ifade etmektedir. Yani bu grafikte; V=4
• Kenarlar (edges veya link): Grafikte yer alan canlı veya cansız nesnelerin aralarındaki toplam ağ sayısını ifade etmektedir. Yani bu grafikte; E=5'dir.

Graph Theory Tarihi

Graph theorinin tarihi, günümüzde birçok bilim insanının kabulü dahilinde 1736 yıllarına dayanmaktadır. Bu tarihte İsviçreli matematikçi Leonhard Euler, günümüzde Königsberg'in yedi köprüsü olarak bilinen yapının problemini çözmeyi başarmıştır. Köprünün hikayesine kısaca bakacak olursak;

Bu köprü eski adı Königsberg(Almanca), ancak günümüzde Kaliningrad olarak bilinen Rusya'nın karaya sınırı olmayan bir şehridir. Bu şehrin merkezinden günümüzde Pregolya olarak bilinen nehir geçmektedir ve bu nehir Königsberg'i 4 parçaya ayırtmaktadır. Ayrılan bölgeleri birleştirebilmek için ise toplamda 7 farklı köprü bulunmaktadır. Graph theory'nin doğuşu ise, "bütün köprülerden yalnızca bir kez geçilerek yürüyüş yapılabilir mi?" sorusuna cevap ararken gerçekleşmiştir. 

1736 yılında İsviçreli matematikçi Leonhard Euler, bu köprüler üzerinde incelemeler gerçekleştirmiş ve bütün köprülerden yalnızca bir defa geçerek yürüyüşün gerçekleşmeyeceğini ispatlamıştır. Bu ispatın ardından Euler, bu yürüyüşün mümkün olduğunu ancak graflarda farklı özelleştirmelere ihtiyaç olacağını söylemiştir. Euler;

1. Genel köprü yapısına bakıldığında birleşik bir graf mevcut ise, bu grafların bütün elmanlarını yalnızca bir kez kullanarak turu tamamlamak için tek dereceli düğüm(node) sayıları eğer mevcut ise iki olmalıdır,
2. Tek dereceli değere sahip düğüm yapıları yürüyüşün başlangıç ve bitiş düğümleri olması gerekmektedir,
3. Eğer grafta böyle düğümler mevcut değilse, yürüyüşe herhangi bir düğümden başlanabilir.

gibi birbirini takip eden önermelerde bulunmuştur. Bu önermelerin temelinde Euler'in savunduğu düşünce;

1. Eğer herhangi bir düğüm başlangıç veya bitişi düğümü olmazsa, bu düğümlere gelen kişiler turlarını tamamlayabilmeleri için üzerinde bulundukları düğümden ayrılmaları gerekecektir. Bu ayrılmar sonucunda köprülerden sadece bir kez geçilerek tur tamamlanamayacağı(ayrılırsa çıkış yolu bulamaz) için, bu düğümlerin çift dereceli olması gerekmektedir.
2. Tek dereceli düğümler ya başlangıç noktası ya da bitiş noktası olarak seçilmelidir. Çünkü, turu yapacak kişi ikinci bir sefer gelişinde çıkış yolunu bulabilmesi gerekmektedir. 
3. Eğer tek dereceli düğüm sayısı ikiden fazla olursa, kişiler çıkış yolunu bulamaz ve tur başarılı bir şekilde tamamlanamaz. 
4. Sonuç olarak, 7 köprü üzerinde gerçekleşecek yürüyüşlerde, kişinin tekrardan başlangıç noktasına ulaşabilmesi için bütün düğümlerin çift dereceli olması gerekmektedir. Böylelikle, başlangıç ve bitiş düğümleri aynı olur, kişi sadece bir düğümden birkez geçmiş sayılır.

Sonuç olarak Euler'in sunmuş olduğu çözüm önerisi sonucunda graph theory'nin ilk kez gösterimi yapılmış ve böylelikle ilk temel atılmıştır.

Graph Theory Temel Bilgileri Nelerdir?

Yukarıda genel hatlarıyla graph theory hakkında temel bilgiler verilmiştir. Ancak bu bilgilerden farklı olarak graph theory sürecini derinlemesine incelemek gerekirse;

1. Nokta: Nokta en, boy veya derinliğe sahip olmayan, 1D,2D ve 3D alanlarda belirli konumlarda bulunan boyutsuz bir ifade olarak tanımlanabilir. 

 

2.Doğru: İki nokta arasındaki bağlantı olarak ifade edilebilir. 

  

3. Köşe (vertex, node): Birden fazla doğrunun birleşimi sonucunda oluşan nokta olarak ifade edilebilir.

4. Kenar (edge): En az iki farklı köşeyi birleştiren bir doğru veya çizgi olarak ifade edilebilir. Bir çizginin kenar olarak ifade edilebilinmesi için başlangıç ve bitiş tepe noktarına sahio olması gerekmektedir. 

 

5. Grafik: Son olarak bahsedilen bu yapıların bir araya gelmesiyle de grafikler meydana gelmektedir. Yani bir grafik: G=(V,E) ikili kümesinden oluşmaktadır.

  

6. Döngü (loop): Herhangi bir grafik yapısı üzerinde bulunan köşeden, tekrar kendisine bir kenar çizilirse bu durum döngü olarak ifade edilmektedir.

 

7. Ark (arc): Grafikte yapılarında yönlendirilmiş çizgi olarak ifade edilmektedir. 

8. Bitişik Köşeler (Adjacent vertices): Grafik yapısında herhangi bir kenar ile birbirlerine bağlanan köşeler olarak ifade edilebilir.

  

9. Derece (degree): Derece en basit ifadesiyle, tepe noktasına bağlanan kenarların sayı olarak ifade edilebilir. Ayrıca, eğer teoe noktasında bir döngü mevcut ise derece iki kez sayılır.

 

10. Öncel (predecessor ): Bir grafikte tepe noktasından önceki düğüm(node) olarak ifade edilebilir.

 

11. Ardıl (successor): Herhangi bir grafikte berlirlenmiş tepe noktasını izleyen düğüm(node) olarak ifade edilebilir.

 

12. Yürüyüş veya Dolaşmak (walk): Grafikte herhangi bir tepe noktası ile başlayıp biten ve birbirlerini izleyen köşe ve kenar dizilerinden oluşan bir yapı olarak ifade edilebilir.

• Circuit: Her kenarı farklılık gösteren kapalı bir yürüyüş olarak ifade edilebilir.
• Closed walk: Bir tepe noktasından başlayıp, tekrardan kendisine doğru yürüyüş olarak tanımlanabilir. Yani bu durum; aynı yerde başlayıp bitme olarak ifade edilebilir.
• Cycle: Herhangi bir tekrarlama gösteren köşeleri olmayan kapalı bir yürüyüş olarak ifade edilebilir.
• Path: Herhangi bir tekrarlanan köşelerin bulunmadığı bir yürüyüş olarak ifade edilebilir.
• Trail: Tüm kenarların farklı olduğu bir yürüyüş olarak ifade edilebilir.