چند گراف با مجموعه رئوس {۵و۴و۳و۲و۱}وجود دارد که درجه تمام رئوس انها زوج است؟
سوالشو دقیق نمیفهمم. ولی اگه منظورش تعداد گرافهای با ۵ راس نامگذاری شده باشه که درجه همه رئوسش زوج باشه میشه جمع حالات زیر
این حالات دنباله رئوس هستن)۰,۰,۰,۰,۰: ۱ حالت (انتخاب ۵ از ۵)
۲,۲,۲,۰,۰: ۱۰ حالت (انتخاب ۳ از ۵)
۲,۲,۲,۲,۰: ۱۵ حالت (تعداد دورهای بطول ۴ از ۵ راس)
۲,۲,۲,۲,۲: ۱۲ حالت (تعداد دورهای بطول ۵ در گراف ۵ راسی)
۴,۲,۲,۲,۲: ۱۵ حالت (۱ از ۵ برای راس درجه ۴ و ۳ حالت برای مجاورت بقیه رئوس)
۴,۴,۲,۲,۲: ۱۰ حالت (۲ از ۵ برای رئوس درجه ۴)
۴,۴,۴,۴,۴: ۱ حالت
جمع حالات میشه ۶۴ حالت. فکر نکنم حالت دیگه ای پیش بیاد.
خودمم همین تحلیلو داشتم فقط مشکلم تو قسمت ۰ ۲ ۲ ۲ ۲ بود که بجای تعداد دور بطول ۴ از اتخاب ۴ از ۵ استفاده کردم
مشکل اینکار کجاست؟چرا مثل حالت ۰ ۰ ۲ ۲ ۲ که شد انتخاب ۳ از ۵ برای این حالت صادق نیست؟
تعداد دورهای متفاوت بطول L از گراف Kp برابر است با:
[tex]\binom{p}{L}\frac{(L-1)!}{2}[/tex]
استدلال: باید L راس از p راس رو انتخاب کنیم. بعد مثل گردنبند حول یک راس ثابت بچینیمشون.( چون دوری مثل abcda با adcba یکی هستن.) چون یکی رو ثابت میگیریم (L-1)! میشه و چون برای هر دور ۲ حالت پیش میاد تقسیم بر ۲ میشه. این فرمول رو توی هرسه رابطه به ازای L=3,4,5 قرار بدین جواب میده. البته درمورد این فرمول قبلاً بحث شده بود. برای همین سریع ازش گذشته بودم.