روش تجزیه

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

نمونه‌ای از تجزیه یک گراف به مولفه‌های دو همبند.

قضیه ویتنی

یک گراف 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]}$ تعریف می‌کنیم که برابر با ارتفاع بالاترین راسی است که از یکی از رئوس زیر درخت v به آن یال وجود دارد. با توجه به این متغیر در صورتی یک راس برشی است که H آن برابر ارتفاع خود آن باشد. پس مسئله ما به این تبدیل می‌شود که H هر راس را محاسبه کنیم.برای این کار در صورتی که H همهٔ بچه‌های v در درخت را بدانیم ${\displaystyle H[v]}$ برابر خواهد بود با مینیمم H بچه‌هایش و کمترین ارتفاع پدران مجاورش. پس در نتیجه می‌توانیم با یک تغییر ساده در الگوریتم

DFS ,H

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

پیچیدگی الگوریتم

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

تجزیه گرافهای جهت دار به مولفه‌های قویاهمبند

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

تعریف

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

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

نمونه‌ای از تجزیه یک گراف به مولفه‌های قویا همبند.

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

الگوریتم استقرایی برای یافتن مولفه‌های قویاً همبند

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

حال سعی می‌کنیم این الگوریتم را با استفاده از الگوریتم DFS پیاده‌سازی کنیم. برای این کار به ازای هر راس دو عدد در نظر می‌گیریم: ۱.عدد dfs:این عدد تعیین می‌کند که این راس چندمین رأسی بوده‌است که توسط DFS پیموده شده‌است. ۲.:عدد ارتفاع: این عدد به ازای راس 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, ISBN 0-262-53196-8