Login

Ch 9: Graph Theory

About This Chapter

Watch video lessons and learn about graph theory concepts. The quizzes that follow each of the lessons can help you gauge your comprehension of the materials.

Graph Theory - Chapter Summary and Learning Objectives

In basic terms, graph theory is all about examining graphs, but more specifically graph theory is closely tied to mapping out travel logistics. In the professional world, map theory helps businesses determine the most effective and productive ways to move or distribute goods between different plotted points. Our instructors will tell you about the vocabulary terms and mathematical equations you will need to know to understand graph theory. At the end of this chapter, you should feel more skilled about the following topics:

  • Basic graph terminology
  • Paths and circuits
  • Completed and weighted graphs
  • Calculating the most efficient circuits
  • The traveling salesman dilemma

Video Objective
Introduction to Graph Theory Learn how to define mathematical graphs, and to recognize loops, vertices, and edges.
Graph Theory Concepts and Terminology Discover the meaning of an isolated vertex as well as connected and disconnected graphs.
Euler Paths and Euler's Circuits Learn to define and provide examples of each of these terms.
Mathematical Models of Euler's Circuits and Euler's Paths Gain practice in solving real-life problems by using Euler circuit and Euler path concepts.
Euler's Theorems: Circuit, Path and Sum of Degrees Learn how to identify graphs that have Euler's circuits or paths.
Fleury's Algorithm for Finding an Euler Circuit Use this algorithm to locate Euler's circuit or path.
Eulerizing Graphs in Math Discover how to identify the optimal eulerization of graphs.
Hamilton Circuits and Hamilton Paths Learn how to model these kinds of problems.
Assessing Weighted and Complete Graphs for Hamilton Circuits Explore the differences between approximate and optimal algorithms, and identify the number of Hamilton circuits in a complete graph.
The Traveling Salesman Problem in Computation Discover how to identify and solve these problems.
Methods of Finding the Most Efficient Circuit Find ways of implementing nearest-neighbor, brute-force and repeated nearest-neighbor algorithms to find solutions to problems. Also, learn about efficient and inefficient algorithms.

11 Lessons in Chapter 9: Graph Theory
Introduction to Graph Theory

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.

Graph Theory Concepts and Terminology

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.

Euler Paths and Euler's Circuits

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.

Mathematical Models of Euler's Circuits & Euler's Paths

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.

Euler's Theorems: Circuit, Path & Sum of Degrees

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.

Fleury's Algorithm for Finding an Euler Circuit

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.

Eulerizing Graphs in Math

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.

Hamilton Circuits and Hamilton Paths

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!

Assessing Weighted & Complete Graphs for Hamilton Circuits

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.

The Traveling Salesman Problem in Computation

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.

Methods of Finding the Most Efficient Circuit

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 95 college courses that prepare you to earn credit by exam that is accepted by over 2,000 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.

Support