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:
Bu durumda Serkan I’in iki çocuğunun olması yeterlidir:
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:
Bu haritaya bir arsa daha ekleyelim:
Eklenen arsa graf için yeni nokta ve çizgi(ler) anlamına gelir:
Harita #2
Yeni haritada üç arsa bulunsun:
Bu haritayı graf haline getirelim:
Grafta da görüldüğü üzere mirasın dağıtılabilmesi için Serkan I’in üç çocuğu olmalıdır:
Harita #3
Üçüncü harita aşağıdaki gibidir:
Bu dört arsanın kurallara uygun dağıtılması için miras dört çocuğa dağıtılmalıdır:
Harita #3’teki durum graf olarak aşağıdaki gibidir:
Harita #4
Serkan I’in bıraktığı arsaların aslında ABD haritasıyla aynı olduğunu varsayalım:
Bu haritayı paylaştırmak için Serkan I’in sadece dört çocuğunun olması yeterlidir:
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
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
kmatematikatolyesi.com 