2 به توان k تا کامپیوتر وجود دارد که با شماره های 000...00(kتا)تا 111...11(k تا ) در مبنای 2 شماره گذاری شده اند دو کامپیوتر در صورتی به هم متصل اند که فقط در یک رقم اختلاف داشته باشند در هر مرحله هر کامپیوتر پیام خود را انتقال میدهد و هیچ کامپیوتری نباید دو تا پیام داشته باشد ثابت کنید 2 به توان k منهای 1 مرحله نیاز است تا همه ی پیام ها به همه ی کامپیوتر ها منتقل شود؟؟
پاسخ : کامپیوتر ها
به گراف این کامپیوتر ها میگن k - مکعب ( k-cube ) که هر راسش متناظره با یک رشته ی دودودیی ِ k - بیتی. گراف k - cube رو با Q[SUB]k[/SUB] نشون میدیم.
این مسئله با استق حل میشه. حالا 4 تا مسئله ی دیگه، شبیه به این:
1. n فرد داریم که هر کدوم دقیقا 1 خبر دارن، هر بار که نفر i با نفر j تماس می گیرن، j تمام خبر های i رو میفهمه و i نیز به همین شکل تمام خبر های j رو؛ ثابت کنید بعد از 2n - 4 تماس همه می تونن از همه ی اخبار مطلع شن.
2. اگر انتقال تماس ها یکطرفه باشد، ثابت کنید با 2n - 2 تماس همه از تمامی اخبار مطلع میشن.
3. حالا برای 2[SUP]n [/SUP]نفر حداقل چند تماس مورد نیازه؟ تماس دوطرفه است.
4. حالا اگه توی هر مرحله چند نفر بتونن با هم در یک مرحله تماس بگیرن ( هر نفر در یک مرحله فقط میتونه به یه نفر زنگ بزنه ) مثلا برای 4 نفر، در یک مرحله 1 با 2 و 3 با 4 میتونه صحبت کنه. با این شرایط برای 2[SUP]n [/SUP]نفر حداقل چند تماس مورد نیازه؟ تماس دوطرفه است.
به گراف این کامپیوتر ها میگن k - مکعب ( k-cube ) که هر راسش متناظره با یک رشته ی دودودیی ِ k - بیتی. گراف k - cube رو با Q[SUB]k[/SUB] نشون میدیم.
1. n فرد داریم که هر کدوم دقیقا 1 خبر دارن، هر بار که نفر i با نفر j تماس می گیرن، j تمام خبر های i رو میفهمه و i نیز به همین شکل تمام خبر های j رو؛ ثابت کنید بعد از 2n - 4 تماس همه می تونن از همه ی اخبار مطلع شن.
2. اگر انتقال تماس ها یکطرفه باشد، ثابت کنید با 2n - 2 تماس همه از تمامی اخبار مطلع میشن.
3. حالا برای 2[SUP]n [/SUP]نفر حداقل چند تماس مورد نیازه؟ تماس دوطرفه است.
4. حالا اگه توی هر مرحله چند نفر بتونن با هم در یک مرحله تماس بگیرن ( هر نفر در یک مرحله فقط میتونه به یه نفر زنگ بزنه ) مثلا برای 4 نفر، در یک مرحله 1 با 2 و 3 با 4 میتونه صحبت کنه. با این شرایط برای 2[SUP]n [/SUP]نفر حداقل چند تماس مورد نیازه؟ تماس دوطرفه است.
آخرین ویرایش توسط مدیر