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

در این مطلب، ابتدا مساله رنگ‌آمیزی گراف و انواع آن و سپس، رنگ آمیزی گراف به روش حریصانه مورد بررسی قرار گرفته است. همچنین، الگوریتم مذکور در زبان‌های برنامه‌نویسی ++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

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

خروجی

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(V² + E است.

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

الگوریتم بالا، از کمترین تعداد ممکن رنگ‌ها استفاده نمی‌کند. همچنین، تعداد رنگ‌های انتخاب شده گاهی بستگی به ترتیب راس‌های پردازش شده دارند. برای مثال، دو گراف زیر را می‌توان در نظر گرفت. در گراف پایین، راس‌های ۳ و ۴ جا به جا شده‌اند.

اگر راس‌های ۰، ۱، ۲، ۳ و ۴ در گراف بالا در نظر گرفته شوند، می‌توان گراف را با استفاده از ۳ رنگ، رنگ‌آمیزی کرد. اما در صورتی که راس‌های ۰، ۱، ۲، ۳ و ۴ در گراف پایین در نظر گرفته شوند، نیاز به چهار رنگ خواهد بود.

بنابراین، ترتیبی که بر اساس آن راس‌ها انتخاب می‌شوند، حائز اهمیت است. پژوهشگران گوناگون، راه‌های مختلفی را پیدا کرده‌اند که نسبت به الگوریتم میانگین، پاسخ بهتری دارد. از جمله شناخته شده‌ترین این روش‌ها، الگوریتم «وِلش-پاول» (Welsh–Powell Algorithm) است که راس‌ها را به ترتیب نزولی درجات در نظر می‌گیرد.

الگوریتم پایه چطور حد بالاتر از d+1 را تضمین می‌کند؟

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

برای رنگ‌آمیزی این راس، نیاز به انتخاب کمترین تعداد رنگ‌ها است که توسط راس‌های مجاور استفاده نشده‌اند. اگر راس‌ها با اعداد ۱، ۲ و ... رنگ‌آمیزی شده باشند، مقدار کوچکترین عدد باید چیزی بین ۱ تا d+1 باشد (توجه به این نکته لازم است که اعداد در حال حاضر توسط راس‌های مجاور گرفته شده‌اند). این مساله را می‌توان از طریق استنتاج نیز ثابت کرد.

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

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

^^