برازش گراف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

برازش گراف همان شبیه سازی یک گراف با یک گراف دیگر می‌باشد.

تعریف[ویرایش]

فرض کنید G و H دو گراف بدون جهت با مجموعه رئوس و یال‌های زیر باشند:
گراف میزبان: ( E_H ,  V_H )
گراف مهمان: ( E_G ,  V_G )

مجموعه  P_H را که شامل تمامی مسیرهای داخل H می‌باشد را در نظر بگیرید به این صورت:
تک تک گره‌ها متعلق به  V_H و هر دو گره متوالی متعلق به  E_H است.

بر این اساس برازش G بر H یک زوج مرتبی مثل ( f_V ,  f_E ) است که در آن:

 f_V :  V_G ---->  V_H
 f_E :  E_G ---->  E_H

و اگر (u,v) متعلق به  E_G باشد، آنگاه  f_E این یال را به مسیری در گراف H نظیر می‌کند. به شرطی که گره شروع این مسیر  f_V (u) و گره پایانی آن  f_V (v) باشد.

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

با این روش اگر گراف G خواصی داشته باشد، بعد از برازش روی گراف H، آن خواص حفظ می‌شود.

چند اصطلاح مهم[ویرایش]

بار[ویرایش]

به نسبت اندازهٔ گراف G و اندازه گراف H بار گفته می‌شود:  |V_G|/|V_H|

ازدحام[ویرایش]

ماکزیمم تعداد یال در G که به یک یال در H نگاشت می‌شود. که مطلوب است برابر یک باشد.

کشش[ویرایش]

ماکزیمم تعداد یال در H که متناظر با یک یال در G باشد.

انبساط[ویرایش]

عکس بار می‌باشد.
برازشی مطلوب است که تمام این چهار پارامتر برابر یک باشد. هرچه بار بیشتر باشد، هر گره وظیفه گره‌های بیشتری را باید انجام دهد.

مثال[ویرایش]

گراف توری دو بعدی را در نظر بگیرید که در هر بعد هشت گره وجود دارد و گره (x , y) به گره‌های (x-1, y) و (x+1, y) و (x, y-1) و (x, y+1) در صورت وجود متصل می‌باشد. به علاوه اینکه x یا y می‌توانند مقادیر ۰ تا ۷ را بگیرند.
همچنین گراف فوق مکعب شش بعدی را هم در نظر بگیرید که هر گره با آدرس (x1,x2,x3,x4,x5,x6) مشخص می‌شود. هر گره دقیقاً به گره‌هایی متصل هست که فقط در یکی از مقادیر x1 تا x6 متفاوت هست.  x_i ها مقادیر ۰ یا ۱ را می‌توانند بگیرند.
فرض می‌کنید می‌خواهیم گراف توری دو بعدی را به گراف فوق مکعب شش بعدی نظیر کنیم.
ابتدا توجه کنید که مقادیر آدرس گره ها در گراف توری از (0,0) تا (7,7) است. همچنین آدرس گره ها در گراف فوق مکعب شش بعدی یک عدد شش بیتی هست. می توانیم، سه بیت کم ارزش این عدد شش بیتی را برای بعد y و سه بیت پر ارزش آن را برای بعد x بگیریم. فقط تابع برازش باید به نحوی باشد که گره های همسایه در گراف توری در گراف فوق مکعب هم همسایه باشند.
برای شروع گره (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) : مانند مورد قبلی، با این تفاوت که کد گری بعد سه بیت پر ارزش را می گذاریم.

چند نمونه :

(0,0) ---> (0,0,0,0,0,0)
(0,1) ---> (0,0,0,0,0,1)
(0,2) ---> (0,0,0,0,1,1)
(0,3) ---> (0,0,0,0,1,0)
(0,4) ---> (0,0,0,1,1,0)
(0,5) ---> (0,0,0,1,1,1)
(0,6) ---> (0,0,0,1,0,1)
(0,7) ---> (0,0,0,1,0,0)
(1,0) ---> (0,0,1,0,0,0)
(1,1) ---> (0,0,1,0,0,1)
.
.
.

منابع[ویرایش]

پیوند به بیرون[ویرایش]