Çizge Kuramı (Graf Teorisi)

Graf teorisi veya çizge kuramı, grafları inceleyen matematik dalıdır. Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf veya çizge, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan (yaylardan, bağıntılardan) oluşur. Daha önceleri Çin, Hint ve İslam dünyasında kullanılmış olmakla birlikte literatür anlamında graf teorisinin temelinin 1736'da Leonhard Euler tarafından atıldığı söylenmektedir. "Graf" kelimesi, ilk kez 1822 yılında James Joseph Sylvester (1814-1897) tarafından kullanılmıştır. 1845 yılında Gustav Kirchhoff (1824-1887), elektrik devrelerinde akım ve gerilimleri hesaplamaya yardımcı olan ve kendi ismiyle anılan ünlü devre kuramlarını graf gösterimiyle yayımlamıştır. 1852 yılında Francis Guthrie (1831-1899), çözülmesi zor olan grafta dört renk problemini (İngiltere'nin kontluklarının haritasını renklendirirken, ortak bir sınırı paylaşan iki bölgenin aynı renk olmaması için en az dört renge ihtiyaç olduğundan hareketle "Herhangi bir haritayı renklendirmek için dört rengin yeterli olacağını varsayan problem") ortaya atmıştır. 1927 yılında Lev Semenovich Pontryagin (1908-1988), 1930 yılında ise Kazimierz Kuratowski (1896-1980), düzlemsel grafların özelliklerini bulmuşlardır. Macar matematikçi Denes König (1844-1944), graf teorisine ilişkin ilk kitabı 1936 yılında yayımlanmıştır. 

Graf (Çizge) Teorisi, çok farklı disiplinlerin çalışma alanına girmektedir. Network ağları, facebook, twitter gibi sosyal ağların kullanımı, kurye hizmetler, (travelling salesman problemi- en kısa yollardan müşteriye ulaşma), mektup dağıtımı, yol bakımı, kar temizleme, itfaiye, acil servis gibi araçların optimum güzergahları, çöp toplama, polislerin yollarda devriye gezinimi gibi pek çok alanda graf teorisi kullanılır. Sosyolojiden, bilgisayar bilimlerine, işletmeden, endüstri mühendisliğine kadar çok geniş alanlarda kullanımı olan bu teori, basitçe bir gerçek hayat probleminin çizge ile modellenmesini amaçlamaktadır. Model oluşturulduktan sonra çizge teorisinde bulunan yöntemler kullanılarak problem çözülebilmekte ve ardından da tekrar gerçek hayata uygulanabilmektedir. Graf (Çizge) teorisi temel olarak bir problemin hat/kenar (edge) ve düğümler (node) ile modellenmesi ve bu modelin bir çizge şeklinde gösterilmesi ilkesine dayanmaktadır. Çizge teorisinde tanımlı olan bazı özellikler bu modelin çözümüne ve dolayısıyla gerçek problemin çözümüne yardımcı olmaktadırlar. Yani çizge teorisinin işe yaraması için öncelikle gerçek dünyadan bir problem çizge olarak modellenir, bu model geometrik olarak çözülür ve daha sonra gerçek dünyaya uygulanır.

Graf teorisinin modern matematiksel tarihi, Königsberg köprüleri problemine dayanır. Leonhard Euler tarafından, 1736 yılında, Königsberg'in yedi köprüsü (Die Sieben Brücken von Königsberg) adında günümüzde hâlâ popülerliğini koruyan bir problem ile ilgili olarak yazılan bir makale, graf teorisinin başlangıç tarihi kabul edilir. Königsberg kentinde Eski Pregel ve Yeni Pregel nehirleri birleşerek Pregel (Pregolya) nehrini oluşturmaktadır. Bu nehirler, şehri dört bölüme ayırmaktadır ve nehir üzerinde bu bölgeleri birleştiren yedi köprü bulunmaktadır. Ortaya atılan probleme göre: Königsberg'in yedi köprüsünden sadece bir ve yalnız bir defa geçmek koşulu ile bir yürüyüş yapılabilir mi? Bu sorun üzerine kafa yoran matematikçiler, çeşitli çözüm önerileri sunmuş ve en sonunda 1736'da İsviçreli matematikçi Leonhard Euler tarafından bir makale yayınlanarak problem cevaplandırılmıştır.

Euler, köprü probleminin çözümünü biraz daha kolaylaştırmak ve şekli gereksiz bileşenlerden arındırmak amacıyla kara parçalarını noktalar yardımıyla, köprüleri ise bu noktaları birleştiren çizgiler (hatlar) olarak gösterdiği bir graf (çizge) çizer. Böylece Euler gündelik hayatta karşılaştığı köprü problemini, bir çizge problemine dönüştürmüş olur. Problemde graflar; graf elemanı, noktalar düğüm, düğüme bağlı olan elemanların sayısı ise düğüm derecesi olarak adlandırılmak üzere soru, "grafın herhangi bir düğümünden başlayarak yedi elemanının her birini bir ve yalnız bir kere kullanarak dolaşmak mümkün müdür?" problemine dönüşür. 1736'da Euler'in incelemeleri böyle bir gezintinin mümkün olmadığını kanıtlamış ve bu tür dolaşmayı mümkün kılacak grafların şu özelliklere sahip olmaları gerektiğini göstermiştir: 

1)Birleşik bir grafın bütün elemanlarını bir ve yalnız bir defa kullanarak dolaşmak için o grafın tek dereceli düğümlerinin sayısı eğer varsa sadece iki olmalıdır. 

2)Tek dereceli düğümler dolaşmanın başlangıç ve bitiş düğümleridir. Grafta böyle düğümler yoksa dolaşmaya herhangi bir düğümden başlanabilir. 

3)Bir graftaki herhangi bir düğümün derecesi, kendisini diğer düğümlere birleştiren hatların sayısı kadardır. 

4)Grafın düğümlerinden derecesi en büyük olanı, aynı zamanda grafın derecesini belirler. 

Köprü problemi olarak verilen üstteki şekilde, A düğümünün derecesi 3'tür çünkü ona bağlanan doğru sayısı yani köprü sayısı 3 tanedir. Aynı şekilde B ve D'nin de düğüm dereceleri 3'tür. Çünkü bu noktalara bağlanan doğru sayısı 3'er tanedir. Şekilde ortadaki C düğümünün düğüm derecesi ise 5'tir. Çünkü C düğümüne ait çizge sayısı 5'tir. 

 

Graftaki her bir düğümün diğer tüm düğümlerle arasında bir hat mevcutsa, yani olabilecek tüm hatlara sahipse, bu tür graflara "tamamlanmış graf" (completed graph) denir. Bu tür bir grafta bütün düğümlerin dereceleri birbirine eşit ve toplam düğüm sayısının bir eksiği kadardır. n düğümlü bir tamamlanmış grafın hat sayısı n.(n-1)/2 tane olur. 𝐺 grafının her nokta ikilisi arasındaki maksimum uzaklığa 𝐺 grafının "çapı" (diameter) denir ve ç𝑎𝑝 (𝐺) veya 𝑑𝑖𝑎𝑚(𝐺) ile gösterilir. 𝐺 grafının her nokta ikilisi arasındaki minimum uzaklığa 𝐺 grafının "yarıçapı" (radius) denir ve 𝑟𝑎𝑑(𝐺) ile gösterilir. Bir G grafında tüm noktaların dereceleri birbirine eşit ise G grafına "regüler graf" denir.

Bir düğüm, başlangıç ya da bitiş düğümü değilse o düğüme gelen kişinin turu tamamlayabilmek için oradan ayrılması gerekecektir. Dolayısıyla bu tip düğümler çift dereceleri olmalıdır. Oysa tek dereceli bir düğüme, örneğin D düğümüne ikinci kez gelen bir kişi çıkış yolu bulamayacaktır. Dolayısıyla bu düğüm ya gezintinin bitiş düğümü olmalıdır ya da başlangıç düğümü olarak seçilmelidir ki ikinci gelişte çıkış yolu bulunabilsin. Buna göre tek dereceli düğüm sayısı ikiden fazlaysa gezinti tamamlanamayacaktır. Yürüyüşün sonunda başlangıç noktasına dönülebilmesi içinse bütün düğümler çift dereceli olmalıdır. Böylece, başlangıç ve bitiş düğümü aynı olan ve her bir elemanı sedece ve en az bir kez içeren turlara "Euler turu" ve Euler turu içeren graflara da "Euler grafları" denmiştir. Euler'e göre her köprüden sadece bir kez geçerek geziyi tamamlayabilmek için ya her kara parçasının köprü sayısı çift ya da iki kara parçasının köprü sayısı tek olmak zorundadır. 

Euler, benzer problemlerde böyle bir dolaşmanın mümkün olması için, yani aynı yoldan bir kez geçilerek tüm yolları dolaşabilmek için mevcut çizgedeki tek dereceli düğüm sayısının (eğer varsa) sadece 2 adet olması gerektiğini ve tek dereceli düğümlerin, gezintinin başlangıç ve bitiş düğümleri olduğunu göstermiştir. Königsberg şehri, toplam dört anakara parçasına yayılmıştır ve bunların her biri komşu yerlere tek sayıda köprüyle bağlanmıştır. Üç noktadan üçer köprü, birinden de beş köprü çıkmaktadır. Bu nedenle Euler hem Köngsberg’i her köprüden sadece ve sadece bir kez geçerek dolaşmanın imkansız olduğunu göstermiştir. Bu sayede Euler, dünyanın herhangi bir yerindeki herhangi bir şehrin köprü ağına uygulanabilecek genel bir kuralı ortaya koymuştur. Bu problemin çözümü çizge teorisinin ilk temelleri olmuş, topolojinin gelişmesine yol açmıştır.

Graflar; Topoloji ve Coğrafi Bilgi Sistemlerindeki tüm konumsal (Spatial IS = Coğrafi/ Konumsal/ Mekansal Bilgi Sistemleri) analizlerin temelini oluşturur. Karayolu, demiryolu, nehirler, boru hatları, telefon, elektrik ve veri hatları gibi birbirlerine çizgi özelliklerle bağlı sistemler ya da yapılar, "ağ" olarak adlandırılır. Ağ yapıları üzerinde bir noktadan diğer bir noktaya erişebilme özelliği vardır. İnsanların bir yerden başka bir yere ulaşımları, servis hizmetlerinin ve malların taşınması ve dağıtılması, kaynak ve enerjinin ulaştırılması ve bilgi iletişimi gibi faaliyetler, tanımlanabilen ağ yapıları içinde gerçekleşir. Bir konumdan bir başka konuma yapılan iletim ya da yolculuklar ağ analizlerinin konusunu oluşturur. Ağ analizleri; şebeke yapısına sahip, birbiriyle birleşen coğrafi varlıkların bağlantı şekillerinden, karar vermeye yönelik sonuç çıkarmaya yarayan konum analizleridir. Bir şehrin sokakları, enerji nakil hatları, bir havayolunun hizmet ağı, ya da su tahliye kanallarının yapısı bu tür ağlar için ilk akla gelen örneklerdendir. Bu sistemler üzerinde optimum kararların alınabilmesi için yapılan sorgulamalar ve analizler coğrafi bilgi sistemlerinde "ağ analizleri" olarak adlandırılırlar. 

Zaman kavramının çok önemli olduğu acil durumlarda; ambulans, itfaiye ve polis araçlarının istenen noktaya en kısa sürede ulaşması, itfaiye merkezlerinin hangi noktalara yerleştirilmesi gerektiği, ya da arıza esnasında hangi binaların elektriklerinin denetlenebileceği gibi uygulamalar da ağ analizleri kapsamındadır. Özellikle gelişmiş ülkelerde, ağ analizlerinin optimum güzergah tespiti dışında farklı alanlarda da kullanıldığı görülmektedir. Dağıtım güzergahı modellemesinden deprem sonrası planlamasına, elektrik hatları arızalarından adres belirlemeye, yatırım analizlerinin yapılmasından güvenlik uygulamalarına kadar çok geniş bir yelpazedeki problemler, ağ analizleri ile çözülmektedir. Herhangi iki nokta arasındaki optimum yolun belirlenmesi olarak adlandırılabilecek ağ analizleri, graflar yardımıyla çözüme kavuşturulur. GPS uydu sistemlerinde, kargo ve lojistik hizmetlerinde optimum dağıtım güzergahlarının belirlenmesi, yönetim ve bilişimde etki alanın ya da merkezi konumun belirlenmesinde, sosyal ağlarda, elektrik devre elemanlarının yerleşiminde, şebeke kurulumu, bilgisayar network ağları, soyağacı (şecere) gibi farklı alanlarda da graflar kullanımı söz konusudur. 

Matematiksel tanımı: Basitçe bir graf (graph), düğüm (vertice, (vertex)-node) olarak adlandırılan noktalar ve bu noktaları birleştiren hatlardan (Hat/Link ) (edge-relation) oluşan ve geometrik/konumsal bir bilgi vermeyip, sadece düğümler arasındaki ilişkiyi gösteren çizgiler topluluğudur. Grafta hat yerine bazen "kenar" ve "çizgi", düğüm yerine de "köşe" şeklinde bir kullanım da vardır.  Bir G grafı, iki küme ile ifade edilir: G = (D, K). Bu ifadede D düğümler kümesi, K ise (düğümler ile ilişkili) hatlar/kenarlar kümesi olarak ifade edilir. Eğer düğümleri birbirine bağlayan hatlar için giriş ve çıkış yönleri belirli ise bu kenarlara "yönlü hatlar" denir. Eğer bir düğümden çıkan ve yine aynı düğüme giren bir hat varsa (mesela A'dan çıkıp A'ya yeniden giren bir kenar), bu bir "döngü" (loop) olarak ifade edilir. Eğer bir düğümden bir başka düğüme giden aynı yöne sahip veya yönsüz iki adet hat varsa bu kenarlara "paralel hatlar" denir. Yönlü bir çizgede komşuluk listesi oluşturulurken, her bir düğüm başlangıç olarak kabul edilerek, ok yönüne göre, o düğümden hangi düğümlere gidilebileceği yazılır. Bir çizgenin türünü, kenarlarının yönlü olup olmadığı, çoklu kenar durumu ve döngü içerip içermediği belirler.  Yönsüz bir grafta, bir düğümün derecesi, kendisine gelen kenarların sayısı kadardır.

Euler Formülü: Tek parça ve düzlemsel bir grafın bölge sayısı (b), hat sayısı (k) ve düğüm sayısı (n) ise b-k+n=2 eşitliği geçerlidir.

Aynı iki düğümün sadece bir hatla bağlandığı, herhangi bir düğümü yine kendisine bağlayan bir hattın (çevrimin) olmadığı, hatların bir değer almadığı ve yönünün tanımlanmadığı, düğüm ve hatların sınıflandırılmadığı graflara "basit graf" denir. Grafta bulunan noktalara/köşelere "düğüm" denir. Grafta hatlar (edges), bir çift düğümle etiketlenir. E={(x,z)} şeklinde gösterilir. Hat bağlantısı olmayan nokta şeklindeki tek başına düğümlere "ayrık düğüm" (isolated vertex) denir. İki ya da daha fazla düğüm arasında birden fazla hat (paralel hatlar) varsa bu tür graflara "çoklu graf" (multi graf) denir. Çoklu graflar da yönsüz ve çevrimsizdir. Örneğin iki şehir arasında iki farklı yol varsa, bu durum çoklu grafla temsil edilir. Basit graflar, çoklu graftır fakat çoklu graflar basit graf değildir. Eğer bir graftaki hatlar yön bilgisine sahipse bu tür graflara "yönlü graf" (Directed graph/Digraph) denir. Bu yön bilgisi bağlantının nereden başlayıp nereden bittiğini belirtir. Yön bilgisi olan graflarda, düğümler arasındaki bağlantının bir yönü vardır. Eğer iki yönde bağlantı varsa ters yönde iki ayrı hat kullanılır ve bu tür graflara "çoklu yönlü graf" denir. Graf yapısında bütün hatlar, aynı çeşittir. Yani ya hepsi yönlüdür ya da değildir. Yol ağını temsil eden bir grafta trafiğin tek ya da çift yönlü oluşu, yönlü graflar için bir örnektir.

Graf yapısındaki hatlar, değer alabilir ve bu değerler grafın yapısına katılabilir. Bir grafın üzerindeki hatların değerleri eşit değilse ve her biri farklı bir değer alabiliyorsa bu tip graflara maliyetli ya da "ağırlıklı graf" (weighted graph) denir. Bütün hatların değeri aynı ise bu graf maliyetli graf olarak isimlendirilmez. Ağırlıkların bir anlamı yoktur ve her hattın değerinin 1 olduğu basit graf gibi değerlendirilir. Şehirlerin arasındaki mesafelerin hatlara değer olarak atandığı yol haritasını temsil eden graflar maliyetli graflar için örnek verilebilir. Birbirini kesmeyen hatlardan oluşacak şekilde çizilebilen graflara "düzlemsel graf" denir. Düzlemsel olmayan graflar, üç boyutlu uzayda ele alındığında hatlarının birbirini kesmeyecek şekilde çizilmesi mümkündür.

Bir düğümden diğerine gidilirken izlenecek düğümlerin tamamı bir "yol" (path) oluşturur. Eğer basit bir graf söz konusu ise, yolun uzunluğu, üzerinden geçilen hat sayısına eşittir. Fakat ağırlıklı graflarda yol uzunluğu, her bir hattın aldığı değerlerin toplamına eşittir. n uzunlugundaki bir yol’un (path) n+1 adet düğümü ve n adet de ardışık hattı vardır. Döngü, başladığı düğüme geri dönen ve aynı düğümden iki kez geçmeyen bir yoldur. Bir graftaki hat sayısı düğüm sayısına eşit yada fazlaysa, o graf en az bir döngü içeriyor demektir. Uzunluğu n olan bir döngüde n adet dügüm vardır. İçinde döngü barındırmayan grafa "ağaç" adı verilir. Ağaç graflar T (tree) ile gösterilir. Ağaca bir hat eklendiğinde mutlaka bir döngü içerir. Bir ağaçtaki hat sayısı düğüm sayısının bir eksiği kadardır. Bir grafta tüm düğümlerin derecesi 2 ise bu graflara "çember graf" denir. Çember grafına ek bir düğüm eklenerek "tekerlek graf" (wheel) oluşturulur.  Bir merkezi nokta ile her biri sadece bu noktayı birleştirilen uç noktalardan oluşan grafa "yıldız" (star) graf denir. Nokta sayısı n olan bir yıldız grafı 𝑆𝑛 ile gösterilir ve kenar sayısı da n-1 tane olur. 𝑆𝑛 yıldız grafında merkezdeki köşenin derecesi n-1, diğer köşelerin derecesi 1 olur. 

Düğüm sayısı üç veya daha fazla olan ve tek bir döngüden oluşan çizgelere “döngü graf” adı verilir. (C_n) ile gösterilir ve burada "n" düğüm sayısını ifade eder. Döngü çizgelerdeki tüm düğümlerin derecesi birbirine eşit ve 2’dir. Tekerlek çizgeler de döngü çizgelerin tam ortasına yeni bir düğüm eklenip bu düğümün diğer tüm düğümlere bağlanmasıyla bir çizge elde edilir. Tekerlek çizgeler, (W_n)şeklinde gösterilir. Tekerlek çizgelerde n düğüm ve 2(n-1) hat içerir. Eğer bir basit çizgede her bir düğüm diğer tüm düğümlerle bir bağlantıya sahipse bu durumda “tamamlanmış graf” varlığından söz edebilir. Tamamlanmış graflar (K_n) şeklinde gösterilir ve n burada düğüm sayısını ifade eder.

Bir grafta her bir düğümün kendisine olan en kısa uzaklıkların satır ve sütun şeklinde matris olarak tanımlanmasıyla "uzaklık matrisi" meydana gelir. Uzaklık matrisi 1969 yılında Frank Harary tarafından tanımlanmıştır. Uzaklık matrisinde her düğümden diğer düğümlere olan en kısa hat sayıları adet olarak sayılır ve bunlar bir matris şeklinde alt alta sırasıyla gösterilir. G grafının uzaklık matrisi, D(G) ile gösterilir ve D(G) uzaklık matrisi nxn boyutunda reel simetrik bir matris olur.

Bir çizgede birden fazla Euler döngüsü bulunabilir mi? sorusunun cevabı matematikçiler tarafından araştırılmış ve 1941 yılında dört matematikçi tarafından bulunan bir teorem ile probleme çözüm sunulmuştur. BEST teoremine göre, bir çizgedeki Euler döngülerinin sayısını bulmak için, bu çizgedeki tüm düğümlerin derecelerinin bir eksiğinin faktöriyelleri hesaplanır ve sonuçlar birbirleriyle çarpılır. Örneğin A, B, C, D düğümlerinden oluşan bir çizgede düğüm dereceleri sırasıyla 4, 4, 2, 2 olsun. Tüm düğüm dereceleri çift sayıda olduğu için burada bir Euler döngüsünün olduğundan söz edebiliriz. Düğüm derecelerinden bir eksilttiğimizde, 3, 3, 1,1 sayılarını elde ederiz. Bu sayıların faktöriyellerini hesapladığımızda da (3!, 3!, 1!, 1!) nihayetinde 6, 6, 1, 1 sayılarını elde ederiz. Bu sayıları birbiriyle çarptığımızda tüm çizgede 36 farklı Euler döngüsü olduğunu söyleyebiliriz.

Graf teorisi üzerine kurulu problemlerle günlük hayatımızda aslında sıkça karşılaşıyoruz. Örneğin çocukluğumuzda ilkokulda sıklıkla yaptığımız elimizi kaldırmadan çizilebilecek ev modeli, aslında bir çizge kuramıdır.  Aşağıdaki şekilden de görülebileceği gibi çizim üzerinde, çizgilerden yalnızca bir kez geçerek, yani elimizi kaldırmadan, çizimi tamamlayabilir miyiz? şeklinde bir problem, bir graf teorisi sorusudur. Bu problemde çizme işlemine tek dereceli düğümlerden başlarsak tüm çizgilerden sadece bir kez geçerek çizimi tamamlayabiliyoruz. Aksi halde çizimi tamamlamak mümkün değil.

Graf teorisi üzerinde yapılan çalışmalar, "Petri ağları" gibi birçok yeni kavramın geliştirilmesine imkân sağlamıştır. Petri ağları, bir sistemin matematiksel bir modelle temsil edilmesine olanak tanır ve süreçlerin grafiksel bir notasyon ile ifade edilmesini sağlar. Bu ağlar, geçiş (transition) ve yerleşim (place) düğümlerinden oluşan, tek yönlü iki parçalı bir grafik yapısına sahiptir. Oklarla gösterilen yönlü kenarlar, bir geçişten önce ve sonra hangi yerlerin bulunduğunu tanımlar. Bu yapı, süreçlerin akışını ve eşzamanlı işlemleri görselleştirmenin yanı sıra matematiksel olarak analiz etmeye de olanak tanır. Petri ağları, 1939 yılında Carl Adam Petri tarafından kimyasal süreçleri tanımlamak amacıyla geliştirildiği literatürde yer alır. Bu model, 1960 yıllardan sonra daha kapsamlı bir matematiksel temel üzerine oturtulmuş ve ağ/sistem analizleri için önemli bir araç haline gelmiştir. 

Kaynakça: 

1. Çizge kuramının Ortaöğretim Matematik dersi müfredatına eklenmesi, Nermin Yılmaz Çilingir, Tasarım Enformatiği, Cilt:2-2

2. Çizge Teorisi (Graph Theory), Sadi Evren SEKER, İstanbul Medeniyet University, YBS Ansiklopedi, Cilt 2, Sayı 2, Haziran 2015 

3. Büyük Çizgeler Daha Küçüklerinin Kopyalarıyla Oluşturulabilir mi? Dr. Tuncay BAYDEMİR, TÜBİTAK Bilim ve Teknik Dergisi, Kasım 2020

4. Sevtap Hamurkoparan, Grafın Uzaklık Matrisi ile ilgili sınır çalışmaları, Gazi Üniversitesi, 2021 

 

Graf Teorisi ile ilgili özet ders notuna ulaşmak için tıklayınız. (PDF)