الگوریتم رنگ آمیزی گراف Welsh-Powell

Question

سلام دوستان

گرافی داریم که الگوریتم powell_welch روی ان بهترین جواب را نده ؟
ممنون

...

Comments

من گشتم دنبال جواب سوالت ولی خیلی چیزی نفهمیدم.
میشه الگوریتم و رو توضیح بدی (فارسی) و بعد سوالی رو که راه حلش این الگوریتم هست رو بگی؟

---

مثلا این سوال رو میشه با این الگوریتم حل کرد :
 چجوری میشه امتحانات  دانشگاه رو جوری برگذار کرد که هیچ کسی 2 تا امتحانش توی 1 روز نباشه .
برای حل  میشه مساله رو به این شکل روی گراف مدل کرد
درس ها رو بصورت راس گراف در نظر میگیریم
هر روزی هم که میشه امتحان برگزار کرد  بصورت یک رنگ مجزا .
و اگر 2 درس دانشجو مشترک داشتن.....  بین 2 راس معادل  یک یال رسم کنیم .

Answer 1

سلام

آره حالت هایی وجود داره که این الگوریتم کمترین تعداد رنگ مورد نیاز رو استفاده نمی کنه

 

 این الگوریتم به این شکل کار می کنه

 

1. اول درجه هر راس رو حساب می کنیم .
2. راس ها رو نزولی مرتب می کنیم
3. راس اول این لیست مرتب شده رو با اولین رنگ رنگ می زنیم
4.  تمامی رئوسی که میتوان انها را با این رنگ رنگ امیزی کرد ، رنگ میکنیم ( به طوریکه هیچ دو راس مجاوری همرنگ نباشند.)
5. راس هایی که رنگ شدن از لیست رو حذف می کنیم و مرحله 3 رو  با یک رنگ دیگه دوباره انجام میدیم

 

مثلا یکی از حالت هایی که این الگوریتم جواب بهینه رو  نمیده گراف 2 بخشی غیر کامل  هستش که با ۲ رنگ میشه رنگش کرد ولی با این الگوریتم بسته به نحوه مرتب کردن لیست  خیلی وقت ها بیشتر از ۲ رنگ استفاده میشه.

برای مثال مراحل انجام این کار رو روی گراف زیر ببینید

 

مرجله 1:

مرحله 2 :

مرحله 3 :

      

مرحله 4 :

                                 

همین طوری که مشخصه با استفاده از این الگوریتم برای گراف بالا به جای استفاده از 2 رنگ از 3 رنگ استفاده شد .

گراف های حلقوی با بیشتر از 4 راس هم خیلی وقت ها این الگوریتم براشون درست جواب نمیده .

Comments

ببخشید من هنوز مثال نقضت رو خوب متوجه نشدم.

هر جوری که نام گذاری کنی از بخشی که شروع به رنگ آمیزی می کنی.

در قدم اول :    طبق جمله چهارم الگوریتمت همه ی هم دسته هایی که از اون شروع کردی رنگ میشن.

(چون گراف کامله پس جمله ی دوم هم تاثیری تو جواب نداره.)

پس فقط دسته ی دومت باقی میمونه که باز هم طبق جمله چهارمت هم دسته های اون رنگ میشن.

---

آهان اره اشتباه شد کامل نباید باشه

---

مثال نقضشو اضافه کردم

---

B,C,D,E,F,A....C,E,A,... ??
اینجور مثال نقض اشتباهه
در ضمن در توضیح این الگوریتم این جمله(همه راس هایی که به راس رنگ شده وصل نیستن رو همون رنگ می کنیم .) درست نیست.

---

قرار نیست بر اساس حروف الفبا مرتب بشن . بر اساس درجه راس ها مرتب میشن
می تونن راس ها به این شکل که گفتم مرتب بشن
(نام گذاری هم نسبیه میشد جوری اسم  گذاری کرد که به این شکل که گفتی مرتب بشن )

اون جمله هم درسته فقط کامل نیست :)

---

منم نگفتم براساس حروف الفبا مرتب بشن
گفتم اینجور حل کردن این سوال اشتباهه

درست اون جمله هم این میشه:
راسی که در ابتدای لیست قرار دارد را با یک رنگ، رنگ زده و تمامی رئوسی که میتوان انها را با این رنگ رنگ امیزی کرد ، رنگ میکنیم ( به طوریکه هیچ دو راس مجاوری همرنگ نباشند.)

---

خب اگر این جوری حل نکنی دیگه welsh-powell نمیشه

---

آهان باشه این چیزی که گفتی بهتر به نظر میرسه  .

---

حالا یه سوال خفن تر!

آیا گرافی وجود دارد که هر جوری راس ها رو لیست کنیم (نه فقط در بعضی شرایط) الگوریتم جواب بهینه رو نده؟!

---

من توی اینترنت گشتم چیزی پیدا نکردم  .
 البته هر چی تعداد راس ها بیشتر بشه احتمال پیدا شدن جواب بهینه کمتر میشه پس شاید بشه با نوشتن یک الگوریتم Brute force که تمام حالت های لیست کردن و تمام حالت های یک گراف  رو در نظر بگیره  همچین چیزی پیدا کرد ( البته ابر کامپیوتر لازم داره :)  )