مي خواهيم در يك گراف همه گره ها را بگونه اي رنگ آميزي کنيم که هيچ دو گره مجاوري يك رنگ نباشند ضمن اينكه کمترين رنگ را به کار برده باشيم. روش انجام کار : تمام راه هايی که بتوان رئوس يک گراف بدون جهت را با mرنگ, رنگ آميزی کرد, پيدا کنيد . اعداد صحيح مثبت nو mيک گراف بدون جهت شامل nراس . گراف را توسط يک آرايه دوبعدی wنشان داده ايم که سطرها و ستون هايش از 1تا nشاخص دهی شده است و [w[i][jدرست است اگر لبه ای بين راس iام و راس jام وجود داشته باشد, واگر نه نادرست است . تمام رنگ آميزی های ممکن گراف با استفاده از mرنگ, به طوری که هيچ دو راس مجاوری همرنگ نباشند.خروجی هر رنگ آميزی, آرايه ای به نام Vcolorاست که از 1تا nشاخص دهی شده و در آن ,[ Vcolor[i مبين رنگ (يک عدد صحيح بين 1تا )mاختصاص داده شده به راس iام می باشد .
مطابق قرارداد n,m,wو Vcolorورودی های روتينهای فوق نمی باشد . در يک پياده سازی از الگوريتم ,روتين های بايستی به صورت محلی در روال ساده ای که , m,nو wرا به عنوان ورودی می پذيرند و Vcolorنيز به عنوان يک متغيير محلی تعريف می شود, نوشته شوند. فراخوانی سطح بالای m_coloringبه صورت ) m_coloring(0خواهد بود.
نتيجه نهايی :
تعداد گره های درخت فضای حالات اين الگوريتم برابر است با :
بدترين زمان اجرای اين الگوريتم به صورت زیر می باشد .
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team