7. The two problems below can be solved using graph coloring. For each problem, represent the situation with a graph, say whether you should be coloring vertices or edges and why, and use the coloring to solve the problem. a. Your Quidditch league has 5 teams. You will play a tournament next week in which every team will play every other team once. Each team can play at most one match each day, but there is plenty of time in the day for multiple matches. What is the fewest number of days over which the tournament can take place? FE b. Ten members of Math Club are driving to a math conference in a neighboring state. However, some of these students have dated in the past, and things are still a little awkward. Each student lists which other students they refuse to share a car with; these conflicts are recored in the table below. What is the fewest number of cars the club needs to make the trip? Do not worry about running out of seats, Just avoid the conflicts. Student: B CDEFIG H Conflicts: BEJ ADG HI BF Al D B CI EH ACFI Hint For (a), you will want the teams to be vertices and games to be edges. Which does it make sense to color?

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
7. The two problems below can be solved using graph coloring. For each
problem, represent the situation with a graph, say whether you should be
coloring vertices or edges and why, and use the coloring to solve the problem.
a. Your Quidditch league has 5 teams. You will play a tournament next week
in which every team will play every other team once. Each team can play
at most one match each day, but there is plenty of time in the day for
multiple matches. What is the fewest number of days over which the
tournament can take place? FE
b. Ten members of Math Club are driving to a math conference in a
neighboring state. However, some of these students have dated in the
past, and things are still a little awkward. Each student lists which other
students they refuse to share a car with; these conflicts are recored in the
table below. What is the fewest number of cars the club needs to make
the trip? Do not worry about running out of seats, Just avoid the conflicts.
Student:
B CDEFIG H
Conflicts: BEJ ADG HI BF Al D B CI EH ACFI
Hint
For (a), you will want the teams to be vertices and games to be edges. Which
does it make sense to color?
Transcribed Image Text:7. The two problems below can be solved using graph coloring. For each problem, represent the situation with a graph, say whether you should be coloring vertices or edges and why, and use the coloring to solve the problem. a. Your Quidditch league has 5 teams. You will play a tournament next week in which every team will play every other team once. Each team can play at most one match each day, but there is plenty of time in the day for multiple matches. What is the fewest number of days over which the tournament can take place? FE b. Ten members of Math Club are driving to a math conference in a neighboring state. However, some of these students have dated in the past, and things are still a little awkward. Each student lists which other students they refuse to share a car with; these conflicts are recored in the table below. What is the fewest number of cars the club needs to make the trip? Do not worry about running out of seats, Just avoid the conflicts. Student: B CDEFIG H Conflicts: BEJ ADG HI BF Al D B CI EH ACFI Hint For (a), you will want the teams to be vertices and games to be edges. Which does it make sense to color?
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 3 images

Blurred answer
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education