Dört Renk Teoremi’ne Nadir Görülen Yeni Bir Kanıt Bulundu.

1970’lerde bilgisayarların yardımıyla tartışmalı bir şekilde çözülmüş olan bu ünlü problemi yeniden ele alan matematikçiler, grafiklerin doğası hakkında önemli yeni içgörüler elde ettiler.


Dört renk teoremi şu şekilde basitçe ifade edilebilir: Birbiri ile bitişik bölgelerden oluşan bir harita verildiğinde, komşu bölgelerin hiçbirinin aynı rengi paylaşmaması koşuluyla, her bölgeyi dört renkten biriyle boyamak mümkün müdür?

Bazı matematik problemleri, çözüldükten çok sonra bile araştırmacıların kafasını kurcalamaya devam eder. Bir ispat ortaya çıkar, hatta kutlanır; ancak yine de bir tatminsizlik hissi devam eder. Belki de argüman fazla karmaşıktır — o ulaşılması zor tek sayfalık makale arayışı sürer — ya da belki de bir şeyin neden doğru olduğuna dair daha derin bir teorik kavrayış sunmamaktadır. Sebep ne olursa olsun, matematikçiler, başka türlü kapanmış sayılan bir konuya defalarca geri dönerler.

Bu tür vakaların en ünlülerinden biri, matematikçilerin kendi alanlarına bakış açısını kökten değiştiren bir problem olan dört renk teoremidir.

Soruyu ifade etmek basit, anlamak ise daha da basit: Birbirine bitişik bir harita verildiğinde, komşu bölgelerin hiçbirinin aynı rengi paylaşmaması koşuluyla her bölgeyi dört renkten biriyle renklendirmek mümkün müdür? 19. yüzyılın ortalarında bu soru, elinde dörtten çok daha fazla renk bulunan ve renk paletini kısıtlamak için özel bir neden görmeyen haritacılar için önemsiz bir konuydu. Ancak hem amatör hem de profesyonel matematikçiler için bu zeka oyunu kısa sürede bir takıntıya dönüştü.

1879’da duyurulan ilk iddia edilen kanıt (yeni bir sekmede açılır), yanlış olduğu kanıtlanana kadar 11 yıl boyunca geçerli kaldı. Ardından avukatlardan, doktorlardan ve ünlü grafik teorisyenlerinden de daha fazla yanlış cevap geldi. Danimarka Teknik Üniversitesi’nden grafik teorisyenlerinden Carsten Thomassen (yeni bir sekmede açılır), “Burada, bir çocuğun bile anlayabileceği bir problem var,” dedi. “Bence bu sorunun bu kadar büyük bir zorluk olmasının nedeni budur.”

Teorem, yaklaşık bir asır sonra nihayet kanıtlandı (yeni bir sekme açar) — ancak o dönemde skandal olarak görülen bilgisayar yöntemleriyle; bu da matematikçilerin, başlangıçta neyi kanıt olarak kabul ettiklerini sorgulamasına neden oldu. Sorunun durumu, bilgisayar kullanımının yaygınlaştığı ve daha basit bir bilgisayar destekli kanıtın (yeni bir sekme açar) bulunduğu 1997 yılına kadar tartışma konusu olmaya devam etti.

Yine de bugün bile, Kopenhag Üniversitesi’nden bilgisayar bilimcisi Mikkel Thorup’un (yeni bir sekme açar) ifadesiyle “dört renk hastalığı” hâlâ dolaşmaya devam ediyor. Thorup ve Thomassen kendilerini bu sorundan muzdarip olanlar arasında sayıyor. Böylesine basit bir ifade için, bunun doğru olmasının daha basit bir nedeni olmalı. Ya da en azından bunu kanıtlamanın daha verimli bir yolu.

Neredeyse on yıllık bir çalışmanın ardından Thorup, Thomassen ve Danimarka, Kanada ve Japonya’daki dört meslektaşları, teorem için bir başka bilgisayar kanıtı daha ortaya koydu.


Görsel: Soldan sağa: Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup ve Bojan Mohar, kısa süre önce dört renk teoremini yeniden kanıtlayan ve bu süreçte haritaları ve grafikleri renklendirmenin daha verimli bir yolunu ortaya çıkaran ekibin üyeleridir.


2026 yılının Mart ayında çevrimiçi olarak yayınlanan (yeni bir sekmede açılır) ve Kasım ayında her yıl düzenlenen Foundations of Computer Science konferansında sunulacak olan bu ispat, bazı açılardan öncekilerden bile daha karmaşıktır. Paris’teki Inria’da bilgisayar bilimcisi olan Georges Gonthier, “Görünüşe göre ispatlarını gerçekleştirirken elektrikten bolca yararlanmışlar,” dedi. Ancak araştırmacılar, argümanlarını oluşturma sürecinde haritaları renklendirmek için çok daha verimli bir yol ortaya koydular. Bunu yaparken, düzlemsel grafikler olarak adlandırılan önemli matematiksel nesnelerin yapısal özelliklerine dair yeni içgörüler elde ettiler ve bu da grafik teorisindeki diğer birçok çözülmesi zor problemde ilerleme kaydedilme potansiyelini ortaya çıkardı.

Gonthier, bu sorunun yanlış başlangıçlar ve boşa çıkan umutlarla dolu geçmişini göz önünde bulundurarak, “bir kez olsun gerçek bir sonuç görmek gerçekten harika” dedi.



Bilgisayarla İlgili Tartışmalar

1852 yılında, matematikçi Francis Guthrie, İngiltere’deki ilçelerin yer aldığı bir haritayı renklendirirken, bunun için sadece dört renge ihtiyaç duyduğunu fark etti. “Acaba bu her zaman geçerli mi?” diye merak etti. Aynı zamanda matematikçi olan kardeşi Frederick’e danıştı; Frederick’in danışmanı Augustus De Morgan bu soruya ilgi duydu ve konuyu daha geniş bir kitleye duyurmaya karar verdi. 1879 yılında, Alfred Bray Kempe adlı bir matematikçi bir çözüm bulduğunu iddia edince, Nature dergisinde yayınlanan bir basın bülteniyle bu başarı duyuruldu.

Görsel: Francis Guthrie

Kempe, kanıtlamak istediği şeyin tam tersini varsaymakla işe başladı: yani, sadece dört renkle boyanamayacak bir harita olduğu varsayımı. Ardından, bu varsayımın nihayetinde bir çelişkiye yol açacağını — yani böyle bir haritanın var olamayacağını — göstermeye çalıştı. Bu durumda, tüm haritaların dört renkle boyanabilir olması gerekirdi.

Öncelikle, dedi, varsayımınızdaki dört renkle boyanamaz haritanın olabildiğince “minimal” olduğunu hayal edin: Eğer haritadan herhangi bir ülkeyi çıkarırsanız, geriye kalan harita dört renkle boyanabilir olur. Ardından, haritanızı düzlemsel grafik olarak yeniden çizerek coğrafyayı ve diğer gereksiz ayrıntıları ortadan kaldırın. Her ülkeyi bir nokta (veya köşe) olarak temsil edin ve bu ülkeler birbiriyle sınır paylaşıyorsa iki nokta arasına bir çizgi (veya kenar) çizin. Harita renklendirme probleminiz artık bir grafik renklendirme problemi haline geldi ve bu da onu grafik teorisinin araçlarına açıyor.


Görsel: Mark Belan / Quanta Magazine


Özellikle 18. yüzyılda, İsviçreli matematikçi Leonhard Euler, düzlemsel grafiklerin birçok yararlı özelliğe sahip olduğunu keşfetti — bunların arasında, bu tür herhangi bir grafiğin en az bir adet, beş veya daha az komşusu olan köşe içereceğinin garantisi de vardı. Bu, grafiğinizin bu altı konfigürasyondan en az birine sahip olması gerektiği anlamına gelir; Kempe buna “kaçınılmaz küme” adını vermişti:


Ve grafiğiniz minimal olduğu için, bu konfigürasyonlardan herhangi birini grafikten çıkarırsanız, geriye dört renkle yeniden renklendirilebilen bir grafik kalır. Kempe’nin dahice hamlesi, bu konfigürasyonlardan hangisini çıkarırsanız çıkarın, grafiğin renklerini her zaman öyle bir şekilde değiştirmenin bir yolunu bulabileceğinizi göstermekti; böylece eksik köşeyi geri eklediğinizde, beşinci bir renge ihtiyaç duymadan tüm köşeleri renklendirmek mümkün olur.


Görsel: Leonhard Euler


Görsel: Mark Belan / Quanta Magazine

Her kaçınılmaz konfigürasyonun bu şekilde “indirgenebilir” olduğunu göstererek, minimal grafiğinizin sonuçta dört renkle boyanabilir olduğunu kanıtlamış oldunuz — ilk varsayımınız yanlıştı. Dört renk teoremi doğru olmalıdır.

Ne yazık ki, Kempe’nin kanıtını açıklamasından 11 yıl sonra, matematikçi Percy John Heawood, onun renk değiştirme prosedüründe ince bir kusur keşfetti: Çıkardığınız köşenin beş komşusu olduğu durumda, Kempe’nin yöntemi aynı renklerin birbirinin yanına gelmesine yol açabilirdi. Heawood, kısmen Kempe’nin yaklaşımının çok zarif olması nedeniyle, başlangıçta bu hatayı bildirmekte tereddüt etti. Ve gerçekten de, Kempe’nin hatasına rağmen, bugün “Kempe zinciri” olarak bilinen renk değiştirme prosedürü, bu soruna yönelik gelecekteki çözümlerin temelini oluşturmaya devam etti. Thomassen, “O kadar ilginç bir hata yapıp, bu hatanın adınızın anısına isimlendirilmesi ilginç değil mi?” dedi.

Sonuçta, Kempe’nin kaçınılmaz kümesindeki son konfigürasyonun indirgenebilir olduğunu kimse kanıtlayamadı. Doğru bir ispatın, bunun yerine 8.900 konfigürasyondan oluşan çok daha büyük ve karmaşık bir kümeyi belirlemeyi — ve bunların hepsinin indirgenebilir olduğunu göstermeyi gerektirdiği ortaya çıktı. Bu görevi elle halletmek imkânsızdı. Bilgisayarlar gerekiyordu.

1976 yılında, matematikçiler Kenneth Appel ve Wolfgang Haken, olasılık sayısını önce 1.936 konfigürasyona, ardından da 1.482’ye indirmek için akıllıca bir yol buldular. Ardından, Illinois Üniversitesi’ndeki süper bilgisayarları kullanarak her birini düzgün bir şekilde indirgediler. Sonunda, dört renk teoreminin çözüldüğünü söylediler.
https://math.illinois.edu/sites/defa...en%20001_0.jpg
Görsel: Kenneth Appel ve Wolfgang Haken

İngiliz matematikçi Augustus De Morgan, dört renk problemine daha geniş bir ilgi uyandırmaya çalıştı. “Bugün bir öğrencim, benim bir gerçek olduğunu bilmediğim — ve hâlâ da bilmediğim — bir olgunun nedenini açıklamamı istedi,” diye yazmıştı 1852 yılında, üretken matematikçi ve fizikçi William Hamilton’a gönderdiği bir mektupta.

Görsel: Augustus De Morgan'ın mektubu


Şüpheci bir dinleyici kitlesiyle karşılaştılar. O dönemde bilgisayarlar korkutucuydu ve teknik açıdan anlaşılmazdı. Appel ve Haken, bilgileri tel ağa elle dokunmuş manyetik malzeme üzerine depolayan çekirdek bellek kullanıyorlardı. Denver’daki Colorado Üniversitesi’nden matematikçi Ellen Gethner (yeni sekmede açılır), “Bu ispatın nasıl güvenilir olabileceğine dair her türlü tartışma vardı,” dedi. “Bir elektrik dalgalanması olursa ve kanıtı geçersiz kılacak o tek konfigürasyonu gözden kaçırırsanız ne olur?”

Yine de çoğu insan, Illinois Üniversitesi’nin daha sonra posta pullarında duyurduğu gibi, “dört renk yeterlidir” fikrini zamanla kabul etmeye başladı. Ve 1997’de bir matematikçiler ekibi, Appel ve Haken’in yaklaşımını basitleştirerek, bir bilgisayar yardımıyla sadece 633 konfigürasyonu belirleyip kontrol ederek bu konuyu kesin olarak çözdü. Bu sefer matematik camiası sonucu hemen kabul etti.

Ancak hikâye henüz bitmemişti.



“Hiçkimsenin Toprakları”nı Arayış

Bu serüvenin son bölümü, 2015 yılında bir Danimarka sahilinde başladı.

Japonya Ulusal Bilişim Enstitüsü’nde grafik teorisyeni olarak görev yapan Ken-ichi Kawarabayashi (yeni sekmede açılır), uzun süredir birlikte çalıştığı Thorup ile bir konferansa katılmıştı. İkili, kısa süre önce birlikte önemli bir makale yayınlamıştı (bu makale, daha sonra onlara prestijli Fulkerson Ödülü’nü kazandıracaktı; bu ödül, on yıllar önce Appel ve Haken’e dört renk teoremi çalışmaları nedeniyle de verilmişti). Şimdi Nyborg’un beyaz kumları üzerinde durmuş, bundan sonra ne yapacaklarını düşünüyorlardı. Kawarabayashi, “Küçük bir proje üzerinde çalışamayız” diye düşündüğünü hatırladı.

Dört renk teoremi, kariyerleri boyunca üzerlerinde büyük bir etki bırakmıştı. Aslında, grafik teorisyenleri olmalarına da kısmen bu teorem ilham vermişti. Yine de 1997’deki sonucun bir yönünden memnun değillerdi: Bu sonuç, matematikçilere herhangi bir grafiği dört renkle boyamak için bir yöntem sunmuştu, ancak bu yöntem verimsizdi. n köşeli bir grafik için boyama işlemi n² adım gerektiriyordu.

Sorun şuydu: Elinize büyük bir grafik verilse ve onu renklendirmek isteseniz, grafiği tarayarak bir konfigürasyon bulmanız, onu kaldırmanız, sonra başka bir konfigürasyon aramanız, onu da kaldırmanız ve böyle devam etmeniz gerekirdi — ta ki grafiği açıkça dört renkle renklendirilebilir bir hale getirene kadar.

Kawarabayashi ve Thorup, kısa süre sonra Simon Fraser Üniversitesi’nden Thomassen ve Bojan Mohar’ın (yeni bir sekmede açılır) da katılımıyla, tek tek değil, paralel olarak indirgenebilecek kaçınılmaz bir konfigürasyon kümesini belirlemek istediler. Bunu başarmak için, aynı anda indirgenmekte olan diğer konfigürasyonların renklendirmelerine müdahale etmeden her bir konfigürasyonu indirgeyebileceklerini garanti etmeleri gerekiyordu. Bu, onlara bir grafiği sadece dört renkle yeniden renklendirmek için çok daha hızlı bir yol sağlayacaktı.

Bu birbirini etkilemeyen konfigürasyonlar nasıl bulunur? Kapsamlı bir arama yaparak.

1976 ve 1997 yıllarında dört renk teoreminin ispatlarında matematikçiler, yalnızca az sayıda bağlantıya sahip köşe kümelerinin bulunduğu bölgelere odaklanmıştı. Kawarabayashi, Mohar, Thomassen ve Thorup ise dikkatlerini, grafiğin her köşesinin diğer altı köşeye bağlı olduğu ve kenarların üçgen bir düzen oluşturduğu, sözde düz alanlara yöneltti. Bu alanlar bir nevi grafiksel “tarafsız bölge” oluşturur: Düz bölgeler, bir konfigürasyonun indirgenebilirliğini kanıtlamak için genellikle kullanılan yapıya sahip olmadığından, bu bölgelerde iyi konfigürasyonları belirlemek daha zordur. Ancak araştırmacılar, düz alanların çok daha yaygın olduğunu fark ettiler. Ve birçok konfigürasyonu birbirleriyle etkileşime girmeden aynı anda indirgeyip yeniden renklendirmek için, aralarından seçim yapabilecekleri çok sayıda seçeneğe ihtiyaçları vardı.

Görsel: Atsuyuki Miyashita (solda) ve Yuta Inoue, grafiklerin genellikle göz ardı edilen bölgelerinde önemli yapıların aranmasına katkıda bulundular.


Bu bölgelerdeki konfigürasyonların araştırılması için iki kişi daha — Kawarabayashi’nin yüksek lisans öğrencileri Yuta Inoue ve Atsuyuki Miyashita — ve aylarca süren hesaplama süresi gerekecekti. “Oldukça naiftik,” dedi Thorup. “Bu kadar uzun süreceğini hiç tahmin etmemiştik.” Ancak sonunda kaçınılmaz olan yeni bir kümeye ulaştılar. Bu küme devasa boyuttaydı ve 8.202 konfigürasyondan oluşuyordu. Ancak umdukları gibi, belirli bir grafikte bu konfigürasyonların çoğunu aynı anda azaltmak mümkün oldu; böylece eskiden birçok adımdan oluşan işlem, sadece birkaç adıma indirgenebildi.

Dört renk teoremi bir kez daha kanıtlanmış oldu. Ve yeni kanıt, çok daha verimli bir renklendirme algoritması sağladı: n köşeli bir grafik için n(log n) adım gerektiriyordu; bu, n²’ye kıyasla önemli bir gelişmeydi.



Yeni Ufuklar

Bir asırdan fazla bir süre önce Kempe’nin başarısız denemesinde olduğu gibi, bu yeni ispatın en büyük değeri, manşetlere taşınan sonucundan ziyade, grafiklerin doğası hakkında sağladığı yeni içgörülerde yatmaktadır. Çalışma, indirgenebilirlik kavramına farklı bir yaklaşım getirerek ve grafiğin gözden kaçan kısımlarını kullanarak, bu önemli matematiksel nesnelerde daha önce bilinmeyen bir yapıyı ortaya çıkarmış ve matematikçilere bunları anlamak için yeni araçlar sunmuştur. Gethner, “Bir mekanizma kurduğunuzda, ne tür problemleri çözebileceğinizi anlarsınız,” dedi.

Örneğin, grafik teorisyenleri sadece düzlemsel grafiklerle değil, halka şeklindeki torus gibi her türlü yüzey üzerinde yer alan grafiklerle de ilgilenmektedir. Bu grafikler, yeni çalışmanın düzlemsel grafiklerde ortaya çıkardığı bazı özellikleri paylaşmaktadır — bu da bu grafikler hakkında da renklendirme teoremlerini kanıtlamayı mümkün kılmaktadır. En son dört renk sonucunun arkasındaki araştırmacılar, şu anda bu soruları ele almak için kendi tekniklerini kullanmaktadır. Thomassen, engellerin devam etmesine rağmen, “Bence doğru yoldayız” dedi.

Bu arada, dört renk problemi hâlâ devam ediyor. Thomassen son sonucundan memnun olsa da, 150 yıldır hem amatörleri hem de profesyonelleri meşgul eden aynı soruyu hâlâ soruyor: Herhangi bir düzlemsel grafik için dört rengin yeterli olmasının daha basit bir açıklaması var mı? Herkesi “aha” dedirtecek efsanevi tek sayfalık kanıt, o teorik zekâ gösterisi?

“Benim istediğim, bilgisayar kullanmadan yapılan bir ispat,” dedi Thomassen. “Ve bu konuyu düşünmekten asla vazgeçmeyeceğim.”


Kaynak: The Four-Color Theorem Gets a Rare New Proof - Gregory Barber / Quanta Magazine



.