تعداد طرق رنگ آمیزی گراف

Question

سلام

اگر گراف G دارای n راس باشد آنگاه Gگراف  با چند رنگ می توان رنگ آمیزی کرد ؟

فکرمی کنید جواب چیه؟

رادیکال n

:)

فکر می کنم مسئله NP هست شاید بشه تقریب زد اما به هر حال باید تمام رئوس دیده بشند حداقل n هزینه داریم اگر فرض کنیم تابع مکاشفه ای یا حریصانه در عین جستجو داشته باشیم

Comments

منظور از سوال به نظر من حداقل تعداد رنگ برای رنگ آمیزی گراف استفاده شه به طورئیکه هیچ یک از 2 ناحیه همجوار هم رنگ نیاشند.

---

من فکر نمی کنم منظور ناحیه همجوار باشه .اگر منظور ناحیه بسته بود می شد map coloring نه graph coloring
البته فرقی هم نمی کرد برای map coloring هم باید اول از روی نقشه یک گراف ساخت بعد سعی کرد راس ها رو رنگ کرد که میشد همون vertex coloring که NP_Complete هست .

Answer 1

آره مساله Vertex coloring  از نظر زمان اجرا جزو مسایل NP_Complete هستش .

منظور سوال تقریب زدن هم نیست  چون تقریب تعریف دقیقی نداره  هر تابعی که جواب درست بده ولی لزوما کمترین تعداد مورد نیاز نباشه میشه در نظر گرفت مثلا من با (1)O میام گراف رو می گیرم بعد تعداد راس ها رو بر می گردونم :)

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

این سوال از کدوم کتابه ؟ :)

Comments

از کتاب خاصی نیست تست علوم کامپیوتر پارساله ، هر 4 گزینه جواب کلاس p داشته ، تو کلید جواب دیدم