همبندی (نظریه گراف)

در ریاضیات و علوم کامپیوتر، همبندی یکی از مفاهیم اولیه نظریه گراف است: همبندی به دنبال حداقل تعداد راس‌ها یا یال‌هایی است که با حذفشان، ارتباط راس‌های باقی‌مانده از بین برود. این مبحث تا حد زیادی به مسئله‌های شبکه شاره مربوط است. همبندی یک گراف، یک مقیاس مهم برای سنجش میزان کمتر بودن خطاهایش به عنوان یک شبکه است.
تعریف مولفه‌ها، برش‌ها و همبندی
در یک گراف بدون جهت ، دو راس و را متصل می‌نامیم اگر گراف مسیری از به داشته باشد. در غیر این صورت، آن‌ها غیرمتصل نامیده می‌شوند. اگر دو راس با مسیری به طول یک (یک یال) به هم متصل باشند، راس‌ها، مجاور(همسایه) نامیده می‌شوند. به یک گراف همبند می‌گوییم، اگر هر دو راس دلخواه آن (از طریق حداقل یک مسیر) به هم متصل باشند.
یک مولفه همبندی یک زیرگراف همبند ماکسیمال از است. هر راس و یالی به یک مولفه همبندی مربوط است.
اگر در یک گراف جهت‌دار، جایگزین کردن تمام یال‌های جهت‌دار با یال‌های بدون جهت منجر به ساخت یک گراف همبند (بدون جهت) شود، در این صورت به این گراف جهت‌دار همبند ضعیف می‌گوییم.به عبارت دیگر این گراف همبند است اگر به ازای هر دو راس دلخواه و ، مسیری جهت‌دار از به یا از به ، وجود داشته باشد.این گراف را قویا همبند می‌نامیم، اگر به ازای هر دو راس دلخواه و ، مسیری جهت‌دار هم از به و هم از به داشته باشیم. مولفه‌های قوی ، زیرگراف‌های قویا همبند ماکسیمال هستند.
یک برش ، راس برشی ، یا مجموعه جداکننده گراف همبند ، مجموعه‌ای از رئوس است که با حذفشان گراف ناهمبند می‌شود. عدد همبندی یا عدد همبند راسی که با نشان داده می‌شود (و G در آن گراف کامل نیست) تعداد مینیمال راس‌های برشی است. یک گراف k-همبند یا k-همبند راسی نامیده می‌شود اگر تعداد رئوس همبندی آن، حداقل k باشد. این بدین معنی است که گراف را زمانی k-همبند می‌نامیم که در آن، یک مجموعه‌ی k-1 عضوی از راس‌هایی که با حذفشان گراف، ناهمبند می‌شود، وجود نداشته باشد. یک گراف کامل با n راس که با نشان داده می‌شود، هیچ راس برشی ندارد، ولی بنابر قرارداد داریم . راس برشی رئوس و مجموعه‌ای از راس‌ها است که با حذف کردنشان، ارتباط بین و قطع می‌شود. عدد همبندی محلی برابر با کمترین تعداد رئوس برشی است که با حذفشان، ارتباط و قطع می‌شود. همبندی محلی برای گراف‌های بدون جهت، متقارن است . علاوه بر این به استثنای گراف‌های کامل، به ازای هر دوانتخاب دلخواه از راس‌های و برابر است با حداقل .
گراف دوهمبند مثالی از گراف k-همبند است.
مفاهیم مشابهی را می‌توان برای یال‌ها تعریف کرد. به عنوان نمونه، اگر حذف یک یال خاص، آن گراف را ناهمبند کند، در این صورت این یال، پل نامیده می‌شود. به‌طور کلی، یال برشی گراف G مجموعه‌ای از یال‌ها است که حذف آن‌ها، گراف را ناهمبند می‌کند. عدد همبند یالی برابر با اندازه کوچکترین مجموعه یال‌های برشی است و عدد همبند یالی محلی رئوس u و v برابر با اندازه‌ی کوچکترین یال برشی است که u و v را از هم جدا می‌کند. همبند یالی محلی متقارن است. یک گراف k-همبند یالی نامیده می‌شود، اگرعدد همبندی یالی آن حداقل k باشد.
قضیه منگر
یکی از مهمترین قضایا درباره همبندی در گراف‌ها قضیه منگر است که عدد همبندی و عدد همبند یالی یک گراف را به صورت مسیرهای مستقل بین رئوس مشخص می‌کند. اگر و راس‌های گراف باشند، آنگاه مجموعه‌ای از مسیرها بین و را مستقل می‌نامیم، اگر هیچ دوتایی از آن‌ها، راس مشترک نداشته باشند (به جز راس‌های u و v). به‌طور مشابه، یک مجموعه، یال-مستقل است، اگر هیچ دو مسیری از آن، یال مشترک نداشته باشند. تعداد مسیرهای دو به دو مستقل بین و به صورت و تعداد مسیرهای دو به دو یال-مستقل بین u و v به صورت نوشته می‌شوند.
قضیه منگر ادعا می‌کند که عدد همبندی محلی با برابر است و عدد همبندی یالی محلی با به ازای هر انتخاب دلخواه از راس‌های u و v برابر است. این قضیه، یک حالت خاص از قضیه جریان بیشینه - برش کمینه است.
جنبه‌های محاسباتی
مسئله تعیین اینکه آیا در یک گراف، دو راس به هم متصل هستند یا نه، می‌تواند به صورت موثر با استفاده از الگوریتم سرچ، مثل جستجوی اول سطح، حل شود. به‌طور کلی، تعیین محاسباتی اینکه آیا یک گراف همبند است،(برای مثال با استفاده از مجموعه‌های مجزا در ساختمان داده)، یا شمارش تعداد مولفه‌های همبندی گراف آسان است. یک الگوریتم ساده به صورت شبه کد به صورت زیر است:
از یک راس دلخواه گراف شروع کن.
از این راس با استفاده از جستجوی اول سطح یا جستجوی عمق اول، شروع به حرکت کن و تمام راس‌هایی که به آن دسترسی پیدا کردی را بشمار.
هر وقت گراف به‌طور کامل پیمایش شد، اگر تعداد راس‌های شمرده شده برابر با تعداد راس‌های گراف باشد، گراف همبند است، در غیر این صورت گراف ناهمبند است.
با استفاده از قضیه منگر، برای هر دو راس دلخواه u و v در یک گراف همبند ، مقادیر و می‌توانند توسط الگوریتم جریان بیشینه - برش کمین تعیین شوند. در این صورت عدد همبندی و عدد همبند یالی گراف به ترتیب برابر با کمینه مقادیر و خواهند بود.
همبندی گراف‌های بدون جهت، در مرتبه قابل حل است.
مسئله محاسبه احتمال اینکه یک گراف تصادفی، همبند باشد، اعتبار شبکه نامیده می‌شود. همچنین مسئله محاسبه اینکه آیا دو راس داده شده، متصل هستند، ST-reliability problem نامیده می‌شود. هر دوی این مسائل sharp-P Hard هستند.
مثال‌ها
عدد همبند راسی و عدد همبند یالی یک گراف ناهمبند هر دو برابر صفر هستند.
1-همبند با همبند بودن هم معنی است.
یک گراف کامل با n راس دارای عدد همبند یالی برابر با N-1 هست. هر گراف ساده‌ی دیگر n راسی، عدد همبند یالی کمتری دارد.
در یک درخت، عدد همبند یالی محلی بین هر دو جفت از راس‌ها برابر با 1 است.
کران‌های همبندی
عدد همبند راسی یک گراف، کوچکتر یا مساوی عدد همبند یالی‌اش است . هردوی آن‌ها، از کمترین درجه گراف، کوچکتر هستند، چون حذف کردن همه رئوس مجاور یک راس با کمترین درجه، ارتباط این راس را با گراف قطع می‌کند.
ویژگی‌های دیگر
اگر همبند باشد آنگاه گراف خطی همبند است.
گراف G 2-همبند یالی است، اگر و تنها اگر یال‌های جهت داری داشته باشد که مجموعه آن یال‌ها، قویا همبند باشد.
بنابر یکی از قضایای G. A. Dirac اگر یک گراف به ازای k‌های بزرگتر مساوی 2، k-همبند باشد، آنگاه برای هر مجموعه k راسی در گراف، دوری وجود دارد که از همه رئوس این مجموعه می‌گذرد.
ریاضیات گسسته
گراف
نظریه گراف