تفاوت میان نسخه‌های «مجاور (نظریه گراف)»

جز
جز (ربات ردهٔ همسنگ (۲۶) +املا+تمیز (۹.۲): + رده:اشیاء نظریه گراف)
[[Imageپرونده:6n-graf.svg|thumbبندانگشتی|گراف G، شامل ۶ راس و ۷ یال است.]]
در [[نظریه گراف]]، [[راس]] مجاور راس v در [[گراف]] G راسی است که با یالی به v وصل شده باشد. مجاور‌هایمجاورهای راس v در گراف G ناشی از [[زیر‌گرافزیرگراف|زیرگرافی]] هستند که همه‌ی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوان مثال، در تصویر روبرو، گرافی با ۶ راس و ۷ یال نمایش داده‌شده‌است. راس ۵ با دو راس ۱، ۲ و ۴ '''مجاور''' است ولی با رئوس ۳ و ۶ '''مجاور نیست'''.
 
معمولامعمولاً مجاورت رئوس را با ('' N''<sub>''G''</sub>(''v'' یا (&nbsp;''N''(''v'' نمایش می‌دهند.
 
مجاور‌هامجاورها معمولامعمولاً در الگوریتم‌های کامپپوتر استفاده می‌شود و توسط [[ماتریس مجاورت]] و [[فهرست مجاورت|لیست مجاورت]] نمایش داده‌می‌شود. همچنین، توسط مجاور‌هامجاورها می‌توان [[ضریب خوشه‌بندی]] گراف را که برابر است با میزان میانگین چگالی مجاور، به دست آورد.
 
[[رأس (نظریه گراف)|راس منفرد]] هیچ مجاوری ندارد. درجه هرراس برابر با تعداد مجاور‌هایش است. حالت خاص [[دور]] است که راس با خود در ارتباط است، اگر چنین یالی وجود داشته باشد راس با خود مجاور است.
 
==خواص محلی در گراف==
[[Image:Octahedron graph.png|thumb|گراف هشت وجهی مجاور چرخه &nbsp;''C''<sub>4</sub> است]]
اگر همه‌ی رئوس گراف G مجاور داشته باشند، [[یکریختی گراف|یکریخت]] این گراف، گرافی مشابه گراف H خواهد بود و G را به‌طور محلی H نامیده‌می‌شود، و اگر همه رئوس در گراف G مجاور‌ داشته‌باشند که متعلق به برخی از گراف‎های خانواده F باشد، G را به طور محلی F می‌نامند. به طور مثال در تصویر، گراف هشت وجهی نمایش داده‌شده‌است، هر راس مجاوری دارد و یکریخت این گراف، [[گراف دوری]] چهار راسی است. پس گراف هشت وجهی به‌طور محلی [[گراف دوری]] &nbsp;''C''<sub>4</sub> نامیده‌می‌شود.
 
[[رأس (نظریه گراف)|راس منفرد]] هیچ مجاوری ندارد. درجه هرراس برابر با تعداد مجاور‌هایشمجاورهایش است. حالت خاص [[دور]] است که راس با خود در ارتباط است، اگر چنین یالی وجود داشته باشد راس با خود مجاور است.
 
== خواص محلی در گراف ==
[[Imageپرونده:Octahedron graph.png|thumbبندانگشتی|گراف هشت وجهی مجاور چرخه &nbsp;''C''<sub>4</sub> است]]
اگر همه‌ی رئوس گراف G مجاور داشته باشند، [[یکریختی گراف|یکریخت]] این گراف، گرافی مشابه گراف H خواهد بود و G را به‌طور محلی H نامیده‌می‌شود، و اگر همه رئوس در گراف G مجاور‌مجاور داشته‌باشند که متعلق به برخی از گراف‎های خانواده F باشد، G را به طور محلی F می‌نامند. به طور مثال در تصویر، گراف هشت وجهی نمایش داده‌شده‌است، هر راس مجاوری دارد و یکریخت این گراف، [[گراف دوری]] چهار راسی است. پس گراف هشت وجهی به‌طور محلی [[گراف دوری]] &nbsp;''C''<sub>4</sub> نامیده‌می‌شود.
 
مثال :
*گرافی بدون مثلث است اگر و تنها اگر آن گراف به صورت مجاور مستقل باشد.
 
== همسایگی(مجاورت) یک مجموعه ==
برای مجموعه A که شامل رئوس است، مجاور‌هایمجاورهای A، اجماع مجاور رئوس هستند. پس مجموعه همه رئوس مجاور برابر است با حداقل اعضا A.
 
== منابع ==
{{پانویس}}
 
* {{یادکرد کتاب | همان = | نام خانوادگی = فرالی| نام = جان ب.| پیوند نویسنده = | نام ویراستار = مهدی| نام خانوادگی ویراستار = بهزاد| پیوند ویراستار = مهدی بهزاد| عنوان = نخستین درس در جبر مجرد| ترجمه = [[مسعود فرزان]]| دیگران = | نشانی = | نشانی بایگانی = | تاریخ بایگانی = | فرمت = | تاریخ بازبینی = | نوع = | ویرایش = | سری = | جلد = اول| تاریخ = | سال = ۱۳۸۳| ماه = | سال اصلی = | ناشر = [[مرکز نشر دانشگاهی]]| مکان = تهران| زبان = | شابک = ۹۶۴-۰۱-۰۳۵۱-۹}}
 
*http://en.wikipedia.org/wiki/Adjacent_vertex
 
 
 
<!--- میان‌ویکی را وارد کنید مثل [[(en:Neighbourhood (graph theory]] --->
 
[[رده:اشیاء نظریه گراف]]
[[رده:نظریه گراف]]
۵۷۷٬۴۵۰

ویرایش