MATH1180 Lecture Notes - Lecture 2: Hamiltonian Path, Glossary Of Graph Theory Terms, K-Nearest Neighbors Algorithm
10 Oct 2016
School
Department
Course
Professor
4.2 The Traveling Sales Person Problem
Hamilton Paths
➢ A path that passes through all the vertices of a graph exactly once.
• If a Hamilton path begins and ends at the same vertex, then it is a Hamilton circuit. If a
graph has a Hamilton circuit, then is a Hamiltonian.
Complete Graph: one in which every pair of vertices is joined by an edge.
Kn: When n equals the number of vertices.
Factorial: ! (ex: 3! = factorial 3)
• n! means multiply all the natural numbers from 1 to n.
Examples:
▪ 5! = 5x4x3x2x1 = 120
▪ 4! = 4x3x2x1 = 24
▪ 3! = 3x2x1 = 6
▪ 2! = 2x1 = 2
▪ 1! = 1
▪ 0! = 1
▪ 4 vertices = 3! Hamilton circuits = 6
▪ 5 vertices = 4! Hamilton circuits = 24
Solving the TSP by Brute Force
• When we assign numbers to the edges of a graph, the graph is called a weighted graph
and the numbers on the edges are called weights. The weight of a path in a weighted
graph is the sum of the weights of the edges of a path.
Method 1: The nearest neighbor algorithm
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
A path that passes through all the vertices of a graph exactly once. If a hamilton path begins and ends at the same vertex, then it is a hamilton circuit. If a graph has a hamilton circuit, then is a hamiltonian. Complete graph: one in which every pair of vertices is joined by an edge. Kn: when n equals the number of vertices. = factorial 3: n! means multiply all the natural numbers from 1 to n. Hamilton circuits = 6: 5 vertices = 4! Solving the tsp by brute force: when we assign numbers to the edges of a graph, the graph is called a weighted graph and the numbers on the edges are called weights. The weight of a path in a weighted graph is the sum of the weights of the edges of a path. Step 1: find the edge with the smallest weight. Step 2: find the edge with the next lowest weight.
