Tuvalet Kağıdı ve 4 Renkle Harita Boyama

ÇizgelerGenelMatematiğin UygulamalarıTuvalet Kağıdı

Sizi bilmem ama ben ‘‘Tuvalet kağıdı ve matematik’’ kavramını duyar duymaz, aklıma tuvalette çözülen matematiksel oyunlar geldi. Örneğin, sudoku ilk moda olduğunda, tuvalette kelime bulmacası çözmeyi seven insanlar alışkanlıklarını sudoku çözmekle değiştirmişlerdi. O kadar ki, sırf tuvalette sudoku çözerek bu işi bir hayli ilerletmiş kişiler tanıdım. Tabi ki herkesin tuvalette geçirdiği süre farklı olabilir, ancak öyle anlıyorum ki tuvalette kendine hobi arayan insanların sayısı hiç de azımsanmayacak kadar çok. Eğer siz de bunlardan biriyseniz size güzel bir soru önerebilirim. Eğer değilseniz, tuvalet dışında da çözmeye çalışmakta özgürsünüz. 

Sorum belli bir çizgenin (ağın) çizimiyle ilgili olacak. Aslında, hemen aşağıdaki Soru 1, 2 ve 3’e bakıp çözmeye koyulmanız için bir engel yok. Ancak, bu soruların çizge kuramının en eski problemlerinden dört renkle harita boyama problemiyle ve elektronik devrelerin tasarımı gibi başka güncel konularla olan bağlantısını anlamak isterseniz, tüm yazıyı okumanızda fayda var. 

Harita boyama problemi, bir yandan bir çocuğa anlatılabilecek kadar basit olup bir yandan da birçok ünlü matematikçiyi 150 yıl uğraştıracak kadar derin bir konu. Bu özelliğiyle, matematik problemleri arasında son derece ayrı bir yere sahip. Harita boyama problemi, ilk defa 1852 yılında bir doktora öğrencisi olan Guthrie tarafından sanıt olarak ortaya atılıyor: bir coğrafi haritada, birbirine komşu olan ülkeleri farklı renklerle boyamak şartıyla, tüm ülkeleri boyamak için her zaman 4 renk yeterli midir?  1879 yılında Kempe bir ispat sunuyor, ancak 1890 yılında Heawood bu ispatta bir hata buluyor. Birçok matematikçinin yoğun çalışmalarına rağmen, yeni bir ispat ancak 1976 yılında Appel ve Haken tarafından geliyor. Bu ispat, belli bir noktada bilgisayar tarafından kontrol edilen 1500 kadar konfigürasyona dayanıyor. Bilgisayar yardımıyla ulaşılan bu buluş, BBC kanalında belgesel haline gelecek kadar yankı uyandırıyor. Bir sonraki, daha kısa ispat ise 1996 yılında Robertson, Sanders, Seymour ve Thomas tarafından, yine bilgisayar destekli bir yaklaşımla geliyor.  Bu ispatların bilgisayara dayanması nedeniyle gerçek birer ispat sayılıp sayılmaması hala tartışmalı olmakla birlikte, artık 4 renk teoremi diye anılan bu sonuca göre her haritanın en fazla 4 renkle boyanabildiğini biliyoruz (örnekler için bakınız Şekil 1). 

Şekil 1

Şekil 1: Çeşitli haritaların dört renkle boyanması.

Ne o? Yoksa size çok inandırıcı gelmedi ve kağıt kalemi alıp 4 renkle boyanamayan bir harita çizmeye mi koyuldunuz? Eğer öyleyse sizi tebrik ediyorum çünkü bu son derece sağlıklı bir yaklaşım. İkna olmanın yolu kesinlikle en başta inanmaktan ve hissetmekten geçiyor. Deneme yaparken şunu gözden kaçırmayın: sadece bir noktada ortak sınırları olan ülkeler komşu sayılmıyor ve farklı  renkle boyanmaları gerekmiyor. Bir diğer husus da, aynı ülkenin birbirinden kopuk kara parçaları mevcut ise, bunları aynı renge boyama gerekliliği yok. Eğer 4 renk teoremini yanlışlayan bir örnek bulamadıysanız, anlatmaya devam edeyim. 

4 renk teoremi çizgelerle çok yakından ilintili. Eğer her ülkeyi/bölgeyi bir düğümle gösterir, birbirine komşu olan iki ülkeyi gösteren düğümler arasına da bir ayrıt (çizgi) koyarsak, bir adet çizge (ağ) elde ederiz. Bu şekilde elde edilen bir çizgede, birbirine ayrıt ile bağlı olan düğümler farklı renkler alacak şekilde tüm düğümleri boyamak, çizgenin elde edildiği haritada ülkelerin boyanması ile birebir aynı problemdir (bakınız Şekil 2). Diğer bir deyişle, harita boyama problemi ile, yukarıda tarif ettiğimiz şekilde elde edilen harita çizgesinin düğümlerinin boyanması problemi birbirine denktir. 

Şekil 2

Şekil 2: Harita boyama probleminin, çizge boyama problemi olarak modellenmesi.

Çizge boyama problemi, sayısız pratik uygulamalarına ek olarak teorik zenginliği nedeniyle de çizge kuramının en çok çalışılan problemlerinden birisidir. Genel olarak, bir çizgenin düğümlerini boyamak için gereken en az renk sayısı, o çizgenin düğüm sayısı mertebesinde olabilir. Bunun en basit örneği, n düğümlü ve her bir düğümü bir diğerine bir ayrıtla bağlı olan (tam) bir çizgedir. Bu çizgenin düğümlerini boyamak için tam olarak n renk gerekmektedir ve n değeri istediğiniz kadar yüksek alınabilir. Bu açıdan bakıldığında, nasıl oluyor da herhangi bir harita çizgesini her zaman en fazla 4 renkle boyamak mümkün oluyor? Demek ki haritalardan elde edilen çizgeler, alelade çizgeler değil. Peki o zaman, harita çizgelerinin en fazla 4 renkle boyanabilmesini sağlayan belirleyici/tanımlayıcı özelliği nedir? Bunu keşfetmek için, tuvalet bilmecelerimizi sormanın yeri geldi. İlki, aslında çok bilinen bir soru: 

Soru 1: Şekildeki her bir ev, karşılarındaki üç kuyunun her birinden su almak istiyor. Ancak bu üç evdeki kişiler birbirleriyle anlaşamadıkları için, yolda karşılaşma ihtimalleri olmasın istiyorlar. Kimsenin kimseyle karşılaşma ihtimali olmadan herkesin tüm kuyulardan su çekmesinin bir yolu var mıdır?

Şekil 3

Şekil 3: Üç ev üç kuyu problemi.

İkinci sorumuzu ise 1840 yıllarında Möbius dersinde sormuş:

Soru 2: Beş oğlu olan bir kral varmış. Ölümünden sonra, topraklarının beş oğlu arasında öyle bir bölünmesini vasiyet etmiş ki, herbir oğlunun toprağı ile diğerlerinin toprakları arasında bir sınır çizgisi olsun. Bu vasiyeti gerçekleştirebilir misiniz?

Dikkat ederseniz, Soru 1, Şekil 4’deki K3,3 çizgesini bir kağıda ayrıtları kesişmeyecek şekilde çizebilir miyiz diye soruyor. Soru 2’nin çizgelerle bağlantısını kurmak için, parçalara ayrılan toprağı Şekil 2’de gösterdiğimiz yolla harita çizgesine çevirmemiz gerekiyor. Bu değişimi yapınca, Soru 2, Şekil 4’deki K5 çizgesi ayrıtları kesişmeyecek şekilde çizilebilir mi sorusuna denk oluyor. Bir çizgeyi belli bir yüzeye ayrıtları kesişmeden çizmeye, o çizgeyi yüzeye gömmek diyoruz. Diğer bir deyişle, gömmek kelimesini ayrıtları kesişmeden çizmek anlamında kullanıyoruz. Düzleme gömülebilen çizgelere de düzlemsel çizgeler diyoruz. Demek ki, Soru 1 ve Soru 2, sırasıyla K3,3 ve K5 çizgelerinin düzlemsel olup olmadığını sormaktadır. 

Şekil 4

Şekil 4: $K_5$ ve $K_{3,3}$ çizgeleri.

Bu noktada kafanızı karıştırma ihtimali olan bir konuya da açıklık getirip öyle ilerleyelim. Diyebilirsiniz ki, dünyamız yuvarlak olduğuna göre gerçek haritalar bir küre üzerine çiziliyor, oysa yukarıdaki anlatımda harita çizgelerini bir kağıt, yani bir düzlem üzerine çiziyoruz. Stereografik izdüşüm denen bir yöntemle kolaylıkla gösterebiliriz ki bir çizgenin küre üzerine gömülmesi ile düzlem üzerine gömülmesi birbirine denktir. 

Şekil 5

Şekil 5: Küre üzerine gömülmüş bir çizgenin stereografik izdüşümü yöntemiyle düzleme gömülmesi. Bu transformasyon terse çevrilebilir olup, düzleme gömülen bir çizgeyi küre üzerine gömmek için de kullanılabilir. Gerekirse çakışmaları önlemek için ışık kaynağını yüzlerden birinin ortasına doğru yaklaştırabiliriz.

Biraz denerseniz göreceksiniz ki, K5 ve K3,3 çizgelerini ayrıtları kesişmeyecek şekilde çizmeyi başaramayacaksınız. Biraz daha uğraşırsanız, bunun mümkün olmadığına dair inancınız iyice pekişecek. Eğer bu inancınızı ispata çevirmek isterseniz birkaç bilgiye daha ihtiyacınız olacak.  Bir çizgenin düzlemsel çiziminde, kapalı bir daire ile tanımlanan her bölgeye yüz adı verilir. Kapalı yüzlere ilaveten, çizgenin en dış bölgesi de dış yüz olarak adlandırılır.

Euler formülü: n düğümlü ve m ayrıtlı bir çizgenin düzlemsel bir çizimindeki yüz sayısı f = m – n + 2’dir.  

Örnek olarak, Şekil 6’daki çizgede n=9 düğüm, m=15 ayrıt ve de f4 dış yüz olmak üzere f = 15 – 9 + 2 = 8 yüz mevcuttur.

Şekil 6

Şekil 6: Bir çizgenin düzleme gömülmesi ve yüzlerinin gösterimi.

Euler formülüne ek olarak bazı gözlemler yaparak şunu da gösterebiliriz: n düğümlü düzlemsel bir çizgede en fazla 3n-6 tane ayrıt olabilir. Tabi bu sonuç sadece basit çizgeler, yani iki düğüm arasında birden fazla ayrıtı olmayan çizgeler için geçerli. Şimdi, Euler formülü, düzlemsel bir çizgede bulunabilecek an fazla ayrıt sayısı, ve birkaç küçük gözlemi de kullanarak, K3,3 ve K5 çizgelerinin düzlemsel olmadığını göstermek mümkün. Meraklılar deneyebilir, takılan bana sorabilir. 

Konu iyice dallandı budaklandı, tuvalet kağıdına ne zaman bağlanacak diye merak ediyorsunuz öyle değil mi? Buraya kadar sabredip okuduğunuza göre şimdi esas soru geliyor.  Soru 1 ve 2’de, açık olarak söylenmeyen bir kısıt vardı. Evler, kuyular ve araziler, bunlar hep küre şeklindeki dünyamız üzerinde. Yani K3,3 ve K5’in ayrıtları kesişmeyecek bir şekilde küre, ya da bu problem için eşdeğer olduğunu daha önce ifade ettiğimiz gibi düzlem üzerinde çizmeye çalıştınız. Peki ya bu kısıtı kaldırırsak, yani bir kağıt üzerine değil de çevrenizde gördüğünüz  başka bir cisim üzerinde çizmeye çalışırsanız… Evet, örneğin tuvalet kağıdı rulosu!

Soru 3: Şekil 4’deki K3,3 ve K5 çizgelerini tuvalet kağıdı rulosu üzerinde ayrıtları kesişmeyecek şekilde çizebilir misiniz?

Bence bu linke tıklayıp da cevabı görmeden önce birazcık kendiniz deneyin. Burada bizi cevaba götüren gözlem, tuvalet kağıdı rulosunun topolojik özellikleri açısından  bir simit şekline denk olmasıdır: her ikisi de bir kürenin ortasından boylu boyunca bir delik açılarak elde edilir. Gerisi, elde edilen cismin ne kadar dolgun ya da ezilmiş olduğu, yüzeyinin yuvarlaklığının ne kadar korunduğu ya da düzleştirildiği ile ilgili detaylardan ibarettir ve bizim sorumuzun cevabını etkilemez.

Tuvalet bulmacalarımız burada sona eriyor. Eğer buraya kadarki kısım merakınızı çektiyse, son bir çaba daha gösterip tüm bunların devamında gelen güncel araştırma konularını anlamaya çok yakınsınız demektir. 

Nasıl düzleme gömülemeyen çizgeler varsa, simit üzerine de gömülemeyen çizgeler mevcuttur. Peki bir yerine iki deliği olan bir simit alırsak, onun üzerine hangi çizgeleri gömebiliriz? Çok delikli simitleri Şekil 7’de görebilirsiniz. Bu soruyu şu şekilde genelleştirmek mümkün: Bir çizgenin hangi özelliklere sahip olması gerekir ki, g delikli bir simit üzerine gömülebilsin? 

Şekil 7

Şekil 7: Delik sayısı g sıfırdan üçe kadar olan simitler.

g delikli bir simite gömülen bir çizgenin yüz sayısını genelleştirilmiş Euler formülü vermektedir: f = m – n + 2 – 2g. Ancak genelleştirilmiş Euler formülü maalesef verilen bir çizgenin g delikli bir simit üzerine gömülebilip gömülemeyeceği sorusuna yanıt vermemiz için yetersiz kalmaktadır. Bir çizgenin cinsi (genus) o çizgenin gömülebildiği simitlerin sahip olduğu en küçük delik sayısıdır. Örneğin, düzlemsel bir çizgenin cinsi sıfırdır çünkü sıfır delikli bir simit (yani küre) üzerine gömülebilir. Genel olarak, verilen bir çizgenin  cinsini hesaplamak NP-zor bir problemdir. 

Çizgelerin çizimiyle ilgili bir diğer önemli araştırma alanı da kesişme sayısı denen bir parametreyi inceler. Verilen bir çizgenin kesişme sayısı, o çizgenin bir düzlem üzerine çizimindeki kesişen en az ayrıt sayısıdır. Örneğin, düzlemsel bir çizgenin kesişme sayısı sıfırdır. Hiç şüphesiz, bir çizgeyi en az sayıda ayrıtı kesişecek şekilde çizmek, çizge ile görselleştirdiğimiz bilginin iletilmesini kolaylaştıracaktır. Şekil 8’de görülebileceği gibi, aynı çizgeyi az ayrıt kesişimi ile çizmek, beynimizin ikili ilişkileri daha kolay algılanmasını sağlamaktadır. 

Şekil 8

Şekil 8: Aynı çizgenin farklı çizimlerinde kırmızı ile gösterilen ayrıt kesişimleri de farklıdır. Burada aynı çizgeden kastımız, birbirine izomorfik (eşyapısal), yani matematiksel nesne olarak aynı ancak çizimleri farklı çizgelerdir.

Çizgelerin kesişme sayısının bir diğer önemli uygulaması ise, bu yazıyı okurken kullandığınız bilgisayar ya da cep telefonunun içinde kullanılan Çok Geniş Ölçekli Tümdevrelerin (VLSI) tasarımıdır. Bu devrelerin etkin, hızlı ve güvenilir şekilde çalışmaları için mümkün olduğunca küçük bir alana yayılması istenir. Şekil 9’da da görülebileceği gibi, altında bir çizge yapısı yatan bu devrelerin kapladığı alanı etkileyen faktörlerden birisi, ilgili çizgenin kesişim sayısıdır.  Devre tasarımında, altta yatan çizge düzlemsel olmadığı zaman başvurulan bir yöntem de devreyi birkaç kat üzerine inşa etmektir. Bu durumda, ihtiyaç duyulan kat sayısı, çizgenin ayrıt kümesinin ayrıştırılabildiği en az düzlemsel çizge sayısı olan çizgenin kalınlığı parametresi ile bağlantılıdır.

Şekil 9

Şekil 9: Çok Büyük Ölçekli Tümdevrelerin ayrıtları kesişmeyen bir çizge şeklinde tasarlanması.

Verilen bir çizgenin cinsini, kesişme sayısını veya kalınlığını hesaplamak hep NP-zor problemlerdir. Güncel çalışmalar bu parametreleri belli özelliklere sahip çizge sınıflarında tam olarak hesaplamak, ya da genel bir çizge için yaklaşık hesaplamalar yapan algoritmalar geliştirmek üzerine yoğunlaşmaktadır. 

Elbette daha anlatacak çok şey var ancak tuvalette çok da uzun kalmak iyi bir fikir olmayabilir. Bu yüzden bu yazıyı yavaş yavaş sonlandıralım. Hangi çizge hangi yüzeye gömülebilir, bir çizgenin cinsi, kesişme sayısı ve kalınlığı nasıl hesaplanır soruları, birçok matematikçinin üzerine yoğunlaştığı derin bir araştırma konusu. Konuyu daha fazla merak edenler, sadece bu alana odaklanan ve 1992 yılından beri her yıl düzenlenen ‘‘International Symposium on Graph Drawing and Network Visualization’’ isimli bir konferansa, onlarca kitaba ve web sayfasına başvurabilir. 

Sabredip yazıyı buraya kadar okuyanlara güzel bir haberim var. Dünyanın ilk ve tek Fields madalyalı kadın matematikçisi, Maryam Mirzakhani’yi tanıyor musunuz? Güzel haber şu: Şimdi, yukarıda anlattıklarımızın yardımıyla, Maryam Mirzakhani’nin çalışmalarını anlamaya artık bir adım daha yakınsınız. Biz bu yazıda çizgeleri belli bir yüzeyin üzerine çizerken ayrıtların kesişmemesine odaklandık. Verilen bir yüzey üzerindeki iki noktayı birleştiren (çizgelerde ayrıta denk gelen) yolun uzunluğunu da hesaba katarsak karşımıza farklı problemler çıkmaktadır.  Örneğin, bir yüzey üzerinde, başladığı noktada biten en kısa (kapalı) yolları (jeodezik) inceleyebiliriz. İşte bu konu, 40 yaşında kaybettiğimiz ünlü  matematikçi Maryam Mirzakhani’nin araştırmalarının yoğunlaştığı alan olup, uzun bir hikayenin başlangıcıdır.

Yazar(lar) hakkında:

Tınaz Ekim, Lille 1 Üniversite’sinden Matematik (1999), Galatasaray Üniversitesi’nden Endüstri Mühendisliği (2001) lisans derecelerini aldıktan sonra, 2002 yılında Paris Dauphine Üniversitesi’nde yüksek lisans derecesini tamamlamıştır. 2006 yılında EPFL’de (Lozan, İsviçre), Matematik Mühendisliği / Yöneylem Araştırması dalında doktorasını tamamlamıştır. 2007 yılından bu yana Boğaziçi Üniversitesi Endüstri Mühendisliği Bölümü’nde öğretim üyesidir. 2016 yılı TÜBA Genç Bilim İnsanı Ödülü (GEBİP) sahibi Tınaz Ekim, 2017-2018 yılında Fulbright araştırma burslusu olarak ABD’de bulunmuştur. Tınaz Ekim, Çizge/Ağ Kuramı, Optimizasyon ve Yöneylem Araştırması alanlarında dersler vermekte ve araştırmalar yapmaktadır.

Bu yazıyı paylaşarak daha fazla kişiye ulaşmasını sağlayın: