ক্রোমেটিক ইন্ডেক্স হলো দিয়ে गये গ্রাফের এজ কালারিং-এর জন্য প্রয়োজনীয় সর্বোচ্চ রঙের সংখ্যা। এটি সাইক্লিক গ্রাফের ক্রোমেটিক ইন্ডেক্স বের করার C++ প্রোগ্রাম।
অ্যালগরিদম
Begin
ভার্টেক্স সংখ্যা 'n' এবং এজ সংখ্যা 'e' ইনপুট নিন।
'e' সংখ্যক এজের জন্য ভার্টেক্স পেয়ার ইনপুট নিন edge[][]-এ।
Function ChromaticIndex() - গ্রাফের এজগুলো রঙ করুন:
A) বর্তমান এজে রঙ 'c' অ্যাসাইন করুন।
B) যদি কোনো অadyacent এজে একই রঙ থাকে, তবে সেই রঙ বাতিল করে পরবর্তী রঙ ট্রাই করুন।
C) সাইক্লিক গ্রাফের ক্রোমেটিক ইন্ডেক্স প্রিন্ট করুন।
D) প্রতিটি এজের রঙ প্রিন্ট করুন।
End
উদাহরণ
#include <iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
int i, c, j, max = -1;
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;
}
}
}
}
for(i = 0; i < e; i++)
if(max < ed[i][2]) max = ed[i][2];
return max;
}
int main() {
int i, v, e, j, max = -1;
cout << "Enter the number of vertices of the graph: ";
cin >> v;
cout << "Enter the number of edges of the graph: ";
cin >> e;
int ed[e][3];
for(i = 0; i < e; i++) {
cout << "\nEnter the vertex pair for edge " << i+1;
cout << "\nV(1): "; cin >> ed[i][0];
cout << "V(2): "; cin >> ed[i][1];
ed[i][2] = -1;
}
cout << "\n\nThe chromatic index of the given graph is: " << ChromaticIndex(ed, e);
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] << ".";
return 0;
}
আউটপুট
Enter the number of vertices of the graph:4 Enter the number of edges of the graph: 5 Enter the vertex pair for edge 1 V(1): 2 V(2):1 Enter the vertex pair for edge 2 V(1): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 3 V(2): 1 Enter the vertex pair for edge 4 V(1): 4 V(2): 2 Enter the vertex pair for edge 5 V(1):1 V(2): 3 The chromatic index of the given graph is: 4 The color of the edge between vertex n(1):2 and n(2):1 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):3 and n(2):1 is: color3. The color of the edge between vertex n(1):4 and n(2):2 is: color3. The color of the edge between vertex n(1):1 and n(2):3 is: color4.
