مجاور (نظریه گراف)

گراف G، شامل 6 راس و 7 یال است.

در نظریه گراف ، راس مجاور راس v در گراف G راسی است که با یالی به v وصل شده باشد. مجاور‌های راس v در گراف G ناشی از زیرگرافی هستند که همه‌ی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوانمثال،در تصویر روبرو، گرافی با 6 راس و 7 یال نمایش داده شده است.راس 5 با دو راس 1، 2 و 4 مجاور است ولی با رئوس 3 و 6 مجاور نیست.

معمولا مجاورت رئوس را با (N_G(v) or  N(v نمایش می‌دهند.

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

راس منفرد هیچ مجاوری ندارد. درجه هرراس برابر با تعداد مجاور‌هایش است. حالت خاص دور است که راس با خود در ارتباط است، اگر چنین یالی وجود داشته باسد راس با خود مجاور است.

خواص مجاورت در گراف

گراف هشت وجهی مجاور چرخه  C₄ است

اگر همه‌ی رئوس گراف G مجاورداشته باشند،هم‌ریخت این گراف، گرافی مشابه گراف H خواهد بود و G را مجاور H می‌نامند. به طور مثال در تصویر، گراف هشت وجهی نشان داده‌شده‌است، که مجاور هر راس همریخت، چرخه‌ای از چهار راس است. پس گراف هشت وجهی مجاور چرخه  C₄ است.

مثال :

• گراف کامل K_n مجاور گراف K_n-1است.
• گراف بدون مثلث است اگر و تنها اگر آن گراف به صورت مجاور مستقل باشد.

همسایگی(مجاورت) یک مجموعه

برای مجموعه رئوس A، مجاور‌های A متحد شده‌های مجاور رئوس هستند، پس مجموعه همه رئوس مجاور برابر است با حداقل اعضا A.

منابع

• فرالی، جان ب. (۱۳۸۳). بهزاد، مهدی، ویراستار. نخستین درس در جبر مجرد. ج. اول. ترجمهٔ مسعود فرزان. تهران: مرکز نشر دانشگاهی. شابک ۹۶۴-۰۱-۰۳۵۱-۹.

• http://en.wikipedia.org/wiki/Adjacent_vertex