Code:
#include iostream
using namespace std;
// A function to color edges of the graph.
int EdgeColoring(int edge[][3], int e)
{
int i, col, j, max = -1;
// Loop to assign a valid color to every edge 'i'.
for(i = 0; i < e; i++)
{
col = 1;
flag:
// Assign a color and then check its validity.
edge[i][2] = col;
for(j = 0; j < e; j++)
{
if(j == i)
continue;
// Check the colors of the edges adjacent to the edge i.
if(edge[j][0] == edge[i][0] || edge[j][0] == edge[i][1] || edge[j][1] == edge[i][0] || edge[j][1] == edge[i][1])
{
// If the color matches then goto line 11 and assign next color to the edge and check again.
if(edge[j][2] == edge[i][2])
{
col++;
goto flag;
}
}
}
}
// Find the coloring index and return it, to main.
for(i = 0; i < e; i++)
{
if(max < edge[i][2])
max = edge[i][2];
}
return max;
}
int main()
{
int i, v, e, j, max = -1;
// take the input of the number of vertex and edges.
cout<<"Enter the number of vertexes of the graph: ";
cin>>v;
cout<<"Enter the number of edges of the graph: ";
cin>>e;
int edge[e][3];
// Take the input of the adjacent vertex pairs of the given graph.
for(i = 0; i < e; i++)
{
cout<<"\nEnter the vertex pair for edge "<
cout<<"\nV(1): ";
cin>>edge[i][0];
cout<<"V(2): ";
cin>>edge[i][1];
edge[i][2] = -1;
}
// Print the chromatic index.
cout<<"\n\nThe chromatic index of the given graph is: "<
// Print the edge color for the edges of the given graph.
for(i = 0; i < e; i++)
cout<<"\nThe color of the edge between vertex V(1):"<
return 0;
}
Output:
Case 1:
Enter the number of vertexes of the cyclic graph: 5
Enter the number of edges of the cyclic graph: 7
Enter the vertex pair for edge 1
V(1): 1
V(2): 2
Enter the vertex pair for edge 2
V(1): 2
V(2): 3
Enter the vertex pair for edge 3
V(1): 3
V(2): 4
Enter the vertex pair for edge 4
V(1): 4
V(2): 5
Enter the vertex pair for edge 5
V(1): 1
V(2): 3
Enter the vertex pair for edge 6
V(1): 2
V(2): 4
Enter the vertex pair for edge 7
V(1): 5
V(2): 1
The chromatic index of the given graph is: 4
The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):2 and V(2):3 is: color2.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):4 and V(2):5 is: color2.
The color of the edge between vertex V(1):1 and V(2):3 is: color3.
The color of the edge between vertex V(1):2 and V(2):4 is: color3.
The color of the edge between vertex V(1):5 and V(2):1 is: color4.
Case 2:
Enter the number of vertexes of the cyclic graph: 4
Enter the number of edges of the cyclic graph: 4
Enter the vertex pair for edge 1
V(1): 1
V(2): 2
Enter the vertex pair for edge 2
V(1): 2
V(2): 3
Enter the vertex pair for edge 3
V(1): 3
V(2): 4
Enter the vertex pair for edge 4
V(1): 4
V(2): 1
The chromatic index of the given graph is: 2
The color of the edge between vertex V(1):1 and V(2):2 is: color1.
The color of the edge between vertex V(1):2 and V(2):3 is: color2.
The color of the edge between vertex V(1):3 and V(2):4 is: color1.
The color of the edge between vertex V(1):4 and V(2):1 is: color2.
More C++ Programs:
