Topoloji ve Kombinatorik · 1736'dan Bugüne
18. yüzyılda Doğu Prusya'nın Königsberg şehrinin ortasından Pregel Nehri geçiyordu. Nehir şehri dört kara parçasına bölüyordu — bir kuzey kıyısı, bir güney kıyısı ve iki ada. Bu dört parça yedi köprüyle birbirine bağlanıyordu.
Şehrin sakinleri yıllarca kendine şunu sordu: Bu yedi köprünün her birinden tam bir kez geçen bir yürüyüş rotası var mı? Nereden başlarsanız başlayın, nerede bitirirseniz bitirin — tek kural: her köprüden yalnızca bir kez.
Kimse bulamadı. Ama bu "bulunamadı" ile "imkânsız" arasında büyük bir fark var. Kendiniz deneyin.
Graf Teorisinin Temelleri
Euler'in dahiyane adımı, Königsberg'i bir graf'a dönüştürmekti: kara parçaları düğüm (vertex/node), köprüler ise kenar (edge) oldu. Mesafeler, şekiller, yönler — hiçbiri önemli değildi; sadece hangi düğümlerin birbirine bağlı olduğu önemliydi.
\(V\) düğümler kümesi, \(E\) kenarlar kümesi. Bir düğümün derecesi (degree) \(\deg(v)\), o düğüme bağlı kenar sayısıdır.
Her kenar, tam olarak iki düğümü birbirine bağlar, dolayısıyla derece toplamına ikişer ikişer katkıda bulunur:
\[\sum_{v\in V}\deg(v)=2|E|\]
Buradan, tek dereceli düğüm sayısı her zaman çifttir. Bu, Euler'in Königsberg kanıtının temel taşı. Aynı zamanda "el sıkışma lemması" adıyla da bilinir: bir partide el sıkışan toplam el sayısı çifttir (her el sıkışma iki kişiyi içerir).
Königsberg grafında dört düğümün dereceleri: kuzey kara 3, güney kara 3, batı ada 5, doğu ada 3. Dört düğümün dördü de tek dereceli. Euler'in teoremi şunu söyler: bir grafta Euler yolu (her kenarı tam bir kez geçen yol) varsa, en fazla 2 düğüm tek dereceli olabilir. Dört tek dereceli düğümle bu imkânsız. Kanıt, 288 yıl önce verildi ve hâlâ geçerli.
Euler yolu: grafın her kenarını tam bir kez kullanan bir yol. Euler çevrimi: başladığı noktaya dönen Euler yolu.
Königsberg: 4 tek dereceli düğüm → imkânsız. Eğer bir köprü daha eklenseydi (örneğin iki adayı birbirine bağlayan sekizinci bir köprü), iki düğümün derecesi çift olurdu ve Euler yolu mümkün olurdu.
1736'dan Günümüze
Euler, "Solutio problematis ad geometriam situs pertinentis" (Konum Geometrisiyle İlgili Bir Problemin Çözümü) başlıklı makalesini St. Petersburg Akademisi'ne sundu (26 Ağustos 1735), 1741'de yayımlandı. Makale iki önemli şeyi yapıyordu: köprü problemini çözdü ve bu çözümün neden sayısal ölçüm olmaksızın çalıştığını gösterdi. Euler, "geometria situs" (konum geometrisi) diyerek mesafeye bakmadan bağlantıyı incelemenin yeni bir matematik alanı olduğunu sezdi. Bugün buna topoloji ve graf teorisi diyoruz.
Kirchhoff, elektrik devrelerini analiz ederken düğümler ve kenarlardan oluşan yapılar kullandı ve "ağaç (tree)" kavramını ortaya koydu: çevrim içermeyen bağlı graflar. Kirchhoff'un gerilim ve akım yasaları, büyük ölçüde bu yapıların matematiksel özelliklerine dayanır. Bu, graf teorisinin fiziksel bir uygulamasının matematiksel teoriden önce geldiği nadir örneklerden biri.
İngiltere haritasını renklendirmeye çalışan Francis Guthrie, komşu bölgelerin farklı renkte olması koşuluyla 4 renkten fazla gerekmediğini fark etti ve bunu hocası De Morgan'a sordu. De Morgan diğer matematikçilere yaydı. Basit bir gözlem gibi görünen bu soru, 124 yıl boyunca çözülemedi.
Hamilton, bir dodekahedronun (12 yüzlü düzgün çokyüzlü) tüm köşelerini tam birer kez ziyaret eden kapalı bir yol bulmayı soran bir bulmaca oyunu icat etti (bir oyun şirketine 25 sterline sattı ama ticari başarı sağlamadı). Bu yapı, bugün Hamilton çevrimi olarak bilinir: her düğümü tam bir kez ziyaret eden kapalı yol. Euler ve Hamilton arasındaki fark kritik: Euler kenarları sayar, Hamilton düğümleri sayar.
Sylvester 1878'de "graph" (graf) kelimesini ilk kez matematiksel anlamda kullandı. Cayley, kimyasal bileşiklerin yapısını modellemek için grafları kullandı ve \(n\) etiketli düğüm üzerindeki ağaç sayısının \(n^{n-2}\) olduğunu keşfetti (Cayley formülü), bu bugün de öğretilen temel bir sonuç.
Kuratowski, bir grafın düzlemsel (planar) olması için gerekli ve yeterli koşulu verdi: grafın "K₅'i (5 düğümlü tam graf) veya K₃,₃'ü (3-3 tam iki parçalı grafı) minör olarak içermemesi." Bu, sonsuz sınıf grafı iki somut yasak alt yapıyla karakterize eden zarif bir sonuç.
Appel ve Haken, 4-renk teoremini kanıtladı, ama yöntem tartışmalı oldu: 1936 indirgenebilir konfigürasyon bilgisayarda tek tek kontrol edildi, toplam süre yüzlerce saat. Bu, "elle kontrol edilemeyen" ilk büyük matematiksel kanıtlardan biriydi ve "bilgisayar kanıtı matematiksel kanıt sayılır mı?" sorusunu gündeme taşıdı. 1997'de Robertson-Sanders- Seymour-Thomas 633 konfigürasyona düşürdü; 2005'te Gonthier bir teorem ispat yazılımıyla bağımsız doğruladı.
Graf teorisinin pratik dönüşümü: ağırlıklı bir grafta iki düğüm arasındaki en kısa yolu bulmak. Dijkstra algoritması bugün GPS navigasyonun, ağ yönlendirme protokollerinin (OSPF) ve sosyal ağ analizinin temelinde.
Hamilton çevriminin varlığını belirleme problemi, NP-tam olarak kanıtlandı: bilinen hiçbir verimli (polinom zamanlı) algoritması yok. Euler çevrimi ise doğrusal zamanda çözülüyor. Aynı "tüm ziyaret et" fikrinin iki varyantı, karmaşıklık teorisinde birbirinden köklü biçimde farklı sınıflarda. Bu, \(P \ne NP\) sorusunun en somut örneklerinden biri.
Araştırmacının Pusulası
Köprü probleminin yanı sıra, Euler bir poliedranın (çokyüzlünün) yüz, kenar ve köşe sayısı arasında evrensel bir bağıntı keşfetti:
\(V\) = köşe (vertex), \(E\) = kenar (edge), \(F\) = yüz (face) sayısı. Bu formül, tüm düzlemsel (planar) bağlı graflar için geçerli (Königsberg gibi çoklu kenarlara da uygulanabilir). Küp için: \(8-12+6=2\). Tetrahedron: \(4-6+4=2\). Oktahedron: \(6-12+8=2\).
Bağlı planar grafta \(V\geq3\) ise \(E\leq3V-6\). Bundan şunu çıkarabiliriz: K₅ (5 düğümlü tam graf, her çift bağlı) planar değildir, çünkü \(E=10>3\cdot5-6=9\). Aynı formül, 4-renk teoremini 5-renge "kolayca" indirir — ama 4'e inmek için Appel-Haken'in yüzlerce saatlik bilgisayar analizi gerekti.
Görünüşte benzer iki problem — biri kenarları ziyaret eder, diğeri düğümleri — matematiksel zorluğu açısından tamamen farklı.
| Özellik | Euler Yolu | Hamilton Çevrimi |
|---|---|---|
| Amaç | Her kenarı bir kez | Her düğümü bir kez |
| Koşul | Tam 0 veya 2 tek dereceli düğüm | Genel koşul yok (NP-tam) |
| Algoritma | O(E) — doğrusal (Hierholzer) | Bilinen en iyi: O(2ⁿ · n²) |
| Sınıf | P (polinom zamanda çözülür) | NP-tam |
Hamilton çevriminin ağırlıklı versiyonu: \(n\) şehri en kısa toplam mesafeyle ziyaret et. Lojistik, çip tasarımı, DNA dizilimi gibi onlarca alanda kritik. Tam çözüm için en iyi bilinen algoritma üstel zamanlı, ama %1'lik hataya sahip polinom-zamanlı yaklaşım algoritmaları var.
Düğüm ekleyin, kenar çizin, Euler koşulunu canlı görün.
Her düzlemsel (planar) grafın köşeleri, komşu köşelerin farklı renkte olması koşuluyla, en fazla 4 renkle renklenebilir.
3 rengin yetmediğini görmek için \(K_4\) (4 düğümlü tam graf) yeterli: her düğüm diğer üçüyle bağlı, 4 farklı renk gerekiyor. 4 rengin her planar graf için yeterli olduğu ise çok daha zor. Appel-Haken, herhangi bir karşı-örnek var olsaydı "minimum" boyutlu bir karşı örnek olacağını, bu minimum örneğin 1936 konfigürasyondan birini içermek zorunda olduğunu, ve bu konfigürasyonların hiçbirinin gerçekte karşı-örnek üretemeyeceğini gösterdi. Her konfigürasyonun kontrolü: bilgisayar.
Bir ağaç (tree), bağlı ve çevrimsiz bir graftır. \(n\) düğümlü her ağaçta tam olarak \(n-1\) kenar vardır. Cayley'nin zarif formülü: \(n\) etiketli düğüm üzerinde kaç farklı ağaç kurulabilir?
\(n=3\): \(3^1=3\). \(n=4\): \(4^2=16\). \(n=5\): \(5^3=125\). Bu formül, önce Sylvester, sonra Cayley tarafından bulundu ve Prüfer dizisi adlı zarif bir kodlama yöntemiyle kanıtlanabilir.
Bu Sayfada
Euler 1736'da yalnızca "Königsberg'de yürüyüş mümkün mü?" diye sormadı — ölçülemeyen, ama yine de kesin olan bir şeyi yakaladı: bağlantı yapısının kendisi. Bu soyutlama, elektrik devrelerini, DNA dizisini, internet protokollerini, sosyal ağları ve NP tamlık teorisini besleyen bir matematik dalı yarattı. Diğer sayfalardaki temalarla köprüler: Cayley formülü, Pisagor üçlülerindeki "sayma" geleneğiyle aynı ruhta; 4-renk teoreminin bilgisayar kanıtı, Kollatz'ın olasılıksal yaklaşımlarıyla aynı "kanıtın sınırları" sorusunu gündeme taşıyor.
Euler yolu teoremi (0 veya 2 tek derece). V−E+F=2 planar graflar için. Kuratowski (K₅ ve K₃,₃ yasağı). 4-renk teoremi (Appel-Haken 1976, bilgisayar destekli). Cayley formülü n^(n-2).
P ≠ NP (Hamilton çevriminin gerçekten zor olup olmadığı). Grafların tanımlanması (graph isomorphism) P'de mi? Büyük graflar için 4-renk teoreminin insan okunabilir kanıtı var mı?
Kaynakça
Çekirgeler Eğitim