![[تصویر: 63562_1_1379095921.png]](https://img.manesht.ir/63562_1_1379095921.png)
جواب ۱ است.چرا؟؟؟؟
این همون گراف پترسونه . این گراف دور به طول فرد داره و دوبخشی نیست . گفته زیر مجموعه های دو عضوی از مجموعه ۵ عضوی ای که داده پس تعداد رئوس گراف می شه [tex]\binom{5}{2}=10[/tex] . هر راس این گراف با [tex]\binom{3}{2}=3[/tex] راس دیگه همسایه و مجاور محسوب می شه . یعنی هر راس گراف درجه اش ۳ می شه . چون این گراف ۳-منتظم هست پس [tex]n\times d=2e[/tex] که n تعداد راس‌ها و d هم درجه همه رئوس است . پس این گراف [tex]10\times 3=30[/tex] پس ۱۵ یال دارد .
یه قضیه داریم که هر گرافی که عدد کروماتیکش ۲ باشه دوبخشیه و بالعکس . این گراف عدد کروماتیکش دو نیست پس دو بخشی هم نیست . شکل خود گراف رو هم برای این سوال کشیدم:
ترکیب ۲ از ۳ را از کجا می فهمیم
به غیر از پترسون بودن از روی مجموعه میشه فهمید؟؟؟؟
(۳۰ دى ۱۳۹۰ ۰۱:۰۴ ق.ظ)vijay نوشته شده توسط: ترکیب ۲ از ۳ را از کجا می فهمیم
به غیر از پترسون بودن از روی مجموعه میشه فهمید؟؟؟؟
صورت سوال گفته، رئوس در صورتی مجاورند که اشتراکات دوبه دوی اعضای آنها تهی باشه . پس مثلا زیرمجموعه {۱,۲} با زیر مجموعه هایی که شامل ۱ و ۲ هستند نمی تونه مجاور بشه . پس می مونه ۳ تا عدد ۳ و ۴ و ۵ . حالا از این ۳ تا عدد می خواهیم زیر مجموعه های دوتایی پیدا کنیم که می شه ترکیب ۲ از ۳ .
روشهای تشخیص گراف دوبخشی:
- رنگ آمیزی: باید بشه با ۲ تا رنگ رنگ آمیزی کرد.
- افراز به دو مجموعه جدا از هم
- حداکثر تعداد یالها در گراف دوبخشی n راسی، [tex]\left \lfloor \frac{n^{2}}{4} \right \rfloor[/tex] میشه
- گراف دوبخشی نباید دارای دور به طول فرد باشه
توی این گراف از مورد ۱ و ۴ میشه استفاده کرد .