روش تجزیه

یک گراف K-همبند (به انگلیسی: K-connected Graph)است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.

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

حال با توجه به رئوس برشی سعی می‌کنیم تعریفی از مؤلفه‌های دوهمبند گراف ارائه دهیم.

مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آن‌ها دوهمبند باشد.

همان‌طور که از تعریف بالا بر می‌آید مؤلفه‌های دوهمبند به صورت مجموعه‌ای از یال‌ها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مؤلفه دو همبند قرار داشته باشد. پس ما به دنبال یک افراز از یال‌ها هستیم. برای این کار از دو لم زیر کمک می‌گیریم:

یال‌های e و f به یک مؤلفهٔ دو همبند تعلق دارند اگر و تنها اگر یک دور وجود داشته باشد که شامل هر دوی آن‌ها باشد.

البته یک مؤلفه دو همبند می‌تواند شامل فقط یک یال باشد و لم بالا فقط مؤلفه‌های با بیش از یک یال را مد نظر دارد.

هر یال فقط در یک مولفه دوهمبند قرار دارد.

حال سعی می‌کنیم با کمک دو لم بالا و الگوریتم جستجوی اول عمق (به انگلیسی: DFS) این کار را انجام دهیم.

فرض کنید که الگوریتم DFS از راس a شروع به پیمایش گراف کند و b یک راس برشی در گراف باشد و B جزئی از گراف باشد که در درخت DFS زیر درخت راس b است. ما چگونه می‌توانیم تشخیص دهیم که راس b یک راس برشی است؟ طبق تعریف، راس b در صورتی راس برشی است که هر مسیری از رئوس مجموعه B به سایر نقاط گراف از راس b بگذرد. چون مجموعه B زیر درخت راس b در درخت DFS است و در درخت DFS نیز یال عرضی وجود ندارد در نتیجه تنها یالها یی که مجموعه B را به قسمتهای دیگر گراف متصل می‌کند یالهایی به پدر رئوس B است. یا به بیان دیگر راس b برشی است اگر و تنها اگر هیچ یالی از مجموعه B به پدرهای b وجود نداشته باشد.

حال برای تشخیص این شرط، به ازای هر راس v یک متغیر ${\displaystyle H[v]}$

همه رئوس را بدست آوریم و به وسیله آن رئوس برشی و در نتیجه مؤلفه‌های دو همبند گراف را تعیین کنیم. تنها حالت خاصی که وجود دارد ریشه درخت است. بر خلاف رئوس دیگر، ریشه در صورتی برشی است که بیش از یک فرزند در درخت داشته باشد.

چون در این الگوریتم فقط از DFS استفاده کرده‌ایم پیچیدگی الگوریتم ما از ${\displaystyle O(|v|+|E|)}$

حال به بررسی گراف‌های جهت دار و شیوه تجزیه آن‌ها به مؤلفه‌های قویا همبند می‌پردازیم.

یک گراف جهتدار را قویا همبند می‌گوییم اگر و تنها اگر به ازای هر دو راس u و v یک مسیر جهتدار از u به v و یک مسیر جهتدار از v به u وجود داشته باشد.

یک مؤلفهٔ قویا همبند یک زیر مجموعهٔ ماکسیمال از رئوس است که زیر گراف القایی آن‌ها قویا همبند باشد.

همان‌طور که می‌بینید بر خلاف مؤلفه‌های دو همبند، مؤلفه‌های قویا همبند زیرمجموعه‌ای از رئوس است. رئوس هر گراف جهتدار را می‌توان به مؤلفه‌های قویا همبند افراز کرد. حال سعی می‌کنیم با استقرا الگوریتمی برای افراز یک گراف به مؤلفه‌های قویا همبند ارائه دهیم.

پایه استقرا:در گراف‌هایی که هیچ یالی ندارند هیچ مؤلفه دو همبندی نیز وجود ندارد. فرض استقرا:ما روش تجزیه گراف‌های با کمتر از m یال را می‌دانیم. گام استقرا:حال یک گراف با m یال را در نظر بگیرید. یال دلخواه e از آن حذف می‌کنیم و گراف حاصل را طبق فرض استقرا به مؤلفه‌های قویا همبند افراز می‌کنیم. حال یال e را به گراف برمی‌گردانیم. در صورتی که e دو راس از یک مؤلفه را به یکدیگر وصل کند در این صورت تأثیری در افراز ما ندارد. تنها زمانی e می‌تواند مشکل ساز باشد که در گراف SCC یک دور ایجاد کند. (گراف scc منسوب به G گرافی است که در آن هر مؤلفهٔ قویا همبند G را یک راس در نظر می‌گیریم و فقط یال‌هایی را در آن می‌آوریم که دو راس از دو مؤلفهٔ مختلف را به هم متصل می‌کنند)در این صورت کل مؤلفه‌هایی که در دور قرار دارند را یک مؤلفه می‌کنیم.

حال سعی می‌کنیم این الگوریتم را با استفاده از الگوریتم DFS پیاده‌سازی کنیم. برای این کار به ازای هر راس دو عدد در نظر می‌گیریم:

1. عدد dfs:این عدد تعیین می‌کند که این راس چندمین رأسی بوده‌است که توسط DFS پیموده شده‌است.
2. :عدد ارتفاع: این عدد به ازای راس x برابر کمترین عدد dfs ای است که x یا یکی از فرزندانش به آن یال داشته‌اند.

در صورتی که به ازای راس x عدد ارتفاع از عدد dfs بیشتر باشد به این معنی است که هیچ‌یک از فرزندان x در درخت DFS به پدری از x یال بازگشتی نداشته‌اند و همچنین هیچ یال عرضی به خارج از زیر درخت x نداشته‌اند. در نتیجه در صورتی که x اولین راسی باشد که چنین شرطی برایش برقرار شده‌است می‌توانیم بگوییم که x و همه فرزندانش یک مؤلفهٔ قویا همبند را تشکیل اده‌اند. پس می‌توانیم با حذف آن‌ها از گراف همین کار را برای بقیه رئوس گراف انجام دهیم و در نتیجه گراف را به مؤلفه‌های قویا همبند افراز کنیم.

چون در این الگوریتم فقط از DFS استفاده کرده‌ایم پیچیدگی الگوریتم ما از ${\displaystyle O(|v|+|E|)}$

• UDI MANBER, دانشگاه آریزونا, مقدمه‌ای بر الگوریتم‌ها (به انگلیسی)
• توماس اچ کورمن، Charles E. Leiserson, رونالد ریوست and کلیفورد استین (2001), مقدمه‌ای بر الگوریتم‌ها (به انگلیسی) (second ed.), MIT Press and McGraw-Hill