پاسخ : سوال گراف
سوال جالبی بود، فقط اضافه می کنم تطابق کامل یعنی یه مجموعه یال M که هر راسی در سر دقیقا یکی از این یال ها اومده باشه. ( => هیچ دو یالی راس مشترک ندارند )
اوّل ثابت می کنیم اگه g تطابق کامل داشته باشه می شه به مسیر های به طول سه افراز کرد: همه یال ها تطابق رو حذف می کنیم. ==> همه رئوس درجه اشون 2 می شه و گرافی شامل چند دور به وجود میاد. ( اثباتش راحته ). حالا هر کدوم از یالایی رو که حذف کردیم اضافه می کنیم و دو تا یال دیگه رو هم در جهت عقربه های ساعت در دور، به مسیر اضافه می کنیم. راحت می شه فهمید مسیر ها همپوشانی ندارند. ( اگه با این چیزی که گفتم پیش برید )
حالا ثابت می کنیم که اگه مسیر های به طول سه داشته باشه، تطابق کامل داره. یال های میانی مسیر های به طول 3 را حذف کنید. همه رئوس درجه اشون دو می شه ( چرا؟ ) حالا اون یال هایی رو که حذف کردیم به مجموعه تطابق اضافه می کنیم تا تطابق کامل به دست بیاد.
سوال جالبی بود، فقط اضافه می کنم تطابق کامل یعنی یه مجموعه یال M که هر راسی در سر دقیقا یکی از این یال ها اومده باشه. ( => هیچ دو یالی راس مشترک ندارند )
اوّل ثابت می کنیم اگه g تطابق کامل داشته باشه می شه به مسیر های به طول سه افراز کرد: همه یال ها تطابق رو حذف می کنیم. ==> همه رئوس درجه اشون 2 می شه و گرافی شامل چند دور به وجود میاد. ( اثباتش راحته ). حالا هر کدوم از یالایی رو که حذف کردیم اضافه می کنیم و دو تا یال دیگه رو هم در جهت عقربه های ساعت در دور، به مسیر اضافه می کنیم. راحت می شه فهمید مسیر ها همپوشانی ندارند. ( اگه با این چیزی که گفتم پیش برید )
حالا ثابت می کنیم که اگه مسیر های به طول سه داشته باشه، تطابق کامل داره. یال های میانی مسیر های به طول 3 را حذف کنید. همه رئوس درجه اشون دو می شه ( چرا؟ ) حالا اون یال هایی رو که حذف کردیم به مجموعه تطابق اضافه می کنیم تا تطابق کامل به دست بیاد.
- ارسال ها
- 9
- لایک ها
- 0
- امتیاز
- 0
پاسخ : سوال گراف
1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به v1 فرد تا یال وصل باشد؟
2_ 1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به همه ی راس ها ذوج تا یال وصل باشد؟
3_آقای x و خانم y به نمایندگی کشور انگلستان در جلسه ای شرکت کرده اند. از 3 کشور دیگر نیز 2 نفر در آن جلسه وجود دارند. پس از دست دادن آنها آقای x از همه ی حاظرین درباره ی تعداد دست دادن هایشان میپرسد.با نهایت تعجب همه ی جواب ها متفاوت بود.آقای x با چند نفر دست داده است؟(تعداد دست دادن ها از 0 تا 6 است)
پ.ن: خیلی ممنون میشم اگه جواب بدین . :63:
1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به v1 فرد تا یال وصل باشد؟
2_ 1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به همه ی راس ها ذوج تا یال وصل باشد؟
3_آقای x و خانم y به نمایندگی کشور انگلستان در جلسه ای شرکت کرده اند. از 3 کشور دیگر نیز 2 نفر در آن جلسه وجود دارند. پس از دست دادن آنها آقای x از همه ی حاظرین درباره ی تعداد دست دادن هایشان میپرسد.با نهایت تعجب همه ی جواب ها متفاوت بود.آقای x با چند نفر دست داده است؟(تعداد دست دادن ها از 0 تا 6 است)
پ.ن: خیلی ممنون میشم اگه جواب بدین . :63:
- ارسال ها
- 9
- لایک ها
- 0
- امتیاز
- 0