Consider the three figures in Figure below. A popular puzzle is to
reconstruct these figures using a pen,
drawing each line exactly once. The pen may not be lifted from the paper while
the drawing is
being performed. As an extra challenge, make the pen finish at the same point
at which it started. This puzzle has a
surprisingly simple solution.
The first figure can be drawn only if the starting point is the lower
left- or right-hand corner, and it
is not possible to finish at the starting point. The second figure is easily
drawn with the
finishing point the same as the starting point, but the third figure cannot be
drawn at all within the parameters of
the puzzle.
We can convert this problem to a graph theory
problem by assigning a vertex to each intersection.Then the edges can be
assigned in the natural manner, as shown in below.
After this conversion is performed, we must find a path in the graph
that visits every edge exactly
once. If we are to solve the "extra challenge," then we must find a
cycle that visits every
edge exactly once. This graph problem was solved in 1736 by Euler and marked the beginning of
graph theory. The problem is thus commonly referred to as an Euler path (sometimes Euler tour) or Euler circuit problem, depending on the
specific problem statement. The Euler tour and Euler circuit
problems, though slightly different, have the same basic solution. Thus, we
will consider the Euler circuit problem
EULER PATH
In graph theory Euler path is a path that visits
each node from the graph exactly once.
EULER CYCLE/EULER CIRCUIT
Euler cycle is a
Euler path that starts and ends with the same node.
EULER GRAPH
Euler graph is a
graph with graph which contains Euler cycle.
EULERS THEOREM
Connected undirected graph is Euler graph if and
only if every node in the graph is of even degree (has even number of edges starting from that node).
Fleury's Algorithm.
1. Pick up a starting Vertex.Condition 1: If all Nodes have even degree, there should be a euler Circuit/Cycle. We can pick up any vertex as starting vertex.
Condition 2: If exactly 2 nodes have odd degree, there should be euler path. We need to pick up any one of this two as starting vertex.
Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible.
2. Get the next vertex in euler Path.
Condition: Don't break the bridge.
i) select the next vertex which has more than one edges.
ii) If next vertex has only one edge,
a) If it is last vertex, We can choose it as next vertex.
b) otherwise dont.
3. Remove the selected edge.
4. Repeat 2 & 3 until all edges have been traversed, and you are back at the starting vertex.
C Program::
#include<stdio.h>
#include<conio.h>
int n;
int b[100],finalPath[100];
char ajMat[100][100];
int fp=0,count=0;
//Display the Euler circuit/path
void displayPath()
{
int i;
for(i=0;i<fp;i++)
{
printf("%d ->",finalPath[i]);
}
}
//To get the degree of node i.e no of edges currently connected to the node
int getDegree(int node)
{
int j,deg=0;
int pos=getIndex(node);
for(j=0;j<n;j++)
{
if(ajMat[pos][j]=='y') deg++;
}
return deg;
}
//To assign the root of the graph
//Condition 1: If all Nodes have even degree, there should be a euler Circuit/Cycle
//We can start path from any node
//Condition 2: If exactly 2 nodes have odd degree, there should be euler path.
//We must start from node which has odd degree
//Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible.
//findRoot() will return 0 if euler path/circuit not possible
//otherwise it will return array index of any node as root
int findRoot()
{
int i,cur=1;//Assume root as 1
for(i=0;i<n;i++)
{
if(getDegree(b[i])%2!=0)
{
count++;
cur=i;//Store the node which has odd degree to cur variable
}
}
//If count is not exactly 2 then euler path/circuit not possible so return 0
if(count!=0 && count!=2)
{
return 0;
}
else return b[cur];// if exactly 2 nodes have odd degree, it will return one of those node as root otherwise return 1 as root as assumed
}
//To get the current index of node in the array b[] of nodes
int getIndex(int node)
{
int k=0;
while(node!=b[k])
k++;
//printf("inside while\n");
//l++;
return k;
}
int isLastNode(int node)
{
int i=0;
int degSum=0;
for(i=0;i<n;i++)
{
degSum=degSum+getDegree(b[i]);
}
if(degSum==2)
return 1;
else
return 0;
}
int getNextNode(int node)
{
int i=0;
int pos=getIndex(node);
for(i=0;i<n;i++)
{
if(ajMat[pos][i]=='y')
{
if(!isHasOneEdge(b[i]))
{
return b[i];
}
else
{
if(isLastNode(b[i]))
return b[i];
}
}
}
return -1;
}
int isHasOneEdge(int node)
{
if(getDegree(node)==1)
return 1;
else
return 0;
}
int isCompleted()
{
int i=0;
for(i=0;i<n;i++)
{
if(getDegree(b[i])>0)
return 0;
}
return 1;
}
void removeEdge(root,eNode)
{
int pos1=0,pos2=0;
pos1=getIndex(root);
pos2=getIndex(eNode);
ajMat[pos1][pos2]='n';
ajMat[pos2][pos1]='n';
}
//To find the Euler circuit/path and store it in finalPath[] array
void eularFind(int root)
{
int eNode;
while(!isCompleted())
{
eNode=getNextNode(root); //get Next node
finalPath[fp++]=eNode; //add the node to euler path
removeEdge(root,eNode); //remove the edge
root=eNode; //change the root
}
/* printf("root=%d\n",root);
eNode=getNextNode(root);
printf("getNextNode=%d \n",eNode);
finalPath[fp++]=eNode;
removeEdge(root,eNode);
root=eNode;*/
}
void printbArray()
{
int i;
for( i=0; i<n; i++)
{
printf("%d ",b[i]);//store the nodes in b[] array
}
}
int main()
{
char v;
int i,j,l;
printf("Enter the number of nodes in a graph\n");
scanf("%d",&n);
printf("Enter the value of node of graph\n");
for( i=0; i<n; i++)
{
scanf("%d",&b[i]);//store the nodes in b[] array
}
//Get the Graph details by using adjacency matrix
printf("Enter the value in adjancency matrix in form of 'Y' or 'N'\n");
printf("\nIf there is an edge between the two vertices then enter 'Y' else 'N'\n");
for( i=0; i<n; i++)
printf(" %d ",b[i]);
for( i=0;i<n; i++)
{
printf("\n%d ",b[i]);
for( j=0; j<n; j++)
{
printf("%c ",v=getch());
ajMat[i][j]=v;
}
printf("\n\n");
}
/* We can manually hard code the Graph value by below. But u need to command the above one to get the edge details.
ajMat[0][0]='n';
ajMat[0][1]='y';
ajMat[0][2]='n';
ajMat[0][3]='y';
ajMat[0][4]='n';
ajMat[0][5]='n';
ajMat[1][0]='y';
ajMat[1][1]='n';
ajMat[1][2]='y';
ajMat[1][3]='n';
ajMat[1][4]='y';
ajMat[1][5]='y';
ajMat[2][0]='n';
ajMat[2][1]='y';
ajMat[2][2]='n';
ajMat[2][3]='y';
ajMat[2][4]='y';
ajMat[2][5]='y';
ajMat[3][0]='y';
ajMat[3][1]='n';
ajMat[3][2]='y';
ajMat[3][3]='n';
ajMat[3][4]='n';
ajMat[3][5]='n';
ajMat[4][0]='n';
ajMat[4][1]='y';
ajMat[4][2]='y';
ajMat[4][3]='n';
ajMat[4][4]='n';
ajMat[4][5]='n';
ajMat[5][0]='n';
ajMat[5][1]='y';
ajMat[5][2]='y';
ajMat[5][3]='n';
ajMat[5][4]='n';
ajMat[5][5]='n';
*/
//findRoot() will return 0 if euler path/circuit not possible
//otherwise it will return array index of any node as root
int root,pos;
if(root=findRoot())
{
if(count) printf("Available Euler Path is\n");
else printf("Available Euler Circuit is\n");
finalPath[fp++]=root;
eularFind(root);
displayPath();
}
else printf("Euler path or circuit not available\n");
getch();
}
Goto Data Structure Concepts
it was very helpful indeed and the encouragement posts also.. keep it up bro :)
ReplyDelete