Çizge Kuramı (Graf Teorisi)

Etiketler :
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. Temeli 1736'da Leonhard Euler tarafından atıldığı söylenmektedir. Çizge Teorisi çok farklı disiplinlerin çalışma alanına girmektedir. Sosyolojiden, bilgisayar bilimlerine, işletmeden, endüstri mühendisliğine kadar çok geniş alanlarda kullanımı olan 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. Çizge teorisi temel olarak bir problemin 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 çözülür ve daha sonra gerçek dünyaya uygulanır.
Graf teorisinin 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. etwork ağları, facebook, twitter gibi sosyal ağların kullanımı, gezgin satışçı probleminin çözümü (travelling salesman problemi- en kısa yollardan müşteriye ulaşma), mektup dağıtımı, yol bakımı, kar temizleme, çöp toplama, yollarda devreye araçlarının gezimi
Euler çözümünde biraz daha kolaylaştırmak ve şekli gereksiz bileşenlerden arındırmak amacıyla kara parçalarının noktalar, köprülerin ise bu noktaları birleştiren çizgiler olarak gösterildiği ikinci bir şekil yani graf (çizge) çizilir. Graflar graf elemanı, noktalar düğüm, düğüme bağlı olan elemanların sayısı ise düğüm derecesi olarak adladı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şma problemine dönüşmüş olur. 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: 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 iki olmalıdır. 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. Şekildeki çizgede 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ı 5tir.
 Çözümün temelinde yatan düşünce şudur: 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. 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. 
 
Matematiksel tanımı: 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) kenarlar kümesi olarak ifade edilir. Eğer düğümleri birbirine bağlayan kenarlar için giriş ve çıkış yönleri belirli ise bu kenarlara yönlü kenarlar denir. Eğer bir düğümden çıkan ve yine aynı düğüme giren bir kenar 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 kenar varsa bu kenarlara paralel kenarlar 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. Derece: Yönsüz bir çizgede, bir düğümün derecesi, kendisine gelen kenarların sayısıdır. 


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.
Düğüm sayısı üç veya daha fazla olan ve tek bir döngüden oluşan çizgelere “döngü çizge” adı verilir. C (n) ile gösterilir ve burada "n" düğüm ve hat 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) bağlantı 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ış çizge” varlığından söz edebilir.. Tamamlanmış çizgeler K(n) şeklinde gösterilir ve n burada düğüm sayısını ifade eder.
Graph 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ının, 1939 yılında Carl Adam Petri tarafından kimyasal süreçleri tanımlamak amacıyla geliştirildiği belirtilir. Bu model 1960'larda daha kapsamlı bir matematiksel temel üzerine oturtulmuş ve sistem analizi 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, Department of Business, Management Information Systems Program, 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, Bilim ve Teknik Dergisi, Kasım 2020

0 yorum:

Fayda vermeyen ilimden Allah'a sığınırım. “Allah'ım; bana öğrettiklerinle beni faydalandır, bana fayda sağlayacak ilimleri öğret ve ilmimi ziyadeleştir."

İlim; amel etmek ve başkalarıyla paylaşmak içindir. Niyetimiz hayır, akıbetimiz hayır olur inşallah. Dua eder, dualarınızı beklerim...

En Çok Okunan Yazılar

Aşağıdaki Yazılar İlginizi Çekebilir!!!