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

بدون خلاصه ویرایش
جز (Hafez صفحهٔ مجاور(نظریه گراف) را به مجاور (نظریه گراف) منتقل کرد)
[[Image:6n-graf.svg|thumb|گراف G، شامل 6۶ راس و 7۷ یال است.]]
در [[نظریه گراف]] ، [[راس]] مجاور راس v در [[گراف]] G راسی است که با یالی به v وصل شده باشد. مجاور‌های راس v در گراف G ناشی از [[زیر‌گراف|زیرگرافی]] هستند که همه‌ی رئوس G را دارد و بین هر دو راس آن یالی وجود دارد. به عنوانمثال،درعنوان مثال، در تصویر روبرو، گرافی با 6۶ راس و 7۷ یال نمایش دادهداده‌شده‌است. شده است.راس 5۵ با دو راس ۱، 2۲ و 4۴ '''مجاور''' است ولی با رئوس 3۳ و 6۶ '''مجاور نیست''' نیست.
 
معمولا مجاورت رئوس را با ('' N''<sub>''G''</sub>(''v'') orیا (&nbsp;''N''(''v'' نمایش می‌دهند.
 
مجاور‌ها معمولا در الگوریتم‌های کامپیوترکامپپوتر استفاده می‌شود و توسط [[ماتریس مجاورت]] و [[فهرست مجاورت|لیست مجاورت]] نمایش داده‌می‌شود. همچنین، توسط مجاور‌ها می‌توان [[ضریب خوشه‌بندی]] گراف را که برابر است با میزان میانگین چگالی مجاور، به دست آورد.
 
[[رأس (نظریه گراف)|راس منفرد]] هیچ مجاوری ندارد. درجه هرراس برابر با تعداد مجاور‌هایش است. حالت خاص [[دور]] است که راس با خود در ارتباط است، اگر چنین یالی وجود داشته باسدباشد راس با خود مجاور است.
 
==خواص مجاورت در گراف==
[[Image:Octahedron graph.png|thumb|گراف هشت وجهی مجاور چرخه &nbsp;''C''<sub>4</sub> است]]
اگر همه‌ی رئوس گراف G مجاورداشته باشند، [[هم‌ریختی|هم‌ریخت]] این گراف، گرافی مشابه گراف H خواهد بود و G را مجاور H می‌نامند. به طور مثال در تصویر، گراف هشت وجهی نشان داده‌شده‌است، که مجاور هر راس همریخت، چرخه‌ای از چهار راس است. پس گراف هشت وجهی مجاور چرخه &nbsp;''C''<sub>4</sub> است.
 
 
مثال :
*گراف کامل ''K''<sub>''n''</sub> مجاور گراف ''K''<sub>''n-1''</sub>است.
*گرافگرافی بدون مثلث است اگر و تنها اگر آن گراف به صورت مجاور مستقل باشد.
 
==همسایگی(مجاورت) یک مجموعه==
۸

ویرایش