Matematik Atölyesi – Graf #4

2014 yılının Kasım ayında Rusya’nın St. Petersburg şehrinde bulunan dünyaca ünlü Hermitage müzesini ziyaret etmiştim. İçinde 1057 tane oda olan Hermitage’ı baştan sona yürüyen biri 22 km mesafe kat etmiş olur. Müzede bulunan eserlerin tamamına bakmak istiyorsanız, her esere sadece 1 dakika ayırsanız bile bu işi 11 yıldan önce bitirmenin mümkün olmadığını bilmeniz gerekir.

hermitage-map-st-petersburg
Hermitage’ın planı.

Bu yüzden Hermitage’ı sadece birkaç saatliğine ziyaret etmeye çalıştığımda nerede ne kadar süre geçirmem gerektiğini iyi ayarlamalıydım. Çünkü devasa müzeyi kısa sürede gezmem, ama bunu yaparken ilgimi çeken eserleri görmem gerekiyordu.

Aslında bu, çok orijinal bir problem değil. Hemen herkes günlük yaşamında bu tür problemlerle karşılaşır: “Ev-iş arasında hangi saatte hangi yolu kullanmalı?” gibi.

Postacının Yolu

St. Petersburg’da bu problemle karşılaşmam çok hoş bir tesadüftü. Çünkü Petersburg 18. yüzyılda ünlü matematikçi Leonhard Euler’e ev sahipliği yapmıştı. İlk graf yazısından hatırlayacağınız üzere Euler Königsberg’in yedi köprüsü problemiyle birlikte çizge teorisinin ortaya çıkmasına önayak olmuştu.

Königsberg probleminden 230 yıl sonra 1960’da Çinli bir matematikçi olan Mei-Ko Kwan soruyu biraz daha farklı şekilde ele almıştı:

Bir postacı rotasındaki evlere elindeki mektupları dağıtmak üzere posta ofisinden ayrılır. Postacının en kısa sürede tüm evlere uğrayıp tekrar posta ofisine dönmesi için nasıl bir rota izlemesi gerekir?

indir
Mei-Ko Kwan

Kwan’a ithafen Çinli Postacı Problemi olarak bilinen bu problemde önemli olan detaylar şunlardır:

  • Postacı rotası üzerindeki tüm sokakları kullanmalıdır. Fakat her sokak sadece ama sadece bir defa kullanılmalıdır.
  • Postacının rotasında başlangıç ve bitiş posta ofisinde olmalıdır.
  • Postacının amacı en kısa sürede yukarıdaki iki şartı yerine getirmektir.

Çizge Teorisinin Gücü

Mei-Ko Kwan Çinli Postacı Probleminin çözümünde Euler’in Königsberg’in yedi köprüsü için ortaya keşfettiklerinden yararlanmıştı. Kwan’a göre problem Euler’in yaptığı gibi graf haline getirebilirdi. Postacının gitmesi gereken mahalleler noktalarla, mahalleler arasındaki mesafeler (yani sokaklar) ise çizgilerle gösterilebilir.

Örnek Graf:

20190324_210039
A, B, C, D ve E harfleri mahalleri, aralarındaki çizgiler yolları gösteriyor. Çizgilerin üzerindeki sayılarsa postacının bir mahalleden diğerine ne kadar sürede gittiğini ifade ediyor.

Hatırlatma

Euler döngüsü nedir?

Eğer bir grafta Euler döngüsü varsa o grafta bulunan tüm çizgiler bir ama sadece bir defa kullanılarak tam bir tur atılabilir demektir. Ayrıca Euler döngüsünde başlangıç ve bitiş aynı noktadadır.

Euler döngüsü ne zaman vardır?

Bir graftaki bir noktanın sahip olduğu çizgi sayısı, o noktanın derecesini verir. Eğer bir grafta Euler döngüsü varsa, o graftaki tüm noktalar çift derecelidir.

Çözüm

Anlaşıldığı üzere Çinli Postacı Probleminin çözümü için postacının rotasında Euler döngüsü olmalıdır. Örneğin postacının güzergahı aşağıdaki gibi olsun:

20190325_123338.jpg
Çizgilerin üzerindeki sayılar harfler mesafeleri (km cinsinden olsun) gösteriyor.

İlk yapılması gereken şey tüm noktaların (harflerin) sahip olduğu çizgi sayısını bulmak:

20190325_123326.jpg

Yukarı görüldüğü üzere graftaki tüm noktalar çift derecelidir. Bu sayede hiç denememize bile gerek kalmadan bu rotada Euler döngüsü olduğunu söyleyebiliriz. O halde postacının en kısa sürede görevini tamamlaması için graftaki yolları kullanması yeterlidir:

20190325_123311.jpg
En kısa güzergah 11 km sürer.

Tek dereceli noktalar varsa grafa yeni çizgiler eklenerek (yani postacı yeni yollar üretmek zorundadır) tüm noktalar çift dereceye çevrilmelidir. Peki bu nasıl yapılır?

  1. Tek dereceli noktaları bul.
  2. Bu noktaları ikili gruplara ayır.
  3. İkili gruplar arası mesafeleri bul. En düşük mesafeliler eklenmesi gereken çizgileri belirtir.
  4. Çizgileri grafa ekle.

Yukarıda verdiğim mahalle örneği üzerinden giderek açıklamaya çalışalım. Sorun postacının A mahallesinden başlayıp yine A’da bitecek gününü en kısa sürede tamamlamak istemesidir.

Önce her mahallenin (yani noktanın) sahip olduğu yol sayısına (yani çizgi sayısına) bakalım:

20190324_210039
A ve D’nin 3’er, B, C ve E’nin 2’şer çizgisi vardır.

Her nokta çift sayıda çizgiye sahip olsaydı burada bir Euler yolu olurdu ve postacının en kısa turu direk mesafelerin toplanmasıyla bulunabilirdi. Fakat A ve D noktalarının tek sayıda çizgiye sahip olması bunu engelliyor:

20190324_210102

Bu durumda yapılması gereken şey, tek çizgiye sahip noktalar arasında yeni yol veya yollar yapmaktır. A ve D mahalleri arasında üç farklı yol vardır. Bunlardan en kısasını bulup grafa eklersek sorumuz çözülmüş olur:

20190324_210157

A-D mahalleri arasındaki yollar yukarıdaki gibidir. Görüldüğü üzere en kısa süre direk A-D arasındaki yoldadır. O halde A-D arasına yeni bir yol eklersek postacının sorunu çözülmüş olur:

Bi’ Göz Atmakta Fayda Var

Aşağıdaki rotada A’dan başlayıp A’ya dönmesi gereken postacının en kısa yolu ne kadar süre alır? Bunu yapabilmek için kullanması gereken rota nedir?

20190324_210225

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Garip Dünyalar #3

Miras

Küçükken bayramdan bayrama, büyüdükten sonraysa sadece düğünlerde görülen uzak akrabayla ilgili en sevdiğim şeydir miras. Milli piyango, sayısal loto ve benzeri oyunlarda şansım yaver gitmediği için ara sıra bana miras kaldığını hayal ederim. Moskova, Cannes, LA’de birer daire satın alıp dört ayda bir diğerine geçerim… Yargılamayın; hayal benim değil mi?!

Bir süre sonra hayal gücümde mirası nasıl harcayacağım konusu sıkıcı gelmeye başladı. Bu yüzden mirasın elde edilme süreciyle ilgili hayaller üretmeye başladım. Play station’da oyun oynarken bile oyunun seviyesini en zora ayarlıyoruz ki zevk alalım. O halde zor yoldan elde edilecek mirasın da zevki başka olur, değil mi?

Hayalimdeki miraslardan birinde avukat bey bana bir harita verir:

“Serkan bey, haritada işaretli olan yerde bir gömü var. Gömünün içinde 24 kg ağırlığında bir Osmanlı definesi bulacaksınız. Gömüye ulaşmak için 15 saat vaktiniz var. Kullanmanız için bir uçak ve uçuş ekibi havalimanında sizi bekliyor.

Yapmanız gereken tek şey pilotlara hangi rotayı izlemeleri gerektiğini söylemeniz. Eğer en kısa rotayı bulamazsanız miras en sevmediğiniz futbol takımına hibe edilecek.”

En Kısa Yol

Google maps sayesinde koordinatları çözdüm: Gömü Los Angeles(LAX) havalimanında. Tek yapmam gereken İstanbul Atatürk ile Los Angeles LAX arasındaki en kısa yolu bulmak.

Üç boyutta iki nokta arasındaki en kısa yol düz çizgidir. O halde harita üzerinde İstanbul ve Los Angeles’i birer nokta olarak düşünürsem, bu iki nokta arasında çizeceğim düz çizgi en kısa yol olacak. Hayalimdeki soruya bak, iki dakikada çözdüm.

Dünya’nın Şekli Ne Serkan?

Eğer Dünya düz olsaydı, şüphesiz tarihin en sıkıcı hayalini kurmuş sayılacaktım. Fakat Dünya’nın yuvarlak olduğunu uzun bir süredir biliyoruz. Ne? Düz Dünyacı mısınız? Lütfen terk edin bu siteyi!

Türk Hava Yolları’nın internet sitesinde İstanbul ile diğer şehirler arasında izlenilen yollar gösterilir. İstanbul ile Los Angeles arasındaki yol aşağıdaki gibidir:

thy rota

Peki ama neden?

projections6
İstanbul-New York arasına bakalım: Bu haritaya göre en kısa yok düz çizgi olmalı.
projections7
Fakat yuvarlak gezegenimize yukarıdan bakıyor olsaydık görüntü bu şekilde olurdu. Harita üzerinde düz çizgi sandığımız yol aslında bir eğridir.

Çünkü Dünya veya bir top gibi yuvarlak şekle sahip şeylerin üzerinde bulunan iki nokta arasındaki en kısa mesafe her zaman bir eğri olacaktır. Bunu bir ip veya oyun hamuru ile deneyip kendiniz de görebilirsiniz.

O halde düz harita üzerinde en kısa yolu bulmak neredeyse imkansızdır. Klasik sorumuzu soralım: Neden?

Çünkü Dünya gibi yuvarlak şekilli nesneler tam olarak 3 boyuttan 2 boyuta  tam olarak indirgenemez. Bugün sahip olduğumuz bazı haritalar belli ölçüde doğru olsa da aslında hiç bir harita %100 doğru ölçeği vermez. Örneğin bir topun üzerinde üç nokta alalım ve bir üçgen çizelim. Bu üçgenin kenarları eğri olacaktır.

Bunu basit bir örnekle daha destekleyebiliriz. Bir portakal üzerine üçgen çizin ve üçgen şeklindeki kabuğu soyun. İlk olarak fark edeceğiniz şey portakalın üzerinde düz çizgiler çizilmesine rağmen üçgenin kenarlarının düz değil eğri olduğudur. İkinci ve en önemlisiyse bu kabuğun kenarları ne yaparsanız yapın hiç bir zaman tam olarak düz hale getirilemez. Bir kenarı masaya bastırdığınızda diğer kenarların havaya kalktığını görebilirsiniz.

Ancak, topoloji sayesinde bu üçgeninin kenarlarını düz çizgiler yapabiliriz. Oyun hamuruyla aynı şeyi denersek, kenarlarını uzatarak üçgeni düz hale getirebiliriz. Ama bu da gerçek ölçekten uzaklaştığımız anlamına gelir.

Sonraki Yazıda: Eratosthenes’in harika yöntemi.

M. Serkan Kalaycıoğlu

 

Matematik Atölyesi: Geometri #1

Sabunlu su kabarcığı ile matematiğin nasıl bir ilişkisi olabilir?

Belli ki matematik profesörü Michael Dorff sabunlu su hazırlayıp içine bir şeyler daldırmayı çok seviyor. (Profesör Dorff’un videosu için tıklayın) Matematiğin hayatın her alanında karşımıza çıktığını söyler dururuz. Bunlardan birine sabunlu suya iki kez daldırdığı bir küp sayesinde ulaşan profesör Dorff, böylece içi boş bir küpün içinde kabarcıktan bir başka küp oluştuğunu gösteriyor.

Matematikçiler küp içinde küp olan şekle “hiperküp” der.

Peki hiperküp nedir?

Maalesef algılarımız üç boyutun ötesini anlamayacak şekilde oluşmamış. Fakat matematik ve fizik sayesinde yüksek boyutların varlığı malumumuz. İşte hiperküp de dördüncü boyutta küpün aldığı şekildir. Yani üç boyutlu bir küp, içine dolan sabunlu su kabarcığı sayesinde dört boyutlu bir küpün şeklini alır. Matematiğin bu güzel yönünü gösteren örneğe rağmen kabarcıkların bize gösterdiği tek şey dördüncü boyut değil. Diğer özellikleri anlayabilmek için biraz geriye gitmemiz gerekiyor.

tesseract
Hiperküp

2400 Yıl Önce

Antik zamanlar ve bilimden bahsederken Yunan isimler havada uçuşur. Eğer bir antik Yunan eseri okuduysanız bunun nedenini biliyorsunuzdur. Tarihte beni en çok etkileyen eser de bir antik Yunan olan Öklid’e aittir. Bu ismi büyük ihtimalle lisede geometri dersinde bir teorem olarak biliyorsunuz. Halbuki Öklid’in milattan önce 400 civarında yazdığı ve 13 ayrı kitaptan oluşan Elementler, sadece matematiğin değil, uygarlık tarihinin en önemli eserlerinden biridir.

Öklid’in Elementleri’nin ne kadar önemli olduğunu anlatmak için bir kıyas yapalım: İnsanoğlunun sıfır(0) sayısını tam olarak açıklamasından beri 1350 yıl, Elementler’in yazımından beriyse 2400 yıldan fazla zaman geçmiştir.

Elementler’de Ne Var?

Bu soruya vereceğim çok fazla cevap var. Şimdilik sadece başlangıçtan bahsedeceğim. Kullanacağım tercüme Ali Sinan Sertöz hocanın çalışmasından geliyor. Elementler için tercüme arıyorsanız işinize kesinlikle yarar.

Elementler’in ilk kitabı verilen yirmi üç adet tanımla başlar. İlk tanım şudur: Nokta, büyüklüğü olmayandır. Yani Elementler’de Öklid en baştan başlayarak tüm geometriyi açıklamaya koyulmuştu. Bunu yaparken ilk kitapta nokta, çizgi, doğru, yüzey… gibi tanımlarla başlayıp, bunların ardına beş adet aksiyom koymuştu.

Aksiyom: Doğruluğu ispat edilmesine gerek kalmadan kabul edilen önerme.

Öklid’in Birinci Aksiyomu: Bir noktadan herhangi başka bir noktaya bir doğru çizilebilir.

IMG_4469

Bir noktadan diğerine sonsuz sayıda eğri çizilebilirken, sadece bir tane doğru çizilebilir. Bu doğru aynı zamanda iki nokta arasındaki en kısa yoldur.

Sabunlu Su Kabarcığı

Öklid, iki nokta arasındaki en kısa yolun bir doğru olduğunu belirtmişti. Peki dört nokta arasındaki en kısa yol neydi?

İşte Profesör Dorff bu sorunun cevabını kabarcıklarda gördüğünü söylüyor. Yazının başında bir küpü sabunlu suya iki kez batırınca dördüncü boyuttan bir şekil olan hiperküpün bulunduğundan bahsetmiştim. Küp bir defa sabunlu suya batırıldığında ise küpün içinde H ile X harflerinin karışımı bir şekil oluşur. İşte bu şekil dört nokta arasında kalan en kısa yolu verir.

ShortestRoadOnSquareWithDotsAndDims-Revised2
Mavi çizgiler dört nokta arasındaki en kısa yolu gösteriyor.

Bakış Açısını Değiştirmek

Özellikle 1990’larda çok popüler olan 3-boyutlu resimlere aşinasınızdır. İlk bakışta anlamsız gözüken bu resimlerin içinde bulunanı bir kez fark edince onu bir daha görmemeniz mümkün değildir.

crater

Matematikçilerin bir kısmı 3-boyutlu resme bakanlar gibidir; bir olayın içinde gizlenmiş matematiği gördüler mi, etraflarındaki her şeye farklı açıdan bakmaya başlar. Matematiği anlamak için ilk şartlardan biri de budur: Bakış açısını değiştirmek.

M. Serkan Kalaycıoğlu