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!
Tuesday, 19 May 2009
Tuesday, 12 May 2009
Tuesday, 5 May 2009
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.
Subscribe to:
Posts (Atom)