تالار گفتمان مانشت

سلام
دوستان میتونید چندجمله ای کروماتیک گراف زیر رو پیدا کنید مخصوصا جناب جویباری که در این زمینه خیلی قوی هستند
کلا تو رنگ آمیزی گراف مشکل دارم من



اینجا u با z و x با v میتونه یکی باشه

خیلی ممنون

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

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

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

(24 دى 1392 12:15 ق.ظ)wokesh نوشته شده توسط: [ -> ]

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

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

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

(24 دى 1392 03:11 ق.ظ)Jooybari نوشته شده توسط: [ -> ]

(24 دى 1392 12:15 ق.ظ)wokesh نوشته شده توسط: [ -> ]

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

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

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

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

(24 دى 1392 04:14 ب.ظ)wokesh نوشته شده توسط: [ -> ]

(24 دى 1392 03:11 ق.ظ)Jooybari نوشته شده توسط: [ -> ]

(24 دى 1392 12:15 ق.ظ)wokesh نوشته شده توسط: [ -> ]

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

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

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

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

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

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

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