10.5 Euler and Hamilton Paths Flashcards
Euler Circuits and Euler paths :
An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path
in G is a simple path containing every edge of G.
NECESSARY AND SUFFICIENT CONDITIONS FOR EULER CIRCUITS
Recall that text theory behind it.
A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.
ALGORITHM 1 Constructing Euler Circuits.
Another algorithm for constructing Euler circuits, called Fleury’s algorithm, is described
in the premble to Exercise 50.
procedure Euler(G: connected multigraph with all vertices of
even degree)
circuit := a circuit in G beginning at an arbitrarily
chosen vertex with edges successively added to
form a path that returns to this vertex
H := G with the edges of this circuit removed
while H has edges
subcircuit := a circuit in H beginning at a vertex in H
that also is an endpoint of an edge of
circuit
H := H with edges of subcircuit and all isolated
vertices removed
circuit := circuit with subcircuit inserted at the
appropriate vertex
return circuit {circuit is an Euler circuit}
Worst case complexity of ALGORITHM 1 Constructing Euler Circuits.
We leave it to the reader (Exercise 66) to show that
the worst case complexity of this algorithm is O(m), where m is the number of edges of G
NECESSARY AND SUFFICIENT CONDITIONS FOR EULER PATHS
Reason it, think of theory before the thm..
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly
two vertices of odd degree.
Necessary and sufficient conditions for Euler paths and circuits in directed graphs :
are given
in Exercises 16 and 17
APPLICATIONS OF EULER PATHS AND CIRCUITS
hint:
Chinese postman problem
The problem of finding a circuit in a graph
with the fewest edges that traverses every edge at least once is known as the Chinese postman problem.
Among the other areas where Euler circuits and paths are applied is in the layout of circuits,
in network multicasting, and in molecular biology, where Euler paths are used in the sequencing
of DNA.
Hamilton Paths and Circuits
Definition 2:
A simple path in a graph G that passes through every vertex exactly once is called a Hamilton
path, and a simple circuit in a graph G that passes through every vertex exactly once is called
a Hamilton circuit. That is, the simple path x0, x1, … , xn−1, xn in the graph G = (V, E) is a
Hamilton path if V = {x0, x1, … , xn−1, xn} and xi ≠ xj for 0 ≤ i < j ≤ n, and the simple circuit
x0, x1, … , xn−1, xn, x0 (with n > 0) is a Hamilton circuit if x0, x1, … , xn−1, xn is a Hamilton
path.
history of hamilton.. u can skip it
This terminology comes from a game, called the Icosian puzzle, invented in 1857 by the
Irish mathematician Sir William Rowan Hamilton. It consisted of a wooden dodecahedron [a
polyhedron with 12 regular pentagons as faces, as shown in Figure 8(a)], with a peg at each
vertex of the dodecahedron, and string. The 20 vertices of the dodecahedron were labeled with
different cities in the world. The object of the puzzle was to start at a city and travel along the
edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the
first city. The circuit traveled was marked off using the string and pegs.
CONDITIONS FOR THE EXISTENCE OF HAMILTON CIRCUITS:
5
There are no known simple necessary and sufficient criteria for the existence of Hamilton circuits.
However,
1. some thms give sufficient conftn to exist.
2. Few properties tell it won’t exist.
- Graph with deg = 1 won’t have this circuit.
-In hamilton circuit each vertex is incident with 2 edges.
- If a vertex in the graph has degree two, then
both edges that are incident with this vertex must be part of any Hamilton circuit.
- While constructing this circuit, if the circuit has passed through a vertex, then all
remaining edges incident with this vertex, other than the two used in the circuit, can be removed
from consideration.
- Hamilton circuit cannot contain a smaller circuit within it.
Hamilton Circuits.
Comment on complete graphs:
Kn has a Hamilton circuit whenever n ≥ 3.Such a circuit can be
built by visiting vertices in any order we choose, as long as the path begins and ends at the same
vertex and visits each other vertex exactly once. This is possible because there are edges in Kn
between any two vertices.
When is existence of hamilton Circuit more likely:
More edges a graph has more likely it is.
So as we add edges to a graph, especially when we make sure to add edges to each vertex, we
make it increasingly likely that a Hamilton circuit exists in this graph.
Consequently, we would
expect there to be sufficient conditions for the existence of Hamilton circuits that depend on
the degrees of vertices being sufficiently large.
DIRAC’S THEOREM
Dirac’s theorem can be proved as a corollary to Ore’s theorem because the conditions of Dirac’s theorem imply those of Ore’s theorem
If G is a simple graph with n vertices with n ≥ 3 such that the
degree of every vertex in G is at least n∕2, then G has a Hamilton circuit.
ORE’S THEOREM
The proof of Ore’s theorem is outlined in Exercise 65
If G is a simple graph with n vertices with n ≥ 3 such that
deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a
Hamilton circuit.
Direc and Ore are sufficient. Show a counter example to show that its not necessary:
C5.
It doesn’t satisfy direc or ore but has a Hamilton circuit.
