Discrete Math: Graph Theory- Hamilton and Euler Circuits

Introduction

This WebQuest is designed to strengthen your knowledge of graph theory.  Thus far, we have investigated two types of graphs in particular: Euler graphs and Hamilton graphs.  Through this WebQuest, you will investigate both types of graphs in hopes of strengthening your knowledge and skills in reference to graph theorey.  You will complete a series of assignments that will reflect on previous learned material and some new material.  Be sure to read carefully and complete all assignments.

Task

You and your partner will investigate multiple Graph Theory applications in order to stregthen your skills.  You will create graphs, define terminology, and solve a few problems of your own.  As you work, you will be recording information in a Google Doc that will be submitted to show completion and knowledge of the material included within this WebQuest.  Your goal should be to become an "expert" in Graph Theory and build on the knowledge you already have.

Process

  1. Create a Google Doc that will be shared with the teacher (Coach Josh Jenkins) when the project is complete.   Once the Doc has been created, define Euler Circuits and paths in 2-3 complete sentences.  Then define Hamiltonian Circuits and paths in 2-3 complete sentences.
  2. Using the following link, http://illuminations.nctm.org/Activity.aspx?id=3550, you are to create two separate graphs:
    1. Create a graph that contains 8 vertices and contains a Euler Circuit.  Take a screen shot of the graph you created and paste it into the Doc.  List one Euler Circuit in the graph.
    2. Create a different graph that contains 8 vertices and a Hamilton Circuit.  Take a screen shot of the graph you created and paste it into the Doc.  List one Hamilton Circuit in the graph.
  3. Click on the following link to get some more practice with Euler Circuits and paths:  http://www.flashandmath.com/mathlets/discrete/graphtheory/graph1.html
    1. For each graph that you encounter, if it has an Euler Circuit or path, list it in the Doc.  If it does not have an Euler Circuit or path, explain why.
  4. Click on the following link to get some more practice with Hamilton Circuits and paths: http://www.flashandmath.com/mathlets/discrete/graphtheory/graph2.html
    1. For each graph that you encounter, if it has a Hamilton Circuit or path, list it in the Doc.  If it does not have an Hamilton Circuit or path, explain why.
  5. There are three videos that you are about to watch.  For each video, find a minimum of three ideas/concepts that you find interesting or note worthy and type them into your Doc.
    1. Dijkstra's Algorithm: https://www.youtube.com/watch?v=gdmfOwyQlcI
    2. Prim's Algorithm:  https://www.youtube.com/watch?v=cplfcGZmX7I
    3. Kruskal's Algorithm:  https://www.youtube.com/watch?v=71UQH7Pr9kU
  6. After taking notes of the above listed algorithms, click on the following link that contains multiple problems of each algorithm: https://docs.google.com/document/d/1oNmEBVYImJRT-yB5QtJrQgf-BEecBC6ytxNpDNy50Oc/pub.  Complete the appropriate algorithms, listing your answers in your Doc that you and your partner created.
  7. Once you are finished with all the material, please share your Doc with Coach Jenkins at Joshua.Jenkins@wilsonschoolsnc.net.

Evaluation

Beginner

(0-5 points)

Understanding

(6-10 points)

Qualified

(11-15 points)

Exemplary

(16-20 points)

 Total= 20 points possible
Euler/Hamilton Definition Student does not explain either of definitions or shows little to no knowledge of the concepts. Student gives a basic explanation of one theory, but does not both, or lacks depth in defining. Student shows a basic knowledge of both theories, but has a limit to the depth of definitions. Student shows full knowledge of each theory and could easily explain each to help someone else understand.
Creation of Graphs One graph is presented.  Not all rules for graphs are provided. Graphs are provided, but lack in depth and circuits are not provided. Both graphs are provided, circuits are given, but not complete.  Errors exist in the layout of circuits. Graphs are given, circuits are given and complete.  Strong knowledge are creativeness are shown.
Experimentation with Applets No explanations or evidence of completing applets is shown. Evidence is shown of completing applets, but one or more errors is made in defining the existing circuits/paths. Each applet has been attempted and evidence shows that student has an understanding of graphs.  two or less errors has been made. Student shows knowledge of what is going on.  No mistakes are made in the work provided.
Videos and Notes No notes are given. Notes are given for one or more videos, but not enough to suit the instructions. Notes provided for at least 2 videos.  Basic knowledge is represented in the notes that are listed. All videos have been watched and all notes are provided.
Completion of attached Problems No problems attempted/submitted. Only 2-3 problems are attempted.  Multiple errors exist in the work submitted. All problems have been attempted, but multiple mistakes have been made in the problems. All problems attempted, no mistakes.
  Total=

Conclusion

Over the past month, you have ventured into a mathematics topic like you never thought existed.  Hopefully completing these tasks today have strengthened your knowledge of graph theory and opened you mind to new and exciting ideas.  Always keep in mind that math is unlimited...it will last forever and exists in every facet of life.  There is not a limit to the way problems can be solved, but keep in mind...we, as humans, are always trying to find different ways of preserving time, money, and saving on anything we can.

Credits

Teacher Page

This WebQuest belongs to and was created by Josh Jenkins for use in high school Discrete Mathematics.  Students are encouraged to strengthen and hone their graph theory skills through the use of the WebQuest.