گراف دوهمبند

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

اگر G یک گراف k-همبند باشد و ${\displaystyle G'\,\!}$ از ${\displaystyle G\,\!}$ با افزودن یک راس جدید y مجاور با حداقل k راس از G٫ یه دست آید٫ آن گاه ${\displaystyle G'\,\!}$ k-همبند است.

قضیه. اگر ۳${\displaystyle n(G)\geq }$٫ آن گاه شرایط زیر برای گراف‌های دوهمبند برقرار و هم ارز هستند.

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

ب) به ازای هر ${\displaystyle x,y\in V(G)}$ مسیرهای درونی مجزا وجود دارد.

پ) به ازای هر ${\displaystyle x,y\in V(G)}$ یک دور میان x و y وجود دارد.

ت) ۱${\displaystyle \delta (G)\geq }$٫ و هر جفت از یال‌ها در ٫G روی یک دور مشترک قرار می‌گیرند.

زیرتقسیم یال ${\displaystyle uv}$ از یک گراف بیسوی G عبارت است از حذف ${\displaystyle uv}$ و افزودن مسیر جدید ${\displaystyle u,w,v}$ میان یک راس جدید ${\displaystyle w}$.

فرع. اگر G دوهمبند باشد٫ آن گاه گراف ${\displaystyle G'\,\!}$ به دست آمده از زیر تقسیم یک یال ٫G دوهمبند است.

یک مسیر افزودن به ٫G افزودن مسیری است به G با طول ۱${\displaystyle l\geq }$ میان دو راس از G ٫ که ${\displaystyle l-1\,\!}$ راس جدید را ارایٔه می‌کند. مسیر افزوده شده را دسته می‌گویند.

شکل ۱

یک تجزیه دسته عبارت است از افراز ${\displaystyle E(G)\,\!}$ به مجموعه‌های ${\displaystyle P_{0},P_{1},...,P_{k}}$ به طوری که ${\displaystyle P_{0}\,\!}$ یک دور باشد٫ و ${\displaystyle P_{i}\,\!}$ به ازای ۱${\displaystyle i\geq }$ یک مسیر افزودن به گراف تشکیل شده به وسیلهٔ ${\displaystyle P_{0},P_{1},...,P_{i-1}}$ باشد.

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

• مشارکت‌کنندگان ویکی‌پدیا. «Biconnected graph». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۲ می۲۰۰۹.
• Douglas B. West (2000), "4.2", Introduction to Graph Theory (second ed.), Prentice Hall, ISBN 0-13-014400-2
• مشارکت‌کنندگان ویکی‌پدیا. «K-vertex-connected graph». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۹ می۲۰۰۹.
• 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