موضوع مقاله: روش تجزیه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش تجزیه | مقدمه: یک گراف ساده را همبند می‌گوییم در صورتی که بین هر دو رأس آن مسیری وجود داشته باشد. | ## بخش 1: روش تجزیه | یک گراف دوهمبند(گراف دوهمبند راسی) ساده گرافی است که بین هر دو راس آن دو مسیر مجزا راسی وجود داشته باشد. قضیه ویتنی یک گراف K-همبند است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم. مطلبی که به‌طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود. حال با توجه به رئوس برشی سعی می‌کنیم تعریفی از مؤلفه‌های دوهمبند گراف ارائه دهیم. تعریف مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آن‌ها دوهمبند باشد. همان‌طور که از تعریف بالا بر می‌آید مؤلفه‌های دوهمبند به صورت مجموعه‌ای از یال‌ها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مؤلفه دو همبند قرار داشته باشد. برای این کار از دو لم زیر کمک می‌گیریم: لم ۱ یال‌های e و f به یک مؤلفهٔ دو همبند تعلق دارند اگر و تنها اگر یک دور وجود داشته باشد که شامل هر دوی آن‌ها باشد. البته یک مؤلفه دو همبند می‌تواند شامل فقط یک یال باشد و لم بالا فقط مؤلفه‌های با بیش از یک یال را مد نظر دارد. حال سعی می‌کنیم با کمک دو لم بالا و الگوریتم جستجوی اول عمق این کار را انجام دهیم. فرض کنید که الگوریتم DFS از راس a شروع به پیمایش گراف کند و b یک راس برشی در گراف باشد و B جزئی از گراف باشد که در درخت DFS زیر درخت راس b است. طبق تعریف، راس b در صورتی راس برشی است که هر مسیری از رئوس مجموعه B به سایر نقاط گراف از راس b بگذرد. | ## بخش 2: روش تجزیه | چون مجموعه B زیر درخت راس b در درخت DFS است و در درخت DFS نیز یال عرضی وجود ندارد در نتیجه تنها یالها یی که مجموعه B را به قسمتهای دیگر گراف متصل می‌کند یالهایی به پدر رئوس B است. یا به بیان دیگر راس b برشی است اگر و تنها اگر هیچ یالی از مجموعه B به پدرهای b وجود نداشته باشد. حال برای تشخیص این شرط، به ازای هر راس v یک متغیر تعریف می‌کنیم که برابر با ارتفاع بالاترین راسی است که از یکی از رئوس زیر درخت v به آن یال وجود دارد. برای این کار در صورتی که H همهٔ بچه‌های v در درخت را بدانیم برابر خواهد بود با مینیمم H بچه‌هایش و کمترین ارتفاع پدران مجاورش. پس در نتیجه می‌توانیم با یک تغییر ساده در الگوریتم DFS ,Hهمه رئوس را بدست آوریم و به وسیله آن رئوس برشی و در نتیجه مؤلفه‌های دو همبند گراف را تعیین کنیم. بر خلاف رئوس دیگر، ریشه در صورتی برشی است که بیش از یک فرزند در درخت داشته باشد. پیچیدگی الگوریتم چون در این الگوریتم فقط از DFS استفاده کرده‌ایم پیچیدگی الگوریتم ما از است. تجزیه گرافهای جهت دار به مولفه‌های قویاهمبند حال به بررسی گراف‌های جهت دار و شیوه تجزیه آن‌ها به مؤلفه‌های قویا همبند می‌پردازیم. تعریف یک گراف جهتدار را قویا همبند می‌گوییم اگر و تنها اگر به ازای هر دو راس u و v یک مسیر جهتدار از u به v و یک مسیر جهتدار از v به u وجود داشته باشد. یک مؤلفهٔ قویا همبند یک زیر مجموعهٔ ماکسیمال از رئوس است که زیر گراف القایی آن‌ها قویا همبند باشد. همان‌طور که می‌بینید بر خلاف مؤلفه‌های دو همبند، مؤلفه‌های قویا همبند زیرمجموعه‌ای از رئوس است. | ## بخش 3: روش تجزیه | حال سعی می‌کنیم با استقرا الگوریتمی برای افراز یک گراف به مؤلفه‌های قویا همبند ارائه دهیم. الگوریتم استقرایی برای یافتن مولفه‌های قویاً همبند پایه استقرا:در گراف‌هایی که هیچ یالی ندارند هیچ مؤلفه دو همبندی نیز وجود ندارد. یال دلخواه e از آن حذف می‌کنیم و گراف حاصل را طبق فرض استقرا به مؤلفه‌های قویا همبند افراز می‌کنیم. در صورتی که e دو راس از یک مؤلفه را به یکدیگر وصل کند در این صورت تأثیری در افراز ما ندارد. (گراف scc منسوب به G گرافی است که در آن هر مؤلفهٔ قویا همبند G را یک راس در نظر می‌گیریم و فقط یال‌هایی را در آن می‌آوریم که دو راس از دو مؤلفهٔ مختلف را به هم متصل می‌کنند)در این صورت کل مؤلفه‌هایی که در دور قرار دارند را یک مؤلفه می‌کنیم. برای این کار به ازای هر راس دو عدد در نظر می‌گیریم: عدد dfs:این عدد تعیین می‌کند که این راس چندمین رأسی بوده‌است که توسط DFS پیموده شده‌است. :عدد ارتفاع: این عدد به ازای راس x برابر کمترین عدد dfs ای است که x یا یکی از فرزندانش به آن یال داشته‌اند. در صورتی که به ازای راس x عدد ارتفاع از عدد dfs بیشتر باشد به این معنی است که هیچ‌یک از فرزندان x در درخت DFS به پدری از x یال بازگشتی نداشته‌اند و همچنین هیچ یال عرضی به خارج از زیر درخت x نداشته‌اند. در نتیجه در صورتی که x اولین راسی باشد که چنین شرطی برایش برقرار شده‌است می‌توانیم بگوییم که x و همه فرزندانش یک مؤلفهٔ قویا همبند را تشکیل اده‌اند. پس می‌توانیم با حذف آن‌ها از گراف همین کار را برای بقیه رئوس گراف انجام دهیم و در نتیجه گراف را به مؤلفه‌های قویا همبند افراز کنیم. | ## جمع‌بندی | پیچیدگی الگوریتم چون در این الگوریتم فقط از DFS استفاده کرده‌ایم پیچیدگی الگوریتم ما از است.