Real MATHEMATICS – Graphs #5

Cruel Traffic Light

I have to drive past the same crossroad almost every single day. Obviously I stop at the longest-lasting traffic light of the crossroad. Within time I started loving these moments because it gave me a chance to think my life over. Though, it doesn’t take too long for me to start thinking about mathematics.

One of those days I found myself questioning the traffic lights and their relationship with mathematics. (After all mathematics is everywhere; isn’t it?) Soon after I realized that there was my beloved graph theory behind traffic lights.

Light #1

Let’s assume a one-way street with two traffic lights: One for the vehicles (we’ll call it A), other for the pedestrians (we’ll call it B):

20190419_014641.jpg

In such situation we have to avoid accidents. This means whenever A has green light, B must have red light and vice versa. We will not take account of the situation when both lights are red. Because even though there won’t be any accident, neither of the sides will be standing still (which is nonsense):

20190419_014737.jpg

All these can be shown using graph theory: Lights will be represented by dots. Dots in a graph will be connected with lines if they are not in the same color:

20190419_014752.jpg

Same thing can be shown with maps: If A and B are two neighboring countries, they should be colored in different colors to avoid confusion:

20190419_014817.jpg

Light #2

This time we will assume a two-way street with three traffic lights: Two for the vehicles from opposite sides (we’ll call them A and B), and one for the pedestrians (we’ll call that C):

20190419_014838.jpg

In such a situation when C is red, either or both of A and B should be green. When C is green, then both A and B should be red:

20190419_014912.jpg

We’ll skip the situation where all three of them are red as no one would move in such situation.

We can show these using graph theory and map coloring as follows:

20190419_014930.jpg

Since we set all the rules graphs make it much easier and clearer to understand the situations.

Light #3

Finally we have a two-way street (A and B), a right turn (C) and two pedestrian lights (D and E) as follows:

20190419_014947.jpg

This time it is a much complex situation:

20190419_015030.jpg

Although using graph theory makes it all easier for us to understand:

How Many Colors?

We will color the following graphs using the same rules we just established above: If two dots are connected with a line, then those dots must have different colors.

Chromatic Numbers: Whenever a graph is being colored, ambition is the use the least number of colors. This number is also known as the chromatic number of a graph.

Here we need 3 colors. Hence chromatic number of the graph is 3. Let’s add one more dot and line to the graph:

This time chromatic number of the graph becomes 2. We’ll add another dot and line:

Now chromatic number becomes 3 again. Let’s add a dot and a line for the last time:

Chromatic number is back to 2.

To be continued…

One Wonders…

What did just happen? What did you notice? Why is it happening?

How can you increase the chromatic number?

M. Serkan Kalaycıoğlu

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.

hermitage-map-st-petersburg
Map of Hermitage.

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?

indir
Mei-Ko Kwan

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:

20190324_210039
A, B, C, D and E are the houses as the lines are the streets. The numbers above the lines show how much time it takes to walk from one house to another.
Reminder (You can read the first three articles of Graphs and learn the detail of the following.)
What is an Euler circuit?
Euler circuit is a walk through a graph which uses every edge (line) exactly once. In an Euler circuit walk must start and finish at the same vertex (point).
How do we spot an Euler circuit?
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:

20190325_123338.jpg
The numbers above each line represents the distances (e.g. in km) between the points.

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

20190325_123326.jpg

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:

20190325_123311.jpg
The shortest path takes 11 km.

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:

20190324_210039

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

20190324_210102

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:

20190324_210157

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?

20190324_210225

M. Serkan Kalaycıoğlu

Real Mathematics – Puzzle #1

Crossing the River

A farmer is walking back home with a wolf, a goat and some lettuce. As he was on his way a river appears in front of him. Luckily for him, he sees an abandoned boat. Though it turned out the boat was not big enough for all of them. Farmer had to choose either one of the wolf, goat or lettuce in each time he crosses the river.

But there was a catch here: If they are left alone wolf would eat the goat and goat would eat the lettuce. What is farmer’s strategy in order to cross this river? (P.s: It is not possible to swim across the river.)

farmer-wolf-goat-cabbage

The Answer

kec3a7iik

Between these three only wolf and lettuce can be left alone. Then farmer should start the process with carrying the goat to the right side of the river.

lahank

Then he should return the left side and picks up either of the wolf or the lettuce. (Let’s assume that he picks the lettuce.) Farmer reaches the right side of the river with the lettuce. Now before he leaves he realizes that lettuce and goat can’t be left alone. So he takes the goat with him to the left side.

kurtk

Now, lettuce is alone on the right side of the river as farmer, goat and the wolf are all on the left side. At this point farmer should carry the wolf to the right side and leaves it there with the lettuce as lettuce and wolf can be left alone without a problem.

hepsik

In the end farmer can go back to the left side of the river and takes the goat to the right side. Hence the problem gets solved.

There wouldn’t be a solution for this puzzle if wolf was eating the lettuce. But, in order to understand that we had to check every possible variation. This would have been a waste of time and energy. Thus we haven’t found an actual method for the solution of this puzzle.

River Algorithm

Graph Theory is a relatively new subject of mathematics. In Graph Theory what matters is the placement and the connection; not the shape. In this part of mathematics objects are described with dots and connections with lines. Then wolf, goat and the lettuce can be represented as dots. Only connection between these three is whether they eat one another or not. In the puzzle goat eats lettuce and wolf eats goat. Hence connections (or lines) should be between them.

If dot disappears, then the connections within disappears as well. In the puzzle we can take only one dot at a time. In the first move we choose the goat. This can be shown in graph as follows:

adsız

Deleting the goat dot means to delete the lines connected to it. Graph has no line after the first move which is what we want to accomplish and we managed to do it with deleting only 1 dot. This means another thing: In order to solve the puzzle there must be as many spaces as the deleted dots in the boat.

adsız2

Let me explain this with an example: Assume that we have to take at least n dots away from the graph in order to get rid of all the lines. This means if boat has n empty spaces the puzzle can be solved.

Let’s add a rabbit to this puzzle.

Second River Puzzle

Now farmer has a goat, a wolf, some lettuce and a rabbit. On top of the previous puzzle rabbit eats the lettuce and wolf eats the rabbit.

adsız3

In the first puzzle we took goat’s dot and saw that there was no line left in the graph. But in the second puzzle none of the four dots is able to extinguish all the lines of the graph.

This is why in order to extinguish all the lines; we must try to remove at least two dots. For instance:

adsız8

As seen above when we take goat and the rabbit, all the lines inside the graph disappears. Using graphs we found an algorithm and with that algorithm we know that the boat must have at least 2 spaces in order to solve the second puzzle.

One Wonders…

  1. Solve the second puzzle.
  2. Let’s add carrot, cat and mice to the second puzzle. Goat, rabbit and mice eats the carrot and cat eats the mice. Try to find how big the boat should be and solve the puzzle for that boat.

M. Serkan Kalaycıoğlu

Real Mathematics – Geometry #3

“There is no royal road to geometry.”

From Euclid to the king who asked Euclid if there is an easier way to learn geometry.

Up until now I have mentioned Euclid and his book Elements a few times. This masterpiece is actually a collection of 13 books and was considered as the source of only known geometry for thousands of years. Historical figures including Newton, Leibniz, Omar Khayyam and many others learned mathematics through Euclid’s Elements.

First book of Elements starts with 23 seemingly obvious and simple definitions. I will mention some of them below.

Elements Book I

Definition 1: A point is that of which has no parts. (Zero dimensions)

Definition 2: A line is length without breadth. (One dimension)

Definition 3: The extremities of a line are points.

Definition 4: A straight line is any one which lies evenly with points itself.

Definition 8: A plane angle is the inclination of the lines to one another when two lines in a plane meet one another and are not lying in a straight-line.

Definition 15: A circle is a plane figure contained by a single line such that all of the straight-lines radiating towards from one point amongst those lying inside the figure are equal to one another.

After reading these definitions for the first time, a few question marks popped up in my head.

For instance the first definition suggests that a point has no dimensions. If that’s so, how can one show a point lying on a plane?

Is it even possible to show something that has no dimensions?!

Which of these two can suggest a point to us? Obviously their sizes don’t matter and neither of them is an illustration of an actual point.

In this context, second definition is not different from the first one: One can’t draw something that has no breadth.

çizgi

Eighth definition is about angles. In order to draw an illustration for a random angle one must know how to draw lines, straight lines and dots.

açı

I’ve just showed you that even basic geometrical shapes are impossible to demonstrate. We can only imagine them in our minds. This means that in a way architects are selling illusions.

It is being told that mathematics has abstract and tangible parts. Whenever a student is dealing with abstract mathematics, teacher ought to give tangible examples so that student can comprehend with the subject easily. Nevertheless, we are helpless even when we want to give a full tangible explanation to a simple thing like a straight line.

Magic inside the Elements

In the first proposition of the first book of Elements given a random straight line, Euclid is showing us how to draw an equilateral triangle from that line.

Just to remind you, Euclid only used an unmarked ruler and a compass in his methods. Stop here and try to think of a way to construct an equilateral triangle from a random straight line.

Euclid’s Method

  1. Assume that we have a finite straight line AB.
    çem
  2. Take AB as radius and draw a circle that has center A.
    çem1
  3. Now take AB as radius and draw another circle that has center B this time.
    çem2
  4. These circles will intersect at two points. Call one of them C.
    çem3
  5. Connect A to C. One can easily see that AB and AC are radii; hence they are equal in length.
    çem4
  6. Then connect B to C. One can observe that BC and BA are radii; hence they are equal in length.
    çem5
  7. AB and AC, BA and BC are equal. Since AB and BA are the same straight line one can conclude that AB=AC=BC.
    çem6
  8. These three straight lines construct an equilateral triangle.
    çem8

One wonders…

These methods are taken from a book that was written around 2300-2400 years ago. What I find fascinating about mathematics is that we are not even capable of showing what a dot is, but we can also explore other planets using the power of the language of mathematics.

Now use Euclid’s materials (an unmarked ruler and a compass) and try to draw the twin of a given random straight line. Hint: Analyze the second proposition of the book I of Elements.

M. Serkan Kalaycıoğlu