پرش به محتویات

همبندی یالی / همبندی رأسی

تعریف

گراف غیرجهت‌دار $G$ با $n$ رأس و $m$ یال داده شده است. همبندی یالی و همبندی رأسی، هر دو، از مشخصه‌های توصیف‌کننده گراف هستند.

همبندی یالی

همبندی یالی $\lambda$ برای گراف $G$، کمترین تعداد یالی است که باید حذف شوند تا گراف $G$ ناهمبند شود.

برای مثال، یک گراف ناهمبند، همبندی یالی برابر با $0$ دارد، یک گراف همبند با حداقل یک پل، همبندی یالی برابر با $1$ دارد، و یک گراف همبند بدون پل، همبندی یالی حداقل برابر با $2$ دارد.

می‌گوییم مجموعه یال‌های $S$ رئوس $s$ و $t$ را جدا می‌کند، اگر پس از حذف تمام یال‌های مجموعه $S$ از گراف $G$، رئوس $s$ و $t$ در مؤلفه‌های همبندی متفاوتی قرار بگیرند.

واضح است که همبندی یالی یک گراف برابر است با کمترین اندازه چنین مجموعه‌ای که دو رأس $s$ و $t$ را از هم جدا می‌کند، که این کمینه بر روی تمام زوج‌های ممکن $(s, t)$ گرفته می‌شود.

همبندی رأسی

همبندی رأسی $\kappa$ برای گراف $G$، کمترین تعداد رأسی است که باید حذف شوند تا گراف $G$ ناهمبند شود.

برای مثال، یک گراف ناهمبند همبندی رأسی برابر با $0$ دارد، و یک گراف همبند با یک نقطه مفصل، همبندی رأسی برابر با $1$ دارد. برای یک گراف کامل، همبندی رأسی را $n-1$ تعریف می‌کنیم. برای سایر گراف‌ها، همبندی رأسی از $n-2$ تجاوز نمی‌کند، زیرا می‌توان زوجی از رئوس را پیدا کرد که با یال به هم متصل نیستند و $n-2$ رأس دیگر را حذف کرد.

می‌گوییم مجموعه رئوس $T$ رئوس $s$ و $t$ را جدا می‌کند، اگر پس از حذف تمام رئوس مجموعه $T$ از گراف $G$، این دو رأس در مؤلفه‌های همبندی متفاوتی قرار بگیرند.

واضح است که همبندی رأسی یک گراف برابر است با کمترین اندازه چنین مجموعه‌ای که دو رأس $s$ و $t$ را از هم جدا می‌کند، که این کمینه بر روی تمام زوج‌های ممکن $(s, t)$ گرفته می‌شود.

ویژگی‌ها

نامساوی‌های ویتنی

نامساوی‌های ویتنی (۱۹۳۲) رابطه‌ای بین همبندی یالی $\lambda$، همبندی رأسی $\kappa$، و کمینه درجه هر رأس در گراف $\delta$ برقرار می‌کنند:

$$\kappa \le \lambda \le \delta$$

به‌طور شهودی، اگر مجموعه‌ای از یال‌ها به اندازه $\lambda$ داشته باشیم که گراف را ناهمبند می‌کند، می‌توان با حذف رئوس مرتبط با این یال‌ها نیز گراف را ناهمبند کرد. می‌توان نشان داد که برای این کار، مجموعه‌ای از رئوس به اندازه حداکثر $\lambda$ کافی است.

و اگر رأسی با کمینه درجه $\delta$ را در نظر بگیریم و تمام یال‌های متصل به آن را حذف کنیم، گراف ناهمبند خواهد شد. بنابراین نامساوی دوم $\lambda \le \delta$ برقرار است.

جالب است بدانید که نامساوی‌های ویتنی را نمی‌توان بهبود بخشید: یعنی برای هر سه عددی که در این نامساوی صدق کنند، حداقل یک گراف متناظر وجود دارد. یک چنین گرافی را می‌توان به صورت زیر ساخت: گراف از $2(\delta + 1)$ رأس تشکیل می‌شود، که $\delta + 1$ رأس اول یک clique (دسته) را تشکیل می‌دهند (تمام زوج رئوس با یک یال به هم متصل هستند) و $\delta + 1$ رأس دوم نیز دسته دوم را تشکیل می‌دهند. علاوه بر این، این دو دسته را با $\lambda$ یال به هم متصل می‌کنیم، به طوری که از $\lambda$ رأس متفاوت در دسته اول و تنها از $\kappa$ رأس در دسته دوم استفاده شود. گراف حاصل، این سه مشخصه را خواهد داشت.

قضیه فورد-فالکرسون

قضیه فورد-فالکرسون بیان می‌کند که بیشترین تعداد مسیرهای یال-مجزا که دو رأس را به هم متصل می‌کنند، برابر با کمترین تعداد یال‌هایی است که این دو رأس را از هم جدا می‌کنند.

محاسبه مقادیر

همبندی یالی با استفاده از شار بیشینه

این روش بر اساس قضیه فورد-فالکرسون است.

ما بر روی تمام زوج رئوس $(s, t)$ پیمایش کرده و برای هر زوج، بیشترین تعداد مسیرهای مجزا بین آن‌ها را پیدا می‌کنیم. این مقدار را می‌توان با استفاده از یک الگوریتم شار بیشینه پیدا کرد: ما $s$ را به عنوان منبع، $t$ را به عنوان چاهک در نظر گرفته و به هر یال ظرفیت $1$ اختصاص می‌دهیم. در این صورت، شار بیشینه برابر با تعداد مسیرهای مجزا خواهد بود.

پیچیدگی این الگوریتم با استفاده از ادموندز-کارپ برابر با $O(V^2 V E^2) = O(V^3 E^2)$ است. اما باید توجه داشت که این پیچیدگی شامل یک فاکتور پنهان است، زیرا ساخت گرافی که الگوریتم شار بیشینه برای تمام منابع و چاهک‌ها کند عمل کند، عملاً غیرممکن است. به خصوص، این الگوریتم برای گراف‌های تصادفی بسیار سریع اجرا می‌شود.

الگوریتم ویژه برای همبندی یالی

مسئله یافتن همبندی یالی معادل با مسئله یافتن برش کمینه سراسری (global minimum cut) است.

الگوریتم‌های ویژه‌ای برای این کار توسعه داده شده‌اند. یکی از آن‌ها الگوریتم استوئر-واگنر (Stoer-Wagner) است که در زمان $O(V^3)$ یا $O(V E)$ کار می‌کند.

همبندی رأسی

در اینجا نیز بر روی تمام زوج رئوس $s$ و $t$ پیمایش کرده و برای هر زوج، کمترین تعداد رئوسی را که $s$ و $t$ را از هم جدا می‌کنند، پیدا می‌کنیم.

با انجام این کار، می‌توانیم از همان رویکرد شار بیشینه که در بخش‌های قبل توضیح داده شد، استفاده کنیم.

هر رأس $x$ که $x \neq s$ و $x \neq t$ باشد را به دو رأس $x_1$ و $x_2$ تقسیم می‌کنیم. این دو رأس را با یک یال جهت‌دار $(x_1, x_2)$ با ظرفیت $1$ به هم متصل می‌کنیم و تمام یال‌های $(u, v)$ را با دو یال جهت‌دار $(u_2, v_1)$ و $(v_2, u_1)$ جایگزین می‌کنیم که هر دو ظرفیت $1$ دارند. طبق این ساختار، مقدار شار بیشینه برابر با کمترین تعداد رئوسی خواهد بود که برای جدا کردن $s$ و $t$ لازم است.

این رویکرد همان پیچیدگی رویکرد مبتنی بر شار برای یافتن همبندی یالی را دارد.