همبندی (نظریه گراف)

نظریه گراف

در ریاضیات و علوم کامپیوتر، همبندی (به انگلیسی: Connectivity) یکی از مفاهیم اولیهٔ نظریهٔ گراف است: همبندی به دنبال حداقل تعداد رأس‌ها یا یال‌هایی است که با حذفشان، ارتباط رأس‌های باقی‌مانده از بین برود. این مبحث تا حد زیادی به مسئله‌های شبکه شاره مربوط است. همبندی یک گراف، یک مقیاس مهم برای سنجش میزانِ کمتر بودن خطاهایش به عنوان یک شبکه است.

تعریف مؤلفه‌ها، برش‌ها و همبندی

در یک گراف بدون جهت $G$، دو رأس $u$ و $v$ را متصل می‌نامیم اگر گراف $G$ مسیری از $u$ به $v$ داشته باشد. در غیر این صورت، آن‌ها غیرمتصل نامیده می‌شوند. اگر دو رأس با مسیری به طول یک (یک یال) به هم متصل باشند، رأس‌ها، مجاور(همسایه) نامیده می‌شوند. به یک گراف همبند می‌گوییم، اگر هر دو رأس دلخواه آن (از طریق حداقل یک مسیر) به هم متصل باشند. یک مؤلفهٔ همبندی یک زیرگراف همبند ماکسیمال از $G$ است. هر رأس و یالی به یک مؤلفهٔ همبندی مربوط است.

اگر در یک گراف جهت‌دار، جایگزین کردن تمام یال‌های جهت‌دار با یال‌های بدون جهت منجر به ساخت یک گراف همبند (بدون جهت) شود، در این صورت به این گراف جهت‌دار همبند ضعیف می‌گوییم.به عبارت دیگر این گراف همبند است اگر به ازای هر دو رأس دلخواه $u$ و $v$، مسیری جهت‌دار از $u$ به $v$ یا از $v$ به $u$، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه $u$ و $v$، مسیری جهت‌دار هم از $u$ به $v$ و هم از $v$ به $u$ داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.

یک برش، رأس برشی، یا مجموعهٔ جداکنندهٔ گراف همبند $G$، مجموعه‌ای از رئوس است که با حذفشان گراف $G$ ناهمبند می‌شود. عدد همبندی یا عدد همبند رأسی که با $\kappa (G)$ نشان داده می‌شود (و G در آن گراف کامل نیست) تعداد مینیمال رأس‌های برشی است. یک گراف k-همبند یا k-همبند رأسی نامیده می‌شود اگر تعداد رئوس همبندی آن، حداقل k باشد. این بدین معنی است که گراف $G$ را زمانی k-همبند می‌نامیم که در آن، یک مجموعه ی k-1 عضوی از رأس‌هایی که با حذفشان گراف، ناهمبند می‌شود، وجود نداشته باشد. یک گراف کامل با n رأس که با $K_{n}$ نشان داده می‌شود، هیچ رأس برشی ندارد، ولی بنابر قرارداد داریم $\kappa (K_{n})=n-1$. رأس برشی رئوس $u$ و $v$ مجموعه‌ای از رأس‌ها است که با حذف کردنشان، ارتباط بین $u$ و $v$ قطع می‌شود. عدد همبندی محلی $\kappa (u,v)$ برابر با کمترین تعداد رئوس برشی است که با حذفشان، ارتباط $u$ و $v$ قطع می‌شود. همبندی محلی برای گراف‌های بدون جهت، متقارن است $\kappa (u,v)=\kappa (v,u)$. علاوه بر این به استثنای گراف‌های کامل، $\kappa (G)$ به ازای هر دو انتخاب دلخواه از رأس‌های $u$ و $v$ برابر است با حداقل $\kappa (u,v)$.

گراف دوهمبند (به انگلیسی: biconnectivity) مثالی از گراف k-همبند است.

مفاهیم مشابهی را می‌توان برای یال‌ها تعریف کرد. به عنوان نمونه، اگر حذف یک یال خاص، آن گراف را ناهمبند کند، در این صورت این یال، پل نامیده می‌شود. به‌طور کلی، یال برشی گراف G مجموعه‌ای از یال‌ها است که حذف آن‌ها، گراف را ناهمبند می‌کند. عدد همبند یالی $\lambda (G)$ برابر با اندازهٔ کوچکترین مجموعهٔ یال‌های برشی است و عدد همبند یالی محلی $\lambda (u,v)$ رئوس u و v برابر با اندازه ی کوچکترین یال برشی است که u و v را از هم جدا می‌کند. همبند یالی محلی متقارن است. یک گراف k-همبند یالی نامیده می‌شود، اگر عدد همبندی یالی آن حداقل k باشد.

قضیهٔ منگر

یکی از مهمترین قضایا دربارهٔ همبندی در گراف‌ها قضیهٔ منگر (به انگلیسی: Menger's theorem) است که عدد همبندی و عدد همبند یالی یک گراف را به صورت مسیرهای مستقل بین رئوس مشخص می‌کند. اگر $u$ و $v$ رأس‌های گراف $G$ باشند، آنگاه مجموعه‌ای از مسیرها بین $u$ و $v$ را مستقل می‌نامیم، اگر هیچ دوتایی از آن‌ها، رأس مشترک نداشته باشند (به جز رأس‌های u و v). به‌طور مشابه، یک مجموعه، یال-مستقل است، اگر هیچ دو مسیری از آن، یال مشترک نداشته باشند. تعداد مسیرهای دو به دو مستقل بین $u$ و $v$ به صورت $\kappa \prime (u,v)$ و تعداد مسیرهای دو به دو یال-مستقل بین u و v به صورت $\lambda (u,v)$ نوشته می‌شوند.
قضیهٔ منگر ادعا می‌کند که عدد همبندی محلی $\kappa (u,v)$ با $\kappa \prime (u,v)$ برابر است و عدد همبندی یالی محلی $\lambda (u,v)$ با $\lambda \prime (u,v)$ به ازای هر انتخاب دلخواه از رأس‌های u و v برابر است. این قضیه، یک حالت خاص از قضیهٔ جریان بیشینه - برش کمینه است.

جنبه‌های محاسباتی

مسئلهٔ تعیین اینکه آیا در یک گراف، دو رأس به هم متصل هستند یا نه، می‌تواند به صورت مؤثر با استفاده از الگوریتم سرچ، مثل جستجوی اول سطح، حل شود. به‌طور کلی، تعیین محاسباتی اینکه آیا یک گراف همبند است،(برای مثال با استفاده از مجموعه‌های مجزا در ساختمان داده)، یا شمارش تعداد مؤلفه‌های همبندی گراف آسان است. یک الگوریتم ساده به صورت شبه کد به صورت زیر است:

1. از یک رأس دلخواه گراف $G$ شروع کن.
2. از این رأس با استفاده از جستجوی اول سطح یا جستجوی عمق اول، شروع به حرکت کن و تمام رأس‌هایی که به آن دسترسی پیدا کردی را بشمار.
3. هر وقت گراف به‌طور کامل پیمایش شد، اگر تعداد رأس‌های شمرده شده برابر با تعداد رأس‌های گراف $G$ باشد، گراف همبند است، در غیر این صورت گراف ناهمبند است.

با استفاده از قضیهٔ منگر، برای هر دو رأس دلخواه u و v در یک گراف همبند $G$، مقادیر $\kappa (u,v)$ و $\lambda (u,v)$ می‌توانند توسط الگوریتم جریان بیشینه - برش کمین تعیین شوند. در این صورت عدد همبندی و عدد همبند یالی گراف $G$ به ترتیب برابر با کمینه مقادیر $\kappa (u,v)$ و $\lambda (u,v)$ خواهند بود.
همبندی گراف‌های بدون جهت، در مرتبهٔ $O(\log n)$ قابل حل است. مسئلهٔ محاسبهٔ احتمال اینکه یک گراف تصادفی، همبند باشد، اعتبار شبکه(به انگلیسی: Network reliability) نامیده می‌شود. همچنین مسئلهٔ محاسبهٔ اینکه آیا دو رأس داده شده، متصل هستند، ST-reliability problem نامیده می‌شود. هر دوی این مسائل sharp-P]] Hard]] هستند.

مثال‌ها

• عدد همبند رأسی و عدد همبند یالی یک گراف ناهمبند هر دو برابر صفر هستند.
• 1-همبند با همبند بودن هم معنی است.
• یک گراف کامل با n رأس دارای عدد همبندِ یالی برابر با N-1 هست. هر گراف ساده ی دیگر n رأسی، عدد همبند یالی کمتری دارد.
• در یک درخت، عدد همبند یالی محلی بین هر دو جفت از رأس‌ها برابر با 1 است.

کران‌های همبندی

• عدد همبند رأسی یک گراف، کوچکتر یا مساوی عدد همبند یالی‌اش است $\kappa (G)<\lambda (G)$. هردوی آن‌ها، از کمترین درجهٔ گراف، کوچکتر هستند، چون حذف کردن همهٔ رئوس مجاور یک رأس با کمترین درجه، ارتباط این رأس را با گراف قطع می‌کند.

ویژگی‌های دیگر

• اگر $G$ همبند باشد آنگاه گراف خطی $L(G)$ همبند است.
• گراف G 2-همبند یالی است، اگر و تنها اگر یال‌های جهت داری داشته باشد که مجموعهٔ آن یال‌ها، قویاً همبند باشد.
• بنابر یکی از قضایای G. A. Dirac اگر یک گراف به ازای kهای بزرگتر مساوی 2، k-همبند باشد، آنگاه برای هر مجموعهٔ k رأسی در گراف، دوری وجود دارد که از همهٔ رئوس این مجموعه می‌گذرد.

جستارهای وابسته

• ریاضیات گسسته
• گراف
• نظریه گراف