ÇİZGE ve HARİTA BOYAMADA MATEMATİKSEL GÖRSELLİK

İbrahim Cahit Arkut-Yakın Doğu Üniversitesi [email protected]

F rancis Guthrie 1852 yılında Londra Üniversitesi’nde okuyan kardeşine hocalarına sorması için “verilen bir haritayı komşu ülkeler aynı renkle boyanmamak koşulu ile en fazla dört renkle boyayabiliyorum; acaba bu her harita için doğru mu?” sorusunu sorduğunda matematikçileri bir yüzyıldan fazla bir süre uğraştıracak bir problem yarattığının farkında değildi. Kardeşinin hocaları ve zamanın önde gelen matematikçileri De Morgan ve Hamilton soruyu cevaplayamadılar.

Soru kısa zamanda matematikçiler arasında meşhur oldu. Doğruluğuna inanılmasına ve ters örnek bulunamamasına karşın sorunun bir teorem ispatı neredeyse 150 yıl sürdü. İspat ancak bilgisayarla yapılabildi. Bu yüzden bu meşhur teoremin bilgisayar kullanamadan bir ispatının olmadığı sanılıyorlardı. Fakat ben spiral zincirler kullanarak bir haritadaki ülkelerin en fazla dört renkle boyanabildiğini bilgisayar kullanmadan kanıtladım. [9] Şekil 1 ve 2, benim yöntemimi kullanarak dört renge boyanmış iki haritayı gösteriyor.

Harita ve çizge boyama üzerine arXiv’da yayımlanan makalelerimin [4, 5, 6, 7] tanıtımını daha kolay yapma ve tartışma ortamı oluşturma gayesi ile İnternet ortamında bir sergi salonu açtım.[3] Son beş yılda 6 bin ayrı ziyaretçi sergime baktı ve yüzlerce yorum yapıldı.

Şekil 1. Grafikte spiral zincir boyama algoritması ile Türkiye, komşu ülkeler, Akdeniz ve göller de bölge kabul edilerek dört renkle boyamaya bir örnek verilmiştir.

Şekil 2. Yuvalanmış beşgenlerden oluşan haritanın spiral zincir yardımı ile boyanması.

elektrik mühendisliği, 440. sayı, kasım 2010 23

Dört Renk Teoreminin Tanımı ve Tarihçesi

Dört Renk Teoremi, “Her köşesinde yalnız üç sınır kesiştiği her sonlu düzlem harita komşu ülkeler aynı renk olmamak koşulu ile en fazla dört renkle boyanabilir” diye tanımlanır. Burada düzlem harita tüm düzlemi sonlu sayıda ülke ile doldurur ve küre üzerine yatırılabilir. Harita elemanları ülke (yüz), sınır (kenar) ve köşe(düğüm)lerden oluşur. Komşuluk tek noktada kabul edilmez ve her köşede yalnız üç sınır kesişir.

Bu teorem 1878 yılına kadar sadece ufak bir grup matematikçi tarafından bilindi. O yıl Kempe Cayley’in teşviki

ile teoreme bir çözüm bulduğunu zannederek bir bulmaca şeklinde matematikçilere AJM’de (American Journal Mathematics) sundu. Fakat bulmacaya Kempe tarafından verilen çözümün yanlış olduğu daha sonra ortaya çıktı. Yine aynı yıl P. Tait yanlışlığı sonradan ispatlanan başka bir kanıt sundu. A.B. Kempe dört renk probleminin ispatı için 1879 yılında iki renkli zincirler kullandı. Fakat 1890’da Heawood, Kempe’in kanıtının yanlış olduğunu gösteren bir ters örnek buldu ve beş rengin tüm haritalar için yeterli olduğunun kanıtladı. Kempe’in kanıtının yanlış olmasına karşın bu kanıtta kullanılan kaçınılmaz kümeler yöntemi teoremin sonunda kanıt-

Şekil 3. Kempe’in kanıtına verilen ters-örneklerin spiral kullanılarak dört renkle boyanması.

lanmasına yol açtı. Şimdi Kempe’in kanıtında önemli yer tutan kaçınılmaz kümeyi tanımlayalım.

Her haritada en az bir tanesi bulunan alt haritaların (konfigürasyon) oluşturduğu kümeye “kaçınılmaz küme” denir. F ile toplam yüzlerin (ülke), E ile toplam dallar (sınır) ve V ile toplam düğümler (köşe) gösterilsin. Fi ile i sınırlı (veya kenarlı) yüzlerin sayısı gösterilsin. Euler’in çok iyi bilinen polyhedral için formulü F+V=E+2 ve harita içindeki toplam parçalar için F = F2 + F3 + F4 + .. .+Fk, 2E = 2F2 + 3F3 + 4F4 +....+ kFk ve 3V = 2F2 + 3F3 + 4F4 +..+ kFk denklemlerini yazabiliriz. Bu denklemler kullanılarak,

4F2 + 3F3 + 2F4 + F5 = 12 + N ≥ 12, N ≥ 0 elde edilir. Yukarıdaki eşitsizlikten Kempe’in kanıtına ışık tutacak olan şu neticeler elde edilir:

1. {F2,F3,F4,F5} kümesi elemanlarının tümü sıfır olamaz. 2. Örneğin, eğer F2=F3=F4=0 ise F5 ≥12 olur. 3. Her düzlem harita U={iki-, üç, dört-,beş-kenarlı} temel kaçınılmaz kümeden en az bir ülke içerir. 4. Bir haritada tüm ülkelerin en az beş kenarı varsa, haritada en az 12 beş-kenarlı ülke bulunur. 5. Yalnız beş ve altı kenarlı ülkelerden oluşan haritalarda 12 beş kenarlı ülke bulunur.

Kempe’in kanıtı dört renk teoremine ters örnek verilemeyeceğine dayanır. Şöyle ki M haritası m ülkeli ve ancak beş renkle boyanan en küçük harita olsun. Yani m ülkeden daha az ülkesi bulunan tüm haritalar dört renkle boyanabilsin. M’in her zaman dört renkle boyanabildiğinin gösterilmesi kanıt için yeterlidir. Kempe temel kaçınılmaz kümenin elemanlarının teker teker her zaman m’nci ülke seçilerek dört renkle boyamanın tamamlanabildiğini gösterdi. Fakat 11 yıl sonra Heawood bir ters örnekle haritada bulunan beşgen ülkenin Kempe zincirlerinde renk takası yaparak dört renkle haritanın boyanamayacağını gösterdi.

24 elektrik mühendisliği, 440. sayı, kasım 2010

Eğer Heawood ters örneği ve diğerleri olmasaydı, Kempe kanıtı geçerli olacak ve dört renk teoremi günümüzde bu kadar popüler olmayacaktı. Fakat Birkhoff , Kempe’in temel indirgenebilir kümesi U’dan pentagonu atarak yerine sonradan adıyla anılacak olan dört beşgenden oluşan Birkhoff elmasının indirgenebilir olduğunu gösterdi. Burada pek sorun çıkmadı, çünkü elmasın etrafındaki altı bölgeli (ülkeli) halkanın 30 dört renk boyama tüm haritanın (halka içindeki dört beşgen) dört renkle boyanmasına engel teşkil etmiyordu. Başka indirgenebilir konfigürasyon olmasaydı, Birkhoff kanıtı doğru veren ilk matematikçi olacaktı. Fakat Franklin 1920’de sırayla üç beşgen, iki beşgen ve bir altıgen, bir beşgen ve iki altıgenden her birinden ikişer tane olmak üzere altı yeni konfigürasyonun indirgenebildiğini gösterdi. İşin kötüsü bu konfigürasyonların bulunması için onlarca kuralın uygulandığı “boşalma” (discharging) yöntemi gerekiyordu. Burada kısaca boşalmadan anlaşılan konfigürasyonun Euler formülünün geçerli olması için başlangıç yükünün bölgelere uygun şekilde dağıtılmasıdır. Sonuç olarak halka büyüklüğü konfigürasyonlar için 6’dan başlayıp 14’e kadar çıktı. Bunların yeterli ve

indirgenebilir olduklarını göstermek için bilgisayardan yardım almaktan başka çare yoktu.

1936 yılında Heesch çizge kuramını kullanarak “boşalma” metodu ile bilgisayarsız indirgenebilir konfigürasyonlar kataloğunu oluşturdu. 1948 yılında Heesch’in verdiği ve kaçınılmaz indirgenebilir konfigürasyonlar kümesi halka büyüklüğünün 18 olması gerektiğini öngören bir seminere katılan Haken problemle ilgilendi. 1965 yılında Haken, Heesch’i ABD’ye davet ederek, Illinois Üniversitesi ILLIAC-IV süper bilgisayarı ile Brookhaven Ulusal Lab’taki Shimamoto’nun izni ve Durre’nin FORTRAN programını Cary bilgisayarında kullandılar. 1967 yılında Heesch, Durre ve Haken kanıtta kullanılan yöntemi bilgisayarlaştırmaya başladılar, fakat çalışmalar yavaş gidiyordu.

Bu arada başka gruplar da bilgisayar kullanarak teoremi kanıtlamaya çalışıyorlardı. Mesela, Karl Durre yine 1965 yılında halka boyamaları kodlamak için matrix kullanarak Algol 60 programı ile indirgenebilirliği test etti. 1971 yılında Shimamoto “horse-shoe” (at nalı şeklinde 8-gen ve etrafına sıralanmış 5-gen ve 6-genler) konfigürasyonun

kanıtı sonlandırdığını düşündü fakat bilgisayar programındaki hata düzeltilince at-nalının indirgenemeyen konfigürasyon olduğu anlaşıldı. Benzer çalışmalar bir yarış ortamında Allaire (Kanada), Swart (G. Afrika), Stromquist ve Bernhart (ABD), Meyer (Fransa) paralel olarak yapılmaktadır.

1971 yılında önce Appel daha sonra da Koch, Haken’in ekibine katıldı. Ekibe katılanlarla moraller düzeldi. Boşalma yöntemleri ile üretilen kaçınılmaz kümelerin bazı konfigürasyonlarının son derece karmaşık şekilde indirgendiği gözlendi. Buna çare olarak Heesch’in herustic kuralı kullanıldı. Sonuçta eğer belli m değerleri için konfigürasyonun yüksek ihtimalle indirgenebilir olduğunu aksi durumlarda başka konfigürasyonlar aranması gerektiğini gösterdiler. Sonunda kaçınılmaz set 487 boşalma kuralı ile üretilir ve testler tamamlanır. Temmuz 1976’da Apel-Haken kanıtının bilgisayarsız ilk testini tamamladılar ve aynı yılın Aralık ayında Illinois Journal of Mathematics Dergisi’nde 1405 konfigürasyon ile birlikte ilk kanıt basılmış oldu. 1989 yılında hatalar ayıklanarak kanıt tekrar basıldı.[1] 1994 yılında Robertson, Sanders, Seymour ve Thomas tam zamanlı ve bir yıl süren çalışma sonucu 32 boşalma kuralı ve 633 konfigürasyonla teoremi tekrar kanıtlar. 2004 yılında Gonthier verilen kanıtın doğru ve hatasız olduğunu başka bir programla teyit eder. Dört renk probleminin daha detaylı tarihçesi ve bilgisayarlı kanıt için [1, 2] kitaplarına başvurulabilir.

Benim Çalışmalarım

Şekil 4. Tait’in üç renk dal boyanma sanısının spiral zincir yardımı ile uygulaması. Yönlenmiş dallar spiral zinciri, kesikli dallar geriye doğru Kempe renk takasını göstermektedir.

Ben dört renk problemle ilgilenmeye 1976 yılında Koch ile yazışmam ve onun doktora tezinin bir kısmını okumam sonucu başladım. 1980 yılında Swart ile Waterloo Üniversitesi’nde bir yıl boyunca dört renk teoreminin kompleksliği konusunda tartıştık. 1995 yılında dört renk kuramı üzerinde çalışanlardan çizge kuramcı Daniel Sanders bazı açık çizge problemleri üzerine sürekli fikir alışverişinde bulunelektrik mühendisliği, 440. sayı, kasım 2010 25

dum. 1998 yılında teoremi bilgisayarsız kanıtlamak için yeni bir yol keşfettim. Maximal düzlem çizgelerde tüm yüzler (face) üçgendir. Bu özellikten yararlanarak çizgenin düğümleri {1, 2, 3, 4} kümesindeki sayılarla numaralandığında bir üçgene karşı düşen üçgen ağırlığı f(∆) düğüm numaralarının toplamı olarak tanımlanabilir. Boyamanın olurlu olması için çizgede düğüm komşu düğümlerin numaraları birbirinden farklı olması gerektiğini gösterdim ve bu özelliği kullanarak maximal çizgede üçgen ağırlıklarının dört renkli boyamaya karşı düşmesi için üçgen dizilerin nasıl ağırlıklandırılması gerektiğini irdeledim.[7] Yine aynı makalede spiral zincirler kullanılarak dört renk problemine kanıt verilebilineceğine değindim.

2005 yılında Tait’in kubik düzlem çizgelerin dallarını üç renkle boyama sanısını dört renk kullanılmadan yine spiral zincir üç renk boyama algoritması ile kanıtladım.[4,10] 2006 yılında Madrid Dünya Matematikçiler Kongresi’nde (ICM2006) sunduğum bildiride spiral zincirler kullanılarak her maximal düzlem çizgenin düğümlerinin her zaman en fazla dört renkle boyandığının kanıtını algoritmik olarak gösterdim.[3] Rogers Cambridge Üniversitesi tarafından basılmakta olan Nrich Dergisi’nde çıkan dört renk teoreminin tarihçesi ile ilgili makalesinde benim çalışmalarıma yer verdi ve çalışmalarım bilgisayarlı kanıta alternatif çalışma olarak sınıflandırıldı.[8] Son olarak çizge kuramı kavramları kullanmadan haritaların

Şekil 5. Dikdörtgensel bölgelerden oluşan soyut bir haritanın dört renk kullanılarak boyanması. Bir halı desenine benzeyen grafikte dış bölgenin de hesaba katıldığına ve dört rengi sağlayan mavi ile boyandığına dikkat edin. Bu koşul problemin genel çözümünde gerekli olduğu için dış bölgeye komşu bölgeler yalnız üç renkle boyanmıştır.

maximal mono-kromatik ve maximal iki-kromatik boyanarak, geriye kalan boyanmamış bölgelerin her zaman ya çevrimsiz (acyclic) ya da çift uzunluklu halkalar haline getirilebilineceğini gösterdim. Bu ise dört renk probleminin ortaya çıktığı Viktorya döneminin matematiksel mantığına uygun ve doğal olarak bilgisayardan yardım beklemeyen bir kanıt olmaktadır.[9]

Kaynakça

[1] Appel, K., and Haken,W. “Every Planar Map is Four-Colorable”, Providence, RI: Amer. Math. Soc., 1989.

[2] Wilson, R., Four Colors Suffice : How the Map Problem Was Solved, Princeton, NJ: Princeton University Press, 2004.

[3] http://www.flickr.com/photos/ 49058045@N00/

[4] http://arxiv.org/abs/math/0408247

[5] http://arxiv.org/abs/math/0507127

[6] http://arxiv.org/abs/0710.2066

[7] http://arxiv.org/abs/0903.4108

[8] Leo Rogers, The Four Colour Theorem, http://nrich.maths.org/6291

[9] I. Cahit, “The Face Labeling of Maximal Planar Graphs”, AMEN, (basımda), 2010 http://www.math.nthu.edu.tw/ _amen/

[10] E. Anshelevich, A. Karagiozova, “Terminal backup, 3D matching, and covering cubic graphs”, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, http://doi.acm.org/10.1145/

1250790.1250849 <

İbrahim Cahit Arkut Kimdir?

İbrahim Cahit Arkut, 1948 yılında Lefkoşa’da dünyaya geldi. Lise tahsilini İstanbul Kabataş Erkek Lisesi’nde tamamladı ve İTÜ Elektrik Fakültesi’nden 1971 yılında mezun oldu. 1994 yılında Doğu Akdeniz Üniversitesi’nde doktorasını tamamladı. Eindhoven, Hollanda (1973-74), Waterloo, Kanada (1980) ve McMaster, Kanada (1986) üniversitelerinde matematik ve bilgisayar biliminde araştırmalarda bulundu. 1975-1998 yıllarında Kıbrıs Telekom Dairesi’nde mühendis olarak çalıştı. 1981’den günümüze kadar Kıbrıs’taki üniversitelerde yarı ve tam zamanlı mühendislik ve matematik bölümlerinde öğretim üyeliği yaptı.

26 elektrik mühendisliği, 440. sayı, kasım 2010