ভাইজিং-এর উপপাদ্য বলে যে সরল গ্রাফের ক্রোম্যাটিক সূচক হয় সর্বোচ্চ ডিগ্রি বা সর্বোচ্চ ডিগ্রি +1 হতে পারে। এখানে, ক্রোম্যাটিক ইনডেক্স মানে গ্রাফের প্রান্ত রঙের জন্য প্রয়োজনীয় সর্বাধিক রঙ।
ভাইজিং এর উপপাদ্য বাস্তবায়নের জন্য এটি একটি C++ প্রোগ্রাম।
অ্যালগরিদম
Begin Take the number of vertices and edges as input. Take the vertex pair for the edges. function EdgeColor() : Color the graph edges. 1) Assign color to current edge as c i.e. 1 initially. 2) If the same color is occupied by any of the adjacent edges, then discard this color and go to flag again and try with the next color. End
উদাহরণ
#include<iostream>
using namespace std;
void EdgeColor(int ed[][3], int e) {
int i, c, j;
for(i = 0; i < e; i++) {
c = 1; //Assign color to current edge 1 initially.
// If the same color is occupied by any of the adjacent edges,
// then discard this color and go to flag again and try next color.
flag:
ed[i][2] = c;
for(j = 0; j < e; j++) {
if(j == i)
continue;
if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
if(ed[j][2] == ed[i][2]) {
c++;
goto flag;
}
}
}
}
}
int main() {
int i, n, e, j, max = -1;
cout<<"Enter the number of vertices of the graph: ";
cin>>n;
cout<<"Enter the number of edges of the graph: ";
cin>>e;
int ed[e][3], deg[n+1] = {0};
for(i = 0; i < e; i++) {
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nN(1): ";
cin>>ed[i][0];
cout<<"N(2): ";
cin>>ed[i][1];
//calculate the degree of each vertex
ed[i][2] = -1;
deg[ed[i][0]]++;
deg[ed[i][1]]++;
}
//find out the maximum degree.
for(i = 1; i <= n; i++) {
if(max < deg[i])
max = deg[i];
}
EdgeColor(ed , e);
cout<<"\nAccording to Vizing's theorem this graph can use 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 N(1):"<<ed[i][0]<<" and N(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<".";
} আউটপুট
Enter the number of vertices of the graph: 4 Enter the number of edges of the graph: 3 Enter the vertex pair for edge 1 N(1): 1 N(2): 2 Enter the vertex pair for edge 2 N(1): 3 N(2): 2 Enter the vertex pair for edge 3 N(1): 4 N(2): 1 According to Vizing's theorem this graph can use maximum of 3 colors to generate a valid edge coloring. The color of the edge between vertex N(1):1 and N(2):2 is: color1. The color of the edge between vertex N(1):3 and N(2):2 is: color2. The color of the edge between vertex N(1):4 and N(2):1 is: color2.
