شنبه ۲۹ ارديبهشت ۱۴۰۳   |  كاربر مهمان  |    
 مسابقه‌ی تصادفی

 
 
 گراف‌هاي فاقد حلقه (مسابقه‌ي شماره‌ي 63)
گراف‌هاي فاقد حلقه (مسابقه‌ي شماره‌ي 63)مسابقه كامپيوتر
تابع مولد و روابط بازگشتي

گراف‌هاي فاقد حلقه 








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




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




سؤال
آرايه‌اي شامل  رأس داريم كه در آن عددي صحيح و مثبت است. مي‌خواهيم اين رؤوس را با يال‌هايي به‌هم وصل كنيم به‌گونه‌اي كه يك اتصال «صحيح» از آرايه‌ها عبارت از اضافه كردن يال‌هاي افقي و عمودي با طول «واحد» بين رؤوس باشد؛ به‌گونه‌اي كه هر رأس به هر رأس ديگر از طريق يال‌ها متصل شده به‌هيچ وجه حلقه‌اي با هر اندازه تشكيل نشود.

به‌عنوان مثال:
براي  آرايه‌هاي ذيل را درنظر بگيريد:

شكل 1 – آرايه‌ي صحيح.

شكل 2 – آرايه‌ي صحيح.

شكل 3 – آرايه‌ي ناصحيح
به‌علت وجود حلقه.

شكل 4 – آرايه‌ي ناصحيح
غيرمتصل.

 

فرض كنيد  تعداد اتصال‌هاي صحيح آرايه‌ي  باشد. در اين صورت  را بيابيد.

1386/12/3لينک مستقيم
فرستنده :
m2006123 HyperLink HyperLink 1387/1/2
مـتـن : من خیلی در زمینه گراف اطلاعاتی ندارم و تنها از روی راهنمایی هایی که کردید تونستم رابطه بازگشتی که تعداد اتصال‌هاي صحيح آرايه‌ي 2*n را مشخص می کند را بیابم.
P(n + 1)=4 P(n) – P(n – 1) A
بنابراین براساس رابطه A
تعداد اتصال‌هاي صحيح آرايه‌ي 2*1 برابر است با:1
تعداد اتصال‌هاي صحيح آرايه‌ي 2*2 برابر است با:4
تعداد اتصال‌هاي صحيح آرايه‌ي 2*3 برابر است با:15
تعداد اتصال‌هاي صحيح آرايه‌ي 2*4 برابر است با:56
تعداد اتصال‌هاي صحيح آرايه‌ي 2*5 برابر است با:209
تعداد اتصال‌هاي صحيح آرايه‌ي 2*6 برابر است با:780
تعداد اتصال‌هاي صحيح آرايه‌ي 2*7 برابر است با:2911
تعداد اتصال‌هاي صحيح آرايه‌ي 2*8 برابر است با:10864
تعداد اتصال‌هاي صحيح آرايه‌ي 2*9 برابر است با:40545
تعداد اتصال‌هاي صحيح آرايه‌ي 2*10 برابر است با:151316
پاسـخ :ايميل فرستنده: m2006123@yahoo.com
تاريخ ارسال:‌ 1386/12/21

دوست خوبم!
سلام
از اين‌كه اين سؤال را با اين دقت مورد بررسي و تحليل قرار دادي تشكر مي‌كنيم.
جوابت كاملاً صحيحه!
بارك‌الله! آفرين و درود بر شما!
يك‌بار ديگر به‌خاطر تصحيح صورت مسأله ازت تشكر مي‌كنيم.
منتظر حضور فعالت در ساير مسابقه‌ها هم هستيم.
واقعاً اسم شما باعث شادي همكاران ما در اين بخش مي‌شود.
انشاءالله موفق باشي!
فرستنده :
m2006123 HyperLink HyperLink 1386/12/14
مـتـن : با توجه به راهنمايي هاي شما به نظرم سوال را بايد به اين صورت تصحيح كنيد.
فرض كنيد تعداد آرايه هاي صحيح آرايه‌ي باشد. در اين صورت را بيابيد.

و يا

زير نويس عكس ها را تغيير دهيد و به جاي آرايه‌ي صحيح از اتصال صحيح استفاده كنيد.
پاسـخ :ايميل فرستنده: m2006123@yahoo.com
تاريخ ارسال: 1386/12/11

دوست خوبم!
ضمن تشكر از شما
تذكر شما بسيار صحيح و به‌جا است و اين مورد را در توضيح اشكال سؤال تصحيح مي‌كنيم.
واقعاً از نهايت دقت و لطف شما در ارائه‌ي اشكال‌هاي‌مان نهايت تشكر و امتنان را داريم.
انشاءالله موفق باشي!
فرستنده :
Azin.H HyperLink HyperLink 1386/12/9
مـتـن : Salam
Javab-e- man hast 3,9,27
Yani baraye 6 raas 3 etesal
Baraye 8 raas 9 etesal
Baraye 10 raas 27 etesal
Javabamo kheili nemitoonam tozih bedam chon bayad shekl bekesham va nemishe.
Man baraye 6 raas 3 etesal e sahih peyda kardam.baraye 8 raas ba estefade az har kodoom az etesal haye ghabli 3 ta etesal-e diga peyda kardam yani 9 etesal.3*3=9baraye 10 raas dobare 3 etesal be har kodoom az 9 etesal-e ghabli ezafe kardam va 9*3=27.
baraye 12 raas fekr mikonam javab 3^4 bashe.
پاسـخ :ايميل فرستنده: hds.azin@gmail.com
تاريخ ارسال: 1386/12/8


آذين جان!
ضمن تشكر از شما
واقعا ببخشيد كه در حال حاضر امكانات زيادي براي ارسال جواب در اختيارتون قرار نداديم.
ولي شايد منظور سؤال رو متوجه نشدي اگر بخوام راهنمايي كرده باشم بايد بگم جواب براي حالت‌هاي ذيل بدين‌صورت است:
- براي 3 رأس 15 اتصال صحيح
- براي 4 رأس 56 اتصال صحيح
- براي 5 رأس 209 اتصال صحيح
- براي 6 رأس 780 اتصال صحيح
- و ...
منتظر جوابت هستيم.
انشاءالله موفق باشي!
فرستنده :
m2006123 HyperLink HyperLink 1386/12/9
مـتـن : تعداد يال هاي عمودي كه مي توانيم در يك آرايه n*2 رسم كنيم برابر است با n
تعداد يال هاي افقي كه مي توانيم در يك آرايه n*2 رسم كنيم برابر است با 2(n - 1)
در نتيجه كل يال هاي عمودي و افقي كه مي توانيم در يك آرايه n*2 رسم كنيم برابر است با 2(n - 1) + n=2n - 2 + n=3n - 2

يك آرايه n*2 را مي توان به n - 1 آرايه 2*2 تبديل كرد به عبارت ديگر مي توان n - 1 آرايه 2*2 متفاوت را در يك آرايه n*2 يافت.

اگر بخواهيم يك آرايه را كه تمام يال هاي آن رسم شده است را به يك آرايه صحيح تبديل كنيم بايد آن يال هايي كه باعث به وجود آمدن حلقه در آرايه مي شوند را از آرايه حذف كرد.

براي از حلقه خارج كردن يك آرايه n*2 مي توانيم يكي از دو كار زير را انجام دهيم:

1.حذف يكي از يال هاي غير مشترك در آرايه هاي 2*2 ( منظور همه يال ها بجز يال هاي عمودي 2 تا n - 1 )
با اين كار يك آرايه 2*2 از حالت حلقه خارج مي شود همان طور كه مي دانيد n - 1 آرايه 2*2 متفاوت را در يك آرايه n*2 داريم در نتيجه با حذف n - 1 يال مي توان تمام آرايه n*2 را از حالت حلقه خارج كرد.

2.حذف يكي از يال هاي مشترك در آرايه هاي 2*2 ( منظور عمودي 2 تا n - 1 )
در اين صورت آرايه 2*2 اول از حلقه خارج مي شود ولي آرايه 2*2 بعدي با وجود حذف يك يال از آن هنوز حلقه برطرف نشده و باز بايد براي برطرف كردن حلقه يكي از يال هاي ديگر را حذف كرد و كار به همين ترتيب تا پايان ادامه مي دهيم.در اين روش همان طور كه ديديد از هر آرايه 2*2 باز يك يال بايد مستقيما حذف مي كرديم در نتيجه با توجه به وجود n -1 آرايه 2*2 (مانند روش اول) بايد n - 1 يال را حذف كنيم تا كل آرايه از حالت حلقه خارج شود.

تذكر 1:در هر دو روش بايد توجه داشت كه بايد يال هايي از آرايه هاي 2*2 را انتخاب كرد كه آرايه را به يك آرايه غير متصل تبديل نكند.
تدكر 2:از هر دو روش به صورت همزمان درصورتي كه شروط مسئله نقض نشود مي توان استفاده كرد.

بنابراين تعداد اتصال هاي صحيح يك آرايه n*2 برابر است با تعداد كل يال ها منهاي تعداد يال هاي حذف شده از آرايه كه برابر است با 3n - 2 - (n - 1)=2n - 1
و جواب مسئله كه يافتن تعداد اتصال هاي صحيح يك آرايه 2*10 برابر 19 است.
پاسـخ :ايميل فرستنده: m2006123@yahoo.com
تاريخ ارسال: 1386/12/4

دوست خوبم!
ضمن تشكر از شما
استدلال‌تان بسيار زيبا انجام شده است البته تا آن‌جا كه مجموع تعداد يال‌ها را در صورت اتصال كامل افقي و عمودي رؤوس به يكديگر محاسبه كرديد.
ولي مشخص نشد چرا شرط ضروري براي عدم تشكيل «حلقه» ان چيزي است كه شما مطرح كرده‌ايد.
براي راهمايي بايد بگوييم:
براي n=1 داريم: T1=1
براي n=2 داريم: T1=4
براي n=3 داريم: Tn=15
براي n=4 داريم: Tn=56
براي n=5 داريم: Tn=209
و ...
منتظر جوابت هستم.
انشاءالله موفق باشي!

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

 

     

 

  

صفحه‌ي اصلي
     

  

راهنماي سايت

     

 

  

آموزش

     

  

بانك سوال

     

 

  

مسابقه

     

 

  

زنگ تفريح

     

 

  

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

     

 

  

معرفي كتاب

     

 

  

مشاوره

     

 

  

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

     

  

اخبار

  

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

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

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)