Discrete Math

posted by .

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.

  • Discrete Math -

    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.

  • Discrete Math -

    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.

  • Discrete Math -

    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.

  • Discrete Math -

    I've got the colors as they should be, but am unsure how to describe how it will help schedule anything.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. math

    An instructor counts homework as 1/3 of the student's grade and the final exam to be 2/3 of the student's final grade. Going into the final exam a student has a homework grade of 48%. What range of scores on the final exam would put …
  2. need help for medical coding 1

    can anybody tell me if they received an examination booklet of medical coding 1, exam 1, lessons 1-3 and medical coding 1, exam 2, lessons 4-6 from penn foster college. because i didn't received any one of them i only received the …
  3. Algebra

    Before the final exam, a student has test scores of 72, 80, 65, 78, and 60. If the final exam counts as one-third of the final grade, what score must the student receive in order to have a final average of 76 percent?
  4. math

    A student’s final grade in chemistry is determined by the following weights: Quizzes 5% Exam 1 20% Exam 2 20% Lab Reports 15% Research Paper 15% Final Exam 25% The student received the following grades: Lab reports: 75 80 70 75 85 …
  5. C++programming

    Write an interactive C program that will accept each student’s name an exam grades as input, determine an average grade for each student, and then display the student’s name, the individual exam grades and the calculated average. …
  6. math

    a student’s grade in a class is simply the mean of five 100-point exams a. If the student has grades of 77, 73, 97, and 89 on the first four exams, what is the students’ grade before taking the last exam?
  7. mathematics

    A student scores 86% in the first terminal and 75% in the second terminal.What percentage must he score on the final exam to obtain an average of 80%. The exams are weighted as first terminal 20%,second terminal 40% and the final exam …
  8. math

    In a course a student's final exam is weighted as heavily as his mid term exam.if a student receives a score of 84 on his final exam 90 on his midterm,what is the average for the course?
  9. word problem, Im lost on how to set this up

    Joe has scored 84, 89, and 90 on his first three exams in his math class. If the standard 70,80,90 scale is used for grades and the exams are equally weighted, what must he score on the final exam, f, in order to a) Get a C average …
  10. word problem, please

    Joe has scored 84, 89, and 90 on his first three exams in his math class. If the standard 70,80,90 scale is used for grades and the exams are equally weighted, what must he score on the final exam, f, in order to a) Get a C average …

More Similar Questions