المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:گراف:همبندی راسی و یالی

همبند در لغت به معنی همبسته و متصل است. این معنا در جاهای مختلفی از مبحث گراف به ذهن خطور می‌کند.
در این‌جا به دو خصوصیت مهم و پرکاربرد از گراف‌ها, همبندی راسی, همبندی یالی پرداخته می‌شود.اما نخست به تعریف چند مفهوم کمک‌کننده می‌پردازیم.

اتصال

در یک گراف بی‌جهت$G$ دو راس $v$ و $u$ به هم متصل‌اند. اگر مسیری بین $v$ و $u$ در $G$ وجودداشته باشد.

همبندی

تعریف غیر رسمی که میتوان برای این واژه ارایه داد. این است که اگر راسی از یک گراف را به سمتی بکشیم دیگر قسمت های آن گراف به حرکت در بیایند.
واما دو تعریف رسمی نیز وجود دارد:

  1. گراف $G$ همبند است. اگر هر دو راس از آن به هم متصل باشد.
  2. راس های گراف $G$ را به دو قسمت $S$ و $G - S$ تقسیم می کنیم آنگاه قطعا یال $v$$u$ وجود دارد که $v$ از مجموعه $S$ و $u$ از مجموعه $G - S$ باشد.

همبندی راسی

همبندی راسی خصوصیتیست که به رده های مختلف گراف ها هم کلاس با اعداد طبیعی اتلاق میشود.برای مثال یک گراف ۴همبند راسی گرافیست که در آن به حذف حداقل ۴ راس برای تضمین ناهمبند شدن لازم باشد. و اما تعریف دقیق:
گراف $G$ $(K)$همبند راسی است اگر اگر حداقل یک زیر مجموعه $K$ راسی از $V$ وجود ذاشته باشد که حذف آن ها $G$ را نا همبند کند. ولی هیچ زیر مجموعه $K-1$ از $V$ وجود نداشته باشد که با حذفشان $G$ ناهمبند شود.

همبندی یالی

این تعریف نیز مانند تعریف بالاست پس بدون توضیح اضافی به تعریف رسمی میپردازیم:
گراف $G$ $(K)$همبند یالی است اگر اگر حداقل یک زیر مجموعه $K$ یالی از $E$ وجود ذاشته باشد که حذف آن ها $G$ را نا همبند کند. ولی هیچ زیر مجموعه $K-1$ از $E$ وجود نداشته باشد که با حذفشان $G$ ناهمبند شود.


ابزار صفحه