برازش گراف: تفاوت میان نسخه‌ها

'''برازش گراف''' همان [[شبیه سازی]] یک [[نظریه گراف|گراف]] با یک گراف دیگر می‌باشد.

'''گراف میزبان''': (<math> E_H </math> , <math> V_H </math>) {{سخ}}

مجموعه <math> P_H </math> را که شامل تمامی مسیر‌هایمسیرهای داخل H می‌باشد را در نظر بگیرید به این صورت: {{سخ}}

تک تک گره‌ها متعلق به <math> V_H </math> و هر دو گره متوالی متعلق به <math> E_H </math> است. {{سخ}}

<math> f_V </math>: <math> V_G </math> ----> <math> V_H </math> {{سخ}}

<math> f_E </math>: <math> E_G </math> ----> <math> E_H </math> {{سخ}}

به بیان ساده تر، هر یال از گراف G به یک یا چند یال در گراف H نظیر می‌شود. {{سخ}}

گراف توری دو بعدی را در نظر بگیرید که در هر بعد هشت گره وجود دارد و گره (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 />{{سخ}}

* (x,y+1) : مانند مورد قبلی، با این تفاوت که [[کد گری]] بعدی سه بیت کم ارزش را می گذاریم.

* (x+1,y) : مانند مورد قبلی، با این تفاوت که کد گری بعد سه بیت پر ارزش را می گذاریم. <br />{{سخ}}

{{پایان چپچینچپ‌چین}}