Bir Köprü Probleminden Doğan Kuram: Çizge Kuramı

Graf Teorisi, Çizge Teorisi veya Çizit Teorisi. Bu kavramlar size tanıdık geliyor mu? Aslında bunların hepsi aynı şeyi ifade ediyor. Bu isimler size tanıdık gelmeyebilir ancak bu teori; günlük hayatımızda oldukça önemli yer tutan sosyal ağlar, ulaşım teknolojileri, öğrenci seçme ve yerleştirme algoritmaları, organ bağışı gibi çeşitli alanlarda kullanılıyor. Öyleyse Çizge Teorisi’ni daha detaylı öğrenmeye ne dersiniz?

Çizge Teorisi matematiğin bir alt dalıdır. Ağ / network / graf / graph gibi kelimelerle de ifade edilir. Çizge Teorisi’nin temeli, Königsberg'in yedi köprüsü problemine dayanır. Bu problem, 18. yüzyılda Königsberg köprülerinden ilham alınarak ortaya atılan ünlü bir matematik problemidir. Königsberg kentinde Pregel Nehri, şehri dört bölüme ayırmaktadır ve nehir üzerinde bu bölgeleri birleştiren yedi köprü bulunmaktadır. Soru şudur: Kentin belirli bir noktasından hareket edip her köprüyü yalnızca bir kez geçerek başlangıç noktasına dönülebilir mi?

Königsberg’in yedi köprüsü problemi ile ilgili görseller:

Bu soru, 1736'da İsviçreli matematikçi Leonhard Euler tarafından cevaplandırılmıştır. Ancak sorunun cevabını öğrenmeden önce bu konuyla alakalı birtakım kavramları öğrenmemizde fayda var. Örnek olarak Facebook’u düşünelim: Milyonlarca insanın birbiriyle ilişki kurduğu bir sosyal platform. Tüm bu ilişkilere çizge deniyor. Her insan bu grafın bir düğümü (node) ve her bağlantı bu çizgenin kenarıdır (edge). Bu örnekteki graf ç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 graf sonlu bir düğüm (node) dizisinin birleşimi ve sonlu bir kenar (edge) ikililerinin birleşiminden oluşmaktadır.

Aşağıdaki görselde kırmızı noktalar düğümleri(node), düğümleri birleştiren çizgiler ise kenarları(edge) temsil ediyor. Yani kısaca grafları birden fazla varlık arasındaki ilişkiyi modelleyebildiğimiz matematiksel bir nesne olarak düşünebiliriz.

Bu kavramları öğrendiğimize göre köprü problemine geri dönebiliriz. Sorumuz her köprüyü yalnızca bir kez geçerek başlangıç noktasına dönülüp dönülemeyeceğiydi. Euler böyle bir şey yapılamayacağının matematiksel ispatını sundu.

Euler, problemi çözmek için öncelikle soruyu basitleştirdi. Nehrin ayırdığı 4 bölgeyi noktalarla, köprüleri de çizgilerle göstererek bir graf oluşturdu. Graf Teorisi terimleriyle konuşursak bir noktadan çıkan farklı yolların sayısına “derece” ismini veririz. Şimdi sağ taraftaki resme bakarak şu çıkarımı yapabiliriz: A, B, D noktalarının derecesi 3; C noktasının derecesi de 5’tir. Bir noktadan yürümeye başlayan birinin başlangıç yerine farklı yollardan dönebilmesi için o noktadan her çıkış-dönüş için iki farklı yol gerekir. O zaman A, B ve D noktalarından yürümeye başlayan biri çıkış-dönüş-çıkış yapabilir. Ancak başlangıç yerine dönmek için gerekli olan son dönüşü yapamaz. Aynı mantıkla baktığımızda C noktasından yürümeye başlayan biri çıkış-dönüş-çıkış-dönüş-çıkış yapabilir ancak son dönüşü yapamaz. Demek ki bu problemde köprülerin her birinden yalnızca bir kez geçilerek başlangıç noktasına dönülemez. Dönülebilmesi için noktaların derecesinin çift olması gerekir. Ancak Königsberg örneğine baktığımızda tüm noktaların derecesinin tek olduğunu görüyoruz.

Euler’in içinde uzaklık ve ölçü kavramı olmayan ama konumlarla (position) ilgilenen yeni bir geometriden söz etmesi, Graf Teorisi’nin ve topolojinin temelini oluşturdu. Bugün Graf/Çizge Teorisi; ulaşımda otoyolların ve havayolların güzergahlarında, bilgisayar oyunlarında, elektrik devrelerinde, şebeke yapılarında ve daha birçok alanda kullanılıyor.

Königsberg problemi, basit bir sorudan hayatımızdaki birçok alanı etkileyen bir teorinin ortaya çıkabileceğinin en güzel örneklerinden biridir. Sorular sormaya ve cevaplarını aramaya devam etmemiz dileğiyle.

Euler’in fotoğrafı: