Many everyday tasks involve conflict, especially when trying to create a schedule. Vertex-edge graphs can be helpful in managing these conflicts to create a workable schedule.
1. The vertex-edge graph below represents a situation of scheduling five meeting dates for teachers in a school. The vertices represent different meetings. The edges between two vertices represent conflict where some teachers need to attend both meetings.
The goal is to schedule all 5 meetings using as few days as possible and avoiding scheduling meetings on the same day that share members.
Use vertex coloring to color the graph, using as few colors as possible, and not using the same color on vertices connected by an edge.
F – faculty meeting
M – math department meeting
S – study hall supervisors meeting
C – spring carnival committee meeting
P – PTA meeting
Once the graph is colored, each color represents a different day for the meetings. Using Monday, Tuesday, Wednesday, Thursday, or Friday, create one possible schedule for these five meetings. Identify which day of the week each meeting should be held and which meetings could be held on the same day.
To solve each of the problems below, draw a vertex-edge graph and then use the graph to help you solve the problem. Remember that the edges represent conflict between the two items represented by the vertices. Be sure to write you answer in real-world terms.
2. An aide to the Senate majority leader in the state legislature is asked to schedule weekly meeting times for several Senate committees. The committees include the Agenda Committee, the Education Committee, the Finance Committee, the Appropriations Committee, and the Ways and Means Committee. The Agenda Committee has members in common with each of the other committees. The Appropriations Committee has members in common with the Ways and Means committee. The schedule must be arranged so that committees with a member in common do not meet at the same time. Committee meetings last for two hours and the available times are 9-11 am on Monday, Wednesday, and Friday. When should the aide schedule each meeting?
3. In Washington D.C. a local tour company offers four different touring packages:
§ Tour 1: Pentagon, Capitol, Lincoln Memorial
§ Tour 2: Ford's Theatre, White House, Capitol, Holocaust Museum,
§ Tour 3: Holocaust Museum, Ford's Theatre, Mount Vernon Tour
§ 4: Mount Vernon, Pentagon, Lincoln Memorial
Because of heightened security they don't want more than one group of tourists visiting the same attraction in one day. Is it possible to schedule all of the tours on Monday and Tuesday?
4. At a wilderness survival training camp, each person was to go out individually, set up camp, and survive for one week. Also, people got points by being able to pinpoint anybody else's camp on a map. You lost points if other people were able to find your camp. About three days into the exercise, Adrienne had come upon both Frieda's and DuJannie's camps. Bart had found Eugenia's and Glenda's camps, and he and DuJannie both found each other's camp. DuJannie had also happened upon Hank's camp, while Hank and Eugenia had found each other's. Hank had also discovered Adrienne's. Carl detected Glenda's camp, and his camp was detected by Frieda. Unfortunately, the base leaders needed to get in touch with Carl, as someone had crashed into his parked car. They found Bart. How could they get a message to Carl?
5. Recently a telephone system in a major manufacturing company went haywire. For several days, the system would only complete certain calls over certain sets of wires. Therefore, in order to get a message to someone else, an employee of this company would have to call another employee to start the message on a route to the person it was for. As best as can be determined, these are the connections:
Connie can call Betty, Al, and Shirley. (This means that she can call them, but neither Al, Betty, nor Shirley can call Connie.)
Al can call Max
Wolfgang can call Darlene
Darlene can call Wolfgang.
Maria can call Betty and Henry.
Marla can call Maria and Connie
Shirley can call Darlene
Max can call Henry
Darlene can call Maria
Henry can call Marla
It is imperative that Max get a message to Betty. How would you tell him to route this message?
Vertex Coloring – Resolving Conflict 02/10/11 (rev. 04/02/12; cvr) Filliater