سلام دوستان.
لطفن اگه کسی میدونه این سوالو توضیح بده چرا اینطوری میشه؟
[tex]P(W_{n},\lambda )=\lambda (C_{n},\lambda -1)[/tex]
ادامه این سوال اینه که باید ثابت کنیم که [tex]P(W_{n},\lambda ) =\lambda (\lambda-2)^{n} \lambda (-1)^{n}(\lambda-2)[/tex]
اگه بالایی رو توضیح بدین این اثباتشو بلدم فقط مشکلم اینجاس که وقتی مثلن[tex]P(W_{4},\lambda )[/tex] رو میخوام خودم بدون فرمول پیدا کنم جواب اون نمیاد طبق فرمول باید جواب بیاد [tex]P(W_{4},\lambda ) =\lambda (\lambda-2)^{4} \lambda(\lambda-2)[/tex]
ولی وقتی خودم بدست میارم این نمیشه.
[tex]W_{4}[/tex] به شکل زیره دیگه.
[attachment=4133]
فرض کنیم راس ۱ ، [tex]\lambda[/tex] باشه راس ۲ نباید همرنگ راس ۱ باشه پس میشه به [tex]\lambda-1[/tex] طریق رنگ کرد و راس ۳ نباید همرنگ ۲ بشه پس باز به [tex]\lambda-1[/tex] طریق و راس ۴ نه باید به رنگ ۱ و نه ۳ باشه پس به [tex]\lambda-2[/tex] طریق و راس ۵ هم به [tex]\lambda-4[/tex] طریق. نمیدونم این روش من درسته یا نه ولی جواب اون نمیاد که!!!
چنتا دیگه از گرافارو هم امتحان میکنم ولی جواب اونی که باید بیاد نمیشه.کجای کارم ایراد داره.لطفن راهنمایی کنین.
P ، W و لاندا اینجا چی هستن؟
این سوال از مبحث چند جمله ای گرافهاس.
[tex]W_{n}[/tex] نماد گرف چرخ با n+1 راس که شبیه عکس بالاییه.و [tex]C_{n}[/tex] هم نماد مداره و p هم یعنی چند جمله ای یه گراف که اینجا چرخه یعنی پیدا کردن تعداد طرق رنگ کردن گراف. لاندا هم که تعداد طرق رنگ آمیزی هر راس گراف.
ممنون توضیح دادی
اما مثل اینکه در سطح من نیست!
[tex]P(W_{n},\lambda )[/tex]
یعنی چی؟ تعداد راه های رنگ کردن گراف چرخ n+1 راسی با...
میتونی یه بار دیگه دو طرف معادله رو فارسی به من بگی؟
تعریف چند جمله ای رنگی گراف G اینه: فرض کنیم G یه گراف و [tex]\lambda[/tex] تعداد رنگهای ممکن برای رنگ آمیزی هر راس G باشه تابع چند جمله ای [tex]P(G,\lambda )[/tex] بنام چندجمله ای رنگی G هست که برحسب متغیر [tex]\lambda[/tex] هست به ما میگه که به چند طریق مختلف میشه با حداکثر [tex]\lambda[/tex] رنگ کل رئوس گراف رو رنگ کرد.
مثلن برای یک مسیر با n راس که اینم با [tex]P_{n}[/tex]نشون میدیم چند جمله ای رنگیمون میشه[tex]P(P_{n},\lambda )=\lambda (\lambda -1)^{n-1}[/tex]
اینم به این طریق ثابت میشه که : برای رنگ آمیزی راس اول از یکی از حداکثر [tex]\lambda[/tex] تعداد رنگ مختلف میشه استفاده کرد.برای راس دوم چون مجاور راس اولیه و نباید همرنگ راس اولی بشه پس اگه از[tex]\lambda[/tex] اون رنگی که برا راس اولی استفاده شده رو برداریم با حداکثر [tex]\lambda-1[/tex] رنگ مختلف میشه راس دومی رو رنگ کرد.راس سومی هم چون مجاور راس دومیه به همون طریقی که گفتم به [tex]\lambda-1[/tex] طریق میشه رنگ آمیزی کرد. تا راس n ام همین روال ادامه داره.با اصل ضرب رابطه ی [tex]\lambda (\lambda -1)^{n-1}[/tex] بدست میاد.
حالا گراف چرخم یه نمونشه. که من خودم توش موندم چرا وقتی خودم رنگ آمیزی میکنم با اون فرموله یکی نمیشه.
سلام. بهتره اول راس وسط رو رنگ کنیم. چون راسهای با اختلاف یک (مثل ۲ و ۴) میتونن همرنگ باشن. رنگ آمیزی میشه برای راس وسط [tex]\lambda[/tex] برای راس ۱ میشه [tex]\lambda -1[/tex] برای راس ۲ میشه [tex]\lambda -2[/tex] چون با وسط و ۱ مجاوره. برای راس ۳ تا n-1 (برای [tex]W_n[/tex] میشه [tex]\lambda -2[/tex] چون فقط با راس قبلی و وسطی مجاورن. حالا اگه n زوج باشه حالتی پیش میاد که رنگها یکی درمیون مثل هم باشن تعداد حالت میشه [tex]\lambda -2[/tex] و ممکن هم هست مثل هم نباشن که میشه [tex]\lambda -3[/tex]. برای n های فرد هم میشه [tex]\lambda -3[/tex].
نمیگم راه حلم درسته. ولی فکر کنم ترتیب رنگ آمیزی باید به این شکل باشه. از این مبحث سوال حل نکردم و زیاد وارد نیستم. شاید ضرایبو اشتباه نوشته باشم.
تشکر. کاش میشد به هرطریقی که میخوایم رنگ آمیزی کنیم جواب درست بدست میومد.
یه سوال:اصلن این مبحث چند جمله ای ها مهمه برا ارشد؟
جواب اینو میدونید که چرا اینطوری میشه؟[tex]P(W_{n},\lambda )=\lambda (C_{n},\lambda -1)[/tex]
اره تا حدودی سوال آخر گسسته امسال یه گراف داده بود و چند گزاره که باید درست بودن اون چند گزاره رو ما می فهمیدیم یکی از اون گزاره ها در مورد رنگ آمیزی بود
رنگ آمیزی گراف همیشه از راس با بیشترین درجه شروع میشه.به نظر من شما درست گفتید آقای lakikharin
ممنون .یاد گرفتم همیشه از بیشترین درجه شروع کنم.ولی من هنوز قانع نشدم.
با این روش هم[tex]P(W_{4},\lambda ) =\lambda (\lambda-2)^{4} \lambda(\lambda-2)[/tex] بدست نمیاد که باز
فکر کنم بهتره اول منظور جمله اولو بگم و بعد با این تعریف روش حلمو بگم:
منظور از [tex]W_n[/tex] چرخیه که مرکزش به n نقطه از محیط حلقه چرخ وصله. تعداد حالات رنگ آمیزیش با [tex]\lambda[/tex] رنگ برابر تعداد حالاتیه که یکی از این [tex]\lambda[/tex] رنگ رو به مرکزش نسبت بدیم و n نقطه روی حلقه رو با [tex]\lambda-1[/tex] رنگ، رنگ آمیزی کنیم. [tex]C_n[/tex] هم حلقه n نقطه ایه ماست. پس فرمول اولیه ثابت شد.
حالا میخاهیم تعداد حالات رنگ آمیزی حلقه (نه چرخ) رو بدست بیاریم. چون ساده تره و براحتی قابل تبدیل به تعداد حالات رنگ آمیزی چرخه.
با توجه به شکل پیوست تعداد حالات رنگ آمیزی با [tex]\lambda[/tex] رنگ چرخ با n راس (A) برابر با مجموع دو شکل B (دوطرف راس جداشده همرنگ نباشند) و C (دوطرف راس جداشده همرنگ باشند) میشه. یک رابطه بازگشتی برای این حالات میشه:
[tex]C_{n,\lambda}=(\lambda-2)C_{n-1,\lambda} (\lambda-1)C_{n-2,\lambda}[/tex]
[tex]C_{2,\lambda}=\lambda(\lambda-1)[/tex]
[tex]C_{3,\lambda}=\lambda(\lambda-1)(\lambda-2)[/tex]
[tex]C_{2,\lambda}=\lambda(\lambda-1)[/tex]
[tex]C_{3,\lambda}=\lambda(\lambda-1)(\lambda-2)[/tex]
فکر کنم [tex]W_4[/tex] همین مقدار بشه و بقیه با استقرا ثابت بشن:
[tex]W_{4,\lambda}=\lambda C_{4,\lambda-1}=\lambda((\lambda-3)C_{3,\lambda-1} (\lambda-2)C_{2,\lambda-1})[/tex]
[tex]=\lambda((\lambda-3)(\lambda-1)(\lambda-2)(\lambda-3) (\lambda-2)(\lambda-1)(\lambda-2))[/tex]
[tex]=\lambda(\lambda-2)((\lambda-3)(\lambda-1)(\lambda-3) (\lambda-1)(\lambda-2))[/tex]
[tex]=\lambda(\lambda-2)(\lambda^3-6\lambda^2 12\lambda-7)[/tex]
[tex]=\lambda(\lambda-2)((\lambda-2)^3-1)=\lambda(\lambda-2)^4 \lambda(\lambda-2)[/tex]
[tex]=\lambda(\lambda-2)((\lambda-3)(\lambda-1)(\lambda-3) (\lambda-1)(\lambda-2))[/tex]
[tex]=\lambda(\lambda-2)(\lambda^3-6\lambda^2 12\lambda-7)[/tex]
[tex]=\lambda(\lambda-2)((\lambda-2)^3-1)=\lambda(\lambda-2)^4 \lambda(\lambda-2)[/tex]
رابطه بازگشتیم فکر کنم درست باشه. برای n=4 هم جوابم با جواب شما یکی شد. اگه استدلال یا رابطه بازگشتی رو متوجه نشدید بگید که بیشتر توضیح بدم.
معذرت میخوام میشه بیشتر توضیح بدین این شکل پیوست و اون رابطه بازگشتی رو چجوری پیدا کردین؟ نخوندم اصلن همچین چیزی!
از روی شکل یک خونه رو که توی C جدا شده رو درنظر بگیرید. اگه رنگ راسهای دوطرفش یکی باشه شکل C بوجود میاد. یعنی راس حذف شده همرنگ راسیه که راس از درجه یک بهش وصله. اگرم دو راس همرنگ نباشن پس میشه بهم وصلشون کرد.
به عبارت دیگه چپ ترین راس رو توی گراف A درنظر بگیرید. رئوس مجاورش اگه همرنگ نباشن میشه اونارو بهم وصل کرد که شکل B بوجود میاد و اگه همرنگ باشن، چپ ترین راس درجش یک میشه و میتونه لاندا منهای یک رنگ بگیره. یکی از دوراس مجاورش حذف میشه و راس مجاور راس حذف شده به راس حذف نشده وصل میشه.
(۱۶ اردیبهشت ۱۳۹۱ ۱۰:۴۳ ب.ظ)Arshad92 نوشته شده توسط: میشه بیشتر توضیح بدین این شکل پیوست و اون رابطه بازگشتی رو چجوری پیدا کردین؟اگر منظورتوت این رابطه است:
(۱۶ اردیبهشت ۱۳۹۱ ۰۵:۵۸ ق.ظ)Lakikharin نوشته شده توسط:رابطه بازگشتی نیست.بلکه به این معنیه که : برای گره اول به تعدا \lambda تا رنگ در اختیار داریم،برای گره دوم که همسایه این گره هستlambda-1\ (چون یکی از رنگها استفاده شده) و به همین ترتیب lambda -2\ و... و بعد همه اینها را در هم ضرب میکنیم.حاصل اون یک چند جمله ای هست.که درجه این چند جمله ای نشان دهنده تعداد رنگ مورد نیاز برای رنگ آمیزی هست[tex]C_{n,\lambda}=(\lambda-2)C_{n-1,\lambda} (\lambda-1)C_{n-2,\lambda}[/tex]
[tex]C_{2,\lambda}=\lambda(\lambda-1)[/tex]
[tex]C_{3,\lambda}=\lambda(\lambda-1)(\lambda-2)[/tex]
فکر کنم [tex]W_4[/tex] همین مقدار بشه و بقیه با استقرا ثابت بشن:
[tex]W_{4,\lambda}=\lambda C_{4,\lambda-1}=\lambda((\lambda-3)C_{3,\lambda-1} (\lambda-2)C_{2,\lambda-1})[/tex]
[tex]=\lambda((\lambda-3)(\lambda-1)(\lambda-2)(\lambda-3) (\lambda-2)(\lambda-1)(\lambda-2))[/tex]
[tex]=\lambda(\lambda-2)((\lambda-3)(\lambda-1)(\lambda-3) (\lambda-1)(\lambda-2))[/tex]
[tex]=\lambda(\lambda-2)(\lambda^3-6\lambda^2 12\lambda-7)[/tex]
[tex]=\lambda(\lambda-2)((\lambda-2)^3-1)=\lambda(\lambda-2)^4 \lambda(\lambda-2)[/tex]
(۱۵ اردیبهشت ۱۳۹۱ ۰۲:۴۰ ب.ظ)Arshad92 نوشته شده توسط: سلام دوستان.
لطفن اگه کسی میدونه این سوالو توضیح بده چرا اینطوری میشه؟
[tex]P(W_{n},\lambda )=\lambda (C_{n},\lambda -1)[/tex]
ادامه این سوال اینه که باید ثابت کنیم که [tex]P(W_{n},\lambda ) =\lambda (\lambda-2)^{n} \lambda (-1)^{n}(\lambda-2)[/tex]
اگه بالایی رو توضیح بدین این اثباتشو بلدم فقط مشکلم اینجاس که وقتی مثلن[tex]P(W_{4},\lambda )[/tex] رو میخوام خودم بدون فرمول پیدا کنم جواب اون نمیاد طبق فرمول باید جواب بیاد [tex]P(W_{4},\lambda ) =\lambda (\lambda-2)^{4} \lambda(\lambda-2)[/tex]
ولی وقتی خودم بدست میارم این نمیشه.
[tex]W_{4}[/tex] به شکل زیره دیگه.
فرض کنیم راس ۱ ، [tex]\lambda[/tex] باشه راس ۲ نباید همرنگ راس ۱ باشه پس میشه به [tex]\lambda-1[/tex] طریق رنگ کرد و راس ۳ نباید همرنگ ۲ بشه پس باز به [tex]\lambda-1[/tex] طریق و راس ۴ نه باید به رنگ ۱ و نه ۳ باشه پس به [tex]\lambda-2[/tex] طریق و راس ۵ هم به [tex]\lambda-4[/tex] طریق. نمیدونم این روش من درسته یا نه ولی جواب اون نمیاد که!!!
چنتا دیگه از گرافارو هم امتحان میکنم ولی جواب اونی که باید بیاد نمیشه.کجای کارم ایراد داره.لطفن راهنمایی کنین.
سلام
رشته من گراف تئوری هست و کاملا مطمینم که جوابی که بهت میدم درسته!
یک چرخ n راسی از یک دور n-1 راسی و یک تک راس تشکیل شده که همه ریوس اون دور به این تک راس وصل هستند.
ما میدونیم که چندجمله ای رنگی دور n راسی به صورت زیر است
[tex]P(C_{n},x)=(x-1)^{n} (-1)^{n}(x-1)[/tex]
همانطور که گفتیم هر دور از وصل کردن تمام راس های یک دور n-1 راسی به یک راس به دست می آید لذا داریم
[tex]W_{n}=C_{n-1}VK_{1}[/tex]
از طزف دیگر داریم
[tex]P(GVK_{1},x)=xP(G,x-1)[/tex]
حالا خواهیم داشت
[tex]P(W_{n-1}VK_{1},x)=xP(W_{n-1},x-1)[/tex]
که اگه با فرمول هایی که گفتم جاگذاری کنی به فرمول مورد نظرت میرسی
فقط توجه داشته باش که من به جای لانداها x گذاشتم!