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]<<".";
}