Scheduling Edge colorings, as explained in Exercise 30, can be used to solve scheduling problems. For instance, suppose five players are competing in a tennis tournament. Each player needs to play every other player in a match (but not more than once). Each player will participate in no more than one match per day, and two matches can occur at the same time when possible. How many days will be required for the tournament? Represent the tournament as a graph, in which each vertex corresponds to a player and an edge joins two vertices if the corresponding players will compete against each other in a match. Next, color the edges, where each different color corresponds to a different day of the tournament. Because one player will not be in more than one match per day, no two edges of the same color can meet at the same vertex. If we can find an edge coloring of the graph that uses the fewest number of colors possible, it will correspond to the fewest number of days required for the tournament- Sketch a graph that represents the tournament, find an edge coloring using the fewest number of colors possible, and use your graph to design a schedule of matches for the tournament that minimizes the number of days required.
Want to see the full answer?
Check out a sample textbook solutionChapter 5 Solutions
Mathematical Excursions (MindTap Course List)
- Construct a niche overlap graph for six species of birds, where the hermit thrush competes with the robin and with the blue jay, the robin also competes with the mockingbird, the mockingbird also competes with the blue jay, and the nuthatch competes with the hairy woodpecker.arrow_forwardA floor plan of a museum is shown. Draw a graph that represents the floor plan, where each vertex represents a room and an edge connects two vertices if there is a doorway between the two rooms. Is it possible to walk through the museum and pass through each doorway without going through any doorway twice? Does it depend on whether you return to the room you started at? Justify your conclusion.arrow_forwardD B G A E C H TREE F B D H A E GRAPH G C Farrow_forward
- Where is the number of stores in that graph?arrow_forwardIn a high school class, there are students of different talents (ex. music, art, debate, sports, etc.). A committee needs to be formed consisting of the maximum number of students such that the committee is diverse – no two students with the same talent are in the committee. Transform this problem to a graph theoretic problem. What are the vertices of the graph? What are the edges of the graph? What do you have to find in the graph?arrow_forwardConsider the following graph. (Enter your answers as comma-separated lists.) A graph with 5 vertices and 7 edges is shown. Loop e1 connects vertex v1 and vertex v1. Edge e2 connects vertex v1 and vertex v2. Edge e7 connects vertex v1 and vertex v3. Loop e3 connects vertex v2 and vertex v2. Edge e6 connects vertex v2 and vertex v3. Edge e4 connects vertex v2 and vertex v5. Edge e5 connects vertex v2 and vertex v5. Vertex v4 is isolated. (a) Find all edges that are incident on v1. (b) Find all vertices that are adjacent to v3. (c) Find all edges that are adjacent to e1. (d) Find all loops. (e) Find all parallel edges. (f) Find all isolated vertices. (g) Find the degree of v3.arrow_forward
- Which system is represented in the graph?arrow_forwardIn this exercise a graph is used to help solve a scheduling problem. Twelve faculty members in a mathematics department serve on the followingcommittees:Undergraduate Education: Tenner, Peterson,Kashina, DegrasGraduate Education: Hu, Ramsey, Degras, BergenColloquium: Carroll, Drupieski, Au-YeungLibrary: Ugarcovici, Tenner, CarrollHiring: Hu, Drupieski, Ramsey, PetersonPersonnel: Ramsey, Wang, UgarcoviciThe committees must all meet during the first week of classes, but there are only three time slots available. Find a schedule that will allow all facultymembers to attend the meetings of all committees on which they serve. To do this, represent each committee as the vertex of a graph, and drawan edge between two vertices if the two committees have a common member. Find a way to color the vertices using only three colors so that no two committees have the same color, and explain how to use the result to schedule the meetings.arrow_forwardEach vertex in the graph represents an animal that needs to be transported to the zoo. Two vertices are connected by an edge whenever the corresponding animals cannot be placed in the same cage (i.e., the edges represent pairs of animals that would harm each other if caged together). What is the fewest number of cages needed to transport these animals? Give a conflict-free way to assign them to cages. S V U W Yarrow_forward
- The floor plan of the art gallery is pictured below. Draw a graph that represents the floor plan, where vertices correspond to rooms and edges correspond to doorways. Is it possible to take a stroll that passes through every doorway without going through the same doorway twice? If so, does it matter whether we return to the starting point?arrow_forwardIn a round-robin tournament the Tigers beat the BlueJays, the Tigers beat the Cardinals, the Tigers beat theOrioles, the Blue Jays beat the Cardinals, the Blue Jaysbeat the Orioles, and the Cardinals beat the Orioles.Model this outcome with a directed graph. this is graph theoryarrow_forwardII. The table below lists five mobile phone companies and indicates whether they have agreements to roam onto each other's networks. Draw a graph that represents this information, where each vertex represents a phone company and an edge connects two vertices if the corresponding companies have a roaming agreement. Then use the graph to answer the questions: which phone company has roaming agreements with the most carries? Which company can roam with only one other networks? SuperCell Yes Lightning Yes Mobile Plus Talkmore Airwave Mobile Plus No No Talkmore No Yes Yes No Yes No No Yes SuperCell Airwave No No Yes Yes Lightning Yes No No Yesarrow_forward
- Discrete Mathematics and Its Applications ( 8th I...MathISBN:9781259676512Author:Kenneth H RosenPublisher:McGraw-Hill EducationMathematics for Elementary Teachers with Activiti...MathISBN:9780134392790Author:Beckmann, SybillaPublisher:PEARSON
- Thinking Mathematically (7th Edition)MathISBN:9780134683713Author:Robert F. BlitzerPublisher:PEARSONDiscrete Mathematics With ApplicationsMathISBN:9781337694193Author:EPP, Susanna S.Publisher:Cengage Learning,Pathways To Math Literacy (looseleaf)MathISBN:9781259985607Author:David Sobecki Professor, Brian A. MercerPublisher:McGraw-Hill Education