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

 

Real MATHEMATICS – Graphs #6

Bequeath Problem

King Serkan I decides to allocate his lands to his children. Obviously he had set up some ground rules for the allocation:

  • Each child will get at least one land.
  • Same child can’t have adjacent lands.

Problem: At least how many children should Serkan I has so that allocation can be done without a problem?

Map #1

Let’s start from a simple map:

20190423_000256.jpg

In this case Serkan I can have two children:

20190423_000310.jpg

As you can remember from the previous article a map and a graph is irreversible. If we represent lands with dots, and let two dots be connected with a line if they are adjacent, we can show maps as graphs:

20190423_000334.jpg

Let’s add another land to this map:

20190423_000402.jpg

Adding a land on a map is the same thing as adding a dot on a graph:

20190423_000507.jpg

Map #2

Let’s assume there are three lands on a map:

20190423_000523.jpg

We can convert this map into graph as follows:

20190423_000537.jpg

As seen above, three children are needed in order to fulfill Serkan I’s rules:

20190423_000553.jpg

Map #3

Let the third map be the following:

20190423_000627.jpg

According to Serkan I’s rules, we will need four children for such map:

20190423_000642.jpg

Map #3 can be shown as a graph like the following:

20190423_000728.jpg

Map #4

For the final map, let’s assume Serkan I left a map that looks like USA’s map:

480271690e1e0485f71988e273730559

Surprisingly four children are enough in order to allocate the lands on the map of USA:

amarikaaa

What is going on?

Careful readers already noticed that adding a dot that connects the other dots in the second map’s graph gives the graph of the third map. Same thing is true for the first and second maps:

Hence, adding a new dot to the graph means adding a new child.

Q: Is it possible to create a map that requires at least five children?

In other words: Is it possible to add a fifth dot to the graph so that it has connection to all existing four dots? (Ps: There can be no crossing in a graph as our maps are planar.)

Then, all we have to do is to add that fifth dot… Nevertheless I can’t seem to do it. When I add the fifth dot outside of the following graph:

It is impossible to connect 1 and 5 without crossing another line. No matter what I try, I can’t do it:

Four Color Theorem

About 160 years ago Francis Guthrie was thinking about coloring maps:

“Can the areas on any map be colored with at most four colors such that no pair of neighboring areas get the same color?”

Incredibly the answer is yes.

This simple problem was introduced for the first time by Francis Guthrie in 1852. Not until 1976 there was no proof for Guthrie’s conjecture. Only then with the help of computers the conjecture was proved. This proof is crucial for mathematics world as it is known as the mathematical theorem that was proven with the help of computers.

One wonders…

20190423_003916.jpg

Add a fourth dot to the graph you see above and connect that dot to the existing dots. (You are free to place the fourth dot wherever you want on the graph.)

Now check your graph: One of those four dots is trapped inside the lines, isn’t it?

Can you fix that?

Explain how you can/can’t do it.

M. Serkan Kalaycıoğlu