### Discrete Math Graph Theory Project

Part 1: Scheduling

The Athens Drive High School Athletics Department has decided to hold team parent meetings at the beginning of the school year.  They would like for every parent to be able to attend every parent meeting that their children are involved in.  However, a number of students play multiple sports and a number of families have multiple children that play different sports.  The conflicts for this school year are shown in the following table:

 Team Has Members in Common With Football Men’s Soccer, Women’s Basketball, Baseball Cross Country Wrestling, Track Softball Men’s Basketball, Baseball, Track Swimming Men’s Soccer, Women’s Basketball Wrestling Women’s Soccer, Men’s Basketball, Football Women’s Soccer Football, Swimming Baseball Cross Country, Track Women’s Basketball Softball

A) Use Google Drawing to create a graph that models this scenario. A video with graph creating tips can be viewed by clicking on the following link: Google Drawing Demo

B) Determine an acceptable schedule for the meetings using the least amount of meeting times possible.

Part 2: Flubergroobles!

Your friend has created an amazing new invention she calls the flubergrooble.  She believes that there is a huge flubergrooble market in four cities that she provided to you.  She does not have enough money to fly through the cities so she is going to drive and really wants to keep her mileage as low as possible to save money.  She is begging for your help!

A) Mr. Wood will give you a set of 4 numbers.  Click on the link: US Cities, and find the city that corrresponds to each of the four numbers you were given.  These 4 cities are the cities that she needs to visit.

B) Using a map site like Google Maps, find the distances between each city she needs to visit.

C) Organize your distance information in a table like the one below.  These are not the four cities you need to consider, this is just and example. (There are X's in the bottom half because they are repeats.  Ex: You already found Miami to New York, there is no need to find New York to Miami).

 Miami New York Las Vegas Seattle Miami X New York X X Las Vegas X X X Seattle X X X X

B) Use a Google drawing to display this information in a weighted graph. The following video shows how to use Google drawing to create a graph and color the vertices:  Google Drawing Demo.

C) Find all of the possible routes she could take and the total distance of each route.  Display this information in a table.

D) Which route should your friend take and how many miles will she have to drive?

Part 3: Aliens Attack!

Aliens have attacked Earth and communications have been severely crippled.  Only the emergency broadcast system still remains.  The following table displays the communication abilities of the remaining major cities in the United States.  The government has asked you to analyze this communication network.

 City Can Broadcast To: Philadelphia New York, Detroit New York Philadelphia, Boston Boston Detroit, New York Dallas Los Angeles, Phoenix Detroit Philadelphia, Dallas, Phoenix Los Angeles Dallas, Phoenix Phoenix Dallas, Los Angeles

A) Use a Google Drawing to create a directed graph modeling the communication network.

B) The government needs to know which cities a message can originate from and reach every other city in the network.  Perform a check on each city and display your findings in a table with two columns.  The first column should be the city the message originates from and the second column should show a path that the information could flow through and reach every other city.  If a message cannot originate in the city and reach every other city, write "message cannot be received by all cities."

C) The government want to set up its home base in the most important city in the network. They want to focus all of their major defenses to protect the government and the broadcast network at the same time. In which city should the goverment set up its base of operations?  (Hint: Is there a city that, if destroyed, there would be cities completely cut off from the communication network)