গ্রাফ কালারিং সমস্যা গ্রাফ লেবেলিংর একটি বিশেষ ক্ষেত্র। এই সমস্যায়, প্রতিটি নোডকে কিছু রঙ দিয়ে কালার করা হয়। কিন্তু কালারিংর কিছু সীমাবদ্ধতা রয়েছে। আমরা যেকোনো দুটি সন্নিহিত ভার্টেক্সের জন্য একই রঙ ব্যবহার করতে পারি না।
এই সমস্যা সমাধান করতে লালচী (greedy) অ্যালগরিদম ব্যবহার করতে হয়, তবে এটি ন্যূনতম রঙ ব্যবহার করার গ্যারান্টি দেয় না।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 আউটপুট: Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
এলগরিদম
graphColoring(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: প্রতিটি নোডকে কিছু রঙ অ্যাসাইন করা।
শুরু
রঙের একটি লিস্ট ঘোষণা করুন
প্রাথমিকভাবে প্রথম নোডের জন্য রঙ 0 সেট করুন
একটি অ্যারে colorUsed সংজ্ঞায়িত করুন যেটি ট্র্যাক করবে কোন রঙ ব্যবহার হয়েছে এবং কোন রঙ কখনো ব্যবহার হয়নি।
প্রথম নোড বাদে সব ভার্টেক্স i এর জন্য, করুন
i কে যেকোনো রঙে অনঅ্যাসাইনড চিহ্নিত করুন
শেষ লুপ
সব ভার্টেক্সের জন্য colorUsed কে false চিহ্নিত করুন
প্রথম ভার্টেক্স বাদে গ্রাফের সব ভার্টেক্স u এর জন্য, করুন
u-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি color[v] অনঅ্যাসাইনড থাকে, তবে
colorUsed[color[v]] := true
শেষ শর্ত
শেষ লুপ
রঙের লিস্টের সব রঙ col এর জন্য, করুন
যদি রঙ ব্যবহার করা নেই, তবে
লুপ ব্রেক করুন
শেষ শর্ত
শেষ লুপ
color[u] := col
u-র সাথে সন্নিহিত প্রতিটি ভার্টেক্স v এর জন্য, করুন
যদি color[v] অনঅ্যাসাইনড থাকে, তবে
colorUsed[color[v]] := false
শেষ শর্ত
শেষ লুপ
শেষ লুপ
গ্রাফের সব ভার্টেক্স u এর জন্য, করুন
নোড এবং তার রঙ প্রদর্শন করুন
শেষ লুপ
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void graphColoring() {
int color[NODE];
color[0] = 0; // প্রথম নোডের জন্য প্রথম রঙ অ্যাসাইন করুন
bool colorUsed[NODE]; // রঙ ব্যবহার হয়েছে কিনা চেক করতে ব্যবহৃত
for(int i = 1; i < NODE; i++)
color[i] = -1; // অন্যান্য সব ভার্টেক্সকে অনঅ্যাসাইনড আরম্ভ করুন
for(int i = 0; i < NODE; i++)
colorUsed[i] = false; // প্রাথমিকভাবে কোনো রঙ নির্বাচন করা হয়নি
for(int u = 1; u < NODE; u++) {
// অন্যান্য NODE - 1টি ভার্টেক্সের জন্য
for(int v = 0; v < NODE; v++) {
if(graph[u][v]){
if(color[v] != -1) // যখন একটি রঙ অ্যাসাইন করা হয়ে থাকে, সেটি অনবেইলেবল করুন
colorUsed[color[v]] = true;
}
}
int col;
for(col = 0; col < NODE; col++)
if(!colorUsed[col]) // এমন একটি রঙ খুঁজে বের করুন যা অ্যাসাইন করা নেই
break;
color[u] = col; // খুঁজে পাওয়া রঙটি লিস্টে অ্যাসাইন করুন
for(int v = 0; v < NODE; v++) {
// পরবর্তী ইটারেশনের জন্য রঙের উপলব্ধতা false করুন
if(graph[u][v]) {
if(color[v] != -1)
colorUsed[color[v]] = false;
}
}
}
for(int u = 0; u < NODE; u++)
cout << "Color: " << u << ", Assigned with Color: " << color[u] << endl;
}
int main() {
graphColoring();
}
আউটপুট
Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
