Graphs: Hamiltonian Path and Circuit

A Hamiltonian path is a path that visits each vertex of the graph exactly once.
A Hamiltonian circuit is a path that uses each vertex of a graph exactly once and returns to the starting vertex.

1. Graphs: Hamiltonian Path
and Circuits
By Prof. Liwayway Memije-Cruz

2. Irish mathematician
who contributed to the
development of optics,
dynamics, and algebra
—in particular,
discovering the algebra
of quaternions. His
work proved significant
for the development of
quantum mechanics.
William Rowan Hamilton

3. https://youtu.be/AamHZhAmR7o

4. Hamiltonian Path and Circuit
A Hamiltonian path is a path that visits
each vertex of the graph exactly once.
A Hamiltonian circuit is a path that uses
each vertex of a graph exactly once and
returns to the starting vertex. A graph that
contains a Hamiltonian circuit is called
Hamiltonian.

5.  In Euler circuits, we looked at closed paths that use
every edge exactly once, possibly visiting a vertex
more than once.
 In Hamiltonian circuits, we look at paths that visit
each vertex exactly once, possibly not passing
through some of the edges.
 But unlike the Euler circuit, where the Eulerian
Graph Theorem is used to determine whether it
contains an Euler circuit or not, we do not have a
straightforward criterion to determine whether or not
a Hamiltonian circuit exists in a graph.

6. Finding Hamilton circuit

7. Determine whether the graph below is Hamiltonian
or not. If it is, find a Hamiltonian circuit. If it is not,
explain why?
Answer: A – B – C – E – D – F – G – A.

8. Dirac’s Theorem
https://www.youtube.com/watch?
v=OGh5JKso0y4

9. Dirac’s Theorem
Consider a connected graph with at least three vertices and no
multiple edges. Let n be the number of vertices in the graph. If
every vertex has degree of at least n/2, then the graph must be
Hamiltonian.

10. Application of Hamiltonian Circuit
The graph below shows
the available flights of a
popular
airline. An edge between
two vertices indicates that
there
is a direct flight between
the two cities. Determine
whether
the graph is Hamiltonian.
If it is, find a Hamiltonian
circuit.

11. Solution
There are ten vertices in the graph, and n/2 =5 . Now,
vertex Manila has 9 edges, Tokyo 5, Seoul 5, Taipei 6,
Hongkong 7, Macau 9, Ho Chi Minh 5, Kuala Lumpur 5,
and Singapore5. Using Dirac’s theorem, the graph is
Hamiltonian.
This means that the graph contains a circuit that visits each
vertex and return to its starting point without visiting a
vertex more than once.
By trial and error, one Hamiltonian circuit is Manila –
Tokyo – Seoul – Taipei – Hongkong – Macau – Bangkok –
Ho Chi Minh – Kuala Lumpur – Singapore – Manila.

12. Remember:
If the graph does not meet the requirements
of the Dirac’s Theorem, it still might be
Hamiltonian.

13. Exercises:
(Aufmann) Use Dirac’s theorem to verify that the
graph is Hamiltonian. Then find a Hamiltonian
circuit.

14. Weighted Graph
A weighted graph is a graph in which each
edge is associated with a value, called a
weight.

15. Travelling Salesman Problem
The travelling salesman problem (TSP) asks the
following question: "Given a list of cities and the
distances between each pair of cities, what is the
shortest possible route that visits each city exactly
once and returns to the origin city?“
The travelling salesman problem consists of a
salesman and a set of cities. The salesman has to
visit each one of the cities starting from a certain
one (e.g. the hometown) and returning to the same
city. The challenge of the problem is that the
travelling salesman wants to minimize the total
length of the trip.

16. Example: Travelling Salesman Problem
The table below lists down the distances (miles) between
the cities having direct routes as well as the corresponding
distances between them.
Draw a graph the represents this information and find two
different routes that visit each of the places and return to its
starting point without visiting any city twice.

17. Example: Travelling Salesman Problem

18. Example: Travelling Salesman Problem

19. The Greedy Algorithm
A method of finding a Hamiltonian circuit in a complete
weighted graph is given by the following greedy algorithm.
1.Choose a vertex to start at, then travel along the connected
edge that has the smallest weight.
2.After arriving at the next vertex, travel along the edge of
smallest weight that connects to a vertex not yet visited.
Continue this process until you have visited all vertices.
3.Return to the starting vertex.
Take Note:
The greedy algorithm attempts to give a circuit of
minimal total weight, although it does not always
succeed.

20. Example
Aaron, Belle, Carol, Donna, Eric, and Fe are best of
friends. The figure below shows the distances (km)
from a friend’s place to another. If Aaron wants to
visit each of his friends’ houses exactly once, what is
the shortest route that he must take?

21. Solution

22. The Edge-Picking Algorithm
Another method of finding a Hamiltonian circuit in
a complete weighted graph is given by the
following edge-picking algorithm.
1.Mark the edge of smallest weight in the graph.
2.Mark the edge of the next smallest weight in the
graph, as long as it does not complete a circuit and
does not add a third marked edge to a single vertex.
3.Continue the process until you can no longer mark
any edges. Then mark the final edge that completes
the Hamiltonian circuit.

23. The Edge-Picking Algorithm
Aaron, Belle, Carol, Donna, Eric, and Fe are best of friends.
The figure below shows the distances (km) from a friend’s
place to another. If Aaron wants to visit each of his friends’
houses exactly once, what is the shortest route that he must
take?

24. Solution
First we mark the line segment from Aaron’s house to Belle’s
house, of weight 1.
Next we mark the segment from Belle’s to Carol’s house, of
weight 2, followed by Carol’s to Donna’s house, of weight 3,
followed by Eric’s to Fe’s house, of weight 6.
Take note that we cannot mark the segment from Eric’s house to
Aaron’s because it can complete a circuit. Also, we cannot mark
the segment from Carol’s to Fe’s house because it can make the
third marked edge on a vertex.
Finally to complete the circuit, we mark the line segment from
Fe’s house back to Aaron’s.
The final Hamiltonian circuit, of total weight
1+2+3+6+9+12=33, is Aaron’s house – Belle’s house – Carol’s
house – Donna’s house – Eric’s house – Fe’s house and back to
Aaron’s.

25. The edge-picking algorithm attempts
to give a circuit of minimal total
weight, although it does not always
succeed.
Remember

26. Application
The table shows the lengths of cables needed to
connect computers to create a network. Find the
minimum length of cable material needed using the
edge-picking algorithm.
A B C D E F
A -- 10 22 9 15 8
B 10 -- 12 14 16 5
C 22 12 -- 14 9 15
D 9 14 14 -- 7 16
E 15 16 9 7 -- 13
F 8 5 16 15 13 --

27. Planar Graphs
A planar graph is a graph that can be drawn so
that no edges intersect each other (except at
vertices).

28. Platonic solids

29. Subgraphs
A part of a graph G is called a subgraph of G.
Subgraph Theorem
“If a graph G has a subgraph that is not planar, the G is also not
planar. In particular, if contains the Utilities Graph or K5 as a
subgraph, G is not planar.”
Nonplanar Graph Theorem
A graph is nonplanar if and only if it has the Utilities Graph or
K5 as a subgraph, or it has a subgraph that can be contracted to
the Utilities Graph or K5.

30. https://youtu.be/Cxdyh7A4-Ho
Euler’s Formula

31. Euler’s Formula
In a connected planar graph drawn with no
intersecting edges, let v be the number of vertices, e
the number of edges, and f the number of faces.
Then v + f = e + 2.

32. Graph Coloring
If the map is divided into regions in some manner, what is
the minimum number of colors required if the neighboring
regions are to be colored differently?
There is a connection between map coloring and graph
theory. Maps can be modeled by graphs using the
countries as the vertices and two vertices (countries) are
adjacent if they share a common boundary.
In graph coloring, each vertex of a graph will be assigned
one color in such away that no two adjacent vertices have
the same color. The interesting idea here is to determine
the minimum number of (distinct) colors to be used so that
we can color each vertex of a graph with no two adjacent
vertices have the same color

33. Four-Color Theorem
The minimum number of colors needed to color a
graph so that no edge connects vertices of the same
color is called the chromatic number.
Four-Color Theorem
The chromatic number of a planar graph is utmost 4.

34. 2-Colorable Graph Theorem
A graph is 2-colorable if and only if it has no circuits
that consist of an odd number of vertices
Determine whether the graph is 2-colorable

35. Scheduling Problem
Six college accreditation committees need to hold
meetings on the same day, but some teachers
belong to more than one committee. In order to
avoid members missing meetings, the meetings
need to be scheduled during different time slots.
An “X” in the table indicates that the two
corresponding committees share at least one
member. Use graph coloring to determine the
minimum number of time slots necessary to
ensure that all faculty members can attend all
meetings.

36. Table
Committee Faculty
Instruction
(FI)
Faculty
Development
(FD)
Outreach
Program
(OP)
Physica
l
Facility
(PF)
Library
Facility
(LF)
Student
Welfare
(SW)
Faculty Instruction X X X
Faculty
Development
X X X X
Outreach Program X X X X
Physical Facility X X X
Library Facility X X X X
Student Welfare X X X X

37. Solution
First we draw a graph representing the six committees using six
vertices or nodes in any configuration. An edge connects two
committees that share at least one member.
Then assign each vertex of the graph with one color in such a
way that no two adjacent vertices have the same color.

38. Conclusion
Obviously, the graph is not 2-colorable because we
can find circuits of odd length but the graph is 3-
colorable. Hence, the minimum number of time slots
necessary to ensure that all faculty members can
attend all meetings is 3.
Schedule of Meetings
First time slot: Faculty Instruction, Student
Welfare
Second time slot: Faculty Development,
Outreach
Program
Third time slot: Library Facility, Physical Facility

39. References:
https://www.coursera.org/lecture/discrete-mathematics/hamilton-cycles-ores-and-diracs-theorem-GOTRs
https://www.britannica.com/biography/William-Rowan-Hamilton
http://math.gmu.edu/~tlim/DiracTheorem.pdf
Baltazar, Ethel Cecille M. Mathematics in the Modern World by C & E
Publishing Inc. 2018
Aufmann et al, Mathematical Excursions (2013)
Baltazar, Ethel Cecille M.
Mame, Neil (Batangas State University),
Manalang, Rodman (UE Manila),
Maquiling Rene (Xavier University),
Mocorro, Ronald (Leyte Normal University) – Powerpoint
Presentation (2017)