Discrete Math Graph Theory Project

Use graph theory to come up with a solution to the following three scenarios.  Your work should be neatly done in a Microsoft Word document titled YOUR NAME Graph Theory Project.  When you have completed your project, save your Microsoft Word document as a PDF and then submit the file in your Google Drive by completing the following steps: 1. log into your Google Drive  2. click on "Shared With Me" at the left.  3. click on the folder labeled as your name.  4. click on the upload button that is directly to the right of the red create button.   5. select the pdf file and click upload. A video showing this process can be viewed by clicking on the following link: Uploading your project for grading.  You will be graded based on the following rubric: Graph Theory Project Rubric

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)
 
Helpful Resources/Tips
  • The following video shows how to use Google drawing to create a graph and color the vertices:  Google Drawing Demo
  • Take pride in your work! Make it look nice!
  • Don't Forget to Check the Rubric!
  • View the video Uploading your project for grading if you need a reminder on how to submit your project correctly.
  • Make sure your project is saved as a PDF file and named YOUR NAME Graph Theory Project.pdf