گراف دوهمبند

یک شبکه ارتباطی در برابر نقص دارای قدرت تحمل است اگر دارای مسیرهای دیگری میان راس‌ها باشد. هر چه مسیرهای مجزا بیشتر باشد٫ بهتر است. این مثال دقیقا مفهوم گراف چند همبند (به انگلیسی: k-vertex-connected graph) است.

موضوعوعات مرتبط با
همبندی (نظریه گراف)
همبندی (نظریه گراف) Algebraic connectivity Cycle rank Rank (graph theory) درخت اس‌پی‌کیوآر St-connectivity K-connectivity certificate Pixel connectivity Vertex separator اجزای قویاً همبند گراف دوهمبند پل (نظریه گراف)

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

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

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

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

گراف غیرجداشدنی (دوهمبند) با n راس (دنباله A002218 در دانشنامه برخط سری‌های صحیح)

راس‌ها	تعداد حالت ها
۱	۰
۲	۱
۳	۱
۴	۳
۵	۱۰
۶	۵۶
۷	۴۶۸
۸	۷۱۲۳
۹	۱۹۴۰۶۶
۱۰	۹۷۴۳۵۴۲
۱۱	۹۰۰۹۶۹۰۹۱
۱۲	۱۵۳۶۲۰۳۳۳۵۴۵
۱۳	۴۸۴۳۲۹۳۹۱۵۰۷۰۴
۱۴	۲۸۳۶۱۸۲۴۴۸۸۳۹۴۱۶۹
۱۵	۳۰۹۹۵۸۹۰۸۰۶۰۳۳۳۸۰۷۸۴
۱۶	۶۳۵۰۱۶۳۵۴۲۹۱۰۹۵۹۷۵۰۴۹۵۱
۱۷	۲۴۴۸۵۲۰۷۹۲۹۲۰۷۳۳۷۶۰۱۰۴۱۱۲۸۰
۱۸	۱۷۸۳۱۶۰۵۹۴۰۶۹۴۲۹۹۲۵۹۵۲۸۲۴۷۳۴۶۴۱
۱۹	۲۴۶۰۳۸۸۷۰۵۱۳۵۰۹۴۵۸۶۷۴۹۲۸۱۶۶۶۳۹۵۸۹۸۱

قضیه. ویتنی

قضیه. (ویتنی[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}}$ باشد.

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

پانویس

1. Two-fold redundancy
2. Network flow
3. Whitney

مثال‌ها

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «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