گراف دوهمبند

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

گراف دوهمبند  حالت خاصی از گراف چند همبند است.

گراف دوهمبند٫ یک گراف همبند است با این خصوصیت که غیر جداشدنی باشد٫ یعنی با حذف یک راس همبند باقی بماند.
این خاصیت برای مدیریت یک گراف با افزونگی دوگانه سودمند است به این منظور که از ناهمبند شدن گراف با حذف یک یال آن جلوگیری شود.

به جهت خاصیت افزونگی٫ استفاده از گراف دوهمبند در زمینه شبکه (ببینید شبکه شاره)٫ بسیار مهم است.

تعداد گراف‌های دوهمبند

قضیه. ویتنی 
قضیه. (ویتنی [۱۹۳۲]) یک گراف بیسوی G که دارای حداقل سه راس باشد٫ دوهمبند است اگر٫ و فقط اگر٫ هر جفت  به وسیلهٔ دو مسیر درونی مجزا٫ یعنی مسیری که به غیر از u و v راس مشترک دیگری ندارد٫ به هم وصل شوند.

لم (بسط لم) 
اگر G یک گراف k-همبند باشد و  از  با افزودن یک راس جدید y مجاور با حداقل k راس از G٫ یه دست آید٫ آن گاه  k-همبند است.

قضیه هم ارزی 
قضیه. اگر ۳٫ آن گاه شرایط زیر برای گراف‌های دوهمبند برقرار و هم ارز هستند.

الف) G همبند است و دارای هیج راس برشی نیست.

ب) به ازای هر  مسیرهای درونی مجزا وجود دارد.

پ) به ازای هر  یک دور میان x و y وجود دارد.

ت) ۱٫ و هر جفت از یال‌ها در ٫G روی یک دور مشترک قرار می‌گیرند.

تعریف. زیرتقسیم یک یال 
زیرتقسیم یال  از یک گراف بیسوی G عبارت است از حذف  و افزودن مسیر جدید  میان یک راس جدید .

فرع. اگر G دوهمبند باشد٫ آن گاه گراف  به دست آمده از زیر تقسیم یک یال ٫G دوهمبند است.

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

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

قضیه. (ویتنی [۱۹۳۲]). یک گراف دو همبند است اگر٫ و فقط اگر٫ دارای یک تجزیه دسته باشد. علاوه بر این٫ هر دور در یک گراف دوهمبند٫ دور آغازی در یک تجزیه دسته‌است.

پانویس

مثال‌ها

منابع 
 
  
 
 Eric W. Weisstein. "Biconnected Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html
 Paul E. Black، "biconnected graph"، in Dictionary of Algorithms and Data Structures [online]، Paul E. Black، ed.، U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/biconnectedGraph.html

خانواده‌های گراف
همبندی گراف