P ، W و لاندا اینجا چی هستن؟

این سوال از مبحث چند جمله ای گرافهاس.

$W_{n}$ نماد گرف چرخ با n+1 راس که شبیه عکس بالاییه.و $C_{n}$ هم نماد مداره و p هم یعنی چند جمله ای یه گراف که اینجا چرخه یعنی پیدا کردن تعداد طرق رنگ کردن گراف. لاندا هم که تعداد طرق رنگ آمیزی هر راس گراف.

ممنون توضیح دادی
اما مثل اینکه در سطح من نیست!

$P(W_{n},\lambda )$
یعنی چی؟ تعداد راه های رنگ کردن گراف چرخ n+1 راسی با...
میتونی یه بار دیگه دو طرف معادله رو فارسی به من بگی؟

تعریف چند جمله ای رنگی گراف G اینه: فرض کنیم G یه گراف و $\lambda$ تعداد رنگهای ممکن برای رنگ آمیزی هر راس G باشه تابع چند جمله ای $P(G,\lambda )$ بنام چندجمله ای رنگی G هست که برحسب متغیر $\lambda$ هست به ما میگه که به چند طریق مختلف میشه با حداکثر $\lambda$ رنگ کل رئوس گراف رو رنگ کرد.

مثلن برای یک مسیر با n راس که اینم با $P_{n}$نشون میدیم چند جمله ای رنگیمون میشه$P(P_{n},\lambda )=\lambda (\lambda -1)^{n-1}$

اینم به این طریق ثابت میشه که : برای رنگ آمیزی راس اول از یکی از حداکثر $\lambda$ تعداد رنگ مختلف میشه استفاده کرد.برای راس دوم چون مجاور راس اولیه و نباید همرنگ راس اولی بشه پس اگه از$\lambda$ اون رنگی که برا راس اولی استفاده شده رو برداریم با حداکثر $\lambda-1$ رنگ مختلف میشه راس دومی رو رنگ کرد.راس سومی هم چون مجاور راس دومیه به همون طریقی که گفتم به $\lambda-1$ طریق میشه رنگ آمیزی کرد. تا راس n ام همین روال ادامه داره.با اصل ضرب رابطه ی $\lambda (\lambda -1)^{n-1}$ بدست میاد.

حالا گراف چرخم یه نمونشه. که من خودم توش موندم چرا وقتی خودم رنگ آمیزی میکنم با اون فرموله یکی نمیشه.

تشکر. کاش میشد به هرطریقی که میخوایم رنگ آمیزی کنیم جواب درست بدست میومد.
یه سوال:اصلن  این مبحث چند جمله ای ها مهمه برا ارشد؟ 
جواب اینو میدونید که چرا اینطوری میشه؟$P(W_{n},\lambda )=\lambda (C_{n},\lambda -1)$

اره تا حدودی سوال آخر گسسته امسال یه گراف داده بود و چند گزاره که باید درست بودن اون چند گزاره رو ما می فهمیدیم یکی از اون گزاره ها در مورد رنگ آمیزی بود

ممنون .یاد گرفتم همیشه از بیشترین درجه شروع کنم.ولی من هنوز قانع نشدم.
با این روش هم$P(W_{4},\lambda ) =\lambda (\lambda-2)^{4} \lambda(\lambda-2)$ بدست نمیاد که باز

معذرت میخوام میشه بیشتر توضیح بدین این شکل پیوست و اون رابطه بازگشتی رو چجوری پیدا کردین؟ نخوندم اصلن همچین چیزی!

(۱۶ اردیبهشت ۱۳۹۱ ۱۰:۴۳ ب.ظ)Arshad92 نوشته شده توسط:  میشه بیشتر توضیح بدین این شکل پیوست و اون رابطه بازگشتی رو چجوری پیدا کردین؟

اگر منظورتوت این رابطه است:

(۱۶ اردیبهشت ۱۳۹۱ ۰۵:۵۸ ق.ظ)Lakikharin نوشته شده توسط:  

$C_{n,\lambda}=(\lambda-2)C_{n-1,\lambda} (\lambda-1)C_{n-2,\lambda}$
$C_{2,\lambda}=\lambda(\lambda-1)$
$C_{3,\lambda}=\lambda(\lambda-1)(\lambda-2)$

فکر کنم $W_4$ همین مقدار بشه و بقیه با استقرا ثابت بشن:

$W_{4,\lambda}=\lambda C_{4,\lambda-1}=\lambda((\lambda-3)C_{3,\lambda-1} (\lambda-2)C_{2,\lambda-1})$

$=\lambda((\lambda-3)(\lambda-1)(\lambda-2)(\lambda-3) (\lambda-2)(\lambda-1)(\lambda-2))$
$=\lambda(\lambda-2)((\lambda-3)(\lambda-1)(\lambda-3) (\lambda-1)(\lambda-2))$
$=\lambda(\lambda-2)(\lambda^3-6\lambda^2 12\lambda-7)$
$=\lambda(\lambda-2)((\lambda-2)^3-1)=\lambda(\lambda-2)^4 \lambda(\lambda-2)$

رابطه بازگشتی نیست.بلکه به این معنیه که : برای گره اول به تعدا \lambda تا رنگ در اختیار داریم،برای گره دوم که همسایه این گره هستlambda-1\ (چون یکی از رنگها استفاده شده) و به همین ترتیب lambda -2\ و... و بعد همه اینها را در هم ضرب میکنیم.حاصل اون یک چند جمله ای هست.که درجه این چند جمله ای نشان دهنده تعداد رنگ مورد نیاز برای رنگ آمیزی هست