همبندی (نظریه گراف)
در ریاضیات و علوم کامپیوتر، همبندی یکی از مفاهیم اولیهٔ نظریهٔ گراف است: همبندی به دنبال حداقل تعداد رأس‌ها یا یال‌هایی است که با حذفشان، ارتباط رأس‌های باقی‌مانده از بین برود. این مبحث تا حد زیادی به مسئله‌های شبکه شاره مربوط است. همبندی یک گراف، یک مقیاس مهم برای سنجش میزان کمتر بودن خطاهایش به عنوان یک شبکه است.
در یک گراف بدون جهت formula_1، دو رأس formula_2 و formula_3 را متصل می‌نامیم اگر گراف formula_1 مسیری از formula_2 به formula_3 داشته باشد. در غیر این صورت، آن‌ها غیرمتصل نامیده می‌شوند. اگر دو رأس با مسیری به طول یک (یک یال) به هم متصل باشند، رأس‌ها، مجاور(همسایه) نامیده می‌شوند. به یک گراف همبند می‌گوییم، اگر هر دو رأس دلخواه آن (از طریق حداقل یک مسیر) به هم متصل باشند. یک مؤلفهٔ همبندی یک زیرگراف همبند ماکسیمال از formula_1 است. هر رأس و یالی به یک مؤلفهٔ همبندی مربوط است.
اگر در یک گراف جهت‌دار، جایگزین کردن تمام یال‌های جهت‌دار با یال‌های بدون جهت منجر به ساخت یک گراف همبند (بدون جهت) شود، در این صورت به این گراف جهت‌دار همبند ضعیف می‌گوییم.به عبارت دیگر این گراف همبند است اگر به ازای هر دو رأس دلخواه formula_2 و formula_3، مسیری جهت‌دار از formula_2 به formula_3 یا از formula_3 به formula_2، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه formula_2 و formula_3، مسیری جهت‌دار هم از formula_2 به formula_3 و هم از formula_3 به formula_2 داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.
یک برش، رأس برشی، یا مجموعهٔ جداکنندهٔ گراف همبند formula_1، مجموعه‌ای از رئوس است که با حذفشان گراف formula_1 ناهمبند می‌شود. عدد همبندی یا عدد همبند رأسی که با formula_22 نشان داده می‌شود (و "G" در آن گراف کامل نیست) تعداد مینیمال رأس‌های برشی است. یک گراف "k"-همبند یا "k"-همبند رأسی نامیده می‌شود اگر تعداد رئوس همبندی آن، حداقل "k" باشد. این بدین معنی است که گراف formula_1 را زمانی "k"-همبند می‌نامیم که در آن، یک مجموعه ی k"-1" عضوی از رأس‌هایی که با حذفشان گراف، ناهمبند می‌شود، وجود نداشته باشد. یک گراف کامل با n رأس که با formula_24 نشان داده می‌شود، هیچ رأس برشی ندارد، ولی بنابر قرارداد داریم formula_25. رأس برشی رئوس formula_2 و formula_3 مجموعه‌ای از رأس‌ها است که با حذف کردنشان، ارتباط بین formula_2 و formula_3 قطع می‌شود. عدد همبندی محلی formula_30 برابر با کمترین تعداد رئوس برشی است که با حذفشان، ارتباط formula_2 و formula_3 قطع می‌شود. همبندی محلی برای گراف‌های بدون جهت، متقارن است formula_33. علاوه بر این به استثنای گراف‌های کامل، formula_22 به ازای هر دو انتخاب دلخواه از رأس‌های formula_2 و formula_3 برابر است با حداقل formula_30.
گراف دوهمبند مثالی از گراف "k"-همبند است.
مفاهیم مشابهی را می‌توان برای یال‌ها تعریف کرد. به عنوان نمونه، اگر حذف یک یال خاص، آن گراف را ناهمبند کند، در این صورت این یال، پل نامیده می‌شود. به‌طور کلی، یال برشی گراف "G" مجموعه‌ای از یال‌ها است که حذف آن‌ها، گراف را ناهمبند می‌کند. عدد همبند یالی formula_38 برابر با اندازهٔ کوچکترین مجموعهٔ یال‌های برشی است و عدد همبند یالی محلی formula_39 رئوس "u" و "v" برابر با اندازه ی کوچکترین یال برشی است که "u" و "v" را از هم جدا می‌کند. همبند یالی محلی متقارن است. یک گراف "k"-همبند یالی نامیده می‌شود، اگر عدد همبندی یالی آن حداقل "k" باشد.
یکی از مهمترین قضایا دربارهٔ همبندی در گراف‌ها قضیهٔ منگر است که عدد همبندی و عدد همبند یالی یک گراف را به صورت مسیرهای مستقل بین رئوس مشخص می‌کند. اگر formula_2 و formula_3 رأس‌های گراف formula_1 باشند، آنگاه مجموعه‌ای از مسیرها بین formula_2 و formula_3 را "مستقل" می‌نامیم، اگر هیچ دوتایی از آن‌ها، رأس مشترک نداشته باشند (به جز رأس‌های "u" و "v"). به‌طور مشابه، یک مجموعه، یال-مستقل است، اگر هیچ دو مسیری از آن، یال مشترک نداشته باشند. تعداد مسیرهای دو به دو مستقل بین formula_2 و formula_3 به صورت formula_47 و تعداد مسیرهای دو به دو یال-مستقل بین "u" و "v" به صورت formula_39 نوشته می‌شوند. قضیهٔ منگر ادعا می‌کند که عدد همبندی محلی formula_30 با formula_47 برابر است و عدد همبندی یالی محلی formula_39 با formula_52 به ازای هر انتخاب دلخواه از رأس‌های "u" و "v" برابر است. این قضیه، یک حالت خاص از قضیهٔ جریان بیشینه - برش کمینه است.
مسئلهٔ تعیین اینکه آیا در یک گراف، دو رأس به هم متصل هستند یا نه، می‌تواند به صورت مؤثر با استفاده از الگوریتم سرچ، مثل جستجوی اول سطح، حل شود. به‌طور کلی، تعیین محاسباتی اینکه آیا یک گراف همبند است،(برای مثال با استفاده از مجموعه‌های مجزا در ساختمان داده)، یا شمارش تعداد مؤلفه‌های همبندی گراف آسان است. یک الگوریتم ساده به صورت شبه کد به صورت زیر است:
با استفاده از قضیهٔ منگر، برای هر دو رأس دلخواه "u" و "v" در یک گراف همبند formula_1، مقادیر formula_30 و formula_39 می‌توانند توسط الگوریتم جریان بیشینه - برش کمین تعیین شوند. در این صورت عدد همبندی و عدد همبند یالی گراف formula_1 به ترتیب برابر با کمینه مقادیر formula_30 و formula_39 خواهند بود. همبندی گراف‌های بدون جهت، در مرتبهٔ formula_61 قابل حل است. مسئلهٔ محاسبهٔ احتمال اینکه یک گراف تصادفی، همبند باشد، "اعتبار شبکه" نامیده می‌شود. همچنین مسئلهٔ محاسبهٔ اینکه آیا دو رأس داده شده، متصل هستند، "ST-reliability problem" نامیده می‌شود. هر دوی این مسائل sharp-P]] Hard]] هستند.