برازش گراف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
MyWikiUser (بحث | مشارکت‌ها) جزبدون خلاصۀ ویرایش |
جز ویرایش MyWikiUser (بحث) به آخرین تغییری که Rezabot انجام داده بود واگردانده شد |
||
خط ۱:
'''برازش گراف''' همان [[شبیه سازی]] یک [[نظریه گراف|گراف]] با یک گراف دیگر می‌باشد.
== تعریف ==
فرض کنید G و H دو گراف بدون جهت با مجموعه رئوس و یالهای زیر باشند:
{{سخ}}
'''گراف میزبان''': (<math> E_H </math> , <math> V_H </math>){{سخ}}
'''گراف مهمان''': (<math> E_G </math> , <math> V_G </math>){{سخ}}
{{سخ}}
مجموعه <math> P_H </math> را که شامل تمامی مسیرهای داخل H می‌باشد را در نظر بگیرید به این صورت:{{سخ}}
تک تک گره‌ها متعلق به <math> V_H </math> و هر دو گره متوالی متعلق به <math> E_H </math> است.{{سخ}}
بر این اساس برازش G بر H یک زوج مرتبی مثل (<math> f_V </math>, <math> f_E </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>{{سخ}}
و اگر (u,v) متعلق به <math> E_G </math> باشد، آنگاه <math> f_E </math> این یال را به مسیری در گراف H نظیر می‌کند. به شرطی که گره شروع این مسیر <math> f_V (u) </math> و گره پایانی آن <math> f_V (v) </math> باشد.
{{سخ}}
به بیان ساده تر، هر یال از گراف G به یک یا چند یال در گراف H نظیر می‌شود.{{سخ}}
با این روش اگر گراف G خواصی داشته باشد، بعد از برازش روی گراف H، آن خواص حفظ می‌شود.
== چند اصطلاح مهم ==
===بار===
به نسبت اندازهٔ گراف G و اندازه گراف H بار گفته می‌شود:
<math> |V_G|/|V_H| </math>
=== ازدحام ===
ماکزیمم تعداد یال در 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 متفاوت هست. <math> x_i </math>ها مقادیر ۰ یا ۱ را می‌توانند بگیرند.{{سخ}}
فرض می‌کنید می‌خواهیم گراف توری دو بعدی را به گراف فوق مکعب شش بعدی نظیر کنیم.{{سخ}}
ابتدا توجه کنید که مقادیر آدرس گره ها در گراف توری از (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) : مانند مورد قبلی، با این تفاوت که کد گری بعد سه بیت پر ارزش را می گذاریم.{{سخ}}
چند نمونه :
{{چپ‌چین}}
<pre>
(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)
.
.
.
</pre>
{{پایان چپ‌چین}}
== منابع ==
{{پانویس}}
* {{یادکرد
*http://en.wikipedia.org/w/index.php?title=Graph_embedding▼
|کتاب=آشنایی با نظریه گراف
|نویسنده = علی رضا علی پور
|ترجمه=
|ناشر =فاطمی
|چاپ=
|شهر=
|کوشش=
|ویرایش=
|صفحه=
|سال=
|شابک=
}}
▲*http://en.wikipedia.org/w/index.php?title=Graph_embedding&direction=next&oldid=465041827
*^ a b Gross, Jonathan; Tucker, Tom (2001), Topological Graph Theory, Dover Publications, ISBN 0486417417 .
== پیوند به بیرون ==
* [http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/embedding.htm/ Graph Embedding]
* [http://mathworld.wolfram.com/GraphEmbedding.html/ Graph Embedding_MathWorld]
<!--- میان‌ویکی را وارد کنید مثل --->
| |||