مفهوم دوهمبندی ( به انگلیسی: 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 وجود نداشته باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک گراف 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 وجود نداشته باشد.
wiki: روش تجزیه