سلام.
راس w بیشترین درجه رو داره. پس اولین رنگ رو به این راس نسبت میدیم.
راس دوم رو u انتخاب میکنیم.
راس سوم رو z میگیریم و هین الآن مسئله رو به دو قسمت همرنگ با u و غیر همرنگ با u تقسیم میکنیم.
با توجه به ۲ حالت مسئله به راحتی میشه رنگ ۳ راس دیگه رو مشخص کرد.

(۲۳ دى ۱۳۹۲ ۱۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام.
راس w بیشترین درجه رو داره. پس اولین رنگ رو به این راس نسبت میدیم.
راس دوم رو u انتخاب میکنیم.
راس سوم رو z میگیریم و هین الآن مسئله رو به دو قسمت همرنگ با u و غیر همرنگ با u تقسیم میکنیم.
با توجه به ۲ حالت مسئله به راحتی میشه رنگ ۳ راس دیگه رو مشخص کرد.

خیلی ممنون
اما سوال اینکه چرا این حالت رو در نظر نمیگیریم که x با v میتونه یکی بشه؟

(۲۴ دى ۱۳۹۲ ۱۲:۱۵ ق.ظ)wokesh نوشته شده توسط:  

(23 دى ۱۳۹۲ ۱۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام.
راس w بیشترین درجه رو داره. پس اولین رنگ رو به این راس نسبت میدیم.
راس دوم رو u انتخاب میکنیم.
راس سوم رو z میگیریم و هین الآن مسئله رو به دو قسمت همرنگ با u و غیر همرنگ با u تقسیم میکنیم.
با توجه به ۲ حالت مسئله به راحتی میشه رنگ ۳ راس دیگه رو مشخص کرد.

خیلی ممنون
اما سوال اینکه چرا این حالت رو در نظر نمیگیریم که x با v میتونه یکی بشه؟

چون راسهای مجاور مشترکشون رو رنگامیزی کردیم. دیگه محدودیت ایجاد نمیکنن.

(۲۴ دى ۱۳۹۲ ۰۳:۱۱ ق.ظ)Jooybari نوشته شده توسط:  

(24 دى ۱۳۹۲ ۱۲:۱۵ ق.ظ)wokesh نوشته شده توسط:  

(23 دى ۱۳۹۲ ۱۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام.
راس w بیشترین درجه رو داره. پس اولین رنگ رو به این راس نسبت میدیم.
راس دوم رو u انتخاب میکنیم.
راس سوم رو z میگیریم و هین الآن مسئله رو به دو قسمت همرنگ با u و غیر همرنگ با u تقسیم میکنیم.
با توجه به ۲ حالت مسئله به راحتی میشه رنگ ۳ راس دیگه رو مشخص کرد.

خیلی ممنون
اما سوال اینکه چرا این حالت رو در نظر نمیگیریم که x با v میتونه یکی بشه؟

چون راسهای مجاور مشترکشون رو رنگامیزی کردیم. دیگه محدودیت ایجاد نمیکنن.

نفهمیدم! مثلا اگه از z یا u شروع میکردیم چی میشد.
جناب جویباری من از چند جمله ای کروماتیک چیزهای محدودی میدونم و شما کلی بحث میکنید.
در هر حال از گذاشتن وقتتون تشکر میکنم.

(۲۴ دى ۱۳۹۲ ۰۴:۱۴ ب.ظ)wokesh نوشته شده توسط:  

(24 دى ۱۳۹۲ ۰۳:۱۱ ق.ظ)Jooybari نوشته شده توسط:  

(24 دى ۱۳۹۲ ۱۲:۱۵ ق.ظ)wokesh نوشته شده توسط:  

(23 دى ۱۳۹۲ ۱۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام.
راس w بیشترین درجه رو داره. پس اولین رنگ رو به این راس نسبت میدیم.
راس دوم رو u انتخاب میکنیم.
راس سوم رو z میگیریم و هین الآن مسئله رو به دو قسمت همرنگ با u و غیر همرنگ با u تقسیم میکنیم.
با توجه به ۲ حالت مسئله به راحتی میشه رنگ ۳ راس دیگه رو مشخص کرد.

خیلی ممنون
اما سوال اینکه چرا این حالت رو در نظر نمیگیریم که x با v میتونه یکی بشه؟

چون راسهای مجاور مشترکشون رو رنگامیزی کردیم. دیگه محدودیت ایجاد نمیکنن.

نفهمیدم! مثلا اگه از z یا u شروع میکردیم چی میشد.
جناب جویباری من از چند جمله ای کروماتیک چیزهای محدودی میدونم و شما کلی بحث میکنید.
در هر حال از گذاشتن وقتتون تشکر میکنم.

باور کنید من هم اولین سوالاتی از این مبحث رو حل میکردم فقط از روی رابطه بین رئوس بود و مطالعه قابل قبول هم روش نداشتم. فقط توی جزوه درسیمون یکی دوتا قاعده از چندجمله ای کروماتیک داشتیم که کاربرد و دلیلش رو نمیدونستم.
رنگامیزی فقط یک حالت ثابت نداره. الگوریتم ساده ای هم نداره که راحت بشه به بهترین جواب رسید. چندتا قاعده رو بهتره رعایت کرد:
۱- بهتره از رئوس با درجه بالا شروع کنیم.
۲- سعی کنیم انتخاب رئوسمون به شکلی باشه که تفاوت رنگ در رئوس اول باعث تغییر تعداد رنگهای رئوس بعدی نشه.

این قواعد معمولاً حل سوالات رو ساده تر میکنه.
توی این مثال هم اگه از ترتیب اول u بعد v و بعد z استفاده میشد جواب خوبی میشد گرفت.

برای این شکل اگه دقت کنید شباهت یا تفاوت رئوس u و v توی رنگ بقیه رئوس تاثیر داره. باید همینجا این اثر رو از بین ببرید.