কমপ্লিট গ্রাফ হলো যেকোনো দুটি ভার্টেক্সের মধ্যে সংযোগকারী এজ থাকে। এটি কমপ্লিট গ্রাফে এজ কালারিং করার C++ প্রোগ্রাম।
অ্যালগরিদম
Begin
ভার্টেক্স সংখ্যা 'n' ইনপুট নিন।
e = n*(n-1)/2 এজ দিয়ে কমপ্লিট গ্রাফ কনস্ট্রাক্ট করুন।
EdgeColor() ফাংশন দিয়ে গ্রাফের এজগুলো রঙ করুন।
A) বর্তমান এজে রঙ 'c' অ্যাসাইন করুন (প্রাথমিক ১)।
B) যদি অadyacent এজে একই রঙ থাকে, তবে সেই রঙ বাতিল করে পরবর্তী রঙ ট্রাই করুন।
C) প্রতিটি এজের রঙ প্রিন্ট করুন।
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;
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, cnt = 0;
cout << "Enter the number of vertexes for the complete graph: ";
cin >> n;
e = (n*(n-1))/2;
int ed[e][3];
for(i = 1; i <= n; i++) {
for(j = i+1; j <= n; j++) {
ed[cnt][0] = i;
ed[cnt][1] = j;
ed[cnt][2] = -1;
cnt++;
}
}
EdgeColor(ed, e);
for(i = 0; i < e; i++)
cout << "\nThe color of the edge between vertex n1):" << ed[i][0] << " and n(2):" << ed[i][1] << " is: color" << ed[i][2] << ".";
return 0;
}
আউটপুট
Enter the number of vertexes for the complete graph: 4 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):1 and n(2):3 is: color2. The color of the edge between vertex n(1):1 and n(2):4 is: color3. The color of the edge between vertex n(1):2 and n(2):3 is: color3. The color of the edge between vertex n(1):2 and n(2):4 is: color2. The color of the edge between vertex n(1):3 and n(2):4 is: color1.
