Graf teorisi, matematiksel bir dal olarak graf adı verilen yapıların ve bu yapılar üzerinde yapılan çeşitli analizlerin incelendiği bir alandır. Bazen hiç beklemediğiniz anlarda bu teori karşınıza gelir. Mesela bu şekli elini hiç kaldırmadan ve bir kenarın üstünden sadece bir kere geçerek çizebilir misin?
Hepimiz küçükken bu soruyla ya da türevleriyle bir yerlerde karşılaşmışızdır. Bazılarımız bu soru sorulduğunda bu şekli çizebildi, bazılarımız ise çizemedi. Peki bu soruyu şekli çizmeden cevaplamak mümkün mü? Ya da bu tarzda sorulara karşı bir genelleme geliştirebilir miyiz? Bu iki soruya da cevabımız evet. Bize gereken sadece matematiksel bir teori olan graf teorisi diğer adıyla çizge teorisi.
Graf (Çizge) Teorisi Nedir?
Matematikte graf ya da çizge, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Daha basit konuşmak gerekirse bir graf, köşeler adı verilen sonlu bir nokta kümesinden ve noktaları birleştiren kenarlar adı verilen çizgi parçaları veya eğrilerden oluşur. Sosyal ağlar, ulaşım ağları veya internet gibi ağlarla çevrili olduğumuz için graf teorisi modern matematikte önemli bir rol oynar
Grafikler, çok çeşitli durumları modellemek için kullanılmaktadır. Bir haritadaki şehirleri incelemek için, eyaletlerin veya ülkelerin sınır ilişkileri, insanlar arasındaki arkadaşlıklar veya aile ilişkilerini grafiklerle göstermek mümkündür. Örneğin aşağıdaki kat planına göz atalım.
Bir grafikte, kenarlar köşeleri birleştirir. Bu yüzden, kat planında neyin nesneleri birbirine bağladığını düşünmemiz gerekiyor. Bu, odaları birbirine bağlayan kapılar olacaktır. Bu yüzden odaları köşeler olarak kabul etmeliyiz. Odaları birbirine bağlayan kapıları da köşeleri birleştiren bir kenarlar olarak çizeceğiz. Oturma odası, mutfak ve yemek odasının hepsinin üç kapısı var. Dışarıya sadece oturma odası ve mutfaktan erişilebilir ve banyo sadece yemek odasına bağlanır. Bu durumda grafiğimiz aşağıdaki gibi olacaktır.
Graf Teorisi İle İlgili Bilmeniz Gereken Bazı kavramlar
Şimdi aşağıdaki iki grafiğe hızlıca bakın. Bunlar aynı mı? Evet cevabı doğru cevaptır. Fiziksel olarak farklı görünseler de, gerçekten aynıdırlar, çünkü aynı şekilde birbirine bağlanmış aynı köşelere sahiptirler. Tek fark, köşelerin fiziksel olarak konumlandırıldığı yerdir
Graf teorisinin ana kavramları oldukça basittir, ancak problemleri bu teoriyi kullanarak çözmek için ihtiyacımız olan epeyce terminoloji vardır. Bu kavramlardan biri derecedir. Bir köşe noktasının derecesi, o noktada kesişen kenarların sayısıdır. Örneğin, aşağıdaki şekilde köşelerin her biri üçüncü dereceye sahiptir. Çünkü her birinin üç kenarı vardır.
Bir grafikteki yol, bitişik köşeler ve bunları birbirine bağlayan kenarların birden fazla kez kullanılmadığı bir dizidir. Bir grafikte bir yol bulurken, bir kenardan yalnızca bir kez geçilmelidir. Aşağıdaki graf bir yolu göstermektedir. Yol B tepe noktasında başlar ve ardından bu sırayla C, E ve F köşelerinden geçer. Yol daha sonra B, C, E, F olarak tanımlanır. Bir grafiğin birçok yolu olabilir ve bir yolun tüm köşeleri veya kenarları içermesi gerekmez. Bir tur ise aynı köşe noktasında başlayan ve biten bir yoldur.
Graf Teorisi İle Nasıl Tanıştık?
Graf teorisi ile ilgili temeller 1735 yılında Leonhard Euler tarafından, tam da bizim sorumuz gibi bir soruyla uğraşırken, ortaya atıldı. Soru şöyleydi: Doğu Prusya’daki Königsberg şehrindeki 7 köprüden bir ve yalnız bir kez geçerek başladığın yere geri dönebilir misin? Euler, bu tür bir sorunun yeni bir düşünme biçimi gerektirdiğini fark etti. Problemin konum geometrisi ile ilgili olduğunu fark eden Euler, böyle bir rota tasarlamanın imkansız olduğunu göstermek için yeni bir geometri türü geliştirdi. Noktalar arasındaki mesafeler önemli değildi. Sayılan tek şey noktalar arasındaki bağlantılardı. Çizdiği şekil aşağıdaki gibi idi.
Daha sonraki mantığı ise dâhiceydi. Düşünüşüne göre, bu yürüyüşü tamamlamak için her köşeden kaç kere çıkıyorsak o kadar geri girmemiz gerekiyordu. Aksi takdirde yürüyüşümüzü başladığımız noktadan başka bir noktada bitirmiş oluyorduk. Bu mantıkla her köşenin derecesi çift olmalıydı. Fakat Königsberg grafının köşelerinin dereceleri ise 5,3,3,3 idi. O halde böyle bir yürüyüş gerçekleştirilemezdi. Fakat bu hala bizim sorumuzu çözmeye yeterli değil çünkü bizim sorumuzdaki graftaki köşelerin dereceleri 4,4,3,3,2. O zaman şimdi Euler’in bir diğer tanımını öğrenelim: Euler yolu.
Euler Yolu
Euler yolu, her kenardan tam olarak bir kez geçen bir yoldur. Bir Euler devresi yada turu, her kenardan tam olarak bir kez geçen bir devredir. Yukarıda tanımladığımız bir yol ile bir Euler yolu arasındaki fark, bir yolun bir grafikteki herhangi bir kenar alt kümesinden geçebilmesi, ancak bir Euler yolunun tüm kenarlardan tam olarak bir kez geçmesidir.
Bir grafta Euler yolunun bulunması için gerek ve yeterli koşul ise o grafın iki köşesi hariç diğer her köşesinin derecesinin çift olmasıdır. Şimdi tekrar bizim sorumuzdaki grafa geçecek olursak, grafımızın tam da Euler yolu tanımına uyduğunu görebiliriz (dereceler 4,4,3,3,2). Bu da demek oluyor ki biz bu şekli elimizi hiç kaldırmadan ve bir kenardan sadece bir kere geçerek çizebiliriz.
Merak edenler için nasıl çizilebileceği gösterilmiştir. Matematiğin soyut gücü ile bu tarz popüler sorulara kalem dahi oynatmadan cevap verebilmek, onun güzelliklerinden sadece birisidir. Yazının devamında göz atmak isterseniz: Üç Ev Üç Kuyu Problemini Neden Yıllardır Çözemiyoruz?
Kaynaklar ve ileri okumalar:
- The bridges of Königsberg; yayınlanma tarihi: 5 Ağustos 2016; Bağlantı: https://plus.maths.org/
- Nesin, A. (2019). Sayma kombinasyon hesapları. İstanbul: Nesin Yayıncılık A.Ş.
- Graph theory; https://en.wikipedia.org/wiki/Graph_theory
Matematiksel
