Embedded Files
Lesson Learning Outcomes:
Lesson Learning Outcomes:
At the end of this lesson, students will be able to:
Compare the different types of graphs.
Explain paths, cycles and planarity in graphs.
Ascertain the isomorphic graphs.
Construct the Euler paths and Euler circuits in graphs.
Construct the Hamilton paths and Hamilton circuits in graphs.
Apply graphs theories in Travelling Salesman Problem (TSP).
Graphs Part II.pdfPRACTICE: TYPES OF GRAPHS
Types of Graphs practice.pdfEULER & HAMILTON IN GRAPHS
Determine whether the following graph has Euler Path, Euler Circuit, Hamilton Path and Hamilton Circuit or not. Construct the paths and circuits if it exists. If not, give a reason.
Determine whether the following graph has Euler Path, Euler Circuit, Hamilton Path and Hamilton Circuit or not. Construct the paths and circuits if it exists. If not, give a reason.
Determine whether the following graph has Euler Path, Euler Circuit, Hamilton Path and Hamilton Circuit or not. Construct the paths and circuits if it exists. If not, give a reason.
Determine whether the following graph has Euler Path, Euler Circuit, Hamilton Path and Hamilton Circuit or not. Construct the paths and circuits if it exists. If not, give a reason.
PRACTICE: EULER & HAMILTON
Exercise - Euler & Hamilton.pdfApply Graphs Theories in Travelling Salesman Problem
The following steps can be applied in order to solve the Travelling Salesman Problem (TSP).
Write down all Hamiltonian circuits
Compute total distance for each
Pick one for which total is minimal
Travelling Salesman Problem
The following graph shows the four cities and the distance(km) between them.
The following graph shows the four cities and the distance(km) between them.
Suppose that a salesman must travel to each city exactly once, starting and ending in city A.
Suppose that a salesman must travel to each city exactly once, starting and ending in city A.
Which route from city to city will minimize the total distance that must be traveled?
Which route from city to city will minimize the total distance that must be traveled?
Page updated
Report abuse