همبند در لغت به معنی همبسته و متصل است. این معنا در جاهای مختلفی از مبحث گراف به ذهن خطور میکند.
در اینجا به دو خصوصیت مهم و پرکاربرد از گرافها, همبندی راسی, همبندی یالی پرداخته میشود.اما نخست به تعریف چند مفهوم کمککننده میپردازیم.
اتصال
در یک گراف بیجهت
همبندی
تعریف غیر رسمی که میتوان برای این واژه ارایه داد. این است که اگر راسی از یک گراف را به سمتی بکشیم دیگر قسمتهای آن
گراف به حرکت در بیایند.
واما دو تعریف رسمی نیز وجود دارد:
- گراف
همبند است. اگر هر دو راس از آن به هم متصل باشد. - راسهای گراف
را به دو قسمت و تقسیم میکنیم آنگاه قطعا یال وجود دارد که از مجموعه و از مجموعه باشد.
همبندی راسی
همبندی راسی خصوصیتیست که به ردههای مختلف گراف ها هم کلاس با اعداد طبیعی اتلاق میشود.برای مثال یک گراف ۴همبند راسی گرافیست که در آن به حذف حداقل ۴ راس برای تضمین ناهمبند شدن لازم باشد.
و اما تعریف دقیق:
گراف
همبندی یالی
این تعریف نیز مانند تعریف بالاست پس بدون توضیح اضافی به تعریف رسمی میپردازیم:
گراف