ভিজিংয়ের থিওরেম বলে যে একটি সিম্পল গ্রাফের ক্রোম্যাটিক সূচক হয় সর্বোচ্চ ডিগ্রি (maxdegree) অথবা সর্বোচ্চ ডিগ্রি+১। এখানে ক্রোম্যাটিক সূচক বলতে গ্রাফের এজ কালারিং-এর জন্য প্রয়োজনীয় সর্বোচ্চ রং বোঝানো হয়েছে।
এটি একটি C++ প্রোগ্রাম যা ভিজিংয়ের থিওরেম বাস্তবায়ন করে।
অ্যালগরিদম
শুরু
ভার্টেক্স এবং এজের সংখ্যা ইনপুট olarak নিন।
এজের জন্য ভার্টেক্স জোড়া ইনপুট নিন।
ফাংশন EdgeColor(): গ্রাফের এজগুলো কালার করুন।
1) বর্তমান এজকে রং c দিন (প্রাথমিকভাবে ১)।
2) যদি একই রং কোনো সन्नিহিত এজে заняস্ত থাকে,
তবে এই রং বাতিল করুন এবং ফ্ল্যাগে ফিরে পরবর্তী রং দিয়ে চেষ্টা করুন।
শেষ
উদাহরণ
#include <iostream>
using namespace std;
void EdgeColor(int ed[][3], int e) {
int i, c, j;
for (i = 0; i < e; i++) {
c = 1; // বর্তমান এজকে রং ১ দিন।
// যদি একই রং কোনো সন্নিহিত এজে থাকে,
// তবে এই রং বাতিল করুন এবং ফ্ল্যাগে ফিরে পরবর্তী রং চেষ্টা করুন।
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];
// প্রতিটি ভার্টেক্সের ডিগ্রি ক্যালকুলেট করুন
ed[i][2] = -1;
deg[ed[i][0]]++;
deg[ed[i][1]]++;
}
// সর্বোচ্চ ডিগ্রি বের করুন।
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.
