صفحهها: ۱ ۲
سلام به دوستان... شدیدا توی این سوال گیر کردم... جوابش را دارم ولی راه حلش را نمیدونم چجوری به جواب برسم... ممنون میشم اگه کسی واسم نحوه رسیدن به جواب را توضیح بده.
سوال: چند جمله ای رنگی گراف های زیر را تعیین کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
کسی میتونه منو راهنمایی کنه؟
سلام. برای رنگ آمیزی بهتره به راسی که بیشترین یال رو داره زودتر از بقیه رنگ نسبت بدی. عکس شماره ۱ راس 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].
اگه توضیح بیشتری نیازه در خدمتم.
خیلی ممنون بابت جوابت... خیلی لطف کردی.. دعات میکنم..
من ۱روز هرچی فک کردم چیزی نفهمیدم از جواب آخرش که در کتاب گسسته گریمالدی بود...
سلام
ببخشید در گراف دوم
چرا واسه aوbدر نظر نگرفتم لاندا و لاندا منهای یک بعد واسه c بگیم میشه ۲ حالت؟ یا با a رنگش یکی هست یا نیست؟
اگر بخواهیم چنین در نظر بگیریم چگونه میتوانیم ادامه دهیم؟
سلام. اگه دو حالت درنظر بگیریم این دو حالت تا این مرحله مشابه میشن. نیازی به این کار نیست. تقسیم حالات رو وقتی انجام میدیم که به راس برای رنگامیزی میرسیم که حداقل دوتا از رئوس مجاورش امکان داشته باشه که همرنگ باشن. توجه داشته باشید که این دو راس مشخص شده در مراحل قبل رنگ آمیزی شدن.
(۱۶ مرداد ۱۳۹۲ ۱۲:۳۰ ب.ظ)Jooybari نوشته شده توسط: سلام. اگه دو حالت درنظر بگیریم این دو حالت تا این مرحله مشابه میشن. نیازی به این کار نیست. تقسیم حالات رو وقتی انجام میدیم که به راس برای رنگامیزی میرسیم که حداقل دوتا از رئوس مجاورش امکان داشته باشه که همرنگ باشن. توجه داشته باشید که این دو راس مشخص شده در مراحل قبل رنگ آمیزی شدن.
چه سوال مسخره ای پرسیده بودم
بله متوجه شدم
بسیار سپاس گزارم
واقعا عالی توضیح دادید
ای کاش جواب سوالات دیگرم هم میدادید
(۰۹ تیر ۱۳۹۲ ۰۱:۲۳ ب.ظ)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] حالت خواهد داشت.آقای جویباری این قسمت را میشه یه توضیحی بدید. چرا تو شکل دوم وقتی a با d رنگش متفاوته میگید [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] حالت داریم. اینجاشو نفهمیدم
خوب [tex]\lambda-2[/tex] حالت برای e داریم. رنگ e نباید مشابه a و d باشه. خود d هم نباید همرنگ c و طبق فرض همرنگ a باشه.
(۲۳ دى ۱۳۹۲ ۱۰:۳۰ ب.ظ)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]
(۲۳ دى ۱۳۹۲ ۱۰:۳۰ ب.ظ)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]
e رو بعد از d رنگ میکنیم. البته فکر کنم یه حالت رو درنظر نگرفتم. حالتی که رنگ a و c یکیه روی d تاثیر میذاره.
(۲۳ دى ۱۳۹۲ ۱۱:۱۲ ب.ظ)Jooybari نوشته شده توسط: e رو بعد از d رنگ میکنیم. البته فکر کنم یه حالت رو درنظر نگرفتم. حالتی که رنگ a و c یکیه روی d تاثیر میذاره.گیر من همینجاست
اگه d را قبل از e رنگ میکنیم
این حالات پیش میاد واسه موقعی که قراره رنگ a و d یکی نباشه
۱/ اگه رنگ a و c یکی باشه d میشه [tex]\lambda-1[/tex] حالت
۲/ اگه رنگ a و c یکی نباشه اونوقت d میشه [tex]\lambda-2[/tex] حالت
که تو هر دو حالت e میشه [tex]\lambda-2[/tex] حالت
یه حالت هم که گفته بودید a و d یه رنگ باشن که d میشه یک و e میشه [tex]\lambda-1[/tex] که در کل میشه ۳ حالت
حالا اشکال کار من کجاست؟
اینم بگم امروز داشتم تست گسسته میزدم و فکرم خیلی خوب کار نمیکنه.
فکر کنم فردا روش فکر کنم بهتر باشه
آقای جویباری یه چیز دیگه هم منو گیج کرده. تو کتاب پارسه نوشته چند جمله ای فامی گراف دور میشه
[tex](\lambda -1) ^n (-1)^n(\lambda -1)[/tex]
که گفته اگه دور زوج باشه عدد فامی اون میشه ۲ و اگه دور فرد باشه عدد فامی اون میشه ۳
و اگه تو معادله ای که شما بدست آوردید مقدار ۲ بذاریم جواب میشه ۲ در صورتی که اگه تو معادله بالا بذاریم جواب میشه صفر و با دو رنگ هم نمیشه این گراف رو رنگ کرد
من خیلی تو این مبحث تسلط ندارم ولی یه کم برام سوال شده که اینا چرا جور در نمیاد
تشکر
(۲۴ دى ۱۳۹۲ ۰۷:۵۵ ق.ظ)masoud67 نوشته شده توسط: آقای جویباری یه چیز دیگه هم منو گیج کرده. تو کتاب پارسه نوشته چند جمله ای فامی گراف دور میشه
[tex](\lambda -1) ^n (-1)^n(\lambda -1)[/tex]
که گفته اگه دور زوج باشه عدد فامی اون میشه ۲ و اگه دور فرد باشه عدد فامی اون میشه ۳
و اگه تو معادله ای که شما بدست آوردید مقدار ۲ بذاریم جواب میشه ۲ در صورتی که اگه تو معادله بالا بذاریم جواب میشه صفر و با دو رنگ هم نمیشه این گراف رو رنگ کرد
من خیلی تو این مبحث تسلط ندارم ولی یه کم برام سوال شده که اینا چرا جور در نمیاد
تشکر
درسته. منم گفتم شرط همرنگی a و c رو به اشتباه درنظر نگرفتم. یه حالت دیگه هم به حالات جوابم باید اضافه بشه.
(۲۴ دى ۱۳۹۲ ۰۸:۵۰ ق.ظ)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]
و در کل با اون فرمول گراف دور یکی میشه