برازش گراف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
In twilight (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Mohammdsadr (بحث | مشارکت‌ها) |
||
خط ۴۳:
گراف توری دو بعدی را در نظر بگیرید که در هر بعد هشت گره وجود دارد و گره (x , y) به گره‌های (x-1, y) و (x+1, y) و (x, y-1) و (x, y+1) در صورت وجود متصل می‌باشد. به علاوه اینکه x یا y می‌توانند مقادیر ۰ تا ۷ را بگیرند. {{سخ}}
همچنین گراف فوق مکعب شش بعدی را هم در نظر بگیرید که هر گره با آدرس (x1,x2,x3,x4,x5,x6) مشخص می‌شود. هر گره دقیقا به گره‌هایی متصل هست که فقط در یکی از مقادیر x1 تا x6 متفاوت هست. <math> x_i </math>ها مقادیر ۰ یا ۱ را می‌توانند بگیرند. {{سخ}}
فرض می‌کنید می‌خواهیم گراف توری دو بعدی را به گراف فوق مکعب شش بعدی نظیر کنیم.<br />
ابتدا توجه کنید که مقادیر آدرس گره ها در گراف توری از (0,0) تا (7,7) است. همچنین آدرس گره ها در گراف فوق مکعب شش بعدی یک عدد شش بیتی هست. می توانیم، سه بیت کم ارزش این عدد شش بیتی را برای بعد y و سه بیت پر ارزش آن را برای بعد x بگیریم. فقط تابع برازش باید به نحوی باشد که گره های همسایه در گراف توری در گراف فوق مکعب هم همسایه باشند. <br />
برای شروع گره (0,0) توری را به گره (0,0,0,0,0,0) فوق مکعب نظیر می کنیم. سپس اگر گره (x,y) به گره (x1,x2,x3,y1,y2,y3) نظیر شده باشد، گره های همسایه (x,y) به ترتیب زیر نظیر می شوند :
* (x,y-1) : در عدد 6 بیتی (x1,x2,x3,y1,y2,y3)، سه بیت پرارزش ثابت می ماند اما سه بیت کم ارزش باید طوری تغییر کند، که هم آدرس قبلی این گره باشد و هم با این گره همسایه باشد. برای همین کد گری قبلی سه بیت کم ارزش را می گذاریم.
* (x,y+1) : مانند مورد قبلی، با این تفاوت که کد گری بعدی سه بیت کم ارزش را می گذاریم.
* (x-1,y) : این دفعه می بایست، سه بیت کم ارزش را ثابت نگه داشت، ولی سه بیت پرارزش کد گری قبلی آن خواهد بود.
* (x+1,y) : مانند مورد قبلی، با این تفاوت که کد گری بعد سه بیت پر ارزش را می گذاریم. <br />
== منابع ==
| |||