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.
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
