Carpeting and Traffic light, what do they have in common? - Part 2

In the previous post, I define a carpeting problem. It quite a simple problem that can be described, including a solution in couple paragraphs. The traffic light problem is quite more complex.

Traffic light setting: I want to setup a traffic light on a intersection (figure 1), which A, B, and C are two-way streets, while D is a one way street, and have to make sure that every one can get thought the intersection safely.

figure 1

If I setup the light as follow:

1. let A go to B and C, and block every one else
2. let B go to A and C, and block every one else
3. let C go to A and B, and block every one else
4. let D go to A, B and C and block every one else.

There will be 4 turns signal for each cycle. I  ensure that every one get their turn, and pass through the intersection safely. 

You may notice that while we let A go to B and C, in the same time C can safely go to A. This raise the question, can we do 3 turns signal in each cycle, and still let every one get through safely?

Let start by draw a picture that will help answer the question.

This picture shows different car directions and relations between them. For example, If I let cars go from D to B (DB), then I can let the car go from D to C (DC), but I can not allow any cars from B to A (BA), or C to A (CA). The cars will crash!. In the picture, I use the red line to connect between directions that can not be allowed at the same time.

I apply this rule to all possible directions, and I get this picture:

Please note that I did not draw AB, BC, or DA, they are right turn. If the drivers are carefully turn, it's always possible. With this picture, I can setup the signal only 3 turn per cycle, as follow:

1. let C to B, and D to B
2. let B to A, and C to A
3. let A to C, and D to C.

and still guarantee every one get through safely. 

More importantly, It's also show that I can not do better than 3 turns!  Why?, consider the BA, CB, and AC. If I allow one of these direction, I can not allow the other two. It's has to be at least 3 turns to allows all three directions to get through.

The picture, some what, look similar to the picture I draw for the carpeting problem, isn't it? That true because, with some preparation, I end up with the same graph coloring problem. For the carpeting, the preparation is quite easy, but not so for the traffic light setup.

Next time I come back with more discussion.