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

 
 
 اسكان در سياره‌ي «رجيس» (مسابقه‌ي شماره‌ي 53) ويژه‌ي ايام‌الله دهه‌ي فجر
اسكان در سياره‌ي «رجيس» (مسابقه‌ي شماره‌ي 53) ويژه‌ي ايام‌الله دهه‌ي فجرمسابقه كامپيوتر
نظريه‌ي گراف‌ها

اسكان در سياره‌ي «رجيس»







اشاره

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




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






سؤال

فرض كنيم در زمان آينده قرار گرفته‌ايم. يك سازمان فضايي ايراني مي‌خواهد 1400 منزل مسكوني در سياره‌ي «رجيس» بنا كند. براي انتقال افراد از يك منزل به منزل ديگر نيز مسيري در فضا درنظر گرفته شده است به‌گونه‌اي كه افراد تنها از اين مسير مي‌توانند از يك منزل به منزل ديگر منتقل شوند.

فرض كنيد نقشه‌ي مسيرها بر روي سياره‌ي «رجيس» به‌گونه‌اي كشيده مي‌شود كه به‌طور اتفاقي  مسير ارتباطي، منازل را به‌گونه‌اي به هم مرتبط مي‌كند كه بين دو منزل بيش از يك مسير ارتباطي وجود نداشته باشد.

حداقل مقدار ‌چقدر باشد تا (بدون توجه به چگونگي مسير ارتباطي) امكان سفر بين هر دو منزل ممكن باشد؟

1386/11/13لينک مستقيم

فرستنده :
محمد HyperLink HyperLink 1387/1/2
مـتـن : سلام
من از یکی از فرمول های مجموعه حلش کرده بودم که متاسفانه توی محاسباتم اشتباه کردم
سعی میکنم فرمولو بزارمش
پاسـخ :محمد جان!
سلام
ضمن تشكر از شما
منتظر جوابت مي‌مونيم.
انشاءالله موفق باشي!

فرستنده :
Kherad HyperLink HyperLink 1386/11/27
مـتـن : سلام .
منظورتون از بين هر دو منزل تنها يك مسير ارتباطي مي‌تونه وجود داشته باشه اینه که اگه به گراف تبدیلش کنیم فقط 1 مسیر می تونه وجود داشته باشه . یا منظورتون اینه که یال موازی نداره ؟


جواب به نظر می رسه n-1 یعنی 1399 باشه .
چون ما یک گراف همبند بدون دور می خوایم . که گراف همبند بدون دور یعنی درخت n-1 یال داره . با استقرا هم ثابت می شه . پایه که درسته (واسه n=1 , n=2 ) . حالا یک درسخت n راسی داریم بی خیال یکی از راسا می شیم . طبق استقرا بین اون n-1 راس n-2 یال وجود داره . حالا راسی که بی خیال شدیم رو در نظر می گیریم . باید حد اقل یک یال داشته باشه چون در غیر این صورت همنبد نسیت . در ضمن باید فقط 1 یال داشته باشه چون در غیر این صورت (چون بین هر 2 راسی که این راس بهشون یال داره مسیر هست ) دور به وجود می یاد .


اما چون گفتین "حداقل" شک کردم .
پاسـخ :ايميل فرستنده: a.i.kheradmand@gmail.com
تاريخ ارسال: 1386/11/19


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

فرستنده :
محمد HyperLink HyperLink 1386/11/18
مـتـن : 9100
Right?
پاسـخ :تاريخ ارسال: 1386/11/13
ايميل فرستنده: p30gamer@gmail.com

محمد جان!
ضمن تشكر از ارسال جوابت
راجع به علت اون هم توضيح بديد! در اين صورته كه مي‌تونيم راجع به Right و False بودنش با هم حرف بزنيم.
انشاءالله موفق باشي!

فرستنده :
علیرضا شفائی HyperLink HyperLink 1386/11/18
مـتـن : سلام
فکر کنم که صورت سوال را درست نفهمیدم.

طبق صورت مسئله بین هر دو منزل بیش از یک راه ارتباطی وجود ندارد
در زبان گراف این خاصیت همون نداشتن دور است.
از جمله بالا میتوان نتیجه گرفت که تعداد ناحیه ها برابر است با 1
v-e+f=k+1
را قبلا اثبات کردیم. میدانیم بین هر دو خانه مسیری هست . پس تعداد مولفه هاش 1 است.
v= 1400
f=1
k=1
=>
1400-e+1=1+1
=>
e=1399

البته فکر کنم روشم زیاد درست نباشه.
همچنین فکر میکنم که از خاصیت درخت بودن میشد استفاده کرد.ولی چون باید همه چیش را ثابت میکردم وقت زیادی میگرفت.در صورتی که این فرمول قبلا اثبات شده بود

اگر سوتی داشت لطفا بگید تا بیشتر روش فکر کنم

با تشکر
ع.ش
پاسـخ :عليرضا جان!
ضمن تشكر از شما
لطفا توضيح بده اعداد مربوط به f (تعداد وجوه) و K (تعداد گراف‌ها) رو از كجا اوردي؟
شايد اين روش شما مسدله رو مشكل‌تر مي‌كنه.
اگر بخوام راهنمايي كنم مي‌تونم بگم بين هر دو منزل تنها يك مسير ارتباطي مي‌تونه وجود داشته باشه ...
عليرضا جان!
منتظر جوابت هستم ها!
انشاءالله موفق باشي!

فرستنده :
emma HyperLink HyperLink 1386/11/18
مـتـن : 700 تا
درسته؟
پاسـخ :تاريخ ارسال: 1386/11/14
ايميل فرستنده: emma_silver72@yahoo.com

emma جان!
ازت به خاظر ارسال جوابت تشكر مي‌كنيم. راجع به علت اون هم براي دوستات توضيح بده!
انشاءالله موفق باشي!

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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