1) Give the definition and example for each of the following term:

a) Euler Path

     -Euler Path is a path in the graph that passes each edge only once.

       Example:

 

 

    b) Euler Circuit

     -Euler Circut is a path in the graph that passes each edge only once and return back to its original position.

Example :

 

2)  Determine what are the properties that differentiate between (a) and (b) in Question 1?

         -Degree of Nodes: Number of Edges on a vertex

          -Euler Path existence: not have more than 2 vertices of odd-degree nodes exist in the graph.

          -Euler Circuit existence: no odd-degree nodes exist in the graph.

 

3) What are the algorithm or step by step to determine (a) and (b) in    Question 1

        -Choose a random vertex

        -Pick an arbitrary edge joined to another vertex and mark the edge.

       -Marked edges cannot be passed again. The above procedure is repeated until all edges are  covered.

 

4) Give the definition and example for each of the following term:

           a) Hamilton Path

                -A path visits each vertex of a graph once and only once.

            Example :

 

           

  b) Hamilton Circuit

                  -Hamilton circuit is a cycle in an undirected graph which visits each vertex exactly once and   also returns to the starting vertex.

Example :

 

 

Question 5.

Hamilton Path – a simple path that passes  through EVERY VERTEX ONCE.

Hamilton Circuit – a simple circuit that passes through EVERY VERTEX EXACTLY ONCE.

 

Question 6.

Nearest Neighbor Algorithm

 1. Choose a starting vertex. (Let take D as starting vertex)

2. The next vertex chosen is the one “nearest” (smallest weight) that has not been visited.  If tie choose one.  Mark the edges covered as they are added to the path.

3. If all vertices have not been visited then repeat step 2 otherwise return to the start.