Altın
%
Dolar
%
Euro
%
Bitcoin
%
Eth
%
Önümüzdeki 5 gün boyunca
Çizge (Graf) Teorisi
BİLİM

Çizge (Graf) Teorisi

1736 yılında temelleri atılan çizgeler yani graflar, bulaşıcı hastalıklar, mühendislik ve bilgisayar bilimleri, hammadde tedarik ağları, bilgisayar oyunları gibi çok sayıda alanda, temelde problemleri çözmek adına oluşturulan bir ağ yapısı. Bu ağlar, düğüm (vertex, node) ve düğümlerin birbirine bağlandıkları noktalar olan edgelerden oluşuyor. Problem tanımlama, modelleme ve çözme konusunda oldukça kolaylık sağlayan bu teori birçok bilim dalı ve teknoloji alanında sıklıkla kullanılıyor. Peki tam olarak nedir bu çizge teorisi? Gelin yakından bakalım.

Yayın Tarihi :23 Eyl 2022
Süre :2.5 Bardak

Derinlere girmeden önce bu teorinin matematikçiler tarafından ortaya atılıp geliştirildiğini belirtelim. Yani problemlerin çözümü için bol miktarda formül ve hesaplama kullanılıyor. Çizge Teorisi temelde küme teorisine dayanıyor. Herhangi bir çizge düğümler ve bağlantılar kümesi olarak ifade edilebiliyor. Bir çizgeyi küme olarak ifade etmek istersek önce düğümler kümesi ve ardından düğümlerin bağlantıları belirtiliyor. Örneğin ABCD noktalarının var olduğu bir düzlem düşünelim. Bu düzlem üzerinde ACD noktaları bir üçgen oluştursun ve üçgenin dışında A noktası ile B noktası arasında tek bir bağlantı gösterilsin. Bu durumda küme G=({A,B,C,D},{(A,B),(A,C),(C,D),(A,D)}) şeklinde ifade edilebiliyor.

Königsberg Köprüsü - corpling.hypotheses.org
Çizge teorisinin temelleri, tüm dünyada tanınan İsviçreli matematikçi ve fizikçi Leonhard Euler tarafından 1736 yılında atılıyor. Königsberg Köprüsü olarak bilinen ünlü bir matematik problemi var. Bu problem, 7 ayrı köprüyle birbirinden ayrılan bölgelerin her defada yalnız bir köprü kullanılarak tüm bölgelerin gezilip gezilemeyeceğini esas alıyor. Königsberg kentinde, Pregel Nehri’nin kolları olan Eski Pregel ve Yeni Pregel nehirleri bölgeyi dört parçaya ayırıyor ve nehir üzerindeki yedi köprü bu bölgeler arasındaki bağlantıyı sağlıyor. Bu durum birçok kişiye tanıdık gelebilir. Elimizi kâğıdın üzerinden kaldırmadan çizilmesi istenilen şekli andırıyor. Esasında bununla tam olarak aynı durum. Bağlantılar ve düğümleri kullanarak aynı çizgi üzerinden geçmeden şekli tamamlamak.

18. yüzyılda Euler, yedi köprünün her birini birer kez kullanarak tüm bölgelere geçilip geçilemeyeceğini araştırıyor ve yaptığı çalışmaların sonucunda bu durumun mümkün olmadığı cevabını veriyor. Kâğıt üzerine çizmeye çalıştığımız şekli tekrar hatırlayacak olursak, bu şeklin 8 ayrı kenarı ve 5 köşesi bulunuyor. Kenarlar bölgeleri, köşeler yani düğümlerde köprüleri ifade ediyor. Eğer diyor Euler, bölge sayısı tek sayı olursa problemin çözümü mümkün değil. Tıpkı Königsberg Köprüsü’nde olduğu gibi, tek sayılı olan 7 bölgenin birinden diğerine bu şekilde geçilemiyor. Yani bir köprüden ikinci kere geçmek zorundasınız.

Biraz daha işin matematiğine girmek gerekirse, Euler her bir düğüme giden ve gelen yolları topluyor ve buna düğüm derecesi adını veriyor. Köprüler işte bu düğüm derecesini gösteriyor. Eğer düğüm derecesi tek sayı ile ifade ediliyorsa bu durumda noktalardan biri ya başlangıç ya da bitiş noktası oluyor. Aynı anda ikisi birden olamıyor ki bu başladığınız noktaya farklı yoldan gelemeyeceğinizin matematiksel ifadesi oluyor. Bunun yanı sıra Euler ilgilendiği bu durumun adını Euler Yolu koyuyor. Eğer Euler yolu başladığı düğümde son buluyor ve tam bir döngü elde ediliyorsa bu durumda buna Euler Döngüsü deniliyor. Euler’in ifade ettiği gibi eğer düğüm derecesi çift sayı olursa bu döngünün varlığından söz edilebiliyor.

Çizge Teorisinde yer alan düğümler ve bağlantıların görselleştirmesi - ezgif.com
Çizge teorisinden yola çıkılarak modern matematikçilerin teorileri bu temel üzerinde geliştiriliyor. Matematik bilimine yaptığı katkılarla tanınan Alman matematikçi Gerhard Ringel, 1963 yılında bir teori ortaya atıyor. Ringel’e göre bir çizgenin, birbirini tekrar eden ve döngü içermeyen parçalara bölünebilmesi mümkün görünüyor. Matematikçiler karmaşık çizgelerin düğümlerini ve bu bağlantıların nasıl bir araya geldiğini uzun yıllardan beri araştırıyorlardı. Bu varsayıma bir cevap verilmesi yaklaşık 60 yıl sürüyor ve yakın zamanlarda R. Montgomery, A. Pokrovskiy ve B. Sudakov problemin çözüldüğünü bildiriyor. 

Çalışmaları sayesinde klasik yöntemlerle çözülemeyen eski bir problemi ortadan kaldıran araştırmacılar, buna benzer çözümü güç sorunların önünü açmış oluyor. Örneğin bir hastanede yatan hastaların temel ihtiyaçları ve tıbbi malzeme eksikliği buna benzer bir sorun teşkil edebiliyor. Küçük çaplı problemler zaten uzun yıllardır bilgisayar programları hatta şimdilerde yapay zeka sayesinde atlatılıyor.

quantdare.com
Asıl problem gittikçe büyüyen sorunlar. 21. yüzyılda internet ağları, insan ihtiyaçları, kalabalıklaşan kentler, öngörülemeyen tehlikeler ve daha birçok çözüm bekleyen sorunun, buna benzer çalışmalar sayesinde en azından kâğıt üzerinde çözüme kavuşturulması umut vadediyor. Bu noktadan sonra hesaplamaları tamamlayan matematikçiler çözüm için masayı yetkililere bırakıyor.

Kaynak:
Dr. Tuncay Baydemir, Çizge Teorisi, Bilim ve Teknik, TÜBİTAK, Kasım 2020.

Yukarı Kaydır