September 28 - October 2

This week we will be starting the Probability and Statistics portion of the course.  Make sure you get the notes printed out so that you can focus on adding to them in class. We will discuss counting methods this week and introduce probability at the end of the week. It is really important that you keep on task with the homework on WebWork as we complete each week.  The best way to learn this material is to practice doing problems.  Remember, there are also additional problem worksheets on Moodle to go along with each homework assignment.  The solutions to those worksheets are available in the CAS.

Your blogs this week just need to be the five fill in the blanks.

Challenge Problem: How many five-card hands chosen from a standard deck contain two aces and three kings?

Graph Theory Review Worksheets

Please print both of these worksheets out and be prepared to discuss them in class on Monday and Wednesday this week.

In Class Worksheet

Graph Theory Exam Review

New Blog Post Prompt - Due by Sunday, September 27

For this additional blog post, I would like you to read one of the articles below and write a 2-3 paragraph response to the article.  Tell me which article you chose and give a brief summary of the article, explaining how graph theory was applied.  Finally, tell me what you thought of the way they applied graph theory in the article.  Were you surprised that graph theory applied in this situation?

“Is Graph Theory Key to Understanding Big Data?”

“Network Theory sheds new light on origins of consciousness”  

Explained: Graphs from MIT News

"New approach to vertex connectivity could maximize networks’ bandwidth” 

“Sudoku and Graph Theory”

“Rebooting the Human Genome” 

September 14-19: Hamiltonian Paths and Trees

This week we will be finishing up most of the graph theory material.  We will start by discussing Hamiltonian paths and circuits and weighted graphs.  A weighted graph is just a graph with numbers (weights) on the edges.  Our goal will be to use weighted graphs and Hamiltonian circuits to solve the Traveling Salesman Problem that we discussed last week.  We will see three algorithms for solving this: The Nearest Neighbor Algorithm, The Side-Sorted (or Best Edge) Algorithm, and the Repetitive Nearest Neighbor Algorithm.  We will also discuss how to solve this using Brute Force.  You will need to memorize each of these algorithms.  We will end the week with a discussion of trees and spanning trees.

Don't forget to keep up with the homework on WebWork.  The first two assignments are due this week.


Challenge Problem: Suppose your favorite presidential candidate is planning a tour of campaign talks in Missouri.  He (or she) will visit Kansas City, St. Louis, St. Joseph, Columbia, Springfield, and Jefferson City.  Using maps.google.com, find the distance between each of these cities.  Using your favorite method from this week, find an optimal route for the candidate to travel, visiting each city once and returning to where he starts.  Describe the method you used and provide all details.  Your solution should also include a picture of an appropriate weighted graph.

September 7-11: Graph Theory

This week we will be discussing Euler circuits and paths.  Last week, we talked about tracing a graph.  An Euler path or circuit is what you get when you can trace a graph.  An Euler path is a path that uses every edge of the graph exactly once.  (Think "E" for Euler and edge.)  An Euler circuit is just an Euler path that begins and ends at the same vertex (so is a circuit).  Euler's Theorem will be an important theorem for us.  It will give us a quick way to determine if a graph has an Euler path or Euler circuit.  You will need to memorize this theorem.

Challenge Problem: The picture below is the floor plan for a section of prison rooms.  If all the doors are open, is it possible for a guard to enter this section at the entrance, pass through each door locking it behind him, and then exit without ever having to open a door that has been previously locked?  Answer by turning this into a graph theory question.  You may describe your graph by giving the vertices and edges or post a picture of your graph in your blog.  Your solution should include a path in the graph you create.

Out of Class Assignment for 9/4

Math 110 Graph Theory Out of Class Assignment

You should complete each of the problems below on a separate sheet of paper. These problems will be collected in class for a grade on Wednesday, September 9, 2015.

1. For each of the following conditions, draw a graph that satisfies the conditions. If you believe it is impossible, explain your reasoning.
   (a) A simple graph with 4 vertices, two of which have degree 2. (b) A simple graph with 3 odd vertices.
   (c) a connected graph with a bridge. Identify the bridge.
   
2. Sketch a graph with vertices A, B, C, D, E and edges {AB, AE, BD, BC, BE, CE, DE}.
   
3. The following questions deal with the graph below.
   
   
   
   
   
   
   
   1. (a)  Give the degree of vertex F .
      
   2. (b)  What is the length of the path FBCGEF?
      
   3. (c)  Can the graph be colored with four colors? Three? If so, give a coloring (label the vertices with the assigned color).
      
4. The following questions deal with the graph below.
   
   
   
   
   
   1. (a)  Give the degree of vertex C.
      
   2. (b)  Is ABGE a path in the graph?
      
   3. (c)  Give a path of length 4 in the graph, starting at A.
      
   4. (d)  Can you start at one vertex, and trace every edge in the graph exactly once (so no repeating edges), and return to the starting vertex? (ie, Does the graph have an Euler circuit?) Why or why not?
      

1