6.3. Question 12: Greedy Strategy for Vertex Colouring

Try these first

1. 1.

   Define vertex colouring.

   Hint

   Think about the application in scheduling.

2. 2.

   What does the Welsh-Powell algorithm do?

   Hint

   No hint provided

3. 3.

   What does the Welsh-Powell algorithm follow?

   • Sorting vertices by alphabet
   • Sorting vertices by degree
   • Randomly selecting vertices

   Hint

   Focus on the concept of degrees.

4. 4.

   True or False: The Welsh-Powell algorithm always finds the optimal solution for vertex colouring.

   • True
   • False

   Hint

   Think about the scenarios we've discussed.

5. 5.

   Given a graph with 6 vertices in a cycle, apply the Welsh-Powell algorithm and determine if it results in using more colours than optimal.

   Hint

   Start with the vertex that has the highest degree.

6. 6.

   Create a more complex graph with connections among vertices, illustrating where the Welsh-Powell algorithm may fail to be optimal. Then show the optimal colour assignment.

   Hint

   Challenge yourself: consider how to minimize colours based on vertex connections.