مجاور (نظریه گراف): تفاوت میان نسخهها
جز ربات ردهٔ همسنگ (۲۶) +املا+تمیز (۹.۲): + رده:اشیاء نظریه گراف |
بدون خلاصۀ ویرایش برچسب: نیازمند بازبینی |
||
خط ۱: | خط ۱: | ||
[[پرونده:6n-graf.svg|بندانگشتی|گراف G، شامل ۶ راس و ۷ یال است.]] |
[[پرونده:6n-graf.svg|بندانگشتی|گراف G، شامل ۶ راس و ۷ یال است.]] |
||
در [[نظریه گراف]]، [[راس]] مجاور راس v در [[گراف]] G راسی است که با یالی به v وصل شده باشد. مجاورهای راس v در گراف G ناشی از [[زیرگراف|زیرگرافی]] هستند که همهی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوان مثال، در تصویر روبرو، گرافی با ۶ راس و ۷ یال نمایش دادهشدهاست. راس ۵ با |
در [[نظریه گراف]]، [[راس]] مجاور راس v در [[گراف]] G راسی است که با یالی به v وصل شده باشد. مجاورهای راس v در گراف G ناشی از [[زیرگراف|زیرگرافی]] هستند که همهی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوان مثال، در تصویر روبرو، گرافی با ۶ راس و ۷ یال نمایش دادهشدهاست. راس ۵ با سه راس ۱، ۲ و ۴ '''مجاور''' است ولی با رئوس ۳ و ۶ '''مجاور نیست'''. |
||
معمولاً مجاورت رئوس را با ('' N''<sub>''G''</sub>(''v'' یا ( ''N''(''v'' نمایش میدهند. |
معمولاً مجاورت رئوس را با ('' N''<sub>''G''</sub>(''v'' یا ( ''N''(''v'' نمایش میدهند. |
نسخهٔ ۳ مهٔ ۲۰۱۵، ساعت ۰۷:۳۰
در نظریه گراف، راس مجاور راس 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.
منابع
- فرالی، جان ب. (۱۳۸۳). بهزاد، مهدی، ویراستار. نخستین درس در جبر مجرد. ج. اول. ترجمهٔ مسعود فرزان. تهران: مرکز نشر دانشگاهی. شابک ۹۶۴-۰۱-۰۳۵۱-۹.
- http://en.wikipedia.org/wiki/Adjacent_vertex