همبند

ایدهی ابتدایی این الگوریتم: الگوریتم جستجو عمق اول با راس دلخواه شروع می‌کند (و جستجوی بعدی عمق اول، بر روی راس‌هایی اعمال می‌شود که دیده نشدهاند). با الگوریتم جستجوی عمق اول، جستجو، هر راسی گراف را دقیقاً یک بار می‌بیند؛ بنابراین، مجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفه‌های قویاً همبند، به عنوان زیردرختهای معین این درخت پوشا، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفه‌های قویاً همبند می‌گویند. هر راسی از مؤلفه‌های قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین راسی باشد که از آن مؤلفه دیده می‌شود.

یک دیدگاه دیگر برای این که چرا دنبال کنندهٔ دیوار نتیجه می‌دهد، دیدگاه توپولوژی است. اگر دیوارها متصل باشند، ممکن است به صورت یک حلقه یا دایره تغییر شکل دهند آنگاه دنبال کردن دیوار به حرکت کردن دور دایره از نقطهٔ آغاز تا پایان خلاصه می‌شود. برای پیشبرد این ایده ملاحظه شود که با گروه کردن مؤلفه‌های همبند دیوارهای مارپیچ، مرزهای آن‌ها به‌طور دقیق همان جواب هستند، حتی اگر بیش از یک جواب وجود داشته باشد. (شکل‌های سمت راست)

در اعتراض به دستگیری مجدد توقف درمان در وضعیتی وخیم وی اقدام به اعتصاب غذای نامحدود در زندان اوین کرد. همبندان او در مصاحبه و با پخش اطلاعیه‌هایی اعلام کردند که با وخیم شدن وضعیت اعتصاب غذای وی و انتقال او به بخش بهداری زندان اوین، مأمورین زندان دست و پای وی را با زنجیر بسته و دهان او را هم با چسب می‌بندند (به دلیل حضور بازرسان بین‌المللی) و در نهایت همان شب او به‌طور مشکوکی فوت می‌کند. وکیل مدافع محمدی، خلیل بهرامیان از قول زندانیان دیگر همبند موکل‌اش از جمله علی افشاری گفت که محمدی در طول چند روز پیش از مرگ، بارها وحشیانه مورد ضرب و شتم قرار گرفته بود و آثار شکنجه بر بدن او به خوبی نمایان بوده‌است.

اگر هر جزء قویا همبند یک راس واحد باشد، گراف حاصل گرافی بدون دور است. یک گراف جهت‌دار، بدون دور است اگر و تنها اگر زیرگرافی قویا همبند با بیش از یک راس نداشته باشد، به دلیل اینکه یک دور جهت‌دار، قویا همبند بوده و هر جزء قویا همبند شامل حداقل یک دور است.

الگوریتم استور-واگنر یک الگوریتم بازگشتی برای حل مسئله برش کمینه در گراف‌های وزن‌دار بدون جهت با وزن‌های نامنفی است. این الگوریتم در سال ۱۹۹۵ توسط مکتیلد استور و فرانک واگنر پیشنهاد داده شد. همبندی گراف یکی از موضوعات کلاسیک در نظریه گراف‌ها می‌باشد و استفاده‌های کاربردی بسیاری مانند طراحی تراشه و مدار، قابل اعتماد بودن شبکات ارتباطی، برنامه‌ریزی حمل و نقل و خوشه بندی دارد. پیدا کردن برش کمینه یک گراف وزن‌دار یه مسئله اساسی الگوریتمی است. به‌طور دقیق این کار شامل پیدا کردن دو بخش مجزا از گراف بطوری که جمع وزن یال‌هایی که این دو بخش را به هم متصل می‌کنند کمینه شود می‌باشد.