C++ Program to Implement the Vizing’s Theorem - Computer Programming

# Computer Programming

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

## Tuesday, September 26, 2017

Write a C++ Program to Implement the Vizing’s Theorem

Program:
#include<iostream>

using namespace std;

// A function to color edges of the graph.
void EdgeColoring(int edge[], 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] = 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] == edge[i] || edge[j] == edge[i] || edge[j] == edge[i] || edge[j] == edge[i])
{
// If the color matches then goto line 11 and assign next color to the edge and check again.
if(edge[j] == edge[i])
{
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], 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];
cout<<"V(2): ";
cin>>edge[i];

edge[i] = -1;
degree[edge[i]]++;
degree[edge[i]]++;
}

// 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]<<" and V(2):"<<edge[i]<<" is: color"<<edge[i]<<".";
}

Output:
Enter the number of vertexes of the graph: 4
Enter the number of edges of the graph: 5

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

Enter the vertex pair for edge 5
V(1): 1
V(2): 3

According to Vizing's theorem, this graph can use a maximum of 4 colors to generate a valid edge coloring

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.

The color of the edge between vertex V(1):1 and V(2): 3 is: color3.