Çizge ile Görünmeyeni Görmek

Hiç İstanbul Metro haritasına dikkatlice baktınız mı? Ya da Instagram'da "arkadaş önerilerinin" nasıl karşınıza çıktığını düşündünüz mü? Belki de Google Maps'in binlerce sokak, trafik ışığı arasından en kısa yolu saniyeler içinde nasıl bulduğunu merak etmişsinizdir.

Çocukken kâğıt üzerinde oynadığımız o meşhur oyunu hatırlayın: Bir şekli kalemi kâğıttan hiç kaldırmadan yani elimizi kaldırmadan aynı çizginin üzerinden iki kez geçmeden çizebilir miyiz?

Görünürde birbirinden tamamen bağımsız gibi duran bu soruların cevabı, dünyayı sadece nesnelerle değil, "ilişkilerle" gören bir matematik disiplininde saklıdır: Çizge Teorisi (Graph Theory).

Bağlantıların Gizli Dünyası

Yüzyıllar boyunca dünyayı cetvellerle, pergel ve açıölçerlerle anlamaya çalıştık. Klasik geometri (Öklid Geometrisi), bize hep şu soruları sordurdu: "Bu bina ne kadar yüksek?", "İki şehir arası kaç kilometre?", "Bu açı kaç derece?". Ancak insan zihni, karmaşık sistemleri yalnızca nicel ölçümler aracılığıyla değil, bu sistemleri oluşturan bileşenler arasındaki ilişkisel yapılar üzerinden değerlendirme eğilimi göstermektedir.

Çizge Teorisi tam bu noktada, "Konum Geometrisi" adıyla ortaya çıkar ve nelerin tek tek konumlarından çok, aralarındaki bağlantı yapısının belirleyici olduğunu söyler: Nesnelerin nerede durduğu değil, birbirlerine nasıl bağlandığı önemlidir.

Bunu bir metro haritası gibi düşünün. Haritadaki istasyonların gerçek dünyadaki mesafeleri veya tünellerin kıvrımları sizi düşündürmez. Sizin için tek gerçek şudur: "Bu istasyon, gitmek istediğim istasyona bağlı mı?"

Bu disiplin, gerçek hayattaki karmaşık yapıları soyutlayarak analiz edilebilir hâle getiren güçlü bir matematiksel çerçeve sunmaktadır. Bir şehrin elektrik dağıtım altyapısından sosyal gruplar arasındaki etkileşim ağlarına kadar birçok sistem, düğümler (noktalar) ve kenarlar (ağ, ilişki, bağlantılar) aracılığıyla modellenebilmektedir. Matematikçilerin G = (V, E) biçiminde ifade ettiği bu temel gösterim, günümüzde yapay zekâ, internet altyapıları ve otonom sistemler gibi modern teknolojilerin kuramsal temelini oluşturmaktadır.

Hayatımızın Gizli Mimarı: Çizgeler Nerede?

Günlük yaşamda bireylerin etkileşimde bulunduğu birçok sistem fark edilmeden karmaşık ilişki ağları içerisinde işlemektedir. Çizge Teorisi yalnızca soyut bir matematik alanı değil; modern toplumların işleyişini anlamada temel bir analitik araçtır.

Sosyal Medyada Çizge

Sosyal medya platformları, insan ilişkilerini büyük ölçekli veri yapılarına dönüştüren dijital ortamlardır. Instagram, X (Twitter) veya LinkedIn gibi platformlar, milyarlarca kullanıcıyı (düğümler) ve aralarındaki etkileşimleri (kenarlar) analiz ederek dijital kimliğimizi oluşturur.

Bu ağlarda çizge teorisinin büyüleyici fenomenleri işler:

• Küçük Dünya Fenomeni: Dünyadaki herhangi bir insana, tanıdıklarınızın tanıdıkları üzerinden ortalama 6 adımda ulaşabileceğinizi biliyor muydunuz? Bu teori, ilk olarak Milgram'ın deneyleriyle ortaya atılmış ve daha sonra modern çizge teorisiyle matematiksel olarak modellenmiştir.
• Üçgen Kapanma İlkesi: "Arkadaşının arkadaşı, senin de arkadaşın olabilir" mantığı, çizge üzerindeki açık uçlu kenarların birleşerek üçgen oluşturma eğilimidir. Algoritmalar bu prensibi kullanarak size "Tanıyor Olabileceğiniz Kişiler" listesini sunar.

Ulaşım ve Lojistik

Bir kargo paketinin Çin'den yola çıkıp kapınıza gelmesi veya sabah trafiğinde işe geç kalmamanız, çizge teorisinin "optimizasyon" gücüne bağlıdır. Navigasyon sistemleri (Google Maps, Yandex), dünyayı "Ağırlıklı Çizge" olarak modeller. Burada yollar kenardır; ancak her kenarın bir "ağırlığı" vardır: Mesafe, trafik yoğunluğu veya yol çalışması.

Sistem, binlerce olasılık arasından maliyeti (zamanı) en düşük olan rotayı Dijkstra veya A* algoritmalarıyla saniyeler içinde hesaplar.

İnternet: Bilginin Örümcek Ağı

"World Wide Web" (Dünya Çapında Ağ) ifadesi, internetin yapısal özelliklerini doğrudan yansıtmaktadır. İnternet, insanlık tarihinde oluşturulmuş en büyük çizge yapılarından biri olarak ele alınmaktadır.

• Fiziksel Katman: Bilgisayarlar, sunucular ve modemler birer düğüm; okyanus tabanındaki fiber optik kablolar ise kenarlardır. Veri paketleri, en güvenli ve hızlı yolu bulmak için bu çizge üzerinde seyahat eder.
• Mantıksal Katman: Web siteleri arasındaki linkler (bağlantılar), yönlü bir çizge oluşturur. Google'ın "PageRank" algoritması, bir web sitesine verilen linkleri ağırlıklı oy olarak yorumlar.

Yapay Zekâ ve Biyoloji

İnsan beyni, yaklaşık 86 milyar nöronun (düğüm) trilyonlarca sinapsla (kenar) birbirine bağlandığı biyolojik bir çizgedir. Bugün Yapay Zekâ (Deep Learning) teknolojisi, beynin bu yapısını taklit eden "Yapay Sinir Ağları" üzerine kuruludur.

Benzer şekilde biyolojide "Protein Etkileşim Ağları", ilaç tasarımında devrim yaratmaktadır. Tüm bu örneklerden anlıyoruz ki gerçek hayattaki bir problemi önce çizge olarak ifade edebilir ve çizge üzerinde çözüm arayıp bulunan sonuçları yeniden gerçek dünyaya aktarabiliriz.

1.1 Çizge Tanımı ve Temel Bileşenler

Günlük hayatta karşılaştığımız birçok problem, düğümler ve bu düğümler arasındaki bağlantılar kullanılarak modellenebilir. Matematikte bu tür yapılar çizge (graph) olarak adlandırılır.

Matematiksel Tanım

Bir çizge, matematikte kısa ve net bir şekilde aşağıdaki gibi gösterilir:

G = (V, E)

Bu gösterimde:

• V (Vertices), çizge üzerindeki tüm düğümlerin (noktaların) oluşturduğu kümedir.
• E (Edges) ise, bu düğümler arasındaki bağlantıları (kenarları) temsil eden kümedir.

Bu tanım sayesinde, bir çizgedeki noktalar ve bu noktalar arasındaki ilişkiler matematiksel olarak açık ve düzenli bir biçimde ifade edilebilir.

Düğümler (Vertices)

Düğümler, modellediğimiz sistemdeki temel noktaları temsil eder. Bu noktalar probleme göre farklı anlamlar kazanabilir. Bu sayede, karmaşık görünen sistemler daha basit parçalara ayrılır ve incelenmesi çok daha kolay hâle gelir.

• Ulaşım ağlarında duraklar veya istasyonlar,
• Sosyal ağlarda kullanıcı hesapları,
• Biyolojik ağlarda proteinler veya türler birer düğümdür.

Kenarlar (Edges)

Kenarlar, düğümler arasındaki etkileşimi veya bağlantıyı ifade eder. Bu bağlantılar fiziksel ya da soyut olabilir. Kenarlar, ilişki, bilgi, enerji veya etkileşim akışını modelleyen temel unsurlardır.

1.2 Çizge Çeşitleri: İlişkilerin Doğası

Gerçek dünya problemlerinde ilişkiler tek tip değildir. Bu nedenle çizgeler, kenarların özelliklerine göre sınıflandırılır. Bu sınıflandırma, kurulacak matematiksel modelin doğruluğunu doğrudan etkiler.

1.2.1 Yönlü ve Yönsüz Çizgeler

İlişkinin doğasını belirleyen en temel ayrımdır.

Yönsüz Çizge

İlişkinin karşılıklı olduğu durumdur. Bu tür çizgelerde kenarlar yön içermez ve şu şekilde gösterilir:

(u, v) = (v, u)

Günlük hayattan en basit örneklerden biri tokalaşmadır: Sen benimle tokalaşırsan ben de seninle tokalaşmış olurum. Benzer şekilde Facebook arkadaşlığı veya iki cihaz arasındaki Wi-Fi bağlantısı, karşılıklı etkileşim gerektiren yönsüz ilişkilere örnektir.

Yönlü Çizge

İlişkinin tek taraflı olduğu durumdur. Kenarların ucunda ok işareti vardır ve şu şekilde gösterilir:

u → v

Örnek verecek olursak "Hediyeleşme". Ali, Veli'ye hediye verdiğinde, Veli'nin de Ali'ye hediye vermiş olduğu kabul edilmez. Bu nedenle ilişki tek yönlüdür. Instagram takibi, tek yönlü sokaklar ve besin zincirleri de yönlü çizgelere örnektir.

1.2.2 Ağırlıklı Çizgeler

Ağırlıklı çizgeler, özellikle en kısa yol, en düşük maliyet veya en verimli rota problemlerinde yaygın olarak kullanılmaktadır.

1.2.3 Yol

Bir labirentte çıkışı ararken attığınız her adımı düşünün. Her kavşak bir düğümü, her koridor ise bir kenarı temsil eder. Labirentten çıkana kadar izlediğiniz adımların tamamı, çizge üzerinde tanımlı bir yol oluşturur.

Basit Yol: Bir yol üzerinde hiçbir düğümün tekrar edilmediği durumdur. Her düğüm yalnızca bir kez ziyaret edilir. Basit yollar, özellikle en kısa yol problemlerinde ve çevrimsiz yapıların analizinde önemlidir.

Yol kavramı, birçok temel algoritmanın merkezinde yer alır. En kısa yol algoritmaları (Dijkstra, A*), bir çizge üzerinde belirli iki düğüm arasındaki en uygun yolu ararken; ağ akışı, bağlantılılık analizi ve döngü tespiti gibi problemler de farklı yol türlerine dayanır.

1.2.4 Bağlantılı Çizgeler

Bir arkadaş grubunu düşünelim. Eğer bu gruptaki herkes, birbirini doğrudan tanımasa bile ortak arkadaşlar aracılığıyla dolaylı olarak birbirine ulaşabiliyorsa grup bütünüyle bağlantılıdır. Başka bir deyişle, herhangi iki kişi arasında mutlaka bir "tanışıklık zinciri" vardır.

1.2.5 Döngü

Döngü, bir başlangıç noktasından hareket edilerek farklı aşamalardan geçildikten sonra tekrar aynı noktaya dönülmesiyle tanımlanabilir. Bu tür yapılar, çizge teorisi bağlamında döngüsel ilişkilerin modellenmesine imkân tanır.

1.3 Özel Çizge Yapıları

1.3.1 Tam Çizgeler

Bir çizgede yer alan her düğüm çifti arasında doğrudan bir kenar bulunuyorsa, bu çizge tam çizge olarak adlandırılır. n düğümlü bir tam çizge Kₙ ile gösterilir.

1.3.2 Ağaçlar

Çizge kuramında ağaç, döngü içermeyen ve bağlantılı olan bir çizge olarak tanımlanır. Bir başka ifadeyle, bir ağaçta herhangi iki düğüm arasında yalnızca bir tek yol bulunur. n düğümlü bir ağaçta kenar sayısı her zaman n − 1'dir.

Ağaç yapılarının en temel ayırt edici özelliği, yapıda hiçbir döngünün bulunmamasıdır. Bu nedenle, bir düğümden başlayarak ilerleyen bir yolun tekrar aynı düğüme geri dönmesi mümkün değildir.

2.1 Königsberg'te Bir Gün

1736 yılında Königsberg (günümüzde Kaliningrad) şehri, Pregel Nehri tarafından iki kola ayrılıyor ve nehir üzerinde yer alan iki ada ile birlikte şehir dört ayrı kara parçasından oluşuyordu. Bu kara parçalarını birbirine bağlayan toplam yedi köprü bulunmaktaydı.

Bu soru, ilk bakışta bir yürüyüş veya planlama problemi gibi görünse de uzun süre boyunca kimse kesin bir çözüm ortaya koyamamıştı.

2.2 Euler'in Devrimsel Yaklaşımı

Ünlü matematikçi Leonhard Euler, bu problemi ele aldığında alışılmış geometrik yöntemlerin dışına çıktı. Euler, problemi çözmek için haritadaki şu unsurları göz ardı etti:

• Binaların şekillerini,
• Köprülerin uzunluklarını,
• Nehrin kıvrımlarını,
• Gerçek mesafelerini.

Bunun yerine Euler, problemi daha soyut bir düzleme taşıdı. Kara parçalarını nokta (düğüm), köprüleri ise bu noktaları birleştiren çizgi (kenar) olarak düşündü. Bu yaklaşım, tarihteki ilk çizge modellemesi olarak kabul edilir.

2.3 Fiziksel Haritadan Matematiksel Çizgeye

Euler'in soyutlaması sayesinde, şehirdeki karmaşık fiziksel yapı matematiksel bir çizgeye dönüştürüldü. Her kara parçası bir düğüm, her köprü ise bir kenar olarak temsil edildi.

Bu modele göre düğümlerin dereceleri şu şekildedir:

• A düğümü: 3 köprü ile bağlıdır ⇒ deg(A) = 3
• B düğümü: 3 köprü ile bağlıdır ⇒ deg(B) = 3
• C düğümü: 5 köprü ile bağlıdır ⇒ deg(C) = 5
• D düğümü: 3 köprü ile bağlıdır ⇒ deg(D) = 3

2.4 Euler ve Hamilton Yaklaşımları

Bir çizge üzerinde tanımlanan yollar, kenarların veya düğümlerin tekrar edilip edilmemesine göre farklı matematiksel kavramlara ayrılmaktadır. Bu çerçevede çizge teorisinin iki temel problemi Euler ve Hamilton yollarıdır.

2.4.1 Euler Yolu ve Euler Döngüsü

Leonhard Euler, yönsüz çizgelerde Euler yolu ve Euler döngüsünün varlığının, yalnızca düğüm derecelerine bağlı koşullarla tespit edilebildiğini göstermiştir. Buna göre:

• Tüm düğümleri çift dereceli olan bir çizge, bir Euler Döngüsüne sahiptir.
• Yalnızca iki düğümü tek dereceli, geri kalan tüm düğümleri çift dereceli olan bir çizge ise bir Euler Yolu içerir.

2.4.2 Hamilton Yolu ve Hamilton Döngüsü

Hamilton yaklaşımı, Euler yaklaşımından farklı olarak kenarlar yerine düğümleri esas alır. Bu bağlamda amaç, bir çizgede yer alan tüm düğümlerin hiçbiri tekrar edilmeden tek bir yol üzerinde ziyaret edilip edilemeyeceğini incelemektir.

Hamilton yolunun başladığı düğümde sona erdiği özel duruma Hamilton Döngüsü adı verilir.

2.4.3 Euler ve Hamilton Yaklaşımlarının Temel Farkı

Özellik	Euler	Hamilton
Odak	Kenarlar	Düğümler
Amaç	Tüm kenarları 1 kez geç	Tüm düğümleri 1 kez ziyaret et
Koşul (varlık)	Düğüm derecelerine göre belirlenir	Genel koşul bilinmiyor
Hesaplama zorluğu	Polinom zamanda çözülebilir	NP-zor

Hamilton yaklaşımı, özellikle Gezgin Satıcı Problemi (TSP) olarak bilinen klasik optimizasyon probleminin kuramsal temelini oluşturmaktadır. Milyonlarca şehir içeren bir haritada en kısa Hamilton döngüsünü bulmak, modern süper bilgisayarları bile zorlayan bir hesaplama problemidir.

Uygulama Alanları

• Lojistik ve Rota Optimizasyonu: Kargo ve dağıtım firmaları, tüm teslimat noktalarına uğrayıp en kısa yoldan depoya dönmek için Gezgin Satıcı Problemi yaklaşımlarını kullanır.
• Kriptografi ve Sıfır Bilgi İspatı: Hamilton döngüleri, sıfır bilgi ispatlarında kritik bir rol oynar. Bu yaklaşım, modern blokzincir teknolojileri ve güvenli kimlik doğrulama sistemlerinin temel yapı taşlarından biridir.

3.1 Çizilemeyen Ağlar ve Düzlemsellik

Bir veri merkezinde yer alan üç farklı sunucu (A, B, C) ile üç farklı veri deposu (Ç, D, E) arasındaki bağlantı ihtiyacını ele alalım. Her bir sunucunun, her bir veri deposu ile yüksek hızlı ve güvenilir biçimde doğrudan veri alışverişi yapması gerekmektedir. Bununla birlikte, sistem tasarım kuralları gereği bağlantıların birbirini kesmemesi, yani çizge üzerinde herhangi bir çapraz bağlantının bulunmaması istenmektedir.

Bu yapı, çizge teorisi açısından incelendiğinde, sunucular ve depolar olmak üzere iki ayrı düğüm kümesinden oluşan ve her sunucunun her depoya bağlandığı tam iki parçalı çizgeye karşılık gelmektedir. Başka bir ifadeyle problem, matematiksel olarak K₃,₃ çizgesinin düzlemsel (kesişimsiz) biçimde çizilip çizilemeyeceğini sorgulamaktadır.

Çözüm denemesinde bazı bağlantılar başarıyla kurulmuş gibi görünse de, kritik bir noktada zorunlu bir çakışma ortaya çıkmaktadır. Özellikle A sunucusunun E deposu ile olan bağlantısı, diğer bağlantılar kesişmeden çizildiğinde, mutlaka mevcut bir kenarın üzerinden geçmek zorunda kalmaktadır.

3.1.1 Düzlemsellik ve İmkânsızlık

Verilen tasarım koşullarına göre, çizgenin düzlemsel olması, yani tüm kenarların bir düzlem üzerinde birbirini kesmeden çizilebilmesi beklenmektedir. Ancak, K₃,₃ çizgesi için bu mümkün değildir.

Çizge teorisinin temel sonuçlarından biri, K₃,₃ çizgesinin düzlemsel olmayan bir çizge olduğudur. Başka bir ifadeyle, bu çizge, ne şekilde çizilirse çizilsin, en az iki kenarın bir noktada kesişmesi kaçınılmazdır.

Dolayısıyla, verilen koşullar altında sunucular ile veri depoları arasında çapraz bağlantı içermeyen bir yapı kurmak matematiksel olarak mümkün değildir.

Problemin doğasının iki boyutlu bir düzlemde çözüme izin vermediğini göstermektedir. Gerçek hayatta bu tür durumlar, çok katmanlı kablolama, farklı seviyelerden geçişler ya da üç boyutlu mimari çözümlerle aşılmaktadır.

4.1 Dünyayı Boyamak: Kromatik Sayı (χ)

Çizge teorisinin temel problemlerinden biri, bir çizgenin düğümlerini, birbirine komşu olan düğümler aynı renge sahip olmayacak biçimde boyamak için gerekli olan en az renk sayısını belirlemektir.

4.1.1 Dört Renk Teoremi ve Haritalar

1852 yılında Francis Guthrie, İngiltere haritasını boyarken komşu bölgelerin ayrılması için yalnızca dört rengin yeterli olduğunu gözlemlemiştir. Bu gözlem, düzlemsel her haritanın en fazla dört renkle boyanabileceğini ifade eden Dört Renk Teoremi'nin temelini oluşturmuştur.

Bir haritayı çizgeye dönüştürmek için:

• Her bölge bir düğüm ile temsil edilir,
• Sınır komşusu olan bölgeler arasına bir kenar çizilir,
• Ortaya çıkan çizgede komşu düğümlerin aynı renkte olmaması gerekir.

4.2 Sudoku Bir Boyama Problemidir

Sudoku genellikle bir sayı yerleştirme bulmacası olarak görülse de matematiksel açıdan bir çizge boyama problemidir. 9×9 boyutundaki klasik bir Sudoku, 81 düğümden oluşan karmaşık bir çizge olarak modellenebilir.

4.2.1 Sudoku'nun Çizgeye Dönüştürülmesi

• Hücreler → Düğümler: Her bir kare, çizgede bir düğümü temsil eder. 4×4 Sudoku için 16, klasik Sudoku için 81 düğüm vardır.
• Kurallar → Kenarlar: Aynı satırda, sütunda veya blokta yer alan hücreler birbiriyle komşudur ve aralarına kenar çizilir.
• Rakamlar → Renkler: Sudoku'daki sayılar, matematiksel modellemede renkler olarak yorumlanır.

4.2.2 K₄ ve Tam Çizge Mantığı

Aynı satırda yer alan dört hücre, birbirleriyle doğrudan ilişkilidir. Bu yapı, her düğümün diğer tüm düğümlere bağlı olduğu tam çizgeyi, yani K₄'ü oluşturur. K₄'ün boyanabilmesi için en az dört farklı renge ihtiyaç vardır.

Benzer şekilde, klasik Sudoku'da her satır, sütun ve blok birer K₉ tam çizgesi oluşturur. Bu nedenle Sudoku çizgesinin kromatik sayısı:

χ(G) = 9

olmak zorundadır.

4.2.3 Algoritmik Çözüm: Geri İzleme (Backtracking)

81 düğüm ve yüzlerce kenardan oluşan bu yapı, bilgisayar ortamında genellikle geri izleme (backtracking) algoritması ile çözülür.

Algoritma şu şekilde çalışır:

• Boş bir düğüm seçilir ve uygun bir renk atanır.
• Çakışma yoksa bir sonraki düğüme geçilir.
• Çakışma oluşursa geri dönülerek alternatif bir renk denenir.

9×9 Sudoku için χ(G) = 9 olduğu bilindiğinden, geri izleme algoritması en kötü durumda bile bir çözümün varlığını teorik olarak garanti eder.

4.3 Kaosun İmkânsızlığı: Ramsey Teoremi

Sudoku çatışmayı önlemeye odaklanırken, Ramsey Teoremi belirli bir büyüklüğün üzerindeki yapılarda bazı düzenlerin kaçınılmaz olduğunu söyler.

4.4 Ramsey Teoremi ve Parti Problemi

Ramsey Teoremi, yeterince büyük her sistemde belirli düzenli yapıların kaçınılmaz olarak ortaya çıktığını ifade eder. Bu ilke, "mutlak kaosun" matematiksel olarak mümkün olmadığını gösteren en güçlü sonuçlardan biridir.

4.4.1 Parti Problemi

Ramsey teorisinin en bilinen örneklerinden biri Parti Problemi'dir. Bir partide 6 kişi bulunduğu varsayılsın. Altı kişilik bu grupta her iki kişi ya birbirini tanır ya da tanımaz. Bu ilişkiler nasıl düzenlenirse düzenlensin, grup içinde mutlaka ya birbirini tanıyan üç kişi ya da birbirini tanımayan üç kişi bulunur.

Her iki kişi arasında yalnızca iki olası ilişki vardır:

• Birbirlerini tanıyorlarsa, aralarındaki ilişki mavi bir kenarla gösterilir.
• Birbirlerini tanımıyorlarsa, aralarındaki ilişki kırmızı bir kenarla gösterilir.

Bu durumda ortaya çıkan yapı, 6 düğümlü tam çizge K₆'dır; ancak kenarlar iki farklı renkle boyanmıştır.

Bu sonuç, şu eşitlik ile ifade edilir:

R(3, 3) = 6

4.4.2 Ramsey Sayıları

4.4.3 Bazı Ramsey Sayıları

Ramsey Sayısı	Değer	Durum
R(3,3)	6	Biliniyor
R(3,4)	9	Biliniyor
R(3,5)	14	Biliniyor
R(4,4)	18	Biliniyor
R(3,6)	18	2022'de bulundu
R(4,5)	25	2017'de bulundu
R(5,5)	43 ≤ R(5,5) ≤ 48	Bilinmiyor
R(6,6)	102 ≤ R(6,6) ≤ 165	Çok zor

4.4.4 Neden Bu Kadar Zor?

Ramsey sayılarının hesaplanmasının güç olmasının başlıca nedenleri şunlardır:

• Olası kenar boyamalarının sayısı astronomik biçimde artar.
• Örneğin R(5,5) için kontrol edilmesi gereken durum sayısı 2⁴³'ten fazladır.
• Bu büyüklük, günümüz bilgisayarları için bile pratik olarak erişilemez düzeydedir.

4.4.5 Erdős'ün Ünlü Sözü

"Uzaylılar gelip R(5,5)'i bulmazsak dünyayı yok ederiz deseler, tüm bilim insanlarını toplar ve bulurduk. Ama R(6,6)'yı isteseler, onlarla savaşmaya çalışırdık."

— Paul Erdős

4.4.6 Uygulama Alanları

Ders programı hazırlamak, sınav takvimi oluşturmak veya ulaşım planlamak gibi zamanla ilişkili planlama problemleri, çizge teorisinin önemli uygulama alanları arasındadır.

Bu tür problemlerde temel amaç, birden fazla görevi çakışma olmadan ve en az sayıda kaynak kullanarak planlamaktır.

4.4.7 Felsefi Yorum

5.1 PageRank Algoritması Nedir?

PageRank, bir çizgedeki düğümlerin göreli önemini ölçmek için geliştirilmiş bir algoritmadır. İlk olarak 1996 yılında, Google'ın kurucuları Larry Page ve Sergey Brin tarafından, web sayfalarının önem sırasını belirlemek amacıyla geliştirilmiştir.

PageRank algoritmasında her bağlantı eşit kabul edilmez. Bağlantı sayısından çok, bağlantının geldiği düğümün önem derecesi dikkate alınır. Önemli bir düğümden gelen bağlantı, önemsiz bir düğümden gelen çok sayıda bağlantıdan daha değerlidir.

Bu yaklaşım, çizge teorisinde ağırlıklı etki fikrine karşılık gelir.

5.1.1 Kulüp İçi İletişim Ağı Örneği

PageRank'in çalışma mantığı, bir okul kulübü içerisindeki iletişim ve bilgi paylaşım ağı üzerinden açıklanabilir. Bir kulüp üyesinin ağ içindeki etkisi, yalnızca kaç kişiyle iletişim kurduğuna değil, bu iletişimin hangi üyeler tarafından başlatıldığına da bağlıdır.

Bu durumu somutlaştırmak için, bir okul kulübünde görev alan beş öğrenciden oluşan bir grup düşünelim: Ahmet, Ayşe, Mehmet, Zeynep ve Can. Başlangıçta tüm üyeler eşit kabul edilir ve her birine başlangıç değeri verilir:

1/5 = 0.20

Öğrenciler arasındaki yönlü bağlantılar aşağıdaki gibidir:

• Ahmet, Ayşe ve Mehmet'e,
• Ayşe, Mehmet'e,
• Mehmet, Zeynep ve Can'a,
• Zeynep, Can'a,
• Can ise Ahmet'e bağlantı vermektedir.

5.1.2 Puanların Dağıtılması (Birinci İterasyon)

Algoritmanın ilk adımında, her öğrenci sahip olduğu puanı, bağlantı verdiği kişi sayısına bölerek paylaştırır.

• Ahmet: İki bağlantısı vardır. Puanını ikiye bölerek Ayşe ve Mehmet'e 0.10 değerinde aktarır.
• Ayşe: Tek bağlantısı olduğu için puanının tamamını Mehmet'e aktarır → 0.20
• Mehmet: İki bağlantısı vardır. Zeynep ve Can'a 0.10 değerinde katkı sağlar.
• Zeynep: Tek bağlantısı (Can) → 0.20 verir.
• Can: Tek bağlantısı (Ahmet) → 0.20 verir.

Bu adım sonunda Mehmet gibi birden fazla kişiden bağlantı alan öğrencilerin puanı artmaktadır. Bu aşamada Mehmet'in ham puanı:

0.10 + 0.20 = 0.30

Öğrenci	Aldığı Puanlar	Yeni PageRank
Ahmet	Can'dan: 0.20	0.20
Ayşe	Ahmet'ten: 0.10	0.10
Mehmet	Ahmet'ten: 0.10 + Ayşe'den: 0.20	0.30 ⭐
Zeynep	Mehmet'ten: 0.10	0.10
Can	Mehmet'ten: 0.10 + Zeynep'ten: 0.20	0.30 ⭐

5.1.3 Sönümleme Faktörü

Gerçek hayatta bir kullanıcı her zaman bağlantıları takip etmez; bazen rastgele başka bir sayfaya geçer. Bu durum sönümleme faktörü (damping factor) ile modellenir.

• α = 0.85 olasılıkla bağlantılar takip edilir,
• 1 − α = 0.15 olasılıkla rastgele bir düğüme geçilir.

PageRank'in genel formülü şu şekilde yazılır:

PR(v) = (1 − α) / N + α × Σ [PR(u) / d(u)]

Burada:

• N: toplam düğüm sayısı
• B(v): v düğümüne bağlantı veren düğümler
• d(u): u düğümünün dış bağlantı sayısı

6.1 Bilgisayar Bilimi ve Algoritmalar

Bilgisayar bilimlerinde veri yapıları ve algoritmaların önemli bir bölümü çizge temelli olarak geliştirilmiştir.

• İnternet yönlendirme protokolleri,
• Sosyal ağ analizleri,
• Arama motorlarının bağlantı yapıları,
• Yapay zekâda durum-uzayı aramaları

çizge modelleriyle incelenir.

Özellikle en kısa yol, en iyi eşleştirme ve geri izleme (backtracking) algoritmaları, Sudoku örneğinde olduğu gibi, karmaşık problemlerin bilgisayar tarafından etkin biçimde çözülmesini mümkün kılar.

6.2 Telefon Hatları ve Kablo Ağları

Telefon ve internet altyapıları, çizge teorisinin günlük hayattaki en somut uygulamalarından biridir. Bu tür ağlarda:

• Telefon santralleri, baz istasyonları ve yönlendiriciler düğüm,
• Bu birimler arasındaki kablolar ve sinyal hatları kenar olarak modellenir.

Bir şehirde telefon kabloları planlanırken, hatların gereksiz yere kesişmemesi, en kısa ve en güvenilir bağlantıların kurulması amaçlanır. Bu problem, en kısa yol, ağ tasarımı ve düzlemsel çizgeler kavramlarıyla doğrudan ilişkilidir.

Ayrıca, bir hattın kopması durumunda iletişimin tamamen kesilmemesi için alternatif yolların bulunması gerekir. Bu durum, çizgelerde bağlantılılık ve yedeklilik kavramlarının önemini ortaya koyar.

6.3 Elektrik ve Enerji Dağıtım Ağları

Elektrik şebekeleri, üretim santrallerinden tüketim noktalarına enerji ileten büyük ölçekli çizgelerdir. Bu sistemlerde:

• Santraller, trafolar ve dağıtım merkezleri düğüm,
• Enerji iletim hatları kenar olarak ele alınır.

Amaç, enerji kaybını en aza indiren ve arıza durumlarında hızla yön değiştirilebilen bir ağ yapısı oluşturmaktır. Bu tür problemler, minimum kapsayan ağaç ve akış problemleri yardımıyla çözülür.

6.4 Ulaşım ve Yol Ağları

Şehir içi ulaşım sistemleri de doğal olarak çizge yapısına sahiptir.

• Kavşaklar düğüm,
• Yollar, ray hatları ve güzergâhlar kenar olarak temsil edilir.

Navigasyon uygulamalarının en kısa veya en hızlı rotayı hesaplaması, çizge teorisinde geliştirilmiş algoritmalara dayanır. Trafik yoğunluğu gibi değişkenler, kenarlara ağırlık verilerek modele dâhil edilir.

6.5 Biyoloji ve Biyoinformatik

Canlı sistemler, yoğun etkileşim içeren ağlardan oluşur. Bu nedenle biyolojide çizge teorisinin uygulama alanı oldukça geniştir.

• Protein–protein etkileşimleri,
• Gen düzenleyici ağlar,
• Sinir hücreleri arasındaki bağlantılar

çizge modelleriyle analiz edilir.

Bu yaklaşım sayesinde, biyolojik sistemlerdeki kritik düğümler, fonksiyonel alt yapılar ve hastalıklarla ilişkili bozulmalar belirlenebilir.

6.6 Sosyal Bilimler ve Sosyal Ağlar

Sosyal ilişkiler, doğal olarak çizge yapısına sahiptir. Bireyler düğüm, aralarındaki ilişkiler ise kenar olarak modellenir.

Bu yaklaşım:

• Toplulukların belirlenmesi,
• Bilgi ve etki yayılımının incelenmesi,
• Sosyal medya analizleri

gibi alanlarda kullanılır.

Ramsey Teoremi, yeterince büyük sosyal yapılarda belirli düzenlerin kaçınılmaz olduğunu göstermesi bakımından, sosyal ağ analizlerine teorik bir temel sunar.

6.7 Ekonomi ve Oyun Teorisi

Ekonomik sistemlerde firmalar, tüketiciler ve piyasalar birbirleriyle etkileşim hâlindedir. Bu ilişkiler:

• Ticaret ağları,
• Finansal bağlantılar,
• Risk yayılımı

çizge teorisi kullanılarak modellenir.

Oyun teorisinde ise, oyuncular arasındaki stratejik ilişkiler çizge yapılarıyla temsil edilir. Bu sayede denge noktaları ve en iyi stratejiler analiz edilebilir.

6.8 Eğitim ve Öğrenme Süreçleri

Eğitimde, bilgiler arasındaki ilişkilerin görselleştirilmesi, öğrenmenin kalıcılığını artırır. Kavram haritaları ve öğrenme ağları, çizge temelli yaklaşımlardır.

Bu kitapta ele alınan Sudoku, harita boyama ve Parti Problemi örnekleri, matematiğin soyut bir alan olmaktan çıkıp günlük hayat ve diğer disiplinlerle nasıl bütünleştiğini göstermektedir.

• Biggs, N., Lloyd, E., & Wilson, R. (1986). Graph Theory. Oxford University Press, Oxford.
• Bogart, K. P. (2004). Combinatorics through guided discovery (pp. 1–21). Kenneth P. Bogart.
• Bondy, J. A., & Murty, U. S. R. (2008). Graduate Texts in Mathematics.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill.
• Demirci, C. et al. (2023). Ortaöğretim matematik 9. sınıf ders kitabı. Millî Eğitim Bakanlığı Yayınları.
• Diestel, R. (2017). Graph Theory. Springer, Berlin, Heidelberg.
• Euler, L. (1741). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 128–140.
• Garey, M. R., & Johnson, D. S. (1990). Computers and Intractability.
• Goldreich, O. (2001). Foundations of cryptography: Volume 2. Cambridge University Press.
• Graham, R. L., Rothschild, B. L., & Spencer, J. H. (1991). Ramsey theory. John Wiley & Sons.
• Gross, J. L., Yellen, J., & Anderson, M. (2018). Graph theory and its applications. Chapman and Hall/CRC.
• Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic polynomials. Notices of the AMS, 54(6), 708–717.
• Langville, A. N., & Meyer, C. D. (2011). Google's PageRank and beyond.
• Milgram, S. (1967). The small world problem. Psychology Today, 2(1), 60–67.
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking. Stanford InfoLab.
• Pistilli, F., & Averta, G. (2023). Graph learning in robotics: a survey. IEEE Access, 11, 112664–112681.
• Radziszowski, S. (2012). Small Ramsey numbers. The Electronic Journal of Combinatorics, DS1.
• Ramsey, F. P. (1987). On a problem of formal logic. In Classic Papers in Combinatorics (pp. 1–24).
• Sitorus, P., & Zamzami, E. M. (2020). An implementation of backtracking algorithm for solving a Sudoku-Puzzle. Journal of Physics: Conference Series, 1566(1), 012038.
• Şeker, S. E. (2015). Çizge teorisi (graph theory). YBS Ansiklopedi, 2(2), 17–29.
• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440–442.
• West, D. B. (2001). Introduction to graph theory. Prentice Hall.