تعداد طرق رنگ آمیزی گراف - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

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

0 امتیاز
50 بازدید
سلام

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

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

رادیکال n

:)

فکر می کنم مسئله NP هست شاید بشه تقریب زد اما به هر حال باید تمام رئوس دیده بشند حداقل n هزینه داریم اگر فرض کنیم تابع مکاشفه ای یا حریصانه در عین جستجو داشته باشیم
سوال شده دی 10, 1393  بوسیله ی Pakniat (امتیاز 382)   1 4 24
منظور از سوال به نظر من حداقل تعداد رنگ برای رنگ آمیزی گراف استفاده شه به طورئیکه هیچ یک از 2 ناحیه همجوار هم رنگ نیاشند.
من فکر نمی کنم منظور ناحیه همجوار باشه .اگر منظور ناحیه بسته بود می شد map coloring نه graph coloring
البته فرقی هم نمی کرد برای map coloring هم باید اول از روی نقشه یک گراف ساخت بعد سعی کرد راس ها رو رنگ کرد که میشد همون vertex coloring که NP_Complete هست .

1 پاسخ

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

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

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

این سوال از کدوم کتابه ؟ :)
پاسخ داده شده دی 10, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
از کتاب خاصی نیست تست علوم کامپیوتر پارساله ، هر 4 گزینه جواب کلاس p داشته ، تو کلید جواب دیدم
...