About This Chapter
Below is a sample breakdown of the Graph Theory chapter into a 5-day school week. Based on the pace of your course, you may need to adapt the lesson plan to fit your needs.
|Day||Topics||Key Terms and Concepts Covered|
|Monday||Graph theory intro and basic concepts||Graph theory, types of vertices, degree of a vertex, edges, path and disconnected and connected graphs|
|Tuesday||Euler paths, circuits and theorems||Euler path, semi-Eulerian, Euler circuit, Eulerian and Euler's circuit and path theorems|
|Wednesday||Fleury's algorithm and Eulerizing graphs||Fleury's algorithm and Eulerizing and semi-Eulerizing graphs|
|Thursday||Hamilton circuits and paths||Hamilton path, Hamilton circuit, weighted and complete graphs|
|Friday||The traveling salesman problem||Solving the traveling salesman problem, nearest and repeated nearest neighbor approaches, brute force method and the cheapest link method|
1. Introduction to Graph Theory
After watching this video lesson, you will understand what graph theory is. You will also see what a graph looks like and be introduced to the basic vocabulary used in graph theory.
2. Graph Theory Concepts and Terminology
After watching this video lesson, you will better understand the workings of a graph in graph theory. Learn the key terms that you will see and what they look like on the graph. Also, learn how to navigate a graph.
3. Euler Paths and Euler's Circuits
Watch this video lesson, and you will see how you can turn a math problem into a challenging brain game. Learn what it means for a graph to be Eulerian or semi-Eulerian.
4. Mathematical Models of Euler's Circuits & Euler's Paths
Watch this video lesson to see how Euler paths and circuits are used in the real world. Learn how to solve real-world problems by drawing a graph and finding Euler paths and circuits.
5. Euler's Theorems: Circuit, Path & Sum of Degrees
Watch this video lesson, and you will understand how Euler's circuit theorem, Euler's path theorem, and Euler's sum of degrees theorem will help you analyze graphs. Also, get some practice with the quiz.
6. Fleury's Algorithm for Finding an Euler Circuit
In this video lesson, you will learn a method for finding an Euler circuit. Learn the one criterion that is the basis for all your decisions when choosing a route.
7. Eulerizing Graphs in Math
After watching this video lesson, you will be able to Eulerize any graph. Learn what it takes to create a Eulerian graph from a non-Eulerian graph. Learn what Fleury's algorithm has to do with all of this.
8. Hamilton Circuits and Hamilton Paths
After watching this video lesson, you will be able to determine how many Hamilton circuits a particular graph has, as well as find Hamilton circuits and paths in these graphs. Then, check out our quiz questions to test your new knowledge!
9. Assessing Weighted & Complete Graphs for Hamilton Circuits
Watch this video lesson and you will discover how to find a Hamilton circuit in a weighted graph. You'll also learn how to find the number of Hamilton circuits in a complete graph.
10. The Traveling Salesman Problem in Computation
Watch this video lesson to learn about the traveling salesman problem. Learn how to identify these types of problems. This is a problem that even computers have a hard time figuring out. Learn why this is so.
11. Methods of Finding the Most Efficient Circuit
After watching this video lesson, you will understand several ways in which you can solve the famous traveling salesman problem. You'll also learn the drawbacks to each solution method.
Earning College Credit
Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.
To learn more, visit our Earning Credit Page
Transferring credit to the school of your choice
Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.
Other chapters within the Contemporary Math Syllabus Resource & Lesson Plans course
- Mathematical Reasoning Lesson Plans
- Solving Math Word Problems Lesson Plans
- Statistics Overview Lesson Plans
- Probability Overview Lesson Plans
- Discrete Probability Distributions Lesson Plans
- Continuous Probability Distributions Lesson Plans
- The Mathematics of Voting Lesson Plans
- The Mathematics of Apportionment Lesson Plans