Graph Theory Projects

Out of the nine math teachers at my school, I'm one of two math teachers that is lucky enough to teach a course called discrete math. Although the other teachers argue it's not a "real math class" and some students do too, I absolutely adore teaching this course. I especially love that this class allows all students to be successful because they don't need any prior knowledge on the topics to do well. Since all students start off with knowing very little about any of the topics we will be studying, it levels the playing field among students. 

In discrete math we study a lot of discrete topics, hence the name. Some of the units of study in this course include: election theory, fair division, graph theory, probability, recursion, and matrices. My favorite topics are those on graph theory. In fact, we just spent the past seven weeks covering various graph theory topics and I'm a little sad to be moving on to probability today.  (I didn't realize we had been on graph theory that long - I just looked at my notebook and saw we started the unit on September 30...crazy!)

The majority of students in this class are just trying to get their 4th math credit to meet North Carolina's graduation requirements, so I try to make this course as fun as possible. Fortunately for me, these topics lend themselves to projects. We culminate every topic with a project and a test. I typically give students 1-2 days to work in class on these projects and if needed, an additional day or two at home. Here are a few of the projects my students completed this semester. For the most part, my students put a lot of time and effort into their projects. I enjoy seeing a students creativity and personality come out through their projects.  

Project Planning (Critical Path Analysis)
Students have to plan and organize an event/task that has time-sensitive operations, in order to find the minimal amount of time needed to complete the task.

Planning the Homecoming Dance - A booklet with graphs on transparency sheets
so that you can see each part individually or all at once. 

Planning a Wedding - Each layer of cake had a different part of the project. 

Conflict Resolution Graphs
Students have to create scenario that involve multiple interest groups, each of whom may have multiple interests, and minimize the conflicts between the groups.

Traveling Salesman Problem (TSP)
College Visits - Students had to find distances between their house and four colleges they are interested in attending. Then they had to plan out the quickest way to visit all 4 colleges once, when beginning and ending at their house. 

Expression Trees (Post Order Traversals)
Students have write a favorite quote on a binary expression tree so that it reads as a post order traversal.

I grade projects on a rubric based on meeting the project requirements and being mathematically correct.  However, since there are 26 students in my class this semester, I always have a few not-so-good projects or I have projects that look great but the math is wrong. To work on eliminating the latter problem, I've started putting a check system into my projects. Students are responsible for getting another student to look over their rough draft before they can begin making their final project. It counts as part of their project grade for both students (the student doing the check and the students work being checked.) That has helped but it hasn't completely gotten rid of the problem. 

I know there are very few online resources for discrete math at the high school level so I'm working on getting my discrete math files uploaded to box.com but it's a slow process. Maybe between thanksgiving break and winter break, I'll be able to get this done before the end of the year! If you want any of my graph theory project files/grading rubrics before then, send me an email.