(۰۷ آبان ۱۳۹۵ ۰۶:۱۹ ب.ظ)mavin1200 نوشته شده توسط: سلام
نمیدونم اینو تو درس پردازش موازی بعنوان تمرین دادن و اصرار داشتن قسمت دومش حتما إثبات بشه
لطفا اگه کسی بلده کمک کنه یا منبع بگید برم بگردم دنبال جواب
ببینید من هم درس شبکه‌های میان ارتباطی رو پاس کردم که همه‌ش از این‌ها خوندیم. جوابی برای تعداد کل مسیرها بین دو گره در یک Hypercube وجود نداره. اگه خود استاد این رو طرح کرده، بهش بگید اگه جوابی داره مقاله‌ش کنه، اگه دانشجوش هم داده که به استاد بگید تمرین بدون جواب داده. اینجا هم می‌تونید ببینید که برای دو دورترین نقطه‌ی خاص (از ۰۰///۰ به ۱۱///۱) فقط تا n=5 جواب داره:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یعنی برای دو دورترین نقطه هم جوابی نیست (چه برسه به تمامی حالات. اگه برای تمامی حالات جواب بود، برای دو دورترین نقطه هم جواب پیدا می‌شد).
اما یک حالت خاص می‌تونه این باشه که این مسیرها با هم گره مشترک نداشته باشند، در اون صورت قابل حل هست، ولی شما این قید رو نگفتید.
قسمت دوم یعنی با تغییر دو گره آیا تعداد مسیرها عوض میشه، منظور از تغییر دو گره رو متوجه نشدم که به قسمت اول ربط داره یا نه.
توو قسمت اول گفته شده که "دورترین گره‌ها" از هم، که میشن گره‌هایی که تمامی بیت‌های آدرسشون با هم فرق داره. حالا اگه منظور تغییر دو گره، انتخاب "دو دورترین گره" دیگه هست خب باز فرق نمی‌کنه چون Hypercube متقارن هست و تعداد مسیرهای رفتن از ۰۰۰ به ۱۱۱، مساوی هست با رفتن از مثلاً ۰۱۰ به ۱۰۱/ این وسط فقط قواعد نام‌گذاری عوض میشه.
مثلا یک راه برای رفتن از ۰۰۰ به ۱۱۱ اینطوری هست:
۰۰۰ [tex]\longleftarrow[/tex] 0
10 [tex]\longleftarrow[/tex]
110 [tex]\longleftarrow[/tex] 11
1
بیت‌هایی که هر بار تغییر کردند رو قرمز کردم که عبارتست از به ترتیب بیت دوم، بیت اول (از چپ) و بیت سوم.
حالا من میگم اگه بخوایم دو گره دیگه، مثل تعداد مسیرهای بین ۰۱۰ و ۱۰۱ رو حساب کنیم، هر مسیر، تناظر یک به یک داره با یک مسیری از ۰۰۰ به ۱۱۱/ پس با حالت بالا، یعنی به ترتیب تغییر بیت دوم، بیت اول و بیت سوم، یک مسیری هم باید از ۰۱۰۱ به ۱۰۱ پیدا بشه، که میشه ۰۱۰، سپس ۰۰۰ (بیت دوم تغییر کرد)، سپس ۱۰۰ (بیت اول از چپ) و سپس ۱۰۱ (بیت سوم).
حالا شما هر مسیر دیگه‌ای از ۰۰۰ به ۱۱۱ پیدا کنید و الگوی تغییر دادن بیت‌ها رو پیدا کنید و همون الگو رو به ۰۱۰ اعمال کنید، آخرش تبدیل میشه به ۱۰۱/ چون قبلاً (یعنی تبدیل ۰۰۰ به ۱۱۱) هر بار یک بیت تغییر می‌کرد، توو مسیر جدید (۰۱۰ به ۱۰۱) هم هر بار یک بیت تغییر خواهد کرد و نگران انتخاب غلط نیستیم، فقط حالت اولیه فرق می‌کنه. شما فوقش شاید لازم باشه اثبات کنید که هر تغییر سکانسی از ۰۰۰ به ۱۱۱، روی یک مسیر دیگه هم valid هست و پیش نمیاد که دو بیت رو تغییر بده و هر بار فقط یک بیت تغییر خواهد کرد. از آنجایی که در ۰۰۰ به ۱۱۱ تمامی بیت‌ها تغییر می‌کنه، برای مسیر دیگه هم اینطور خواهد بود.
خلاصه، هر مسیر بین دو دورترین نقطه‌ی خاص، یک سکانس (الگوی تغییر) داره که اگه همون الگوی تغییر رو روی یک مبداً دیگه اعمال کنید، به دورترین نقطه‌ی متناظر با خودش خواهد رسید و سکانس ایجاد شده هم معتبر خواهد بود (بین هر دو گره فقط یک بیت تغییر می‌کنه).
