سوال گراف

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#2
پاسخ : سوال گراف

سوال جالبی بود، فقط اضافه می کنم تطابق کامل یعنی یه مجموعه یال M که هر راسی در سر دقیقا یکی از این یال ها اومده باشه. ( => هیچ دو یالی راس مشترک ندارند )
اوّل ثابت می کنیم اگه g تطابق کامل داشته باشه می شه به مسیر های به طول سه افراز کرد: همه یال ها تطابق رو حذف می کنیم. ==> همه رئوس درجه اشون 2 می شه و گرافی شامل چند دور به وجود میاد. ( اثباتش راحته ). حالا هر کدوم از یالایی رو که حذف کردیم اضافه می کنیم و دو تا یال دیگه رو هم در جهت عقربه های ساعت در دور، به مسیر اضافه می کنیم. راحت می شه فهمید مسیر ها همپوشانی ندارند. ( اگه با این چیزی که گفتم پیش برید )
حالا ثابت می کنیم که اگه مسیر های به طول سه داشته باشه، تطابق کامل داره. یال های میانی مسیر های به طول 3 را حذف کنید. همه رئوس درجه اشون دو می شه ( چرا؟ ) حالا اون یال هایی رو که حذف کردیم به مجموعه تطابق اضافه می کنیم تا تطابق کامل به دست بیاد.
 

MMR.ARSHAM

New Member
ارسال ها
9
لایک ها
0
امتیاز
0
#4
پاسخ : سوال گراف

1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به v1 فرد تا یال وصل باشد؟

2_ 1_با مجموعه راس های v1 تا v6 چند گراف ساده میتوان رسم کرد که به همه ی راس ها ذوج تا یال وصل باشد؟

3_آقای x و خانم y به نمایندگی کشور انگلستان در جلسه ای شرکت کرده اند. از 3 کشور دیگر نیز 2 نفر در آن جلسه وجود دارند. پس از دست دادن آنها آقای x از همه ی حاظرین درباره ی تعداد دست دادن هایشان میپرسد.با نهایت تعجب همه ی جواب ها متفاوت بود.آقای x با چند نفر دست داده است؟(تعداد دست دادن ها از 0 تا 6 است)

پ.ن: خیلی ممنون میشم اگه جواب بدین . :63:
 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#5
پاسخ : سوال گراف

سوال 1
اگه راس اولی رو کلا جدا کنیم بین بقیه به
میتونیم یال بکشیم
حالا میایم همسایه های راس اولی رو مشخص میکنیم
یا یه همسایه داره که میشه
حالت (5)
یا سه تا همسایه داره
که میشه (10)
یا 5 تا داره که میشه 1 حالت
جواب هم میشه:

البته اگه اشتباه نکرده باشم
 

MMR.ARSHAM

New Member
ارسال ها
9
لایک ها
0
امتیاز
0
#6
پاسخ : سوال گراف

گرافی داریم که دنباله درجات راس های آن 8_7_6_5_4_3_3_2_1_1 است. از روی این گراف گرافی جدید میسازیم به این صورت که به ازای هر یال این گراف یک راس قرار میدیم و 2 تا یالی که در گراف اولیه راس مشترک دارند , در گراف جدید به هم وصل میکنیم. گراف جدید چند یال دارد؟


 

sa1378

New Member
ارسال ها
1,403
لایک ها
1,077
امتیاز
0
#7
پاسخ : سوال گراف

گرافی داریم که دنباله درجات راس های آن 8_7_6_5_4_3_3_2_1_1 است. از روی این گراف گرافی جدید میسازیم به این صورت که به ازای هر یال این گراف یک راس قرار میدیم و 2 تا یالی که در گراف اولیه راس مشترک دارند , در گراف جدید به هم وصل میکنیم. گراف جدید چند یال دارد؟


جواب میشه 2 از 8 بهعلاوه 2 از 7 به علاوه ...
چون به ازای هر دو یالی که در یک راس مشترک هستن یه یال تشکیل میشه
 
بالا