Real MATHEMATICS – Graphs #4

I visited the world famous Hermitage museum in Saint Petersburg (Russia) back in 2014. Hermitage is so huge that it has 1057 rooms and one would have to walk around 22 km to see all the rooms. And numbers of artistic & historical items are not that shallow either: It is believe that it would take a little over 11 years if one would spare 1 minute for each piece of art.

Now you can relate why I had trouble when I wanted to visit Hermitage for a few hours. I didn’t have enough time and I wanted to see important art works such as the Dessert: Harmony in Red by Henri Matisse. Eventually I realized that this is a problem I had faced before.

Actually, each and every one of you must have faced such problems in your daily lives. Most common one: “Which route you should take between home and work during rush hour traffic?”

Postman’s Path

Facing such problem in Saint Petersburg is a pleasing coincidence as this magnificent city once was home to one of the giants of mathematics: Leonhard Euler. If you take a look at the first article of graphs you can see that Euler is the person who initiated the discovery of Graph Theory with his solution to the famous Seven Bridges of Königsberg problem.

In 1960 (almost 230 years after the solution of Königsberg) a Chinese mathematician named Mei-Ko Kwan took a similar problem into his hands:

A postman has to deliver letters to a given neighborhood. He needs to walk through all the streets in the neighborhood and back to the post-office. How can he design his route so that he walks the shortest distance?

This problem is given the name Chinese Postman Problem as an appreciation to Kwan. There are a few things you should know about the postman problem:

• Postman must walk each street once.
• Start and finish point must be at the post-office.
• Postman must fulfill these two conditions in the shortest possible time.

Power of Graphs

Mei-Ko Kwan turned to Euler’s Königsberg solution in order to solve the postman problem. According to Kwan postman problem could have been shown as a graph: Lines represent the streets and letters represent the houses.

Example Graph:

A graph has an Euler circuit if and only if the degree of every vertex is even. In other words, for each vertex (point) count the number of edges (lines) it has. If that number is even for each vertex, then it is safe to say that our graph has an Euler circuit.

Solution

As you can see above, if the degree of every vertex in a graph is even, then we can conclude that the graph has an Euler circuit. Let’s assume that the following is our graph:

First of all we must determine the degree of each vertex:

As seen above all the vertices have even degrees. This is how we can conclude that the graph has an Euler circuit even without trying to find the path itself. Hence the postman can use the existent roads and finish his route in the shortest time:

When a graph has vertices with odd degrees, then we must add new line(s) to the graph in order to create an Euler circuit. These are the steps you can follow:

1. Find the vertices that have odd degrees.
2. Split these vertices into pairs.
3. Find the distance for each pair and compare them. The shortest pair(s) shows where to add new line(s).
4. Add the line(s) to the graph.

Let’s use an example and test Kwan’s algorithm for the solution. Assume that A is the starting point. First we must check the degrees of the vertices:

Unfortunately A and D have odd degrees which is why the postman can’t finish his walk:

Here we have only one pair that is A-D. There are three routes between A-D. If we find the shortest one and add that to our graph, we will have an Euler circuit:

The shortest one is the line between A-D as seen above. If we add that line, we will have the shortest route for the postman:

One wonders…

If the post office is at A, what is the route for the postman to take so that he will finish his day in the shortest way?

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.

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?

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:

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:

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

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:

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:

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:

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:

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?

M. Serkan Kalaycıoğlu

Real Mathematics – Geometry #17

Why do we have round wheels in cars and bicycles?

Square Wheels

Let’s construct a square wheel like the following and test if it can be used as an efficient wheel:

After turning the squared-wheel 45 degrees the square will look like the one on the right:

At this position it is clear even to the naked eye that the height of the wheel is taller comparing to its original state. If we continue turning the wheel for another 45 degrees it goes back to its original position.

Squared-wheel has big disadvantages. A car or a bicycle with squared-wheels will be doomed as height of the vehicle constantly changes.

Triangle Wheels

Among the triangles equilateral is the best one for constructing a wheel as all of its sides have equal length:

After turning the triangular-wheel 60 degrees to the left, it will have the same height:

Although let’s go 30 degrees back and examine the height of the wheel:

Here height of the wheel is clearly taller than the height of the original state. This proves that it is not appropriate to construct a triangular-wheel on a vehicle. Otherwise you might have problems with your spine.

Power of the Circle

The reason why circle is the most powerful and convenient shape for our vehicles is that neither of its height nor width changes while rotating. This separates circle from all the other polygons and makes it the best shape for wheels.

Nonetheless, one wonders if circle is the only possible shape for wheels.

Reuleaux Triangle

Leonardo da Vinci is one of those names that appear in your mind when someone mentions Renaissance. The relationship between this magnificent figure and Reuleaux triangle comes from a world map that was found inside his pupil Francesco Melzi’s notes:

This is known as one of the very first maps that included America. It is believe that this 1514-dated drawing was due to Leonardo da Vinci. If this is true, then it is safe to assume that da Vinci was the first person ever who used the Reuleaux triangle.

It was Leonhard Euler whom discovered the shape and explained it mathematically almost 200 years after da Vinci’s map. You probably realized this from my articles: “It is either Euler or Gauss.”

How come it is called Reuleaux? Because a century after Euler, a German engineer named Franz Reuleaux discovered a machine using Reuleaux triangle. In 1861 Franz Reuleaux wrote a book that made him famous and today he is known as the father of kinematics.

How to Construct Reuleaux Triangle?

I will show you my favorite method for its construction using three identical circles. First draw a circle that has radius r:

Then pick a point on that circle as a center and draw a second circle again with radius r:

At last, pick one of the crossings of the circles as center and draw a third circle with radius r:

The central area of these three circles is a Reuleaux triangle:

When a Reuleaux triangle is rotating, it will have the same height at all times just like the circle:

One wonders…

1. Using Euclid’s tools (a compass and an unmarked ruler) draw an equilateral triangle.
2. Try to construct Reuleaux triangle with on the equilateral triangle.
3. Can you contruct Reuleaux polygon(s) other than the triangle?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Geometri #17

Neden araba ve bisikletlerde kullanılan tekerlekler yuvarlaktır?

Kare Tekerler

Deneme-yanılma ile neden bu şekilden taşıtlara tekerlek yapılamayacağını görelim. Diyelim ki tekerlekler aşağıdaki gibi kare şekilde olsun:

Karelerin 45 derece döndükten sonraki hali sağdaki gibidir:

İlk duruma göre karenin yüksekliği değişmiştir. Bir 45 derece sonraysa yükseklik ilk duruma gelir.

Kare tekerleğin zaafı büyüktür. Tekerler döndükçe taşıtın yüksekliği sürekli olarak değişir (yükselip-alçalır).

Üçgen Tekerler

Üçgen çeşitleri için tüm kenarları birbirine eşit olanı (yani eşkenar üçgen) tekerlek yapmak için en uygun şekil olarak görülür.

Elimizde aşağıdaki gibi bir eşkenar üçgen tekerlek olsun:

Sola doğru 60 derece çevirince eşkenar üçgen tekerleğin durumu:

Görüldüğü üzere tekerleğin yüksekliği değişmemiştir. Yoksa eşkenar üçgenden tekerlek elde edilebilir mi? Gelin bir de ilk durumdan 30 derece sola çevirdikten sonraki durumu inceleyelim:

Görüldüğü üzere yükseklik ilk duruma göre artıyor. Yani eşkenar üçgenden de tekerlek yapmak uygun olmaz. Bu tür tekerlekler üzerinde yapılan yolculuklar sonrasında sakatlanmanız olasıdır.

Çemberin Gücü

Çember şeklinde tekerleğin kullanılma nedeni çemberin yüksekliğinin dönerken hiç değişmemesinden gelir. Bu yönden çemberin şekli kare ve üçgen gibi çokgenlerden farklıdır.

Yuvarlak dışında bir şekilden tekerlek yapılamaz mı?

Reuleaux Üçgeni

Rönesans denilince akla gelen ilk isimlerden biri Leonardo da Vinci’dir. Bu muhteşem şahsiyetin Reuleaux üçgeni ile ilişkisi ise da Vinci’nin öğrencisi Francesco Melzi’nin notlarının arasında bulunan bir dünya haritasından gelir:

1514 civarında yapıldığı düşünülen bu dünya haritası Amerika kıtasını barındıran ilk haritalardan biri olarak bilinir. Bu haritanın Leonardo da Vinci tarafından çizildiği düşünülür. Eğer bu doğruysa da Vinci’nin Reuleaux üçgenini kullanan ilk kişi olduğu varsayımı haksız bir varsayım olmaz.

Reuleaux üçgenini ilk kez keşfeden ve onun matematiksel özelliklerini açıklayan kişiyse Euler’di. Artık yazılardan şunu anlamış olmanız gerekiyor: “Ya Euler’dir ya da Gauss.”

Reuleaux üçgeni ismini Alman mühendis Franz Reuleaux’dan alır. 1861’de yazdığı kitapla meşhur olan, daha sonra yaptığı çalışmalarla “kinematiğin babası” unvanını hak etmiştir.

Reuleaux Üçgeni Nasıl Oluşturulur?

Şahsen en sevdiğim yöntem üç tane çemberin kesişimiyle oluşturmaktır. Öncelikle r yarıçaplı bir çember çizelim:

Daha sonra merkezi bu çemberin üzerinde olan bir başka r yarıçaplı çember çizelim:

En son olarak iki çemberin kesişim noktalarından birini seçip onu merkez kabul ederek r yarıçaplı üçüncü bir çember daha çizelim:

Bu üç çemberin kesişerek ortada oluşturduğu şekil Reuleaux üçgenidir:

Reuleaux üçgeni döndürüldüğünde tıpkı çemberde olduğu gibi yüksekliği hep aynı kalır:

Bi’ Göz Atmakta Fayda Var

1. Öklid’in aletlerini (sadece pergel ve ölçüsüz cetvel) kullanarak eşkenar üçgen çizin.
2. Çizdiğiniz eşkenar üçgenden Reuleaux üçgeni elde etmeye çalışın.
3. Üçten fazla kenarı olan Reuleaux şekli çizilebilir mi?

M. Serkan Kalaycıoğlu

Real Mathematics – Life vs. Maths #1

Circle-Match Relationship

Mathematics is a language we use to explain the event that occur in nature. Mathematicians (good ones though) are in a way masters of this language. They possess crucial abilities such as seeing things others can’t see and finding connections between things that seem unrelated with one another.

Contrary to popular belief “knowing mathematics” doesn’t only mean knowing how to make calculations or being good with numbers. A mathematician ought to point out and explain the relationship, symmetry and pattern… In places you wouldn’t even imagine mathematics could exist!

For instance it is possible to use mathematics and find a connection between a circle and a match.

Circle

Let me start with circle. Any straight line segment that passes through the center of the circle with its endpoints lie on the circle is called a diameter of the circle. And in any circle the shortest distance between its center and boundary is called a radius of the circle. A radius is half the length of a diameter.

To draw a circle with a compass is not that hard. Distance of the openness of the compass gives the radius. If one opens a compass with 3 cm, he/she will draw a center that has radius 3.

Circumference of the circle above is roughly 18,85 cm. Let’s use a calculator to find the relationship between the diameter and circumference of this circle.

18,85/6=3,141666666…

Now let me use a cup. This cup’s mouth is in a circle shape and its circumference is about 25,8 cm.

Its diameter is about 8,2 cm. Now let’s divide the circumference with its diameter:

25,8/8,2=3,14634146…

In both examples ratio of circumference of a circle to its diameter is roughly 3,14. This is not a coincidence; humans realized this connection more than 4000 years ago.

Brief History of the Mysterious Number

2000 BC: Humans thought that this ratio as 3. According to the Rhind papyrus from ancient Egypt it was 3,16045.

250 BC: Ancient Greek Archimedes calculated this ratio’s average as 3,1418.

800 BC: Al-Khwarizmi calculated the ratio as 3,1416 which was a better approximation than Archimedes’.

Mathematicians didn’t stop attempts for thousands of years. In 1874 William Shanks found the first 707 digits of this ratio. Unfortunately he made a mistake on the 528th digit. Nevertheless it was a huge accomplishment to find this ratio’s first 527 digits correctly.

In 1949 computers took over the mission. A computer found this ratio’s first 2000 digits correctly.

I tried it find if I could find the number “1907” (the year when my favorite team was founded) inside those 2000 digits. It was a success.

In the 18th century Leonhard Euler who is known as one of the greatest mathematicians of all times gave this ratio its name and symbol: π.

Transcendental

In 1882 a German scientist named Ferdinand von Lindemann proved that the number π is transcendental.

According to great German philosopher Immanuel Kant a transcendental knowledge is not real; it exists only in our minds. Majority of the mathematicians agree that this word defines the number π perfectly.

In other words the number π can’t be shown as the ratio of any two rational numbers.

Also in the decimal presentation of the number π continues without any repetition… Forever!

This means that every number combination can be found inside the number π. From your birthday to your elementary school number, everything is inside the number π. All you need to do is to continue calculating its digits.

This website is created by Wolfram. Using its searching engine you can find at what digit your birthday sits inside the number π.

I checked Leonhard Euler’s birthday and found the following:

Try and see yourself. It is astonishing to see your birthday inside the number π.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Garip Dünyalar #1

Euler Karakteristiği

• Boş bir kağıt parçasına noktalar yerleştirin.
• Noktalar arasına istediğiniz kadar çizgi koyun.
• Çizgiler birbirini kesmemeli.
• Kağıtta bulunan noktaların her biri birbirine çizgilerle direk ve dolaylı olarak bağlanmış olmalı. Diğer bir deyişle herhangi bir noktadan diğerine çizgilerden bir yol olmalıdır.
• Böylece şekilde “yüz” oluşturulur. Yüzler çizgilerle kapanmış alanlardır.
• Çizgi ve noktaların dışında kalan alan da bir yüz olarak sayılır. Yani bir düzlemde en az bir tane yüz vardır.
• Her zaman:
Nokta Sayısı – Çizgi Sayısı + Yüz Sayısı = 2
olur. Buna Euler’in çokyüzlü formülü denir.

Örnek 1: Üç Nokta

Üç nokta konulur ve aralara çizgiler çekilir.

Oluşturulan yüzler şu şekildedir.

Euler formülü uygulanır.

Örnek 2: Dört Nokta

Noktalar şekildeki gibi birleştirilir.

Toplam üç yüz, dört nokta ve beş çizgi vardır. Buradan Euler formülü bize aşağıdaki sonucu verir.

Örnek 3: Beş Nokta

Beş nokta, yedi çizgi ve dört yüz elde edilmiş olan şekil aşağıdaki gibidir.

Peki bu şekle bir nokta daha eklersek ne olur?

Yeni eklenen F noktasından üç çizgi ve iki yeni yüz çıkardık. Sanki Euler formülü bu sefer tutmayacak gibi!

Ama sonuç yine Euler’i haklı çıkarır. Altı nokta, on çizgi ve altı yüz bulunduran şeklimize Euler formülü uygulanınca cevap yine ikidir.

Örnek 4: Beş Nokta ve Sıfır Yüz

Her seferinde neden çizgilerle kapalı alan yapıyoruz diyebilirsiniz. Yani hiç yüz yapmadan noktaları birleştirirsek ne olur? (Biliyoruz ki her düzlemde nokta ve çizgilerin dışı bir yüz olarak kabul edilir. Bu nedenle her düzlemde en az bir tane yüz olur.)

O halde beş noktayı şekildeki gibi dört çizgiyle birleştirelim. Sonuçta Euler’in kuralına göre herhangi bir noktadan diğerine gidilebiliyor. Ayrıca birbiriyle kesişen çizgiler de yok.

Burada Euler formülü uygulanınca beş nokta, dört çizgi ve bir yüz vardır. Formül yine doğrudur.

Tarih Sevenler İçin

Şu ana dek okuduğunuz yazılarda iki isimden sıklıkla bahsettim: Leonhard Euler ve Öklid.

Öklid, okul geometrisi diyebileceğim (gerçek isimlerinden birisi Öklid geometrisidir) iki ve üç boyutlu geometrinin kaynağı olan kitapların yazarıdır. Euler ise 800’ün üzerinde çalışmasıyla tarihin en verimli matematikçilerinden biridir.

Öklid’in 13 kitaptan oluşan Elementler’i milattan önce 200’lerde yazılmıştı. Binlerce yıl boyunca sayısız bilim insanı Öklid’in kitaplarıyla sadece geometriyi değil matematiği öğrenmişti. Modern bilimi başlatan kişi olan bilinen, aynı zamanda modern fiziğin babası olan Isaac Newton dahil tüm bilim insanları Öklid ile matematiğe giriş yapıyordu.

Elementler yazıldıktan 2000 yıl sonra dahi geometriyle ilgili her şeyi içerdiğine inanılıyordu. Hatta 18. yüzyılda yaşamış olan tarihin en önemli filozoflarından Immanuel Kant, Öklid dışı bir geometrinin varlığını düşünmenin bile anlamsız olduğunu savunmuştu. Kant’ın özellikle Almanya’da bilim dünyasında sahip olduğu etki, Gauss gibi tarihin en iyi/büyük matematikçisi olarak görülen bir bilim insanını dahi bastırmıştı. Gauss’un başrol oynadığı bu konuyla ilgili başka bir yazım olacak.

İşte Euler, her şeyi bulunduğu düşünülen geometri konusuna çok önemli katkılarda bulunmuştu. Euler’in ismine atfedilen bir sürü formül vardır. Fakat kanımca tarihin en sade ve en güzel formülü budur.

Bi’ Göz Atmakta Fayda Var

Peki Euler formülü üç boyutlu şekillerde işe yarar mı? Örneğin bir küreyi ele alın. Bu küre üzerinde iki nokta alın ve bu noktaları birleştirin. Karşınıza ne çıktı?

Aynı kürede üçüncü bir nokta alın ve bunu diğer iki noktayla birleştirin. Sonuç ne oldu?

M. Serkan Kalaycıoğlu

Real Mathematics: Graphs #2

You’ve been sent for scouting a forest nearby your village. You are done with your duty and on your way back home you are bringing a wolf, a goat and some cabbage with you. Wolf would like a piece of goat and goat is looking hostile against the cabbage, but they can’t do anything with your presence. Then you come across with a deep river. Luckily for you, there is a small boat on coast.

The Catch: Boat is so small it allows you to take only either one of wolf, goat or cabbage. Is there any way you can take everything to the other side of the river safely?

Solving Puzzles with Graphs

In the previous article I told you how Euler used a brand new approach to a seemingly insignificant puzzle and how his method became the basis of graph theory. Drawing graphs in certain cases really improve the chances of reaching an answer. Graphs also help us understand why there is not a solution, in case problem has no solution. Graphs are so powerful at times they can even show us what kinds of conditions are needed to solve a problem that has no solution.

In the river problem, let’s use Euler’s methods. You are all on the left side of the river and you have to get across the right side of it. Now assume that left side of the river is assigned as position 1, and right side as position 2.

There are wolf, goat and cabbage. In the puzzle, those three stand on the position 1 which might be shown as a point named 111 (wolf-goat-cabbage on the positions 1-1-1). Ultimate goal of the puzzle is to find a way to get them all to the point 222.

There are eight different positions for the wolf, goat and cabbage: 111, 112, 121, 122, 211, 212, 221 and 222. For instance 112 means wolf is at position 1 (left side of the river), goat is at position 1 (left side of the river) and cabbage is at position 2 (right side of the river).

Drawing the Graph

We assumed that all these 3-digit numbers represent a point. To get from one point to another, we could only change exactly one digit of it, as we are allowed to take exactly one of wolf, goat or cabbage into our boat. Then there are limited ways to go from one point to another. Let’s assume that if you can go from one point to another, then there is a line connecting those two points.

For instance 111 and 112 has a connection as there is exactly one digit that differ those numbers. Although 111 and 212 has no connection as there are more than one digit that differ those numbers.

Finally we found our points and lines and how they could be drawn as a graph. I think Euler would be proud of us.

Our starting point 111 has three options: 112, 121, 211. Our graph looks like following when all relationships between points are shown:

As our ambition is to reach point 222 from the point 111, it is easy to see the ways to the solution in the graph. However we can’t move between points as we’d like to. We can only use paths which satisfy puzzle’s rules: If they are left alone, wolf eats goat and goat eats cabbage.

Solution

The point 111 has three options: 112, 121 and 211. If we select 112 (taking cabbage to the right side) wolf and goat would be alone, so this path is not good for us. The point 211 would mean leaving goat with cabbage which is forbidden as well. Hence there is only one way to select from the point 111: The path to the point 121.

The point 121 has three options: 111, 122 and 221. We can’t go back, so the point 111 is out. We should choose either 122 or 221.

Choosing 122

This would mean that we are taking cabbage to the right side of the river, near the goat. There are again three options: 121, 222 or 112. We can’t go backwards, so the point 121 is out.

222: Choosing this path would give us the answer. But, in order to do that we must leave goat and cabbage alone and go get wolf. Until we are back to the right side of the river, goat would be doing its final chewing. Hence, we can’t choose this path.

112: This is the only real option we can choose.

From 112, there are again three options: 122, 212 and 111. We can’t go backwards, so the points 122 and 111 are out. Path to the point 212 is the only choice.

At the point 212, wolf and cabbage are on the right side of the river and goat is on the left side. Here, we can go to the left side, pick goat with us and reach the point 222. This would give us the solution we were looking for.

Choosing 221

Now go back and choose the path to the point 221. There are again three options from 221: 222, 211 and 121. We can’t choose the point 121 as it would mean going backwards. Going to the point 222 would solve all our problems, but if we try to do that, we would have to leave wolf and goat alone at the position 2. This gives us the option 211.

The point 211 also gives us three options: 111, 221 and 212. Choosing 111 and 221 would mean going backwards. Then we must follow the path to 212. From the point 212, we can directly choose the path to the point 222. And we would again find the solution within the lines of the rules of the puzzle.

Check It Out

Add other animals and vegetables to these three and try to draw the graph. Using the graph, see if you can find a solution to your puzzle.

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).

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:

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.
2. İki Köprü: İki kara parçası arasında iki köprü olursa.
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.

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.

Bi’ Göz Atmakta Fayda Var

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

M. Serkan Kalaycıoğlu

Real Mathematics: Graphs #1

Puzzles and mathematics have a deeper relationship than one might assume. When you take a look at history of mathematics, it is not that rare to see a puzzle causing mathematics to change.

Without a doubt, Seven Bridges of Königsberg (1736) is the most famous one of those stories.

Leonhard Euler, one of the most influential mathematicians of all times, was given this puzzle/problem in the 18th century. Euler had a great reputation for solving “unsolvable” questions, and major of Königsberg asked for his help. Euler was not pleased to receive this problem at first as he said “… I don’t believe this question has anything to do with mathematics.” Although after some time he believed that the problem was interesting enough to deal with.

Euler’s solution to Seven Bridges of Königsberg problem culminated a couple brand new mathematics branches to emerge: Topology and graph theory. What fascinates me about this story is that these branches came out almost 150 years after Euler’s solution.

Seven Bridges of Königsberg

Take any book on graph theory. Open first chapter’s first title. You’ll see Euler’s solution for this simple problem:

The old town of Königsberg has seven bridges as shown on the map. Is it possible to take a walk through the town, visiting each part of the town and crossing each bridge once and only once?

I encountered with this problem for the first time in the junior year of my math major. I first thought that the question was dull and I could solve it with ease. After spending a night with full of disappointments and a lot of cursing, I gave up. I knew that it was impossible to take that walk and I knew that it was possible when I removed one bridge. But I didn’t know why.

Soon enough, I realized that I needed fundamentals of the graph theory to understand the answer. Euler’s solution to this simple puzzle is the basis of a whole new mathematics branch: Graph theory.

What Euler Did

First thing Euler did was to imagine that bridges and lands as two different groups. According to him, solution of Königsberg problem didn’t depend on the physical appearances of them. Euler realized that it didn’t matter how long or curvy a bridge is, or if a land is an island or not.

He just thought that bridges could be represented as edges numbered from 1 to 7, and lands could be represented as vertices named A,B,C and D. When all Königsberg problem map is put into a piece of paper with using on edges and vertices, we would end up with a graph.

Degree of a vertex is the number of edges it has.

According to Euler, in order to find a solution for Königsberg problem either of these should be found in the graph:

1. Exactly two vertices should have odd number of degrees. That would mean one of the vertices is the start of the tour as the other is the finish.
2. All of the vertices should have even number of degrees. That would mean one could start the tour from any vertex.

Why?

If a vertex is neither start nor finish of the tour, then in case one edge comes to that vertex another one should leave so that the vertex would be neither the start nor the finish. (Because if an edge comes to a vertex and another doesn’t leave, it means that vertex is the finish of the tour. And if an edge leaves from a vertex but another doesn’t come back to it, then it means that vertex is the start of the tour.) This would mean that the vertex should have even number of degree. Although, if vertex has odd number of edges, in order to keep odd degree we shouldn’t let another edge to leave in case there is an edge coming to that vertex. This would mean that the so called vertex is either start or finish of the tour.

Also, if there are no vertices in the graph with an odd degree, then a chosen vertex could well be both start and finish of the tour.

Eulerian Path: If a path/tour in a graph contains each edge of the graph once and only once, then that path is called Eulerian Path.

I am aware that the paragraph above is a bit confusing. Let me give you a few examples to clear your mind about degree of a vertex.

Examples:

1. One Bridge: Two lands and one bridge graph.
2. Two Bridges: Two lands and two bridges graph.
3. Three Lands: Add land C into the previous graph.

In this case there are two vertices with odd number of degrees. Hence, there is a solution for this graph but vertices B and C should be the start and finish of the path.

Solution to Königsberg

Euler saw the Seven Bridges of Königsberg as this graph.

Numbers of degrees for the vertices are 5, 3, 3 and 3 in order. This means that the Königsberg graph has more than two odd numbers of vertices which is a violation for the rule. This is concludes that there is no such tour/path for the seven bridges of Königsberg.

Topology is the mathematical study of the properties that are preserved through twisting and stretching of objects. (Tearing, however, is not included.) Topologically a circle and an ellipse are equivalent to each other.

Check it out

Which objects are topologically equivalent to each other ?