سلام
آره حالت هایی وجود داره که این الگوریتم کمترین تعداد رنگ مورد نیاز رو استفاده نمی کنه
این الگوریتم به این شکل کار می کنه
-
اول درجه هر راس رو حساب می کنیم .
-
راس ها رو نزولی مرتب می کنیم
-
راس اول این لیست مرتب شده رو با اولین رنگ رنگ می زنیم
-
تمامی رئوسی که میتوان انها را با این رنگ رنگ امیزی کرد ، رنگ میکنیم ( به طوریکه هیچ دو راس مجاوری همرنگ نباشند.)
-
راس هایی که رنگ شدن از لیست رو حذف می کنیم و مرحله 3 رو با یک رنگ دیگه دوباره انجام میدیم
مثلا یکی از حالت هایی که این الگوریتم جواب بهینه رو نمیده گراف 2 بخشی غیر کامل هستش که با ۲ رنگ میشه رنگش کرد ولی با این الگوریتم بسته به نحوه مرتب کردن لیست خیلی وقت ها بیشتر از ۲ رنگ استفاده میشه.
برای مثال مراحل انجام این کار رو روی گراف زیر ببینید
مرجله 1:
مرحله 2 :
مرحله 3 :
مرحله 4 :
همین طوری که مشخصه با استفاده از این الگوریتم برای گراف بالا به جای استفاده از 2 رنگ از 3 رنگ استفاده شد .
گراف های حلقوی با بیشتر از 4 راس هم خیلی وقت ها این الگوریتم براشون درست جواب نمیده .