گراف k همبند¶

گراف k همبند¶

به گرافی k همبند گویند اگر بیش از k راس داشته باشد و هرگاه کمتر از k راس از گراف حذف کنیم گراف ناهمبند نشود و همینطور k بیشترین مقدار ممکن باشد و آن را به شکل \(\kappa (G)\) هم نشان می دهند. تعریف دیگری هم برای این مفهوم موجود است و آن به این صورت است که "کمترین تعداد راسی که با حذف آن ها از گراف، گراف ناهمبند شود" که البته این تعریف یک مشکل دارد و آن هم گراف های کامل است. اگر توجه کنید هیچگاه با حذف هر تعدادی راس از گراف های کامل نمی توانید آن ها را ناهمبند کنید و در نهایت می توانید آن را راس تنها کنید که با این اوصاف با یک تغییر در تعریف دوم می توانیم آن را درست کنیم. بنابراین می توانیم بگوییم - کمترین تعداد راسی که با حذف آن ها از گراف، گراف ناهمبند یا راس تنها شود. \(\kappa (u,v)\) تعریف می شود کمترین تعداد راسی که با حذف آن ارتباط بین u و v قطع می شود(یا به عبارتی در دو مولفه جدا قرار می گیرند).

گراف k همبند یالی¶

همانند گراف k همبند تعریف می شود فقط این تعریف بجای راس ها برای یال ها صدق می کند. بنابراین گراف k همبند یالی گرافی است که با حذف حداقل k یال بتوان آن را ناهمبند یا راس تنها کرد که آن را با \(\kappa^{\prime}(G)\) نشان می دهیم. توجه کنید که این مقدار می تواند صفر هم باشد. اگر همبند باشد و گراف یال برشی داشته باشد یک شود. همچنین \(\kappa^{\prime}(u,v)\) تعریف می شود کمترین تعداد یالی که با حذف آن ها ارتباط بین u و v قطع می شود و آن ها را در دو مولفه جدا قرار می دهد.

قضیه منجر (Menger)¶

چند مسیر بین راس های u و v را مجزا می نامیم اگر این چند مسیر بجز دو راس u و v راس مشترک دیگری نداشته باشند. حال می توان گفت که کمترین تعداد راسی که با حذف آن ها ارتباط بین دو راس u و v قطع می شود برابر بیشترین تعداد مسیر مجزا بین این دو راس است.

همین قضیه برای یال ها هم استفاده می شود و به این شکل است که کمترین تعداد یال که با حذفشان ارتباط دو راس را قطع می کنند برابر بیشترین تعداد مسیر مجزا بین دو راس است.