رنگ آمیزی گراف به روش حریصانه — به زبان ساده

۲۰۴۲ بازدید
آخرین به‌روزرسانی: ۱۵ آذر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
رنگ آمیزی گراف به روش حریصانه — به زبان ساده

در این مطلب، ابتدا مساله رنگ‌آمیزی گراف و انواع آن و سپس، رنگ آمیزی گراف به روش حریصانه مورد بررسی قرار گرفته است. همچنین، الگوریتم مذکور در زبان‌های برنامه‌نویسی ++C و «جاوا» (Java) پیاده‌سازی شده است. مساله رنگ آمیزی گراف، به بحث تخصیص رنگ به راس‌های گراف بر اساس محدودیت‌های مشخصی می‌پردازد. انواع مسائل رنگ‌آمیزی گراف در ادامه بیان شده‌اند.

رنگ‌آمیزی راس‌ها: این مساله، یکی از معروف‌ترین مسائل رنگ‌آمیزی گراف است. در مساله رنگ‌آمیزی راس‌ها، هدف آن است که با تعداد m رنگ داده شده، راس‌های گراف به گونه‌ای رنگ شوند که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. دیگر مسائل رنگ‌آمیزی گراف مانند رنگ‌آمیزی یال‌ها (هیچ راسی بین دو یال با رنگ مشابه وجود نداشته باشد) و رنگ‌آمیزی چهره (رنگ‌آمیزی نقشه جغرافیایی) را می‌توان به مساله رنگ‌آمیزی راس‌ها تبدیل کرد. پیش از این، در مطلب «حل مساله رنگ آمیزی گراف با الگوریتم پس گرد»، این مساله با استفاده از الگوریتم «پس‌گرد» (Backtracking) حل شد و در این مطلب، این مساله با استفاده از الگوریتم «حریصانه» (Greedy) حل خواهد شد.

شماره کروماتیک: کوچکترین عدد از (تعداد) رنگ‌ها که برای رنگ‌آمیزی گراف G مورد نیاز است، شماره کروماتیک نامیده می‌شود. برای مثال، گراف زیر را می‌توان حداقل با ۳ رنگ، رنگ‌آمیزی کرد.

رنگ آمیزی گراف به روش حریصانه

مساله پیدا کردن عدد کروماتیک برای یک گراف داده شده، «ان‌پی کامل» (NP-Complete) است.

کاربردهای مساله رنگ آمیزی گراف

مساله رنگ‌آمیزی گراف، کاربردهای بسیار زیادی دارد که به برخی از آن ها در زیر اشاره شده است.

برنامه‌ریزی روی جدول زمانی: فرض می‌شود که قرار است برنامه امتحانات یک دانشگاه تنظیم شود. لیستی از موضوعات مختلف وجود دارد و دانشجویان گوناگون دروس مختلف را ثبت کرده‌اند. بسیاری از دانشجویان دروس مشترکی را اخذ کرده‌اند (در واقع برخی از دروس، دانشجویان مشترکی دارند). چطور می‌توان امتحانات را به گونه‌ای برنامه‌ریزی کرد که هیچ دو امتحانی که یک دانش‌آموز مشترک دارند، در یک زمان واحد نباشند؟ حداقل بازه‌های زمانی مورد نیاز برای برگزاری کلیه امتحانات چه میزان است؟ این مساله را می‌توان به عنوان مساله گراف نشان داد که در آن، هر راس یک موضوع و هر یال بین دو راس به معنی وجود دانش‌آموز مشابه است. پس برنامه‌ریزی جدول زمانی امتحانات یک مساله رنگ‌آمیزی گراف است که در آن حداقل بازه‌های زمانی برابر با عدد کروماتیک گراف است.

تخصیص فرکانس رادیویی موبایل: هنگام تخصیص فرکانس‌های رادیویی به برج‌ها، این شرط وجود دارد که فرکانس‌های تخصیص پیدا کرده به کلیه برج‌ها در موقعیت یکسان، باید متفاوت باشند. چگونه می‌توان فرکانس‌ها را با این محدودیت تخصیص داد؟ حداقل تعداد فرکانس‌های مورد نیاز چند تا است؟ این مساله نیز نمونه‌ای از مسائل رنگ‌آمیزی گراف است که در آن، هر برج نشانگر یک راس و یال بین دو برج نشانگر آن است که آن‌ها در رِنج یکدیگر قرار دارند.

سودوکو: سودوکو نیز نوعی از مسائل رنگ‌آمیزی گراف محسوب می‌شود که در آن، هر سلول نشان‌گر یک راس است و اگر راس‌ها در سطر، ستون یا بلوک مشابهی باشند، یک یال بین آن‌ها وجود دارد.

تخصیص ثبات: در بهینه‌سازی کامپایلر، «تخصیص ثبات» (Register Allocation) فرآیند تخصیص تعداد بالایی از متغیرهای برنامه هدف در تعداد کمی از ثبات‌های «واحد پردازش مرکزی» است. این مساله نیز از جمله مسائل رنگ‌آمیزی گراف است.

گراف دو بخشی: می‌توان با رنگ‌آمیزی یک گراف تنها با استفاده از دو رنگ، بررسی کرد که آیا گراف دو بخشی است یا خیر. اگر بتوان گراف را تنها با دو رنگ، رنگ‌آمیزی کرد، گراف دو بخشی است.

رنگ‌آمیزی نقشه: رنگ‌آمیزی نقشه‌های جغرافیایی کشورها یا شهرهای یک کشور به صورتی که در آن هیچ دو کشور یا شهر هم‌جواری دارای رنگ مشابه نباشند نیز از جمله مسائل رنگ‌آمیزی گراف است. بر اساس «قضیه چهار رنگ» (Four Color Theorem)، برای رنگ‌آمیزی هر نقشه به صورتی که هیچ دو کشور/شهر مجاوری دارای رنگ مشابه نباشند، فقط چهار رنگ کافی است. در نقشه‌های ساده‌تر، تنها سه رنگ کافی است و از رنگ چهارم برای برخی نقشه‌ها استفاده می‌شود.

سایر کاربردها: مساله رنگ‌آمیزی گراف، کاربردهای متعدد و متنوع دیگری نیز دارد. برای مثال، شبکه‌ای از هزاران سرور وجود دارد که از آن‌ها برای توزیع محتوا در اینترنت استفاده می‌شود. آن‌ها هر هفته نرم‌افزارها یا به روز رسانی‌های جدیدی را نصب می‌کنند. به روز رسانی‌ها نمی‌تواند روی همه سرورها به طور هم‌زمان اتفاق بیفتد زیرا ممکن است فعالیت سرور طی مراحل نصب متوقف شود. همچنین، نباید هر بار تنها یکی از سرورها به روز رسانی شود زیرا این کار زمان زیادی می‌برد.

بنابراین، سرورهای زیادی هستند که نباید هم‌زمان فعالیت آن‌ها متوقف شود زیرا فعالیت‌های حیاتی انجام می‌دهند و در عین حال به دلیل زمان‌بر بودن پروسه بیان شده برای تک به تک آن‌ها به طور جداگانه، این کار نیز ممکن نیست. مساله بیان شده، حالت متداولی از کاربرد مساله رنگ‌آمیزی گراف برای انجام زمان‌بندی است. شایان توجه است که برای گرافی با ۷۵۰۰۰ گره، تنها ۸ رنگ برای رنگ‌آمیزی کافی است. بنابراین، در مساله مربوط به سرورها نیز در این شرایط، می‌توان کار به روز رسانی را در هشت گذر انجام داد.

رنگ آمیزی گراف به روش حریصانه

در مساله رنگ‌آمیزی راس‌های گراف، چنانکه پیش از این نیز بیان شد، هدف رنگ کردن راس‌ها به شیوه‌ای است که هیچ دو راس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگ‌آمیزی گراف با حداقل رنگ‌های ممکن وجود ندارد و این مساله از جمله مسائل «ان‌پی کامل» (NP Complete) محسوب می‌شود.

«الگوریتم‌های تقریبی» (Approximate Algorithms) گوناگونی برای حل این مساله وجود دارند. در ادامه، روش حریصانه برای مساله رنگ‌آمیزی گراف مورد بررسی قرار گرفته است. این روش تضمین نمی‌کند که کمترین تعداد رنگ‌ها را استفاده کند، اما حد بالا در تعداد رنگ‌ها را تضمین می‌کند. الگوریتم پایه هرگز نمی‌تواند بیش از d+1 رنگ که در آن d برابر با درجه بیشینه راس‌ها در گراف داده شده است را استفاده کند.

الگوریتم حریصانه پایه

  1. اولین راس را با اولین رنگ، رنگ‌آمیزی کن.
  2. اقدامات زیر را برای v-1 راس باقیمانده انجام بده
    1. راس کنونی را با رنگ دارای کمترین شماره‌گذاری (کمریتن تعداد استفاده) که پیش از این برای هیچ راس مجاوری استفاده نشده، رنگ‌آمیزی کن. اگر همه رنگ‌هایی که پیش از این استفاده شده‌اند در راس‌های مجاور این راس وجود دارند، یک رنگ جدید به راس v تخصیص بده.

کد رنگ آمیزی گراف به روش حریصانه در ++C

کد رنگ آمیزی گراف به روش حریصانه در جاوا

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 باشد (توجه به این نکته لازم است که اعداد در حال حاضر توسط راس‌های مجاور گرفته شده‌اند). این مساله را می‌توان از طریق استنتاج نیز ثابت کرد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۸ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeksGeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *