Today it is the last hour we work on the project. So everybody is working hard. They try to finish the map of European Union. They are colouring seven maps to show the differents steps of the realisation of the final map. And we are working hard as you can see on the computer to make the project end. Our friend on the picture is making the work of at least 2 people!

Seems that it takes more time than expected...

Everybody is working.
Some people are cutting and pasting the different pieces of the map.
The other ones start to apply the algorithm by typing the ordered list of countries.
I think we won't have time to finish today but I promise that I'll make a picture of the final poster.

Welsh-Powell algorithm

We are going to use this algorithm to colour the map instead of brute-force.


Step 1: Make a list of all the vertices, by decreasing degree.
Step 2: Choose a new color, called "current" colour, and colour the first uncoloured vertex.
Step 3: Using the current colour, colour all uncoloured vertices that are not linked with any already current coloured vertex.
Step 4: If all the vertices are not coloured, go to step 2.

Greedy colouring

• We have studied graphs in the past few weeks. The conclusion of those lessons is a little project: we have to draw a graph representing the European Union in order to colour a map of Europe. The rules we have to obey are: two countries with a common border can't be coloured the same way and we have to use as few colours as possible.

• Some people made the graph using a geometry software, other people found an empty map and we are typing this text right now.