مسابقه‌ی تصادفی

 
 
 شماره‌گذاري رؤوس يك گراف (مسابقه‌ي شماره‌ي 76)
شماره‌گذاري رؤوس يك گراف (مسابقه‌ي شماره‌ي 76)مسابقه كامپيوتر
شمارش و نظريه‌ي گراف‌ها ... سؤال همراه با جواب

شماره‌گذاري

رؤوس يك گراف





اشاره
آن‌چه با عنوان «چكيده» در اول مسابقه‌ها و زنگ‌تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.


چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي – دانش
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها و روش‌شناسي»
 اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «ترجمه» > «تفسير»
    - «فهميدن» > «ترجمه» > «تحليل» > «تحليل روابط»
    - «فهميدن» > «ترجمه» > «تركيب» > «توليد يك نقشه يا مجموعه‌ اقدام‌هاي پيشنهادي»
    - «فهميدن» > «ترجمه» > «تركيب» > «استنتاج مجموعه‌اي از روابط انتزاعي»
 نتايج مورد نظر 
    - آشنايي با گراف‌ها
    - روش حل مسأله با استفاده از شمارش
 محتواي آموزشي
    - نظريه‌ي گراف‌ها
    - شمارش.





شكل 1.

 

سؤال
در شكل 1 هر رأس با يكي از مقسوم‌عليه‌هاي متفاوت 2008 ‌شماره‌گذاري مي‌شود به‌گونه‌اي كه اگر دو رأس با يك يال به يكديگر مرتبط شده باشند شماره‌‌ي يك رأس بر شماره‌ي رأس ديگر بخش‌پذير باشد.

به‌نظر شما به چند روش مختلف مي‌توان رؤوس شكل 1 را شماره‌گذاري كرد؟




ياداوري
زماني كه با دوران يا انعكاس بتوان شماره‌گذاري ديگري را به‌دست آورد آن دو نوع شماره‌گذاري «يكسان» خواهند بود.




جواب

مقسوم‌عليه‌‌هاي عدد 2008 شامل اعداد 1، 2، 4، 8، 251، 502 و 1004 هستند. شش زوج از اين اعداد ويژگي مود نظر را تأمين نمي‌كنند (اين‌كه يكي بر ديگري بخش‌پذير باشد):





اين زوج‌ها با يك يال، قابل ارتباط با يكديگر نيستند.

 

شكل 2.

رؤوس شكل 1 را با حروف  مشخص مي‌كنيم (شكل 2).

هر شكلي كه امكان دارد جواب مسأله را تأمين كند به‌گونه‌اي دوران مي‌دهيم كه عدد 251 بر روي نقطه‌ي C قرار گيرد. همان‌طور كه در شكل 2 مشاهده مي‌شود هر رأس در شكل 2 با يال‌هايي به چهار رأس ديگر متصل شده ولي با سه رأس ديگر مرتبط نيست.

چون عدد 251 نمي‌تواند به اعداد 2، 4 يا 8 مرتبط شود سه عدد ديگر بايد در سه نقطه‌اي قرار گيرد كه در شمال شكل واقع شده است يعني نقاط: .

اكنون موقعيت‌هاي متفاوت عدد 8 را در اين سه محل درنظر مي‌گيريم:

 

شكل 3.

حالت اول - عدد 8 در موقعيت A قرار دارد

تنها دو مقسوم‌عليه‌اي كه مي‌توانند در موقعيت B و D باشند به‌ترتيب اعداد 1 و 2008 هستند. اكنون انعكاس شكل را بر خط منطبق بر محور AC در نظر مي‌گيريم به‌گونه‌اي كه عدد 1 در نقطه‌ي B و عدد 2008 در نقطه‌ي D قرار بگيرد.

 

شكل 4.

اعداد 2 و 4 نقاط AD و AB را اشغال مي‌كنند به‌گونه‌اي كه اعداد 502 و 1004 در نقاط CD و CB قرار مي‌گيرند. تنها زوج ممنوع  است به‌گونه‌اي كه اگر عدد 4 در نقطه‌ي AD باشد عدد 502 در نقطه‌ي BC خواهد بود. هم‌چنين اگر عدد 4 در نقطه‌ي AB باشد عدد 502 در نقطه‌ي CD خواهد بود.

در شكل 4 دو جواب براي اين حالت نشان داده شده است.

 

شكل 5.




حالت دوم - عدد 8 در موقعيت A قرار ندارد

اگر عدد 8 در موقعيت A قرار نداشته باشد انعكاس شكل را بر روي خط منطبق بر محور AC در نظر مي‌گيريم؛ به‌گونه‌اي كه عدد 8 در نقطه‌ي AD قرار گيرد. در اين صورت، اعداد 2 و 4 به‌ترتيب در نقاط A و AD قرار مي‌گيرد در حالي كه اعداد 502 و 1004 در نقاط B و BC خواهند بود تا هيچ يالي با عدد 8 مرتبط نشود.

با توجه به آن‌كه اعداد 4 و 502 نمي‌توانند از طريق يك يال به يكديگر مرتبط شوند تنها بايد عدد 4 در نقطه‌ي A و عدد 502 در نقطه‌ي BC قرار داشته باشد.

در اين صورت عدد 2 در نقطه‌ي AB و عدد 1004 در نقطه‌ي B قرار خواهند گرفت. بنابراين تنها مقسوم‌عليه‌هاي اعداد 1 و 2008 مي‌توانند در نقطه‌ي D يا CD واقع شوند.


بنابراين با توجه به دو امكان شماره‌گذاري در هر حالت، جمعاً چهار روش براي شماره‌گذاري وجود خواهد داشت.

1387/2/19لينک مستقيم

فرستنده :
هادي يامي HyperLink HyperLink 1387/2/25
مـتـن : اولا من با نظر دوم شخص قبلي موافقم و دوما فكر مي كنم جواب 16شود از آنجايي كه جوابم راه تشريحيش طولاني است حال و حوصله ي تايپ آن را ندارم. لطفا اگر مي شود خودتان را نيز معرفي كنيد.
پاسـخ :ايميل فرستنده: hadi_yamico@yahoo.com
تاريخ ارسال: 1387/2/24

هادي جان!
ضمن تشكر از شما
از اين‌كه اين‌چنين با شجاعت در پاسخگويي به اين سؤال شركت كردي تشكر مي‌كنيم.
ولي دوست خوبم!
براي اين‌كه ساير دوستانت هم از روش تفكر و استدلال شما اگاه باشن راه‌حلت رو هم براي اطلاع اون‌ها ارسال كن!
ممكنه تو راه‌حل متوجه اشتباه جوابت بشي!
منتظر جوابت هستيم
ضمناً چون اين سايت مربوط به سازمان پژوهش و برنامه‌ريزي آموزشي آموزش و پرورشه، ممكنه معرفي كارشناسامون بي‌اشكال نباشه.
انشاءالله موفق باشي!

فرستنده :
m2006123 HyperLink HyperLink 1387/2/23
مـتـن : 1-بجز اين سوال به نظرم مي رسد كه سوالات شما آسان تر و گاهي هم مبهم شده است.(شايد علت آسان به نظر رسيدن سوال همان ابهام موجود در سوال ها بوده است)
2-به نظرم محتواي آموزشي اين سوال شمارش و آناليز تركيبي باشه و نه احتمال
3-جواب سوال هم فكر مي كنم 6 باشد.
ممنون
پاسـخ :ايميل فرستنده: m2006123@yahoo.com
تاريخ ارسال: 1387/2/22

دوست خوبم!
از اين‌كه با ما كماكان در ارتباط هستي خيلي خوشحاليم
فكر مي‌كرديم ما رو فراموش كردي و مشغول فعاليت بيش‌تري تو زمينه‌ي المپياد هستي ...
در مورد اول سعي مي‌كنيم سؤال‌ها رو در سطوح مختلفي بيان كنيم ضمن اين‌كه سؤال‌هاي اخير خيلي هم ساده نشده و شايد حدس مثل هميشه! درست باشه
در مورد دوم صحبت شما كاملا صحيحه و اشتباه از ناحيه‌ي ما صورت گرفته و از شما به‌خاطر ياداوري اون تشكر مي‌كنيم.
راجع به علت جوابت هم دوست داريم مثل هميشه منتظر توضيح‌هاي خيلي خوبي هستيم كه ارائه مي‌كني.
مي‌گن دوست خوب كسيه كه اشكالات اونو بگه ... تو دوست خوب بخش مسابقه‌ي المپياد كامپيوتري! و دوست داريم همين‌طور فعال با ما ارتباط داشته باشي.
باز هم از راهنمايي‌هاي سازنده‌ات تشكر مي‌كنيم.
انشاءالله موفق باشي!

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2260
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2260