For each of the graphs shown below, first give an unique name to each edge (e.g.

Question

For each of the graphs shown below, first give an unique name to each edge (e.g., a, b, · · · etc.), and then determine if a graph has Euler path or not, as well as a Hamiltonian cycle or not. If a graph does not have an Euler path, say “No”. If a graph has a Euler path, please list the path using the similar format shown in the previous example: node name, edge name, node name, edge name, · · · , · · · , node name. If a graph does not have an Hamiltonian cycle, say “No”. If a graph has a Hamiltonian cycle, please list the path using the similar format shown in the previous example: node name, edge name, node name, edge name, · · · , · · · , node name.

Explanation / Answer

//solution to find hamilton cycle or not.

//draw the graph inside main function and check whether its having hamiltonian cycle present or not.....

program:

/* C/C++ program for solution of Hamiltonian Cycle problem
using backtracking */
#include<stdio.h>

// Number of vertices in the graph
#define V 10

void printSolution(int path[]);

/* A utility function to check if the vertex v can be added at
index 'pos' in the Hamiltonian Cycle constructed so far (stored
in 'path[]') */
bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
   /* Check if this vertex is an adjacent vertex of the previously
   added vertex. */
   if (graph [ path[pos-1] ][ v ] == 0)
       return false;

   /* Check if the vertex has already been included.
   This step can be optimized by creating an array of size V */
   for (int i = 0; i < pos; i++)
       if (path[i] == v)
           return false;

   return true;
}

/* A recursive utility function to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
   /* base case: If all vertices are included in Hamiltonian Cycle */
   if (pos == V)
   {
       // And if there is an edge from the last included vertex to the
       // first vertex
       if ( graph[ path[pos-1] ][ path[0] ] == 1 )
       return true;
       else
       return false;
   }

   // Try different vertices as a next candidate in Hamiltonian Cycle.
   // We don't try for 0 as we included 0 as starting point in in hamCycle()
   for (int v = 1; v < V; v++)
   {
       /* Check if this vertex can be added to Hamiltonian Cycle */
       if (isSafe(v, graph, path, pos))
       {
           path[pos] = v;

           /* recur to construct rest of the path */
           if (hamCycleUtil (graph, path, pos+1) == true)
               return true;

           /* If adding vertex v doesn't lead to a solution,
           then remove it */
           path[pos] = -1;
       }
   }

   /* If no vertex can be added to Hamiltonian Cycle constructed so far,
   then return false */
   return false;
}

/* This function solves the Hamiltonian Cycle problem using Backtracking.
It mainly uses hamCycleUtil() to solve the problem. It returns false
if there is no Hamiltonian Cycle possible, otherwise return true and
prints the path. Please note that there may be more than one solutions,
this function prints one of the feasible solutions. */
bool hamCycle(bool graph[V][V])
{
   int *path = new int[V];
   for (int i = 0; i < V; i++)
       path[i] = -1;

   /* Let us put vertex 0 as the first vertex in the path. If there is
   a Hamiltonian Cycle, then the path can be started from any point
   of the cycle as the graph is undirected */
   path[0] = 0;
   if ( hamCycleUtil(graph, path, 1) == false )
   {
       printf(" Solution does not exist");
       return false;
   }

   printSolution(path);
   return true;
}

/* A utility function to print solution */
void printSolution(int path[])
{
   printf ("Solution Exists:"
           " Following is one Hamiltonian Cycle ");
   for (int i = 0; i < V; i++)
       printf(" %d ", path[i]);

   // Let us print the first vertex again to show the complete cycle
   printf(" %d ", path[0]);
   printf(" ");
}

// driver program to test above function
int main()
{

   bool graph1[V][V] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0 },
   {1, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
   {0, 1, 0, 1, 0, 0, 0, 1, 0, 0 },
   {0, 0, 1, 0, 1, 0, 0, 0, 1, 0 },
   {1, 0, 0, 1, 0, 0, 0, 0, 0, 1 },
   {1, 0, 0, 0, 0, 0, 0, 1, 1, 0 },
   {0, 1, 0, 0, 0, 0, 0, 0, 1, 1 },
   {0, 0, 1, 0, 0, 1, 0, 0, 0, 1 },
   {0, 0, 0, 1, 0, 1, 1, 0, 0, 0 },
   {0, 0, 0, 0, 1, 0, 1, 1, 0, 0 },
                  
                   };

   // Print the solution
   hamCycle(graph1);
  
// Let us create the following graph
/*
   bool graph2[V][V] = {{0, 1, 0, 1, 0 ,0 ,1 },
                   {1, 0, 1, 0, 0, 1 ,0 },
                   {0, 1, 0, 1, 0, 0 ,1 },
                   {1, 0, 1, 0, 1, 0 ,0 },
                   {0, 0, 0, 1, 0, 1 ,1 },
                   {0, 1, 0, 0, 1, 0,1 },
                   {1, 0, 1, 0, 1, 1 ,0 },
                   };

   // Print the solution
   hamCycle(graph2);
*/
   return 0;
}

output:

1.solution doesnt exist

Fleury’s Algorithm for printing Eulerian trail or cycle

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.

//solution to find euler path

//draw the graph inside main function and check whether its having hamiltonian cycle present or not.....

program:

// A C++ program to check if a given graph is Eulerian or not
#include<iostream>
#include <list>
using namespace std;

// A class that represents an undirected graph
class Graph
{
   int V; // No. of vertices
   list<int> *adj; // A dynamic array of adjacency lists
public:
   // Constructor and destructor
   Graph(int V) {this->V = V; adj = new list<int>[V]; }
   ~Graph() { delete [] adj; } // To avoid memory leak

   // function to add an edge to graph
   void addEdge(int v, int w);

   // Method to check if this graph is Eulerian or not
   int isEulerian();

   // Method to check if all non-zero degree vertices are connected
   bool isConnected();

   // Function to do DFS starting from v. Used in isConnected();
   void DFSUtil(int v, bool visited[]);
};

void Graph::addEdge(int v, int w)
{
   adj[v].push_back(w);
   adj[w].push_back(v); // Note: the graph is undirected
}

void Graph::DFSUtil(int v, bool visited[])
{
   // Mark the current node as visited and print it
   visited[v] = true;

   // Recur for all the vertices adjacent to this vertex
   list<int>::iterator i;
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
       if (!visited[*i])
           DFSUtil(*i, visited);
}

// Method to check if all non-zero degree vertices are connected.
// It mainly does DFS traversal starting from
bool Graph::isConnected()
{
   // Mark all the vertices as not visited
   bool visited[V];
   int i;
   for (i = 0; i < V; i++)
       visited[i] = false;

   // Find a vertex with non-zero degree
   for (i = 0; i < V; i++)
       if (adj[i].size() != 0)
           break;

   // If there are no edges in the graph, return true
   if (i == V)
       return true;

   // Start DFS traversal from a vertex with non-zero degree
   DFSUtil(i, visited);

   // Check if all non-zero degree vertices are visited
   for (i = 0; i < V; i++)
   if (visited[i] == false && adj[i].size() > 0)
           return false;

   return true;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian) */
int Graph::isEulerian()
{
   // Check if all non-zero degree vertices are connected
   if (isConnected() == false)
       return 0;

   // Count vertices with odd degree
   int odd = 0;
   for (int i = 0; i < V; i++)
       if (adj[i].size() & 1)
           odd++;

   // If count is more than 2, then graph is not Eulerian
   if (odd > 2)
       return 0;

   // If odd count is 2, then semi-eulerian.
   // If odd count is 0, then eulerian
   // Note that odd count can never be 1 for undirected graph
   return (odd)? 1 : 2;
}

// Function to run test cases
void test(Graph &g)
{
   int res = g.isEulerian();
   if (res == 0)
       cout << "graph is not Eulerian ";
   else if (res == 1)
       cout << "graph has a Euler path ";
   else
       cout << "graph has a Euler cycle ";
}

// Driver program to test above function
int main()
{
   // Let us create and test graphs shown in above figures
   Graph g1(5);
   g1.addEdge(1, 0);
   g1.addEdge(0, 2);
   g1.addEdge(2, 1);
   g1.addEdge(0, 3);
   g1.addEdge(3, 4);
   test(g1);

   Graph g2(5);
   g2.addEdge(1, 0);
   g2.addEdge(0, 2);
   g2.addEdge(2, 1);
   g2.addEdge(0, 3);
   g2.addEdge(3, 4);
   g2.addEdge(4, 0);
   test(g2);

   Graph g3(5);
   g3.addEdge(1, 0);
   g3.addEdge(0, 2);
   g3.addEdge(2, 1);
   g3.addEdge(0, 3);
   g3.addEdge(3, 4);
   g3.addEdge(1, 3);
   test(g3);

   // Let us create a graph with 3 vertices
   // connected in the form of cycle
   Graph g4(3);
   g4.addEdge(0, 1);
   g4.addEdge(1, 2);
   g4.addEdge(2, 0);
   test(g4);

   // Let us create a graph with all veritces
   // with zero degree
   Graph g5(3);
   test(g5);

   return 0;
}

output:

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.