مجاور (نظریه گراف): تفاوت میان نسخهها
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱۰: | خط ۱۰: | ||
==خواص مجاورت در گراف== |
==خواص مجاورت در گراف== |
||
[[Image:Octahedron graph.png|thumb|گراف هشت وجهی مجاور چرخه ''C''<sub>4</sub> است]] |
[[Image:Octahedron graph.png|thumb|گراف هشت وجهی مجاور چرخه ''C''<sub>4</sub> است]] |
||
اگر همهی رئوس گراف G مجاورداشته باشند، [[یکریختی گراف|یکریخت]] این گراف، گرافی مشابه گراف H خواهد بود و G را بهطور محلی H |
اگر همهی رئوس گراف G مجاورداشته باشند، [[یکریختی گراف|یکریخت]] این گراف، گرافی مشابه گراف H خواهد بود و G را بهطور محلی H نامیدهمیشود، و اگر همه رئوس در گراف G مجاور داشتهباشند که متعلق به گراف برخی از گرافهای خانواده F باشد، G را به طور محلی F مینامند. به طور مثال در تصویر، گراف هشت وجهی نشان دادهشدهاست، هر راس مجاوری دارد و یکریخت این گراف، [[گراف دوری]] چهار راس است. پس گراف هشت وجهی بهطور محلی [[گراف دوری]] ''C''<sub>4</sub> نامیدهمیشود. |
||
نسخهٔ ۲۵ ژوئن ۲۰۱۳، ساعت ۱۴:۱۵
در نظریه گراف، راس مجاور راس v در گراف G راسی است که با یالی به v وصل شده باشد. مجاورهای راس v در گراف G ناشی از زیرگرافی هستند که همهی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوان مثال، در تصویر روبرو، گرافی با ۶ راس و ۷ یال نمایش دادهشدهاست. راس ۵ با دو راس ۱، ۲ و ۴ مجاور است ولی با رئوس ۳ و ۶ مجاور نیست.
معمولا مجاورت رئوس را با ( NG(v یا ( N(v نمایش میدهند.
مجاورها معمولا در الگوریتمهای کامپپوتر استفاده میشود و توسط ماتریس مجاورت و لیست مجاورت نمایش دادهمیشود. همچنین، توسط مجاورها میتوان ضریب خوشهبندی گراف را که برابر است با میزان میانگین چگالی مجاور، به دست آورد.
راس منفرد هیچ مجاوری ندارد. درجه هرراس برابر با تعداد مجاورهایش است. حالت خاص دور است که راس با خود در ارتباط است، اگر چنین یالی وجود داشته باشد راس با خود مجاور است.
خواص مجاورت در گراف
اگر همهی رئوس گراف G مجاورداشته باشند، یکریخت این گراف، گرافی مشابه گراف H خواهد بود و G را بهطور محلی H نامیدهمیشود، و اگر همه رئوس در گراف G مجاور داشتهباشند که متعلق به گراف برخی از گرافهای خانواده F باشد، G را به طور محلی F مینامند. به طور مثال در تصویر، گراف هشت وجهی نشان دادهشدهاست، هر راس مجاوری دارد و یکریخت این گراف، گراف دوری چهار راس است. پس گراف هشت وجهی بهطور محلی گراف دوری C4 نامیدهمیشود.
مثال :
- گراف کامل Kn مجاور گراف Kn-1است.
- گرافی بدون مثلث است اگر و تنها اگر آن گراف به صورت مجاور مستقل باشد.
همسایگی(مجاورت) یک مجموعه
برای مجموعه رئوس A، مجاورهای A متحد شدههای مجاور رئوس هستند، پس مجموعه همه رئوس مجاور برابر است با حداقل اعضا A.
منابع
- فرالی، جان ب. (۱۳۸۳). بهزاد، مهدی، ویراستار. نخستین درس در جبر مجرد. ج. اول. ترجمهٔ مسعود فرزان. تهران: مرکز نشر دانشگاهی. شابک ۹۶۴-۰۱-۰۳۵۱-۹.