سوالي از تركيبيات

Olympiad

New Member
ارسال ها
1,268
لایک ها
134
امتیاز
0
#1
در يك جنگل 9 حيوان زندگي ميكنند و هر حيوان يك لانه براي خود دارد.بين هر دو لانه نيز يك مسير وجود دارد.براي انتخاب سلطان جنگل،عده اي از حيوانات نامزد مي شوند.هر يك از اين نامزدها تصميم گرفتند براي تبليغات انتخابي از لانه ي خود شروع كرده و با استفاده از مسيرهاي بين لانه ها به لانه ي تمام حيوانات ديگر برود و در پايان به لانه ي خود برگردد. (البته به هيچ لانه اي دو بار وارد نميشود)پس از پايان تبليغات انتخابي معلوم شد از هيچ يك از مسيرهاي بين دو لانه بيش از يك نامزد عبور نكرده است.حداكثر تعداد نامزذهاي انتخاباتي سلطان جنگل را بيابيد.
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#2
Olympiad گفت
در يك جنگل 9 حيوان زندگي ميكنند و هر حيوان يك لانه براي خود دارد.بين هر دو لانه نيز يك مسير وجود دارد.براي انتخاب سلطان جنگل،عده اي از حيوانات نامزد مي شوند.هر يك از اين نامزدها تصميم گرفتند براي تبليغات انتخابي از لانه ي خود شروع كرده و با استفاده از مسيرهاي بين لانه ها به لانه ي تمام حيوانات ديگر برود و در پايان به لانه ي خود برگردد. (البته به هيچ لانه اي دو بار وارد نميشود)پس از پايان تبليغات انتخابي معلوم شد از هيچ يك از مسيرهاي بين دو لانه بيش از يك نامزد عبور نكرده است.حداكثر تعداد نامزذهاي انتخاباتي سلطان جنگل را بيابيد.
با گراف K[SUB]9[/SUB] متناظر می کنیم. گراف K[SUB]9[/SUB] دقیقا
راس دارد. هر یک از نامزدها باید دوری همیلتنی را طی کند که طول آن 9 است. پس حداکثر 4 نفر ممکن است نامزد باشند. فکر نمی کنم ارائه ی یک مثال کار سختی باشد!
 
بالا