رنگ آمیزی گراف به روش حریصانه — به زبان ساده
در این مطلب، ابتدا مساله رنگآمیزی گراف و انواع آن و سپس، رنگ آمیزی گراف به روش حریصانه مورد بررسی قرار گرفته است. همچنین، الگوریتم مذکور در زبانهای برنامهنویسی ++C و «جاوا» (Java) پیادهسازی شده است. مساله رنگ آمیزی گراف، به بحث تخصیص رنگ به راسهای گراف بر اساس محدودیتهای مشخصی میپردازد. انواع مسائل رنگآمیزی گراف در ادامه بیان شدهاند.
رنگآمیزی راسها: این مساله، یکی از معروفترین مسائل رنگآمیزی گراف است. در مساله رنگآمیزی راسها، هدف آن است که با تعداد m رنگ داده شده، راسهای گراف به گونهای رنگ شوند که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. دیگر مسائل رنگآمیزی گراف مانند رنگآمیزی یالها (هیچ راسی بین دو یال با رنگ مشابه وجود نداشته باشد) و رنگآمیزی چهره (رنگآمیزی نقشه جغرافیایی) را میتوان به مساله رنگآمیزی راسها تبدیل کرد. پیش از این، در مطلب «حل مساله رنگ آمیزی گراف با الگوریتم پس گرد»، این مساله با استفاده از الگوریتم «پسگرد» (Backtracking) حل شد و در این مطلب، این مساله با استفاده از الگوریتم «حریصانه» (Greedy) حل خواهد شد.
شماره کروماتیک: کوچکترین عدد از (تعداد) رنگها که برای رنگآمیزی گراف G مورد نیاز است، شماره کروماتیک نامیده میشود. برای مثال، گراف زیر را میتوان حداقل با ۳ رنگ، رنگآمیزی کرد.
مساله پیدا کردن عدد کروماتیک برای یک گراف داده شده، «انپی کامل» (NP-Complete) است.
کاربردهای مساله رنگ آمیزی گراف
مساله رنگآمیزی گراف، کاربردهای بسیار زیادی دارد که به برخی از آن ها در زیر اشاره شده است.
برنامهریزی روی جدول زمانی: فرض میشود که قرار است برنامه امتحانات یک دانشگاه تنظیم شود. لیستی از موضوعات مختلف وجود دارد و دانشجویان گوناگون دروس مختلف را ثبت کردهاند. بسیاری از دانشجویان دروس مشترکی را اخذ کردهاند (در واقع برخی از دروس، دانشجویان مشترکی دارند). چطور میتوان امتحانات را به گونهای برنامهریزی کرد که هیچ دو امتحانی که یک دانشآموز مشترک دارند، در یک زمان واحد نباشند؟ حداقل بازههای زمانی مورد نیاز برای برگزاری کلیه امتحانات چه میزان است؟ این مساله را میتوان به عنوان مساله گراف نشان داد که در آن، هر راس یک موضوع و هر یال بین دو راس به معنی وجود دانشآموز مشابه است. پس برنامهریزی جدول زمانی امتحانات یک مساله رنگآمیزی گراف است که در آن حداقل بازههای زمانی برابر با عدد کروماتیک گراف است.
تخصیص فرکانس رادیویی موبایل: هنگام تخصیص فرکانسهای رادیویی به برجها، این شرط وجود دارد که فرکانسهای تخصیص پیدا کرده به کلیه برجها در موقعیت یکسان، باید متفاوت باشند. چگونه میتوان فرکانسها را با این محدودیت تخصیص داد؟ حداقل تعداد فرکانسهای مورد نیاز چند تا است؟ این مساله نیز نمونهای از مسائل رنگآمیزی گراف است که در آن، هر برج نشانگر یک راس و یال بین دو برج نشانگر آن است که آنها در رِنج یکدیگر قرار دارند.
سودوکو: سودوکو نیز نوعی از مسائل رنگآمیزی گراف محسوب میشود که در آن، هر سلول نشانگر یک راس است و اگر راسها در سطر، ستون یا بلوک مشابهی باشند، یک یال بین آنها وجود دارد.
تخصیص ثبات: در بهینهسازی کامپایلر، «تخصیص ثبات» (Register Allocation) فرآیند تخصیص تعداد بالایی از متغیرهای برنامه هدف در تعداد کمی از ثباتهای «واحد پردازش مرکزی» است. این مساله نیز از جمله مسائل رنگآمیزی گراف است.
گراف دو بخشی: میتوان با رنگآمیزی یک گراف تنها با استفاده از دو رنگ، بررسی کرد که آیا گراف دو بخشی است یا خیر. اگر بتوان گراف را تنها با دو رنگ، رنگآمیزی کرد، گراف دو بخشی است.
رنگآمیزی نقشه: رنگآمیزی نقشههای جغرافیایی کشورها یا شهرهای یک کشور به صورتی که در آن هیچ دو کشور یا شهر همجواری دارای رنگ مشابه نباشند نیز از جمله مسائل رنگآمیزی گراف است. بر اساس «قضیه چهار رنگ» (Four Color Theorem)، برای رنگآمیزی هر نقشه به صورتی که هیچ دو کشور/شهر مجاوری دارای رنگ مشابه نباشند، فقط چهار رنگ کافی است. در نقشههای سادهتر، تنها سه رنگ کافی است و از رنگ چهارم برای برخی نقشهها استفاده میشود.
سایر کاربردها: مساله رنگآمیزی گراف، کاربردهای متعدد و متنوع دیگری نیز دارد. برای مثال، شبکهای از هزاران سرور وجود دارد که از آنها برای توزیع محتوا در اینترنت استفاده میشود. آنها هر هفته نرمافزارها یا به روز رسانیهای جدیدی را نصب میکنند. به روز رسانیها نمیتواند روی همه سرورها به طور همزمان اتفاق بیفتد زیرا ممکن است فعالیت سرور طی مراحل نصب متوقف شود. همچنین، نباید هر بار تنها یکی از سرورها به روز رسانی شود زیرا این کار زمان زیادی میبرد.
بنابراین، سرورهای زیادی هستند که نباید همزمان فعالیت آنها متوقف شود زیرا فعالیتهای حیاتی انجام میدهند و در عین حال به دلیل زمانبر بودن پروسه بیان شده برای تک به تک آنها به طور جداگانه، این کار نیز ممکن نیست. مساله بیان شده، حالت متداولی از کاربرد مساله رنگآمیزی گراف برای انجام زمانبندی است. شایان توجه است که برای گرافی با ۷۵۰۰۰ گره، تنها ۸ رنگ برای رنگآمیزی کافی است. بنابراین، در مساله مربوط به سرورها نیز در این شرایط، میتوان کار به روز رسانی را در هشت گذر انجام داد.
رنگ آمیزی گراف به روش حریصانه
در مساله رنگآمیزی راسهای گراف، چنانکه پیش از این نیز بیان شد، هدف رنگ کردن راسها به شیوهای است که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگآمیزی گراف با حداقل رنگهای ممکن وجود ندارد و این مساله از جمله مسائل «انپی کامل» (NP Complete) محسوب میشود.
«الگوریتمهای تقریبی» (Approximate Algorithms) گوناگونی برای حل این مساله وجود دارند. در ادامه، روش حریصانه برای مساله رنگآمیزی گراف مورد بررسی قرار گرفته است. این روش تضمین نمیکند که کمترین تعداد رنگها را استفاده کند، اما حد بالا در تعداد رنگها را تضمین میکند. الگوریتم پایه هرگز نمیتواند بیش از d+1 رنگ که در آن d برابر با درجه بیشینه راسها در گراف داده شده است را استفاده کند.
الگوریتم حریصانه پایه
- اولین راس را با اولین رنگ، رنگآمیزی کن.
- اقدامات زیر را برای v-1 راس باقیمانده انجام بده
- راس کنونی را با رنگ دارای کمترین شمارهگذاری (کمریتن تعداد استفاده) که پیش از این برای هیچ راس مجاوری استفاده نشده، رنگآمیزی کن. اگر همه رنگهایی که پیش از این استفاده شدهاند در راسهای مجاور این راس وجود دارند، یک رنگ جدید به راس v تخصیص بده.
کد رنگ آمیزی گراف به روش حریصانه در ++C
1// A C++ program to implement greedy algorithm for graph coloring
2#include <iostream>
3#include <list>
4using namespace std;
5
6// A class that represents an undirected graph
7class Graph
8{
9 int V; // No. of vertices
10 list<int> *adj; // A dynamic array of adjacency lists
11public:
12 // Constructor and destructor
13 Graph(int V) { this->V = V; adj = new list<int>[V]; }
14 ~Graph() { delete [] adj; }
15
16 // function to add an edge to graph
17 void addEdge(int v, int w);
18
19 // Prints greedy coloring of the vertices
20 void greedyColoring();
21};
22
23void Graph::addEdge(int v, int w)
24{
25 adj[v].push_back(w);
26 adj[w].push_back(v); // Note: the graph is undirected
27}
28
29// Assigns colors (starting from 0) to all vertices and prints
30// the assignment of colors
31void Graph::greedyColoring()
32{
33 int result[V];
34
35 // Assign the first color to first vertex
36 result[0] = 0;
37
38 // Initialize remaining V-1 vertices as unassigned
39 for (int u = 1; u < V; u++)
40 result[u] = -1; // no color is assigned to u
41
42 // A temporary array to store the available colors. True
43 // value of available[cr] would mean that the color cr is
44 // assigned to one of its adjacent vertices
45 bool available[V];
46 for (int cr = 0; cr < V; cr++)
47 available[cr] = false;
48
49 // Assign colors to remaining V-1 vertices
50 for (int u = 1; u < V; u++)
51 {
52 // Process all adjacent vertices and flag their colors
53 // as unavailable
54 list<int>::iterator i;
55 for (i = adj[u].begin(); i != adj[u].end(); ++i)
56 if (result[*i] != -1)
57 available[result[*i]] = true;
58
59 // Find the first available color
60 int cr;
61 for (cr = 0; cr < V; cr++)
62 if (available[cr] == false)
63 break;
64
65 result[u] = cr; // Assign the found color
66
67 // Reset the values back to false for the next iteration
68 for (i = adj[u].begin(); i != adj[u].end(); ++i)
69 if (result[*i] != -1)
70 available[result[*i]] = false;
71 }
72
73 // print the result
74 for (int u = 0; u < V; u++)
75 cout << "Vertex " << u << " ---> Color "
76 << result[u] << endl;
77}
78
79// Driver program to test above function
80int main()
81{
82 Graph g1(5);
83 g1.addEdge(0, 1);
84 g1.addEdge(0, 2);
85 g1.addEdge(1, 2);
86 g1.addEdge(1, 3);
87 g1.addEdge(2, 3);
88 g1.addEdge(3, 4);
89 cout << "Coloring of graph 1 \n";
90 g1.greedyColoring();
91
92 Graph g2(5);
93 g2.addEdge(0, 1);
94 g2.addEdge(0, 2);
95 g2.addEdge(1, 2);
96 g2.addEdge(1, 4);
97 g2.addEdge(2, 4);
98 g2.addEdge(4, 3);
99 cout << "\nColoring of graph 2 \n";
100 g2.greedyColoring();
101
102 return 0;
103}
کد رنگ آمیزی گراف به روش حریصانه در جاوا
1// A Java program to implement greedy algorithm for graph coloring
2import java.io.*;
3import java.util.*;
4import java.util.LinkedList;
5
6// This class represents an undirected graph using adjacency list
7class Graph
8{
9 private int V; // No. of vertices
10 private LinkedList<Integer> adj[]; //Adjacency List
11
12 //Constructor
13 Graph(int v)
14 {
15 V = v;
16 adj = new LinkedList[v];
17 for (int i=0; i<v; ++i)
18 adj[i] = new LinkedList();
19 }
20
21 //Function to add an edge into the graph
22 void addEdge(int v,int w)
23 {
24 adj[v].add(w);
25 adj[w].add(v); //Graph is undirected
26 }
27
28 // Assigns colors (starting from 0) to all vertices and
29 // prints the assignment of colors
30 void greedyColoring()
31 {
32 int result[] = new int[V];
33
34 // Initialize all vertices as unassigned
35 Arrays.fill(result, -1);
36
37 // Assign the first color to first vertex
38 result[0] = 0;
39
40 // A temporary array to store the available colors. False
41 // value of available[cr] would mean that the color cr is
42 // assigned to one of its adjacent vertices
43 boolean available[] = new boolean[V];
44
45 // Initially, all colors are available
46 Arrays.fill(available, true);
47
48 // Assign colors to remaining V-1 vertices
49 for (int u = 1; u < V; u++)
50 {
51 // Process all adjacent vertices and flag their colors
52 // as unavailable
53 Iterator<Integer> it = adj[u].iterator() ;
54 while (it.hasNext())
55 {
56 int i = it.next();
57 if (result[i] != -1)
58 available[result[i]] = false;
59 }
60
61 // Find the first available color
62 int cr;
63 for (cr = 0; cr < V; cr++){
64 if (available[cr])
65 break;
66 }
67
68 result[u] = cr; // Assign the found color
69
70 // Reset the values back to true for the next iteration
71 Arrays.fill(available, true);
72 }
73
74 // print the result
75 for (int u = 0; u < V; u++)
76 System.out.println("Vertex " + u + " ---> Color "
77 + result[u]);
78 }
79
80 // Driver method
81 public static void main(String args[])
82 {
83 Graph g1 = new Graph(5);
84 g1.addEdge(0, 1);
85 g1.addEdge(0, 2);
86 g1.addEdge(1, 2);
87 g1.addEdge(1, 3);
88 g1.addEdge(2, 3);
89 g1.addEdge(3, 4);
90 System.out.println("Coloring of graph 1");
91 g1.greedyColoring();
92
93 System.out.println();
94 Graph g2 = new Graph(5);
95 g2.addEdge(0, 1);
96 g2.addEdge(0, 2);
97 g2.addEdge(1, 2);
98 g2.addEdge(1, 4);
99 g2.addEdge(2, 4);
100 g2.addEdge(4, 3);
101 System.out.println("Coloring of graph 2 ");
102 g2.greedyColoring();
103 }
104}
105// This code is contributed by Aakash Hasija
خروجی
Coloring of graph 1 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 1 Coloring of graph 2 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 3
پیچیدگی زمانی الگوریتم بالا در بدترین حالت برابر با (O(V2 + E است.
تحلیل الگوریتم پایه
الگوریتم بالا، از کمترین تعداد ممکن رنگها استفاده نمیکند. همچنین، تعداد رنگهای انتخاب شده گاهی بستگی به ترتیب راسهای پردازش شده دارند. برای مثال، دو گراف زیر را میتوان در نظر گرفت. در گراف پایین، راسهای ۳ و ۴ جا به جا شدهاند.
اگر راسهای ۰، ۱، ۲، ۳ و ۴ در گراف بالا در نظر گرفته شوند، میتوان گراف را با استفاده از ۳ رنگ، رنگآمیزی کرد. اما در صورتی که راسهای ۰، ۱، ۲، ۳ و ۴ در گراف پایین در نظر گرفته شوند، نیاز به چهار رنگ خواهد بود.
بنابراین، ترتیبی که بر اساس آن راسها انتخاب میشوند، حائز اهمیت است. پژوهشگران گوناگون، راههای مختلفی را پیدا کردهاند که نسبت به الگوریتم میانگین، پاسخ بهتری دارد. از جمله شناخته شدهترین این روشها، الگوریتم «وِلش-پاول» (Welsh–Powell Algorithm) است که راسها را به ترتیب نزولی درجات در نظر میگیرد.
الگوریتم پایه چطور حد بالاتر از d+1 را تضمین میکند؟
در اینجا، d حداکثر درجه در گراف داده شده است. به دلیل آنکه d حداکثر درجه است، یک راس نمیتواند به بیش از d راس متصل شده باشد. هنگامی که یک راس رنگآمیزی میشود، حداکثر d رنگ ممکن است توسط همسایگان آن راس مورد استفاده قرار گرفته باشند.
برای رنگآمیزی این راس، نیاز به انتخاب کمترین تعداد رنگها است که توسط راسهای مجاور استفاده نشدهاند. اگر راسها با اعداد ۱، ۲ و ... رنگآمیزی شده باشند، مقدار کوچکترین عدد باید چیزی بین ۱ تا d+1 باشد (توجه به این نکته لازم است که اعداد در حال حاضر توسط راسهای مجاور گرفته شدهاند). این مساله را میتوان از طریق استنتاج نیز ثابت کرد.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
^^