روش تجزیه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
نمونه‌ای از تجزیه یک گراف به مولفه‌های دو همبند.

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

DFS ,H

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

پیچیدگی الگوریتم[ویرایش]

چون در این الگوریتم فقط از DFS استفاده کرده‌ایم پیچیدگی الگوریتم ما از 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 استفاده کرده‌ایم پیچیدگی الگوریتم ما از O(|v|+|E|)\,\! است.

منابع[ویرایش]