Matematik Atölyesi – Algoritma #6

2600ler…

Sonunda Dünya dışında yaşayabileceğimiz bir gezegen keşfedildi. Bilim insanlarının T-489 ismini verdiği bu gezegende yaşam koşulları Dünya’ya benzer görünüyor. Uydu görüntüleri T-489’da su bulunduğunu gösterirken gezegenin atmosferinin de Dünya’nınki ile tıpatıp aynı olduğu keşfedildi.

T-489’un bulunduğu sistem.

Büyük devletlerin uzay ajansları ortak bir ekip gönderip T-489’da yaşam olup olmadığını kontrol etmekte anlaştı. Hazırlanan plana göre uydu görüntülerinden elde edilen veriler ışığında T-489’da belirlenen bir noktaya inecek ilk ekip, burada güvenli alan ve merkez üs oluşturacak.

Güvenli alan oluşturulduktan sonra ise yine uydu sayesinde belirlenmiş olan noktalara üç ayrı ekip gönderilecek. Bu ekipler hem bulundukları bölgelerde yaşam koşullarını inceleyecek, hem de farklı yaşam formları olup olmadığını kontrol edecek.

T-489’da bulunan merkez üs, keşfe çıkacak ekipler için bir harita yapacak. Merkez üssün hazırladığı harita hem gezegen üzerinde yolculuğun nasıl yapılabileceğini, hem de ekiplerden herhangi birinin sorun yaşaması durumunda üsse nasıl geri dönmesi gerektiğini açıklamak zorunda.

Haritanın görünümü: Sarı nokta merkez üs, diğer noktalar ise keşif ekiplerinin ziyaret edeceği konumlar.

Herhangi bir anda bir ekibin nerede olduğunun bilinemeyeceği durumlar için merkez üste çalışanlar çizdikleri haritaya bir de algoritma eklemeli. Bu, öyle bir algoritma olmalı ki, algoritmayı takip eden ekip(ler) sonunda merkez üsse varır.

Yol Boyama Problemi

1970’de Roy Adler’in ortaya attığı bir problem olan yol boyama problemi (road coloring problem), 2007’de yılında İsrailli matematikçi Trahtman tarafından çözülmüştü.

Trahtman, yukarıdaki gibi bir graf (veya harita) düşünmüştü; noktalar arasında bulunan yolların belirli yön ve renkleri vardı. Bu yön ve renkleri bulduğu algoritmaya göre oluşturan Trahtman’a göre grafın herhangi bir noktasından başlayıp üç kere mavi-kırmızı-kırmızı yolları izleyen biri her zaman sarı noktada duracaktır.

T-489’da Kaos

Gezegende keşfe çıkacak ekipler için harita yapmanız gerekiyor. Merkez üs ve gezilmesi gereken noktalar aşağıdaki gibi:

Keşif ekiplerinin yaşayabileceği en kötü duruma hazırlanmanız gerekiyor. Eğer ekiplerden birinin iletişimi kopar ve haritaya ulaşma şansı kalmazsa, yaratacağınız algoritma hayatlarını kurtaracaktır.

Geliştirdiğiniz fikir şöyle ilerliyor: Gidilmesi gereken her konumun girişine bir tabela konulacak. Bu tabelalarda sadece yolun yönü ve rengi yazacak. (Tabelalara haritaların asılmamasının nedeni, zeki bir uzaylı türüyle karşılaşılması durumunda merkez üssün yerinin direk uzaylılara gösterilmemesidir.)

Yarattığınız algoritmaya göre iki defa kırmızı-mavi yapmak ekipleri merkez üsse ulaştırır:

Bi’ Göz Atmakta Fayda Var

Keşif yapılacak bir nokta daha olsun. Haritanız için öyle bir algoritma yaratın ki, izlenen algoritma sizi hep M noktasına (yani merkez üsse) geri döndürsün.

(Bunu yaparken en az sayıda yol kullanmaya özen gösterin.)

Matematik Atölyesi – Graf #6

Miras Problemi

Kral Serkan I ölüm döşeğindeyken sahip olduğu arsaları çocuklarına dağıtmaya karar verir. Doğal olarak Serkan I’in bazı koşulları vardır:

  • Her çocuk en az bir arsa alacak.
  • Birbirine komşu arsalar aynı çocuğun olmayacak.
  • Yukarıdaki koşullar sağlanmadığı takdirde mirasın tamamı “Fener Ol” kampanyası vasıtasıyla Frey’in bonservisine harcanacak.

Problem: Serkan I’in en az kaç çocuğu olmalı ki herhangi bir arsa paylaşımında sorun yaşanmasın?

Harita #1

Basit bir haritadan başlayalım:

20190423_000256.jpg

Bu durumda Serkan I’in iki çocuğunun olması yeterlidir:

20190423_000310.jpg

Bir önceki yazıdan hatırlayacağınız üzere harita ile graf birbirlerine dönüşebilir. Eğer arsalar noktaları ve iki arsanın komşu olması bu iki noktanın arasında çizgi olduğunu ifade ederse, haritamız aşağıdaki gibi graf olarak gösterilebilir:

20190423_000334.jpg

Bu haritaya bir arsa daha ekleyelim:

20190423_000402.jpg

Eklenen arsa graf için yeni nokta ve çizgi(ler) anlamına gelir:

20190423_000507.jpg

Harita #2

Yeni haritada üç arsa bulunsun:

20190423_000523.jpg

Bu haritayı graf haline getirelim:

20190423_000537.jpg

Grafta da görüldüğü üzere mirasın dağıtılabilmesi için Serkan I’in üç çocuğu olmalıdır:

20190423_000553.jpg

Harita #3

Üçüncü harita aşağıdaki gibidir:

20190423_000627.jpg

Bu dört arsanın kurallara uygun dağıtılması için miras dört çocuğa dağıtılmalıdır:

20190423_000642.jpg

Harita #3’teki durum graf olarak aşağıdaki gibidir:

20190423_000728.jpg

Harita #4

Serkan I’in bıraktığı arsaların aslında ABD haritasıyla aynı olduğunu varsayalım:

480271690e1e0485f71988e273730559

Bu haritayı paylaştırmak için Serkan I’in sadece dört çocuğunun olması yeterlidir:

amarikaaa

Ne Oluyor?

Dikkat ederseniz harita #2’nin grafından harita #3’ün grafına tek bir hareketle (yeni bir nokta koyarak) geçmek mümkündür. Hatta harita #1’den harita #2’ye geçiş de graf üzerine yeni bir nokta eklenip (3 numaralı olan) diğer iki noktaya bağlanarak gerçekleşmiştir:

O halde bir haritaya yeni bir mirasçı eklemek demek grafa yeni bir nokta eklemek demektir.

Peki en az beş çocuğun gerektiği bir harita yaratılabilir mi?

Bu soru aslında grafa (hiçbir çizgiyle kesişmeden) tüm noktalarla bağlantısı olan beşinci bir nokta eklenip eklenemeyeceği anlamına da gelir.

Yani tek yapmamız gereken dört noktalı grafa beşincisini ekleyip bu yeni noktayı diğerleriyle birleştirmektir. Fakat deneyince bunun mümkün olmadığı görülür. Örneğin beşinci noktayı en dışarı koyarsak:

1 ile 5’in arasında diğerleriyle kesişmeyen bir çizgi çizmek mümkün değildir. Ne yaparsak yapalım aynı sonuçta karşılaşırız:

Dört Renk Teoremi

Yaklaşık 160 yıl önce Francis Guthrie harita boyamak üzerine düşünüyordu:

“Düzlemde çizilmiş olan herhangi bir haritayı komşu ülkeler farklı renkte olacak şekilde boyamak için kaç renk yeterlidir?”

İnanılmaz bir şekilde cevap sadece dörttür.

Matematikle ilgili olan/olmayan hemen herkesin anlayabileceği basitlikteki bu soru ilk defa 1852’de Francis Guthrie tarafından ortaya atılmıştı. Ancak 120 yıl sonra (1976’da) dört rengin yeterli olduğu bilgisayarda 1936 farklı senaryo incelenerek ispatlanmıştı. Bu ispat çok önemlidir çünkü tarihte ilk kez bir matematik teoremi bilgisayar kullanılarak ispat edilmişti.

Bi’ Göz Atmakta Fayda Var

20190423_003916.jpg

Yukarıdaki grafa dördüncü noktayı ekleyin ve diğerlerine çizgilerle bağlayın. (Bunu yaparken dördüncü noktayı istediğiniz yere koymakta serbestsiniz.)

Şimdi elinizdeki grafa bakın: Dört noktadan herhangi biri çizgilerin içinde kalmış değil mi?

Bunu engellemenin yolu var mı?

Neden var/yok?

M. Serkan Kalaycıoğlu

 

Matematik Atölyesi – Graf #5

Zalim Trafik Işığı

Hemen her gün aynı dört yol ağzından geçiyorum. Tabii olarak en uzun süre kırmızı yanan ışığın bulunduğu tarafı kullanmak zorundayım. Bir bakıma beklemek iyi geliyor: Hayatla ilgili bazı şeyleri düşünmeme olanak sağlıyor. Fakat düşüncelere matematik eğitiminin girmesi çok fazla zaman almıyor.

Bu kısa düşünce seanslarında aklıma takılanlardan biri matematiğin trafik ışıklarıyla ne tür bir ilgisi olabileceğiydi. Kısa bir araştırmadan sonra karşıma matematiğin en sevdiğim kısımlarından biri olan çizge teorisi çıktı.

Işık #1

Tek yön araç akışı olan ve yayaların karşıdan karşıya geçebildiği bir yol düşünün.Araçlar için olan ışığa A, yaya için olanaysa B diyelim:

20190419_014641.jpg

Bu durumda kaza olmaması için A’da yeşil renk yanarken B’de kırmızı, B’de yeşil yanarken ise A’da kırmızı yanmalı. Her iki ışığın da kırmızı yanması kaza yok demekse de anlamsızdır; çünkü öyle bir durumda kimse yerinden kıpırdayamamış olur:

20190419_014707.jpg

Bu durumu çizge teorisinde nokta ve çizgi olarak da gösterebiliriz. A ve B noktalar olurken, aralarında çizgi bulunması noktaların farklı renklerde olduğunu gösterir:

20190419_014721.jpg

Aynı şeyi alan boyama ile de göstermek mümkündür: A ile B komşu iki ülke gibi düşünülebilir. Komşu ülkeler birbirleriyle karışmasın diye farklı renklerde boyanır:

20190419_014817.jpg

Işık #2

İkinci örnekte gidiş-geliş bir yol ve yayalar için konan trafik ışıkları olsun. Araçlar için olan trafik ışıkları A ve B, yayalar için olansa C harfiyle gösterilsin:

20190419_014838.jpg

Bu yolda C kırmızıyken A ile B’nin her ikisi veya herhangi biri yeşil yanabilir. C yeşilken ise A ile B’nin her ikisi de kırmızı olmalıdır:

20190419_014858.jpg

Hepsinin kırmızı olduğunda kaza olmayacaksa da kimse bir yere gidemediği için bu durumu es geçeriz.

İkinci trafik ışığını çizge teorisinde ve harita boyamayla aşağıdaki gibi ifade edebiliriz:

20190419_014930.jpg

Kurallar belirlendikten sonra çizge teorisinin trafik ışıklarının yanış şeklini ne kadar daha sade açıkladığını görebiliyoruz.

Işık #3

İki yönlü bir yolda sağa dönüş ve yayalar için iki ışık koyulmuş bir durumu ele alalım:

20190419_014947.jpg

Bu sefer öncekilere kıyasla görünürde çok daha karmaşık bir durumla karşı karşıyayız:

20190419_015005.jpg

Fakat çizge teorisi ve harita boyamayla karmaşa çözülür:

Kaç Renk Yeter

İki nokta arasında bir çizgi varsa bu noktaların farklı renkte olması gerektiğini düşünerek aşağıdaki grafleri boyayalım.

Kromatik Sayı: Herhangi bir grafte renklendirme/boyama yaparken amaç en az sayıda renk kullanmaktır. İşte bu sayıya bir grafin kromatik sayısı denir.

Burada en az 3 renk gerekir. Yani grafin kromatik sayısı 3’tür. Grafe bir nokta ve çizgi daha ekleyelim:

Nokta ve çizgi sayısı artmasına rağmen kromatik sayı 2’ye düşer. Bir nokta ve çizgi daha eklersek:

Kromatik sayı yine 3 olur. Son bir defa daha nokta ve çizgi ekleyelim:

Kromatik sayı tekrar 2’ye düştü.

Devam edecek…

Bi’ Göz Atmakta Fayda Var

Burada gerçekleşen şey ne? Ne fark ettiniz? Neden öyle oluyor?

Kromatik sayıyı nasıl artırabilirsiniz?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Graf #3

Pardon, sizi tanıyor muyum?

1928 yılında Frank Ramsey bir matematik problemiyle uğraşıyordu. Bu genç matematikçi uğraştığı problemi çözebilmek için yepyeni bir matematik branşını başlatmak zorunda kalmıştı. Maalesef Frank Ramsey bulgularını açıkladığı makale henüz yayımlanmadan 27 yaşında hayatını kaybetmişti. Fakat genç yaşında hayata veda etmesine rağmen Ramsey ölümsüz olmayı başarmıştı: Çünkü bugün bahsi geçen matematik branşına Ramsey Teorisi diyoruz.

Ramsey teorisinde temel sorulardan biri şudur: Kaosun (ya da rastgeleliğin) olduğu bir ortamda her zaman düzen bulunabilir mi? (Burada kaostan kasıt düzensizliktir.)

220px-Frank_Plumpton_Ramsey
Frank Ramsey (1903-1930)

Ramsey teorisi matematiğin mantık branşının bir alt dalı gibi görünse de bu yeni branşın bir çok uygulama alanı vardır. Bunlardan biri hemen hemen Ramsey teorisiyle aynı zaman diliminde ortaya çıkan çizge teorisidir.

Bu yazıda iki branşı bir araya getiren bir sorudan bahsedeceğim.

İhtiyaç Duyulanlar: Rastgele seçilmiş altı kişi.

Kaos: Altı kişi içinde bulunanların hangilerinin arkadaş, hangilerinin birbirine yabancı olduğu. (Arkadaş olmak iki yönlüdür: Sean Connery’i filmlerden tanıyor olmanız onunla arkadaş olduğunuz anlamına gelmez.)

Aranan Düzen: Bu altı kişi içinde herhangi üç kişinin birbiriyle arkadaş çıkması veya herhangi üç kişinin birbirine yabancı olması.

IMG_6185

Altı kişinin grafını çizelim. Grafta noktalar kişileri, düz çizgi arkadaş olmayı, kesik çizgiyse yabancı olmayı ifade etsin.

IMG_6186

Peki kaos nerede diye sorabilirsiniz. Altı kişi için arkadaş olup olmama ihtimali 30.000’den fazladır. Yani bu graf 30.000’den fazla ihtimalden sadece birini gösteriyor.

220px-Rasputin_PA
Rasputin herkesi tanır…

Grafta üç kişinin arkadaş olması düz çizgili üçgen; üç kişinin yabancı olmasıysa kesik çizgili üçgenle gösterilmiş olur. O halde grafın içinde üçgenleri aramamız gerekiyor. Şekilde de görüldüğü üzere bu altı kişinin içinde her iki üçgenden de bulunuyor: Örneğin Bill-Rasputin-Lewinsky bir arkadaş üçgeni oluştururken Alexandra-Lewinsky-Hürrem bir arkadaş olmayanlar üçgeni oluşturur.

Peki çizilebilecek her grafta (30.000’den fazla olduğunu hatırlayın) arkadaş olan veya olmayan üçlü bulunur mu?

Evet

Her ihtimali tek tek denemek imkansız olduğuna göre bir ispat yöntemi bulmak gerekir.

Sadece Rasputin’i ele alalım. Rasputin herkesle arkadaş olsaydı arkadaş sayısı 5, yabancı olduğu kişi sayısı ise 0 olurdu. Eğer 4 kişiyle arkadaş olsaydı, 1 kişiyle yabancı olurdu. Bu ihtimallerin tamamı aşağıdaki gibidir:

Bu ihtimaller sadece Rasputin değil, gruptaki herkes için geçerlidir. Buradan şu çıkarımı yapabiliriz: Gruptaki herkeste hep en az 3 arkadaş veya yabancı (arkadaş değil) ilişkisi vardır.

Hadi biz Rasputin’in üç kişiyle arkadaş olduğu durumu ele alalım:

IMG_6188

Bu durumda Rasputin ile arkadaş üçgeni oluşturmamak için Lewinsky-Hürrem-Alexandra birbirleriyle tamamen yabancı olmalıdır.

IMG_6189
Bu durumda Lewinsky-Hürrem-Alexandra bir üçgen yaratır.

Fakat üç kişinin arkadaş olmaması bu sefer kesik çizgili bir üçgeni sağlar. Bu da altı kişi için geçerli olan 30.000’den fazla ihtimalin tamamında en az bir tane üç arkadaş veya yabancı olduğunu gösterir.

Lewinsky-Hürrem-Alexandra üçgenini bozduğumuzda bu sefer Rasputin ile iki kadını kapsayan bir üçgen oluşuyor.

Bi’ Göz Atmakta Fayda Var

5 kişilik bir grupta herhangi 3 kişinin arkadaş çıkması veya herhangi 3 kişinin arkadaş çıkmaması ihtimali var mıdır?

M. Serkan Kalaycıoğlu

Matematik Atölyesi: Graf #2

Yazıyı okumadan önce Bulmaca I başlıklı yazıyı okumanız gerekir. Yine de kısaca hatırlatmamızı yapalım: Yanınızda keçi, kurt ve lahana ile evinize dönerken karşınıza büyük bir nehir çıkıyor. Şansınıza nehirde terk edilmiş bir sal görüyorsunuz. Salın kapasitesi çok küçük ve karşıya her seferinde keçi, kurt ve lahanadan birini geçirebiliyorsunuz.

Fakat burada bir sorun var çünkü keçiyi kurt ile yalnız bırakmak istemezsiniz. Siz lahanayı bırakıp gelene dek keçiden geriye pek bir şey kalmayabilir. Aynı şekilde keçi ile lahanayı da yalnız bırakmamak gerekir, çünkü lahana keçinin en sevdiği yemeklerden biridir. Üçlü arasında sadece kurt ile lahanayı yalnız bırakabiliyorsunuz.

Peki herkesi nehrin karşısına nasıl geçireceksiniz?

Graf Kullanarak Bulmaca Çözmek

Bu basit görünümlü bulmacayı graf haline getirip çözümü bulabiliriz. Bunun için nehrin sol tarafı 1, sağ tarafı ise 2 rakamı ile gösterilsin. İlk durumda herkes nehrin sol, yani 1 numaralı tarafındadır. Bunu 111 (Kurt-Keçi-Lahana) ile gösterebiliriz.

O halde bu üçlü için sekiz farklı konum vardır: 111, 112, 121, 122, 211, 212, 221 ve 222. Örneğin 112 demek kurt ve keçi nehrin solunda, lahana ise nehrin sağında demektir. Nihai amaç ise 222 konumuna gelmektir.

Grafı Çizmek

Biz bu sekiz konumun her birinin bir nokta ifade ettiğini varsayalım. Noktalar arasında geçişler ise çizgilerle gösterilsin. Noktalarımız ve bu noktalar arasında geçişi gösteren çizgilerimiz var. O halde şimdi helva yapabiliriz! Pardon, graf çizebiliriz demek istemiştim.

Başlangıç noktamız olan 111’den hareket edilebilecek üç nokta vardır: 112, 121, 211. (Örneğin 211’e gitmek demek kurdu sağa götürüp, keçi ve lahanayı solda yalnız bırak demektir.) Grafa döküldüğünde tüm ilişkiler şu şekilde gösterilir:

111

Eğer bu bağlantıların hepsini istediğimiz gibi kullanabilseydik, 111’den 222’ye ulaşmak çok basit olurdu. Fakat bulmaca bize iki kural vermiş ve bunlara göre bazı noktalar arasındaki bağlantılar (ya da çizgiler) kullanılamaz.

Çözüm

Yapılacak ilk hareket, çözümün kalanını belirler. Biliyoruz ki keçi ile lahana, kurt ile de keçi yalnız bırakılamaz. Bu yüzdendir ki ilk hamlede kurt ya da lahana karşı tarafa götürülemez. Grafikte bunun karşılığı şudur: İlk hareket 211 ve 112 yolundan yapılmamalıdır.

IMG_5358

O halde 111’den gidilebilecek tek yol kalır: 121 yolu. Bu da keçinin karşıya taşınması anlamına gelir. Böylece nehrin 1 tarafında kurt ve lahana yalnız kalır ki bulmacaya göre bu bir sorun teşkil etmez.

IMG_5359

İkinci harekete 121’den başlanacağına göre gidilebilecek üç nokta vardır: 111, 122 ya da 221. Zaten 111’den geldiğimiz için buraya geri dönmenin bir anlamı yoktur. Bu yüzden 122 ya da 221 noktalarından biri seçilmek zorundadır. Yani kurt ya da lahanadan birini nehrin 2 tarafına taşımalıyız.

122 yönünden gidersek:

Eğer 122 noktasına gidersek (ki bu lahanayı nehrin 2 tarafına götürmek demektir) keçi ile lahana yan yana kalmış olur. 122 noktasından sonra yine üç noktaya gitme şansımız vardır: 222, 121, 112.

  • 121: Bu noktadan geldiğimiz için geri dönmemizin bir anlamı olmaz. Yani 121’ye doğru gidilmez.
  • 222: En doğru seçim bu gibi görünür. Zaten amacımız herkesi nehrin 2 numaralı tarafında geçirmektir. Fakat 122’den 222’ye geçmek demek, lahanayı keçi ile yalnız bırakıp kurdu almak için nehrin 1 numaralı tarafına gitmek demektir. Bunu yaparsak biz kurdu alana dek keçi lahanayı hunharca katleder. Yani 122’den direk 222’ye gidemeyiz.
  • 112: O halde 122 noktasından gidebileceğimiz tek yer burasıdır. Bir diğer deyişle lahanayı karşıya bırakıp keçiyi geri götürmek.

112 noktasından gidilebilecek üç nokta vardır: 122, 212, 111. 111’e gitmek hem sorunun başına dönmek hem de keçiyi kurda teslim etmektir. 122 noktası ise bir önceki noktadır: Geri dönmenin bir anlamı olmadığını söylemiştik. O halde 112’den gidilebilecek tek yer 212 noktasıdır. Bu da keçiyi nehrin 2 numaralı kısmına geçirmek anlamına gelir.

212 noktasından direk 222 noktasına gidebiliriz. Çünkü 212 durumunda kurt ile lahana yalnız bırakılabilir. Böylece nehrin diğer kısmına gidip keçi alınabilir.

221 yönünden gidersek:

121 noktasından hareket edebileceğimiz iki farklı yön vardı. Bunlardan 221 yönünü seçseydik bulmacanın çözümüne ulaşabilir miydik?

221’den gidilebilecek noktalar 222, 211 ve 121’dir. Geri dönmek yok; bu yüzden 121 seçeneği devre dışı kalır. 221’den 222’ye direk geçip bulmacayı çözmüş olurduk ama bunu yapmak demek kurt ile keçiyi yalnız bırakıp lahanayı almaya gitmek demektir. O halde 221’den sonra gidilmesi gereken tek yön vardır: 211.

211’den gidilebilecek noktalar: 111, 221 ve 212’dir. 111 ve 221 noktalarına gitmek, geri dönmek manasına geleceği için buradan gidilmesi gereken nokta 212’dir. 212’den sonra 222, 211, 212 noktalarından birine doğru hareket edilmelidir. 212 noktasının anlamı şudur: Kurt ve lahana nehrin 2 numaralı tarafında, keçi ise 1 numaralı tarafta. Kurt ve lahana yalnız bırakılabileceği için keçiyi almaya gidebiliriz. Bu yüzden 212’den 222’ye geçip bulmacayı çözmüş oluruz.

Bi’ Göz Atmakta Fayda Var

Bu üçlü arasına yeni hayvan ve bitkiler koyun. Kendi kendinize kurallar yaratın ve bu kurallara göre graf çizmeye çalışın. Sonucun olup olmadığını ve neden/nasıl sorularını graf ile açıklayın.

M. Serkan Kalaycıoğlu

 

Matematik Atölyesi: Graf #1

Bulmaca ve matematiğin ilişkisi sanıldığından daha derindir. Matematik tarihi incelendiğinde önemsiz olduğu düşünülen bazı bulmacaların matematiği değiştirdiği, hatta yeni alanlara yol açtığı görülür. Şüphesiz bunlardan en ünlüsü Königsberg’in yedi köprüsüdür (1736).

18. yüzyılın en önemli matematikçilerinden biri olan Leonhard Euler’in “… bu sorunun matematikle bir ilişkisi olduğunu düşünmüyorum.” dediği Königsberg bulmacası çözüldükten yaklaşık 150 yıl sonra iki önemli matematik dalının ortaya çıkmasına yardımcı olmuştu: Topoloji ve çizge teorisi (nam-ı diğer graf teorisi).

Görsel 1
Leonhard Euler

Königsberg’in Yedi Köprüsü

Herhangi bir çizge teorisi kitabını açıp ve ilk bölümün ilk sayfasına baktığınızda karşınıza Euler’in çözdüğü Königsberg problemi çıkar. Soru şudur:

indir (1)

 

Königsberg şehrinin ortasında geçen nehrin üzerinde yedi adet köprü vardır. Bu köprülerin her biri bir ama sadece bir defa kullanılarak şehrin tamamı gezilebilir mi?

Bu soruyla ilk defa karşılaştığımda sorunun basitliği sebebiyle cevaba kendi kendime ulaşacağımı düşünmüştüm. Fakat saatler süren uğraşlarım boşa gitmiş, sonuca bir türlü ulaşamamıştım.

Aslında çözümün olmadığını anlamıştım. Örneğin köprülerden birini kaldırınca soru çözülüyordu. Ama bunun nedenini açıklayacak bilgim yoktu. Zaten kısa bir süre sonra bu sorunun neden çizge teorisi anlatılırken gösterilen ilk şey olduğunu anlamıştım. Sorunun çözümü yepyeni bir matematik branşının temelini oluşturuyordu.

Euler’in Yaptığı

Euler soruyu ele alırken köprü ve kara parçalarını iki ayrı gruba ayırmıştı. Euler’in zihninde köprüler 1’den 7’ye numaralandırılmış çizgiler, kara parçaları ise A-B-C-D harfleriyle isimlendirilmiş noktalardı. Bunları çizdiğimizde karşıya çıkan şekle graf denilir.

Euler çözümünü açıklamak için en baştan başlamış ve önce tanımlar yapmıştı. Ona göre Königsberg sorusunda yer alan köprülerin ve kara parçalarının fiziksel özellikleri sorunun çözümü için önem teşkil etmiyordu. Böylece soru grafa indirgendiğinde karşısında sadece gerekli bilgiler yer alıyordu. Königsberg sorusunda hangi kara parçaları arasında kaç tane köprü olduğu dışında önemli hiçbir bilgi yoktu.

Tanım: Bir noktaya bağlı olan çizgi sayısı, o noktanın derecesidir.

Euler’e göre bir grafta istenilen türde tur atılabilmesi için iki şart gerekir:

  1. Tüm grafta tam olarak iki tane noktanın derecesi tek ise. Bu iki noktadan biri turun başladığı yer, diğeri ise bittiği yer olur.
  2. Grafta bulunan tüm noktaların dereceleri çift ise. Böylece grafta turun atılabilmesi için istenilen noktadan başlanılabilir.

Neden?

Bir nokta başlangıç ya da bitiş noktası değilse, o noktaya gelen çizgi varsa noktadan çıkan çizgi de olmalıdır ki nokta son veya ilk duran olmasın. (Eğer bir çizgi gelen noktadan başka bir çizgi çıkmıyorsa, o nokta turun sonlandığı yerdir. Eğer bir çizgi çıkan bir noktaya tekrar bir çizgi gelmiyorsa, o halde o nokta turun başladığı yerdir.) Bu yüzden de noktanın derecesi çifttir. Fakat tek dereceli bir noktadan bahsediyorsak, o noktaya gelen çizgi varsa derecenin tek kalması için noktadan çıkan başka bir çizginin olmaması gerekir. Bu da tek dereceli noktaların ya başlangıç ya da bitiş olduğunu gösterir.

Bir grafta tek dereceli nokta yoksa, o grafta başlangıç ve bitiş noktası aynı nokta olabilir.

Euler Yolu: Bir graftaki tüm noktalar, grafta bulunan kenarlar bir ama sadece bir defa kullanılarak gezilebiliyorsa, bu grafta atılan tura Euler Yolu denir.

Basit Örnekler

  1. Tek Köprü: İki kara parçası arasında tek köprü olursa, graf aşağıdaki gibi olur.
    köpr
  2. İki Köprü: İki kara parçası arasında iki köprü olursa.
    Görsel 8
  3. Üç Kara Parçası: Eğer bir önceki duruma C kara parçası ve B-C arasına bir tane köprü eklenirse, graf aşağıdaki gibi olur.
    Görsel 7
    Bu durumda iki tane tek sayıda derecesi olan (B ve C) nokta vardır. Yani çözüm mümkündür ama başlangıç ve bitiş noktaları B-C noktaları olmalıdır. Kendiniz deneyerek görebilirsiniz.

Königsberg Çözümü

Euler’e göre Königsberg problemi aşağıdaki gibi graf haline getirilip çözülür.

Noktaların dereceleri sırayla 5, 3, 3, 3’tür. Yani Königsberg probleminde ikiden fazla tek sayıda dereceye sahip olan nokta vardır. Bu yüzden de problemin çözümü yoktur.

Topoloji: En basit haliyle deforme edildiğinde (kıvırmak, uzatmak, çekiştirmek gibi) özellikleri değişmeyen cisimlerin geometrik şekillerini inceleyen matematik dalıdır. (Bir cismin topolojik özelliği o cisim yırtılır ve/veya delinirse bozulur.) Örneğin bir çember ile bir elips topolojide aynı şeydir.

IMG_5281
Bir simit ile bir kahve kupası topolojide aynı şeyi ifade eder.

Bi’ Göz Atmakta Fayda Var

Aşağıdaki resimde bulunan objelerden hangileri topolojide aynı şeyi ifade eder?

IMG_5282

M. Serkan Kalaycıoğlu

 

Matematik Atölyesi: Bulmaca #2

Küçüklüğümde izlediğim filmlerden bir “en iyi 10” listesi yapsam Zor Ölüm (Die Hard) üçlemesindeki (dörtleme olduğunu biliyorum. Hatıralarımın bozulmasından korktuğum için 2007’de çıkan son filmi izlemedim.) filmlerin tamamı listeye girerdi.

Serinin üçüncü ve son (evet inat ediyorum) filminde çılgın Alman teröristimiz Simon Gruber, ana karakterlerimiz John McClane ve Zeus Carver’a bir bulmaca bırakmıştı. Film boyunca sosyopat teröristimiz Simon, McClane&Carver ikilisine acı çektirmeyi başarmıştı. İkilinin en zorda kaldığı anlardan biri olan bu bulmaca, tüm seride en sevdiğim sahnedir.

die-hard-vengeance-laptop

İlgili sahne için tıklayın… ya da önce soruyu kendiniz çözmeye çalışın, video bir yere kaçmıyor.

Simon diyor ki…

“Çantanın içinde zaman ayarlı bir bomba var. Bombayı durdurmak için tek şansınız 5 ve 3 litrelik su şişelerini kullanarak 4 litre su elde etmeniz. Eğer doldurduğunuz su tam 4 litre gelmezse çantadaki terazi bunu fark edecek ve geri sayım durmayacak.”

dayhard

Eğik Bilardo Masası

Bir önceki yazıda nokta ve çizgilerin bulmaca çözerken nasıl yardımcı olduğundan bahsetmiştim. Çok ilginç ama bu bulmacada da grafik çizerek hızlı bir şekilde sonuca ulaşılabiliyor. Önce uygulayacağımız yöntem için bazı kurallar koymamız gerekiyor.

Kurallar

  • Noktalar şişelerdeki su miktarını (litre bazında), çizgiler ise kazanılan&kaybedilen su miktarını göstersin.
  • Noktaları gösterirken sayı ikilileri kullanalım. İlk sayı 5 litrelik şişedeki miktarı, ikinci sayı 3 litrelik şişedeki miktarı ifade etsin.
  • Örneğin elimizdeki şişelerde hiç su olmaması (0,0) noktasıyla ifade edilir.
  • (1,2) noktası 5 litrelik şişede 1 litre, 3 litrelik şişede 2 litre su var anlamına gelir.

O halde grafiğimiz şu şekilde olur.

dayhard1

Sorunun Çözümü

Çizdiğim bu grafiğe eğik bilardo masası dememin bir nedeni var: Noktalar arası hareket tıpkı bir bilardo topunun masada yaptığı hareket gibidir. Bir yön seçeriz ve topu oraya doğru göndeririz. Doğal olarak top ancak masanın bir kenarına ulaştığında tam yansıma yaparak yoluna devam eder.

Örneğin (0,0) noktasından gidilebilecek iki yön vardır; (0,3) ya da (5,0). Biz topu (0,3) yönüne gönderirsek aradaki (0,1) ve (0,2) noktalarını geçmiş oluruz. Yansıma, doğrultu üzerindeki son nokta olan (0,3)’te gerçekleşir gelince ve top (3,3)’e doğru devam eder.

Çözüme başlarken önce 5 litrelik (bundan sonra büyük şişe diyelim) şişeyi dolduralım. Bu, (5,0) noktasından başlamak anlamına gelir. Büyük şişedeki suyun 3 litresini diğer şişeye dolduralım dersek, bu da topu (5,0) noktasından (2,3) noktası doğrultusuna doğru vurmak anlamına gelir.

dayhard2

Buradan itibaren top tam yansımayla (2,0) noktasına doğru gider.

(2,0) noktasına gelen top, (0,2)’ye doğru yansır. Oradan da (5,2) noktasına ilerler.

(5,2)’den yansıyan top, (4,3)’e doğru gider. Artık durabiliriz çünkü (4,3) noktası büyük şişede 4 litre su olduğunu ifade eder.

dayhard7

 

Yanda görülen yol, 4 litre suya ulaşmak için yapılması gerekenleri tek tek anlatır:

  • Büyük şişeyi doldur.
  • 3 litresini diğer şişeye boşalt.
  • Küçük şişeyi boşalt.
  • Büyük şişede kalan 2 litre suyu diğer şişeye dök.
  • 5 litrelik şişeyi doldur ve ondan küçük şişede kalan 1 litrelik boşluğa su dök.
  • Böylece büyük şişede 4, diğerinde 3 litre su kalmış olur.

 

Eğer John McClane ve Zeus Carver grafik çizmeyi bilseydi, bulmacayı çok daha kısa sürede çözerlerdi. Oturduğum yerden Zor Ölüm’deki ikiliyi eleştirmek kolay tabi ki. Çok iyi biliyorum ki gerçek bir bomba ile karşı karşıya kalan ben olsaydım, öbür dünyaya erken yaşta göç etmiştim.

Bi’ Göz Atmakta Fayda Var

Simon diyor ki…

  1. “4 litreyi elde etmek için ikinci bir yol daha var mı?”
  2. “1 dakika içinde bu iki şişeyle 1 litre su elde etmenin iki farklı yolunu bulun.”
  3. “6 ve 15 litrelik şişelerle 5 litre su elde etmek mümkün müdür? Her iki ihtimali de ispatla.”

M. Serkan Kalaycıoğlu

 

 

Matematik Atölyesi: Bulmaca #1

Nehir Geçme Bulmacası

Evine dönerken yanında bir kurt, bir keçi ve biraz da lahana bulunduran çiftçinin karşısına bir nehir çıkar. Nehrin kenarında gördüğü kayık çiftçinin her seferde kurt, keçi ya da lahanadan birini yanına almasına izin verecek büyüklüktedir.

Problem ise şudur: Eğer yalnız kalırlarsa kurt keçiyi, keçi ise lahanayı yiyecektir. Bu durumda çiftçi ne yapmalıdır? (Not: Nehrin karşısına yüzerek geçmek mümkün değildir.)

farmer-wolf-goat-cabbage

Cevap

keçiik

Bu üçlü arasında sadece kurt ile lahananın yalnız kalmasında sorun yoktur. O halde önce keçi karşıya geçilir.

lahank

Geri dönülür kurt veya lahanadan biri alınır. (Biz lahanayı aldığımızı düşünelim.) Lahana karşıya bırakılınca keçi ile yalnız kalmaması için keçi geri götürülür ve nehrin sol tarafına bırakılır.

kurtk

Bu sefer kurt kayığa alınır ve nehrin sağ tarafına götürülür. Böylece nehrin sağ tarafında kurt ile lahana kalmış olur ki bunda bir sorun yoktur.

hepsik

En son hamlede keçi karşıya geçirilir ve problem çözülmüş olur.

Bulmacada kurt yalnız kaldıklarında lahanayı da yiyor olsaydı, çözüm mümkün olmazdı. Fakat bunu anlayabilmek için tüm varyasyonları denememiz gerekecekti. Bu da boşa zaman ve enerji kaybı anlamına gelir. Yani bulmacada çözüme ulaşılmasına rağmen doğru bir yöntem bulmuş değiliz.

Peki bu tip bir soruyla uğraşırken işi kolaylaştıracak genel bir yöntem bulmak mümkün müdür?

Nehir Algoritması

Matematiğin görece yeni bir alanı olan çizge teorisinde bir cismin ne olduğu değil, nerede ve kimlerle bağlantılı olduğu önemlidir. Bu dalda noktalar cisimleri, çizgiler ise bağlantıları gösterir. O halde bulmacadaki keçi, kurt ve lahananın her birini nokta olarak gösterelim. Örneğin kurt yalnız kaldıkları takdirde keçiyi yediği için kurtla keçi arasında yeme ilişkisini ifade eden bir çizgi bulunsun.

Yani çizgilerle bağlanan noktalar bulmaca için tehlike arz eder. Çizilecek grafikte bir nokta ortadan kaybolduğunda, noktaya bağlı olan çizgiler de kaybolur.

bağlant

Bulmacaya göre her seferinde yanımıza üçlüden birini alabiliyoruz. Bunu yaparken hangisini seçeceğimize nokta-çizgi yöntemiyle şöyle karar veririz: Noktalardan hangisi kapatılırsa (o noktaya bağlı olan doğrular da kaybolacağı için) tüm grafikte çizgi kalmaz?

baglant

Eğer keçiyi gösteren nokta kapatılırsa, ona bağlı olan doğrular da yok sayılır. Geride sadece kurt ve lahanayı gösteren noktalar kaldığı için soruya buradan başlamak gerekir.

Yarattığımız algoritmanın bize söylediği başka bir şey daha var: Kayıkta en az silinen nokta sayısı kadar yer olmalıdır. Böylece çizilen grafik ne kadar karmaşık olursa olsun kayıkta yer durumuna bakarak sorunun çözümünün olup olmadığı hemen anlaşılabilir.

Peki nehir bulmacasındaki üçlüye bir de tavşan eklenirse ne olur?

İkinci Nehir Örneği

Diyelim ki çiftçinin yanındakiler kurt, keçi, lahana ve tavşan olsun. Yalnız kaldıkları takdirde keçi ve tavşanı kurt, lahanayı ise keçi ve tavşan yiyor. Bu durumda grafik şöyle olur:

dörtlü

Bulmacanın bir önceki versiyonunda sadece keçiyi gösteren noktayı kapamak grafikteki tüm çizgileri yok etmişti. Bu sefer dörtlünün her biri teker teker denenmesine rağmen hiçbir nokta tek başına grafikteki tüm çizgileri yok edemiyor.

  1. Tavşan noktası ve noktaya bağlı çizgiler kaldırılınca.
  2. Lahana noktası ve noktaya bağlı çizgiler kaldırılınca.
  3. Keçi noktası ve noktaya bağlı çizgiler kaldırılınca.
  4. Kurt noktası ve noktaya bağlı çizgiler kaldırılınca.

O halde iki noktayı kaldırmayı denemeliyiz. Örneğin;

dörtlü5

tavşan ve keçi noktaları ile noktalara bağlı çizgiler kaldırılınca grafik bu hale geliyor. Yani sonuca ulaşmak için ilk adımı başarıp kayıkta kaç kişilik yer olması gerektiğini bulduk: Kayıkta en az iki kişilik yer olunca bulmaca çözülebilir.

Başta basit bir bulmaca gibi görünen nehirden karşıya geçme sorusunu çizge teorisiyle birleştirince karşımıza önce grafikler çıktı. Bu grafikleri düşünerek bir algoritma yazdık ve karmaşık durumları hızlıca çözme yolunun nereden geçtiğini öğrenmiş olduk.

Bi’ Göz Atmakta Fayda Var

  1. Kurt-keçi-lahana-tavşan sorusunu çözün.
  2. Kurt-keçi-lahana-tavşan dörtlüsünün yanına havuç, kedi ve fare üçlüsünü ekleyelim. Havucu keçi, tavşan ve farenin, fareyi ise sadece kedinin yediğini varsayalım. Bu durumda her şeyi nehrin öteki tarafına geçirebilmek için kayığın boyutu en az kaç kişilik olmalıdır?

M. Serkan Kalaycıoğlu