# Ch 9: Graph Theory

## 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
Test your knowledge with a 30-question chapter practice test
Chapter Practice Exam
Test your knowledge of this chapter with a 30 question practice chapter exam.
Not Taken
Practice Final Exam
Test your knowledge of the entire course with a 50 question practice final exam.
Not Taken

### 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.