C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Implement the Vizing's Theorem Program to Implement the Vizing's Theorem - This algorithm Implements Vizing's Theorem. - According to this theorem, the chromatic index of the simple graph can be either maxDegree or maxDegree+1. - The chromatic index is the maximum number of color needed for the edge coloring of the graph. - This algorithm takes the input of the number of vertexes and the number of edges in the graph. - It takes the input of vertex pairs for the given number of edges. - It assigns a color to edges without assigning the same color to two adjacent edges. - Exit. #include<iostream> using namespace std; // A function to color edges of the graph. void EdgeColoring(int edge[][3], int e) { int i, col, j; // 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; } } } } } 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], degree[v+1] = {0}; // 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 "<<i+1; cout<<"\nV(1): "; cin>>edge[i][0]; cout<<"V(2): "; cin>>edge[i][1]; edge[i][2] = -1; degree[edge[i][0]]++; degree[edge[i][1]]++; } // Find the maximum degree. for(i = 1; i <= v; i++) { if(max < degree[i]) max = degree[i]; } // Color the edges of the graph. EdgeColoring(edge , e); cout<<"\nAccording to Vizing's theorem this graph can use a maximum of "<<max+1<<" colors to generate a valid edge coloring.\n\n"; for(i = 0; i < e; i++) cout<<"\nThe color of the edge between vertex V(1):"<<edge[i][0]<<" and V(2):"<<edge[i][1]<<" is: color"<<edge[i][2]<<"."; }