I was hoping if you could help me to solve this problem. Thank you.
A department wants to schedule final exams so that no student has more than one exam on any given day. There are 7 vertices of degrees 3,3,4,4,4,5,6 which show the courses that are being taken by more than one student, with an edge connecting two vertices if there is a student in both courses. Find a way to color the vertices of the graph with only 4 colors so that no 2 adjacent vertices have the same color and explain how to use the result to schedule the final exams.
The sum of the degrees of the 7 vertices add up to an odd number (3+3+4+4+4+5+6=29), which is impossible if there are only 7 vertices (courses).
Is there a typo?
Vertex colour would represent a different exam date, and edges would represent students.
Yes, there's a typo. It's actually 3+4+4+4+4+5+6=30 and there's a graph included in this problem but I don't know how to show the graph so that was why I just described how it looked like with all the vertices and degrees of each. Let me list those vertices and edges:
MCS100 connects to MCS101,110,135.
MCS101 connects to 100,135,130,120.
MCS102 connects to 135,130,120,110.
MCS110 connects to 102,100,135,120.
MCS120 connects to 110,102,101,135,130.
MCS130 connects to 120,102,101,135.
MCS135 connects to 130,120,110,102,101,100.
Thank you.
To solve the colouring problem, there is no systematic way that guarantee results.
However, for simple cases the greedy method usually works.
You can start by assigning two adjacent vertices colour numbers, say
1 to 100, and
2 to 101.
Now observe that 100-101-135 form a triangle, so 135 has to have a third colour, so
3 to 135.
Now check if there are other triangles with 100-101 as a base (none).
Similarly check if there are other triangles that use 100-135 as a base:
100-135-110: so 110 has to be assigned either colour 2 or colour 4.
Continue this by trial and error, you should get the colouring in a couple of tries. If you don't succeed, post.
I've got the colors as they should be, but am unsure how to describe how it will help schedule anything.
To solve this problem, we can use a graph coloring algorithm. In this case, we need to color the vertices of the graph with four colors so that no two adjacent vertices have the same color. This will ensure that no two courses with shared students have their final exams on the same day.
Here's a step-by-step approach to solve this problem:
1. Start by assigning an arbitrary color to the first vertex.
2. Move on to the next vertex and assign it a color different from its adjacent vertices that have already been colored. If all four colors have been used by the adjacent vertices, choose any color that has not been used yet.
3. Repeat step 2 for all remaining vertices, ensuring that each vertex is assigned a color that is different from its adjacent vertices.
To schedule the final exams based on these colorings, assign each course to a different day based on the color assigned to its corresponding vertex. For example, all courses assigned the color "red" will have their final exams on one day, courses assigned the color "blue" on another day, and so on. This way, no two courses with shared students will have their exams on the same day.
To summarize, solve the coloring problem using the graph coloring algorithm, and then use the resulting color assignments to schedule the final exams.