(۰۹ تیر ۱۳۹۲ ۰۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام. برای رنگ آمیزی بهتره به راسی که بیشترین یال رو داره زودتر از بقیه رنگ نسبت بدی. عکس شماره ۱ راس t درجش از بقیه بیشتره. تعداد [tex]\lambda[/tex] رنگ میتونیم بهش نسبت بدیم. (لاندا تعداد رنگ هامونه.) مرحله بعد چون درجه تمام رئوس برابره و محدودیت روی اونها مساویه یکی رو انتخاب میکنیم. (منظور از محدودیت تعداد رئوس مجاوری هستن که به اونها رنگ نسبت دادیم.) راس w رو انتخاب میکنم. مسلماً رنگی که به t نسبت دادیم رو نمیتونیم به w بدیم. پس تعداد رنگ هاش میشه [tex]\lambda-1[/tex]. حالا روی x و z محدودیت بیشتری نسبت به y داریم. این محدودیت بخاطر مجاورت با راس w هست. راس x رو انتخاب میکنم. تعداد حالاتش [tex]\lambda-2[/tex] چون با دو راس رنگ آمیزی شده که اون دو راس باهم مجاور هستن مجاور شده. (در صورت مجاور نبودن اون دو راس میبایست حالت مشابهت رنگ رئوس رو درنظر بگیریم. این حالت برای آخرین راس اتفاق می‌افته.) رئوس y و z وضعیت مشابه دارن. من y رو انتخاب میکنم. این هم [tex]\lambda-2[/tex] حالت داره. میریم سراغ راس z. به یه مشکل میخوریم. با سه راس رنگ آمیزی شده مجاوره که دو تا از اونها باهم مجاور نیستن. (یعنی میتونن همرنگ باشن.) پس نمیتونیم یک عدد ثابت به y نسبت بدیم. میتونیم y و z رو باهم بگیریم. اگه y همرنگ با w نباشه [tex]\lambda-3[/tex] حالت داره و با این شرط z هم [tex]\lambda-3[/tex] حالت خواهد داشت. اگر هم رنگ y با w برابر باشه تعداد رنگ y برابر ۱ و رنگ x برابر [tex]\lambda-2[/tex] خواهد بود. پس رنگ دو راس y و z باهم برابر [tex](\lambda-3)^2 \lambda-2[/tex] میشه. چند جمله ای حاصل میشه [tex]\lambda(\lambda-1)(\lambda-2)((\lambda-3)^2 \lambda-2)[/tex].

برای شکل دوم راس a و b و c به ترتیب [tex]\lambda[/tex] و [tex]\lambda-1[/tex] و [tex]\lambda-1[/tex] رنگ خواهند گرفت. برای d دو حالت داریم. حالت متفاوت با a که [tex]\lambda-2[/tex] حالت داره و در این صورت e هم [tex]\lambda-2[/tex] حالت خواهد داشت. حالت دوم هم مشابهت a و d هست که d فقط ۱ حالت و e هم [tex]\lambda-1[/tex] حالت خواهد داشت. حالت کلی میشه [tex]\lambda(\lambda-1)^2((\lambda-2)^2 \lambda-1)[/tex].

اگه توضیح بیشتری نیازه در خدمتم.

(۰۹ تیر ۱۳۹۲ ۰۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  برای شکل دوم راس a و b و c به ترتیب [tex]\lambda[/tex] و [tex]\lambda-1[/tex] و [tex]\lambda-1[/tex] رنگ خواهند گرفت. برای d دو حالت داریم. حالت متفاوت با a که [tex]\lambda-2[/tex] حالت داره و در این صورت e هم [tex]\lambda-2[/tex] حالت خواهد داشت.

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

(09 تیر ۱۳۹۲ ۰۱:۲۳ ب.ظ)Jooybari نوشته شده توسط:  برای شکل دوم راس a و b و c به ترتیب [tex]\lambda[/tex] و [tex]\lambda-1[/tex] و [tex]\lambda-1[/tex] رنگ خواهند گرفت. برای d دو حالت داریم. حالت متفاوت با a که [tex]\lambda-2[/tex] حالت داره و در این صورت e هم [tex]\lambda-2[/tex] حالت خواهد داشت.

آقای جویباری این قسمت را میشه یه توضیحی بدید. چرا تو شکل دوم وقتی a با d رنگش متفاوته میگید [tex]\lambda-2[/tex] حالت داریم. اینجاشو نفهمیدم

(۲۳ دى ۱۳۹۲ ۱۰:۳۰ ب.ظ)Jooybari نوشته شده توسط:  خوب [tex]\lambda-2[/tex] حالت برای e داریم. رنگ e نباید مشابه a و d باشه. خود d هم نباید همرنگ c و طبق فرض همرنگ a باشه.

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

(23 دى ۱۳۹۲ ۱۰:۳۰ ب.ظ)Jooybari نوشته شده توسط:  خوب [tex]\lambda-2[/tex] حالت برای e داریم. رنگ e نباید مشابه a و d باشه. خود d هم نباید همرنگ c و طبق فرض همرنگ a باشه.

نمیدونم کجای کار دارم اشتباه میکنم
اگه رنگ d با a را متفاوت فرض کنیم برای e داریم [tex]\lambda-2[/tex] حالت که درسته. اما برای خود d چرا میگیم [tex]\lambda-2[/tex] حالت؟ d رنگش با a و c متفاوته ولی e را چرا در نظر نگرفتیم؟ شاید e هم رنگش با a و c متفاوت باشه و حالات d بشه [tex]\lambda-3[/tex]

(۲۳ دى ۱۳۹۲ ۱۱:۱۲ ب.ظ)Jooybari نوشته شده توسط:  e رو بعد از d رنگ میکنیم. البته فکر کنم یه حالت رو درنظر نگرفتم. حالتی که رنگ a و c یکیه روی d تاثیر میذاره.

(۱۶ مرداد ۱۳۹۲ ۱۲:۳۰ ب.ظ)Jooybari نوشته شده توسط:  سلام. اگه دو حالت درنظر بگیریم این دو حالت تا این مرحله مشابه میشن. نیازی به این کار نیست. تقسیم حالات رو وقتی انجام میدیم که به راس برای رنگامیزی میرسیم که حداقل دوتا از رئوس مجاورش امکان داشته باشه که همرنگ باشن. توجه داشته باشید که این دو راس مشخص شده در مراحل قبل رنگ آمیزی شدن.

(۲۴ دى ۱۳۹۲ ۰۷:۵۵ ق.ظ)masoud67 نوشته شده توسط:  آقای جویباری یه چیز دیگه هم منو گیج کرده. تو کتاب پارسه نوشته چند جمله ای فامی گراف دور میشه
[tex](\lambda -1) ^n (-1)^n(\lambda -1)[/tex]
که گفته اگه دور زوج باشه عدد فامی اون میشه ۲ و اگه دور فرد باشه عدد فامی اون میشه ۳
و اگه تو معادله ای که شما بدست آوردید مقدار ۲ بذاریم جواب میشه ۲ در صورتی که اگه تو معادله بالا بذاریم جواب میشه صفر و با دو رنگ هم نمیشه این گراف رو رنگ کرد
من خیلی تو این مبحث تسلط ندارم ولی یه کم برام سوال شده که اینا چرا جور در نمیاد
تشکر

(۲۴ دى ۱۳۹۲ ۰۸:۵۰ ق.ظ)Jooybari نوشته شده توسط:  درسته. منم گفتم شرط همرنگی a و c رو به اشتباه درنظر نگرفتم. یه حالت دیگه هم به حالات جوابم باید اضافه بشه.

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

(24 دى ۱۳۹۲ ۰۸:۵۰ ق.ظ)Jooybari نوشته شده توسط:  درسته. منم گفتم شرط همرنگی a و c رو به اشتباه درنظر نگرفتم. یه حالت دیگه هم به حالات جوابم باید اضافه بشه.

فکر کنم اینجوری بشه،
۱/ اگه a و c یه رنگ باشن پس c یک حالت داره و d میتونه [tex]\lambda -1[/tex] و e هم [tex]\lambda -2[/tex]

۲/ اگه a و c یه رنگ نباشن، پس c میتونه [tex]\lambda -2[/tex] حالت داشته باشه (یعنی رنگی متفاوت از a و b) که تو این مورد d دو حالت میتونه داشته باشه
۲/الف d با a همرنگ باشه که d یک حالت داره و e برابر با [tex]\lambda -1[/tex] حالت
۲/ب d با a همرنگ نباشه که d میتونه [tex]\lambda -2[/tex] حالت داشته باشه (رنگ d متفاوت از رنگ a و c) و در آخر e هم [tex]\lambda -2[/tex]

و در کل با اون فرمول گراف دور یکی میشه

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