Graph theory can be used to help solve many real world problems. For example, we can use graph colorings to help us solve situations like the one described below. There are 8 people enrolled in the Extended Learning classes as part of a summer study abroad program. They are taking the classes as shown in the table. Landry Journalism, Literature, Psychology, French Ollie Psychology, Sociology, Journalism, Astronomy Psychology, Literature Ignacio Noel Mathematics, Literature, French, Journalism Gene Beatrix Jamie Callie Astronomy, Mathematics, Literature, Journalism Journalism, Mathematics, History Mathematics, French, Astronomy French, Astronomy, Journalism The host university needs to schedule final exams for these students and would like to use the minimum number of time slots required. We can use graph theory to help us analyze this situation. We begin by making a graph using the data in the table. Draw the following graph on a piece of paper. In our graph, each vertex represents one of the classes. Two vertices are connected if there is a student taking both of those classes. Note that if a student is taking both of those classes, then those final exams cannot occur at the same time. G H A Use the graph you drew to determine what is the minimum number of final exam times slots needed so that the people can take all of their final exams. (Hint: Would a vertex coloring or an edge coloring be more useful here?)
Graph theory can be used to help solve many real world problems. For example, we can use graph colorings to help us solve situations like the one described below. There are 8 people enrolled in the Extended Learning classes as part of a summer study abroad program. They are taking the classes as shown in the table. Landry Journalism, Literature, Psychology, French Ollie Psychology, Sociology, Journalism, Astronomy Psychology, Literature Ignacio Noel Mathematics, Literature, French, Journalism Gene Beatrix Jamie Callie Astronomy, Mathematics, Literature, Journalism Journalism, Mathematics, History Mathematics, French, Astronomy French, Astronomy, Journalism The host university needs to schedule final exams for these students and would like to use the minimum number of time slots required. We can use graph theory to help us analyze this situation. We begin by making a graph using the data in the table. Draw the following graph on a piece of paper. In our graph, each vertex represents one of the classes. Two vertices are connected if there is a student taking both of those classes. Note that if a student is taking both of those classes, then those final exams cannot occur at the same time. G H A Use the graph you drew to determine what is the minimum number of final exam times slots needed so that the people can take all of their final exams. (Hint: Would a vertex coloring or an edge coloring be more useful here?)
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Transcribed Image Text:In the following table, indicate in which final exam time slot each class could be placed (i.e. 1,2, etc).
Psychology
History
Sociology
Mathematics
French
Journalism
Astronomy
Literature
Transcribed Image Text:Graph theory can be used to help solve many real world problems. For example, we can use graph colorings to help us
solve situations like the one described below.
There are 8 people enrolled in the Extended Learning classes as part of a summer study abroad program. They are taking
the classes as shown in the table.
Landry Journalism, Literature, Psychology, French
Ollie Psychology, Sociology, Journalism, Astronomy
Ignacio
Psychology, Literature
Noel Mathematics, Literature, French, Journalism
Gene
Beatrix
Jamie
Callie Astronomy, Mathematics, Literature, Journalism
Journalism, Mathematics, History
Mathematics, French, Astronomy
French, Astronomy, Journalism
The host university needs to schedule final exams for these students and would like to use the minimum number of time
slots required. We can use graph theory to help us analyze this situation.
We begin by making a graph using the data in the table. Draw the following graph on a piece of paper. In our graph, each
vertex represents one of the classes. Two vertices are connected if there is a student taking both of those classes. Note that
if a student is taking both of those classes, then those final exams cannot occur at the same time.
E
G
B
H
A
Use the graph you drew to determine what is the minimum number of final exam times slots needed so that the people can
take all of their final exams.
(Hint: Would a vertex coloring or an edge coloring be more useful here?)
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 1 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
