task 6

EULER PATH	EULER CIRCUITS
Definition : A path in a multigraph that includes exactly once all the edges and has different first and last vertices.	Definition : A circuit that includes exactly once all the edges and has same initial and end vertex.
Example : Different start and ending points. Edges: A: 2    B: 5   C: 3   D:4   E: 2 All even degree except two with odd degree Properties : all vertices have even degree edges and 2 vertices have odd degree of edges.	Example : Same starting and ending points Edges: A: 2   B: 6   C: 4   D: 4   E: 2 All have even degree Properties : all vertices have even degree of edges.

Fluery’s algorithm

To find an Euler path or an Euler circuit:

            1.         Make sure the graph has either 0 or 2 odd vertices.

     2. If there are 0 odd vertices, start anywhere. If there are 2

         odd vertices, start at one of them.

     3. Follow edges one at a time. If you have a choice between

        a bridge and a non-bridge,(always choose the non-bridge).

     4. Stop when you run out of edges.

Hamilton Path

-a path that includes each vertex of the graph once and only once.

Example of Hamilton Path                                                     

                                                     

 

Hamilton Circuit

-a circuit that include each vertex of the graph once and only once.(at the end,the circuit must return to the starting vertex).

Example of Hamilton Circuit

                                       

                                   

Properties that differentiate between Hamilton path and Hamilton Circuit

Hamilton Path	Hamilton Circuit
A simple path in a graph G that passes through every vertex exactly once.	A simple circuit in a graph G that passes through every vertex exactly once except begin/end vertex
Hamilton Path ⇒Hamilton Circuit	Hamilton circuit →Hamilton path
Begin and end vertex always be different	Begin and end vertex must be same
Example: (1,2,3,4,5,6,7,8,9,1)-Hamilton Path	Example: (1,2,3,4,5,6,7,8,9,1)-Hamilton Circuit
	-A graph with a vertex of degree one cannot have a Hamilton circuit. -If a vertex in a graph has degree two, then both edges that are incident to this vertex must be part of any Hamilton circuit.
	Once a vertex is part of the Hamilton circuit ,all other edges of that vertex can be removed
	A Hamilton circuit cannot contain a smaller circuit within it.

algorithm or step by step to determine Hamilton Path and Hamilton Circuit


To determine existence of Hamilton circuit and Hamilton path is

1.  Graph with a vertex of degree one cannot have a Hamilton circuit, because in a    Hamilton      circuit,   each vertex is incident with two edges in the circuit.
2.  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.
3. DIRAC’S Teorem - 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.
4.  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.