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. 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
Graf (Çizge) Teorisi Nedir?
Hikâyemiz 18. yüzyılda, o dönemde Alman Prusyası’na bağlı olan canlı Königsberg kentinde başlar (şehir bugün Kaliningrad adıyla anılmakta ve Rusya sınırları içinde yer almaktadır). Pregel Nehri’nin kıyısında kurulu olan kent, kültürel ve ekonomik açıdan oldukça gelişmiş bir merkezdi.
Coğrafi olarak Königsberg, iki büyük adadan oluşuyordu; bu adalar hem birbirine hem de Pregel’in kuzey ve güney kıyılarına toplam yedi köprüyle bağlanıyordu.
Bir eğlence olarak başlayan bu uğraşta, Königsberg halkının kentin dört bölgesini dolaşan ve yedi köprünün her birinden tam olarak bir kez geçen bir yol çizmeye çalıştığı anlatılır. Bu bulmaca kısa sürede yayıldı ve bölgede oldukça tanınır hâle geldi.
Ancak 1730’ların ortalarına kadar, İsviçreli matematikçi Leonhard Euler (1707–1783) bu probleme dair çözümünü yayımlayana dek, mesele matematiksel bir açıklığa kavuşmadı. Euler, birçok kent sakininin sezgisel olarak tahmin ettiği sonucu matematiksel olarak doğruladı. Königsberg’de böyle bir yürüyüş mümkün değildi.
Elbette Euler gibi parlak bir zihin, bu bulmacayı yalnızca eğlence olsun diye ele almadı. Onu asıl ilgilendiren, bu problemin daha karmaşık sorunları temsil etmek ve çözmek için bir model sunmasıydı. Euler’in çözümündeki temel fikir şuydu. Kentin coğrafi haritası, bölgelerin büyüklükleri ya da köprülerin fiziksel ölçüleri tamamen önemsizdi. Önemli olan tek şey, bölgelerin birbirleriyle nasıl bağlandığıydı.
Bu nedenle Euler, kenti basit bir diyagramla temsil etti. Dört kara parçasının her birini düzlem üzerinde bir noktayla, iki bölgeyi birbirine bağlayan her köprüyü ise bu noktalar arasında bir doğru ya da eğriyle gösterdi. Bu diyagram, bugün “graf” olarak adlandırılan yapının bilinen ilk örneğidir.
Graf Teorisi İle İlgili Bilmeniz Gereken Bazı kavramlar
Euler’in geliştirdiği bu yaklaşım, bugün graf teorisi olarak bilinen bir matematik alanının doğmasına zemin hazırladı. Euler’in öncü çalışmalarından sonra, yaklaşık bir yüzyıl boyunca graf teorisinde kayda değer bir gelişme yaşanmadı.
Ancak 19. yüzyılla birlikte bu alan giderek daha fazla matematikçinin ilgisini çekmeye başladı. “Graf” terimi ilk kez 1878 yılında İngiliz matematikçi James Sylvester tarafından kullanıldı. Aynı yüzyılda, yine İngiliz matematikçi Arthur Cayley graf teorisi alanında bugün hâlâ en önemli sonuçlar arasında sayılan çalışmalar yürüttü.
20. yüzyıla gelindiğinde ise graf teorisi, diğer bilim dallarında en fazla uygulama alanı bulan matematik dallarından biri olarak kabul görmüştür. Bu alandaki çalışmalar, dünya çapındaki ağın yapısını daha iyi anlamayı ve geliştirmeyi de mümkün kıldı. Nitekim internet, web sayfalarının “düğüm”, onları birbirine bağlayan bağlantıların ise “kenar” olduğu dev bir graf olarak ele alınmaktadır.
Matematikte graf, günlük dilde çoğu zaman “ağ” dediğimiz yapıya karşılık gelir. Köşe adı verilen düğümlerden ve bu düğümleri birbirine bağlayan kenarlardan oluşur. Bir köşenin derecesi, ona bağlı olan kenarların sayısıdır. Graflar, çok çeşitli durumları modellemek için kullanılmaktadır. Örneğin aşağıdaki kat planına göz atalım.
Bir grafikte kenarlar köşeleri birbirine bağlar. Bu nedenle bir kat planını grafikle temsil ederken, hangi unsurların birbirine bağlantı sağladığını belirlememiz gerekir. Bu bağlamda, odaları birbirine bağlayan kapılar temel bağlantı unsurlarıdır.
Dolayısıyla odaları köşe olarak, bu odalar arasındaki kapıları ise köşeleri birleştiren kenarlar olarak ele alırız. Oturma odası, mutfak ve yemek odasının her birinin üçer kapısı vardır. Dışarıya yalnızca oturma odası ile mutfaktan çıkış vardır. Banyo ise sadece yemek odasına bağlıdır. Bu koşullar altında elde edilen graf, aşağıdaki biçimde olur.
Ş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
Euler Yolu
Graf teorisinde Euler yolu, bir graftaki her kenardan yalnızca bir kez geçilen bir yürüyüştür. Bu yürüyüş sırasında aynı köşeden birden fazla kez geçmek mümkündür. Eğer bu yol başladığı köşede bitiyorsa, buna Euler çevrimi ya da Euler döngüsü denir. Bu kavramlar ilk kez Leonhard Euler tarafından, 1736 yılında Königsberg’in Yedi Köprüsü problemi incelenirken ortaya konmuştur.
Problemin özü oldukça basittir: Verilen bir grafta, her kenarı tam olarak bir kez kullanarak kesintisiz bir yol çizmek mümkün müdür? Üstelik bunu yaparken başladığımız noktaya geri dönebilir miyiz?
Euler’in ortaya koyduğu kural bu soruya net bir yanıt verir. Bir grafın Euler çevrimine sahip olabilmesi için, grafın bağlantılı olması ve tüm köşelerinin çift dereceye sahip bulunması gerekir; yani her köşeye bağlı kenar sayısı çift olmalıdır. Euler bu koşulun zorunlu olduğunu göstermiş, bunun aynı zamanda yeterli olduğunu da ileri sürmüştür. Bu iddianın eksiksiz matematiksel ispatı ise 1873 yılında Carl Hierholzer tarafından yapılmıştır.
Bugün Euler Teoremi olarak bilinen bu sonuç şunu söyler. Bir graf, ancak ve ancak bağlantılıysa ve tüm köşeleri çift dereceliyse bir Euler çevrimine sahiptir.
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.Ş.
- Taheri-Dehkordi, Meysam. (2024). Graph Theory; History, Applications and Vision. 10.22108/msci.2024.139804.1623.
Matematiksel
