Matematik Atölyesi – Graf #7

Serkan Hocanın Sistemi

Serkan hoca öğrencilerine her hafta belli sayıda soru verir. Bu sorulardan bir veya daha fazlasını çözen öğrenciler, çözdükleri soruların karşılığında bir ödül alır. Ödülü belirlemek için her dönem başında Serkan hoca ile sınıfları arasında bir anlaşma yapılır. Bu dönem için yapılan anlaşmaya göre ödül olarak oreo dağıtılacaktır:

10 soru verilirse:

  • 10, 9 ve 8’ini yapanlar 10 oreo,
  • 7, 6 ve 5’ini yapanlar 5 oreo,
  • 4, 3 ve 2’sinin yapanlar 2 oreo,
  • 1’ini yapanlar 1 oreo,
  • Hiç soru yapmayanlar ise oreo almayacaktır.

Dikkat edenler Serkan hocanın oreo ödüllerinin bir mantığı olduğunu anlamıştır: 10, 5, 2 ve 1.

Bunlar, soru sayısını (yani 10’u) kalansız bölen doğal sayılardır.

Ödül Dağıtım Makinesi (Ö.D.M.)

1 ay sonra…

Ödül sistemi başlayalı 4 hafta geçmişken Serkan hoca önemli bir sorunla karşı karşıya kalmıştı. Toplam 10 sınıfı olan Serkan hoca, her hafta birkaç saatini ödül dağıtmakla geçirmişti.

Neredeyse okuldaki tüm boş vaktini oreo dağıtmakla geçiren Serkan hoca, ödül dağıtımını kolayca halletmek için bir makine tasarlamayı düşünür:

  • Ö.D.M. 4 hazneden oluşacak. (10, 5, 2, ve 1’den dolayı.)
  • Haznelerin sırasıyla 10, 5, 2 ve 1 oreoluk kapasitesi olacak.
  • Makineye oreo girişi 10’luk hazneden olacak. Kurulan bağlantılarla diğer haznelere buradan oreo aktarılacak.
  • Altın Kural: Herhangi iki hazne arasında bağlantı olması için bu iki haznenin kapasiteleri birbirine kalansız bölünebiliyor olmalı.

10 soru için Ö.D.M. bağlantıları:

  • 10’luk hazne ile 5, 2 ve 1’likler arasında.
  • 5’lik hazne ile 10 ve 1’likler arasında.
  • 2’lik hazne ile 10 ve 1’likler arasında.
  • 1’lik hazne ile 10, 5 ve 2’likler arasında.

O halde Ö.D.M.’nin krokisi aşağıdaki gibi olur:

Yine mi graf?!

Graf teorisiyle tanışıklığınız varsa (veya blogda yer alan graf yazılarını okuduysanız), Serkan hocanın yarattığı sistemin aslında bir tür düzlemsel graf olduğunu fark etmişsinizdir:

10 soruluk Ö.D.M.’nin graf olarak gösterimi.

Birbirine kalansız bölünebilen sayılar (yani noktalar) arasında düzlemselliği bozmayacak şekilde (yani birbirini kesmeyecek şekilde) bağlantılar (yani çizgiler) çekilir.

Bi’ Göz Atmakta Fayda Var

Peki Serkan hoca soru sayısını değiştirip 12 yaparsa ne olur?

12 soru için ödüller 12’yi kalansız bölen doğal sayılardır: 12, 6, 4, 3, 2 ve 1.

Bu durumda Serkan hoca makinesini kurabilir mi? Bir diğer değişle 12’lik Ö.D.M. için bağlantılar (birbirini kesmeyecek şekilde) yerleştirilebilir mi?

Örnek dizilim.

İpucu: Önce hangi noktalar arasında çizgi çekilmeli ona bakın. Ayrıca noktalar istenilen şekilde dizilebilir.

M. Serkan Kalaycıoğlu

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 #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 – 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